| 2009 | SVM-Optimization and Steepest-Descent Line Search. | Hans Ulrich Simon, Nikolas List |
| 2009 | Learnability and Stability in the General Learning Setting. | Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, Karthik Sridharan |
| 2009 | Stochastic Convex Optimization. | Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, Karthik Sridharan |
| 2009 | The Complexity of Improperly Learning Large Margin Halfspaces. | Shai Shalev-Shwartz, Ohad Shamir, Karthik Sridharan |
| 2009 | Homogeneous Multi-Instance Learning with Arbitrary Dependence. | Sivan Sabato, Naftali Tishby |
| 2009 | A Note on Learning with Integral Operators. | Lorenzo Rosasco, Mikhail Belkin, Ernesto De Vito |
| 2009 | Generalised Pinsker Inequalities. | Mark D. Reid, Robert C. Williamson |
| 2009 | Learning Convex Bodies is Hard. | Luis Rademacher, Navin Goyal |
| 2009 | On the Sample Complexity of Learning Smooth Cuts on a Manifold. | Hariharan Narayanan, Partha Niyogi |
| 2009 | Tighter Bounds for Multi-Armed Bandits with Expert Advice. | H. Brendan McMahan, Matthew J. Streeter |
| 2009 | Empirical Bernstein Bounds and Sample-Variance Penalization. | Andreas Maurer, Massimiliano Pontil |
| 2009 | Domain Adaptation: Learning Bounds and Algorithms. | Yishay Mansour, Mehryar Mohri, Afshin Rostamizadeh |
| 2009 | Online Multi-task Learning with Hard Constraints. | Gbor Lugosi, Omiros Papaspiliopoulos, Gilles Stoltz |
| 2009 | Taking Advantage of Sparsity in Multi-Task Learning. | Karim Lounici, Massimiliano Pontil, Alexandre B. Tsybakov, Sara A. van de Geer |
| 2009 | Hybrid Stochastic-Adversarial On-line Learning. | Alessandro Lazaric, Rmi Munos |
| 2009 | Escaping the Curse of Dimensionality with a Tree-based Regressor. | Samory Kpotufe |
| 2009 | Complexity of Teaching by a Restricted Number of Examples. | Hayato Kobayashi, Ayumi Shinohara |
| 2009 | The Isotron Algorithm: High-Dimensional Isotonic Regression. | Adam Tauman Kalai, Ravi Sastry |
| 2009 | Reliable Agnostic Learning. | Adam Tauman Kalai, Varun Kanade, Yishay Mansour |
| 2009 | Consistent Partial Identification. | Sanjay Jain, Frank Stephan |
| 2009 | New Results for Random Walk Learning. | Jeffrey C. Jackson, Karl Wimmer |
| 2009 | A Spectral Algorithm for Learning Hidden Markov Models. | Daniel J. Hsu, Sham M. Kakade, Tong Zhang |
| 2009 | Predicting the Labelling of a Graph via Minimum $p$-Seminorm Interpolation. | Mark Herbster, Guy Lever |
| 2009 | Adaptive Rates of Convergence in Active Learning. | Steve Hanneke |
| 2009 | Active Learning for Smooth Problems. | Eric Friedman |