| 2004 | The Budgeted Multi-armed Bandit Problem. | Omid Madani, Daniel J. Lizotte, Russell Greiner |
| 2004 | On the Convergence of Spectral Clustering on Random Samples: The Normalized Case. | Ulrike von Luxburg, Olivier Bousquet, Mikhail Belkin |
| 2004 | A General Convergence Theorem for the Decomposition Method. | Nikolas List, Hans Ulrich Simon |
| 2004 | Replacing Limit Learners with Equally Powerful One-Shot Query Learners. | Steffen Lange, Sandra Zilles |
| 2004 | Toward Attribute Efficient Learning of Decision Lists and Parities. | Adam R. Klivans, Rocco A. Servedio |
| 2004 | Perceptron-Like Performance for Intersections of Halfspaces. | Adam R. Klivans, Rocco A. Servedio |
| 2004 | Learning Intersections of Halfspaces with a Margin. | Adam R. Klivans, Rocco A. Servedio |
| 2004 | Learning Monotonic Linear Functions. | Adam Kalai |
| 2004 | Graphical Economics. | Sham M. Kakade, Michael J. Kearns, Luis E. Ortiz |
| 2004 | Deterministic Calibration and Nash Equilibrium. | Sham M. Kakade, Dean P. Foster |
| 2004 | Kernelizing Sorting, Permutation, and Alignment for Minimum Volume PCA. | Tony Jebara |
| 2004 | A Statistical Mechanics Analysis of Gram Matrix Eigenvalue Spectra. | David C. Hoyle, Magnus Rattray |
| 2004 | Suboptimal Behavior of Bayes and MDL in Classification Under Misspecification. | Peter Grnwald, John Langford |
| 2004 | Bayes and Tukey Meet at the Center Point. | Ran Gilad-Bachrach, Amir Navot, Naftali Tishby |
| 2004 | PExact = Exact Learning. | Dmitry Gavinsky, Avi Owshanko |
| 2004 | Model Selection by Bootstrap Penalization for Classification. | Magalie Fromont |
| 2004 | Performance Guarantees for Regularized Maximum Entropy Density Estimation. | Miroslav Dudk, Steven J. Phillips, Robert E. Schapire |
| 2004 | Concentration Bounds for Unigrams Language Model. | Evgeny Drukh, Yishay Mansour |
| 2004 | Learning Classes of Probabilistic Automata. | Franois Denis, Yann Esposito |
| 2004 | Minimizing Regret with Label Efficient Prediction. | Nicol Cesa-Bianchi, Gbor Lugosi, Gilles Stoltz |
| 2004 | Regret Bounds for Hierarchical Classification with Linear-Threshold Functions. | Nicol Cesa-Bianchi, Alex Conconi, Claudio Gentile |
| 2004 | An Inequality for Nearly Log-Concave Distributions with Applications to Learning. | Constantine Caramanis, Shie Mannor |
| 2004 | Polynomial Time Prediction Strategy with Almost Optimal Mistake Probability. | Nader H. Bshouty |
| 2004 | Oracle Bounds and Exact Algorithm for Dyadic Classification Trees. | Gilles Blanchard, Christin Schfer, Yves Rozenholc |
| 2004 | A Framework for Statistical Clustering with a Constant Time Approximation Algorithms for K-Median Clustering. | Shai Ben-David |