| 2004 | A Framework for Statistical Clustering with a Constant Time Approximation Algorithms for K-Median Clustering. Shai Ben-David |
| 2004 | A Function Representation for Learning in Banach Spaces. Charles A. Micchelli, Massimiliano Pontil |
| 2004 | A General Convergence Theorem for the Decomposition Method. Nikolas List, Hans Ulrich Simon |
| 2004 | A New PAC Bound for Intersection-Closed Concept Classes. Peter Auer, Ronald Ortner |
| 2004 | A Statistical Mechanics Analysis of Gram Matrix Eigenvalue Spectra. David C. Hoyle, Magnus Rattray |
| 2004 | An Improved VC Dimension Bound for Sparse Polynomials. Michael Schmitt |
| 2004 | An Inequality for Nearly Log-Concave Distributions with Applications to Learning. Constantine Caramanis, Shie Mannor |
| 2004 | Bayes and Tukey Meet at the Center Point. Ran Gilad-Bachrach, Amir Navot, Naftali Tishby |
| 2004 | Bayesian Networks and Inner Product Spaces. Atsuyoshi Nakamura, Michael Schmitt, Niels Schmitt, Hans Ulrich Simon |
| 2004 | Boosting Based on a Smooth Margin. Cynthia Rudin, Robert E. Schapire, Ingrid Daubechies |
| 2004 | Concentration Bounds for Unigrams Language Model. Evgeny Drukh, Yishay Mansour |
| 2004 | Consistency in Models for Communication Constrained Distributed Learning. Joel B. Predd, Sanjeev R. Kulkarni, Harold Vincent Poor |
| 2004 | Convergence of Discrete MDL for Sequential Prediction. Jan Poland, Marcus Hutter |
| 2004 | Data Dependent Risk Bounds for Hierarchical Mixture of Experts Classifiers. Arik Azran, Ron Meir |
| 2004 | Deterministic Calibration and Nash Equilibrium. Sham M. Kakade, Dean P. Foster |
| 2004 | Graphical Economics. Sham M. Kakade, Michael J. Kearns, Luis E. Ortiz |
| 2004 | Inferring Mixtures of Markov Chains. Tugkan Batu, Sudipto Guha, Sampath Kannan |
| 2004 | Kernelizing Sorting, Permutation, and Alignment for Minimum Volume PCA. Tony Jebara |
| 2004 | Learning Classes of Probabilistic Automata. François Denis, Yann Esposito |
| 2004 | Learning Intersections of Halfspaces with a Margin. Adam R. Klivans, Rocco A. Servedio |
| 2004 | Learning Monotonic Linear Functions. Adam Kalai |
| 2004 | Learning Over Compact Metric Spaces. Ha Quang Minh, Thomas Hofmann |
| 2004 | Learning Theory, 17th Annual Conference on Learning Theory, COLT 2004, Banff, Canada, July 1-4, 2004, Proceedings John Shawe-Taylor, Yoram Singer |
| 2004 | Learning a Hidden Graph Using O(log n) Queries Per Edge. Dana Angluin, Jiang Chen |
| 2004 | Local Complexities for Empirical Risk Minimization. Peter L. Bartlett, Shahar Mendelson, Petra Philips |
| 2004 | Minimizing Regret with Label Efficient Prediction. Nicolò Cesa-Bianchi, Gábor Lugosi, Gilles Stoltz |
| 2004 | Model Selection by Bootstrap Penalization for Classification. Magalie Fromont |
| 2004 | On the Convergence of MDL Density Estimation. Tong Zhang |
| 2004 | On the Convergence of Spectral Clustering on Random Samples: The Normalized Case. Ulrike von Luxburg, Olivier Bousquet, Mikhail Belkin |
| 2004 | On the Learnability of E-pattern Languages over Small Alphabets. Daniel Reidenbach |
| 2004 | Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary. H. Brendan McMahan, Avrim Blum |
| 2004 | Oracle Bounds and Exact Algorithm for Dyadic Classification Trees. Gilles Blanchard, Christin Schäfer, Yves Rozenholc |
| 2004 | PExact = Exact Learning. Dmitry Gavinsky, Avi Owshanko |
| 2004 | Perceptron-Like Performance for Intersections of Halfspaces. Adam R. Klivans, Rocco A. Servedio |
| 2004 | Performance Guarantees for Regularized Maximum Entropy Density Estimation. Miroslav Dudík, Steven J. Phillips, Robert E. Schapire |
| 2004 | Polynomial Time Prediction Strategy with Almost Optimal Mistake Probability. Nader H. Bshouty |
| 2004 | Regret Bounds for Hierarchical Classification with Linear-Threshold Functions. Nicolò Cesa-Bianchi, Alex Conconi, Claudio Gentile |
| 2004 | Regularization and Semi-supervised Learning on Large Graphs. Mikhail Belkin, Irina Matveeva, Partha Niyogi |
| 2004 | Reinforcement Learning for Average Reward Zero-Sum Games. Shie Mannor |
| 2004 | Replacing Limit Learners with Equally Powerful One-Shot Query Learners. Steffen Lange, Sandra Zilles |
| 2004 | Sparseness Versus Estimating Conditional Probabilities: Some Asymptotic Results. Peter L. Bartlett, Ambuj Tewari |
| 2004 | Statistical Properties of Kernel Principal Component Analysis. Laurent Zwald, Olivier Bousquet, Gilles Blanchard |
| 2004 | Suboptimal Behavior of Bayes and MDL in Classification Under Misspecification. Peter Grünwald, John Langford |
| 2004 | The Budgeted Multi-armed Bandit Problem. Omid Madani, Daniel J. Lizotte, Russell Greiner |
| 2004 | The Optimal PAC Algorithm. Manfred K. Warmuth |
| 2004 | Toward Attribute Efficient Learning of Decision Lists and Parities. Adam R. Klivans, Rocco A. Servedio |
| 2004 | Towards a Characterization of Polynomial Preference Elicitation with Value Queries in Combinatorial Auctions (Extended Abstract). Paolo Santi, Vincent Conitzer, Tuomas Sandholm |