| 2005 | From External to Internal Regret. | Avrim Blum, Yishay Mansour |
| 2005 | Towards a Theoretical Foundation for Laplacian-Based Manifold Methods. | Mikhail Belkin, Partha Niyogi |
| 2005 | A PAC-Style Model for Learning from Labeled and Unlabeled Data. | Maria-Florina Balcan, Avrim Blum |
| 2005 | Teaching Classes with High Teaching Dimension Using Few Examples. | Frank J. Balbach |
| 2005 | Competitive Collaborative Learning. | Baruch Awerbuch, Robert D. Kleinberg |
| 2005 | Learning Convex Combinations of Continuously Parameterized Basic Kernels. | Andreas Argyriou, Charles A. Micchelli, Massimiliano Pontil |
| 2005 | Improved Minimax Bounds on the Test and Training Distortion of Empirically Designed Vector Quantizers. | Andrs Antos |
| 2005 | Learning a Hidden Hypergraph. | Dana Angluin, Jiang Chen |
| 2005 | Learnability of Bipartite Ranking Functions. | Shivani Agarwal, Dan Roth |
| 2005 | Stability and Generalization of Bipartite Ranking Algorithms. | Shivani Agarwal, Partha Niyogi |
| 2005 | On Spectral Learning of Mixtures of Distributions. | Dimitris Achlioptas, Frank McSherry |
| 2004 | Statistical Properties of Kernel Principal Component Analysis. | Laurent Zwald, Olivier Bousquet, Gilles Blanchard |
| 2004 | On the Convergence of MDL Density Estimation. | Tong Zhang |
| 2004 | The Optimal PAC Algorithm. | Manfred K. Warmuth |
| 2004 | An Improved VC Dimension Bound for Sparse Polynomials. | Michael Schmitt |
| 2004 | Towards a Characterization of Polynomial Preference Elicitation with Value Queries in Combinatorial Auctions (Extended Abstract). | Paolo Santi, Vincent Conitzer, Tuomas Sandholm |
| 2004 | Boosting Based on a Smooth Margin. | Cynthia Rudin, Robert E. Schapire, Ingrid Daubechies |
| 2004 | On the Learnability of E-pattern Languages over Small Alphabets. | Daniel Reidenbach |
| 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 | Bayesian Networks and Inner Product Spaces. | Atsuyoshi Nakamura, Michael Schmitt, Niels Schmitt, Hans Ulrich Simon |
| 2004 | Learning Over Compact Metric Spaces. | Ha Quang Minh, Thomas Hofmann |
| 2004 | A Function Representation for Learning in Banach Spaces. | Charles A. Micchelli, Massimiliano Pontil |
| 2004 | Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary. | H. Brendan McMahan, Avrim Blum |
| 2004 | Reinforcement Learning for Average Reward Zero-Sum Games. | Shie Mannor |