| 2008 | Model Selection and Stability in k-means Clustering. | Ohad Shamir, Naftali Tishby |
| 2008 | On the Equivalence of Weak Learnability and Linear Separability: New Relaxations and Efficient Boosting Algorithms. | Shai Shalev-Shwartz, Yoram Singer |
| 2008 | Learning Random Monotone DNF Under the Uniform Distribution. | Linda Sellie |
| 2008 | Geometric & Topological Representations of Maximum Classes with Applications to Sample Compression. | J. Hyam Rubinstein, Benjamin I. P. Rubinstein |
| 2008 | Density Estimation in Linear Time. | Satyaki Mahalanabis, Daniel Stefankovic |
| 2008 | Concentration Inequalities. | Gbor Lugosi |
| 2008 | Combining Expert Advice Efficiently. | Wouter M. Koolen, Steven de Rooij |
| 2008 | Sparse Recovery in Large Ensembles of Kernel Machines On-Line Learning and Bandits. | Vladimir Koltchinskii, Ming Yuan |
| 2008 | Regret Bounds for Sleeping Experts and Bandits. | Robert D. Kleinberg, Alexandru Niculescu-Mizil, Yogeshwer Sharma |
| 2008 | Unsupervised Learning for Natural Language Processing. | Dan Klein |
| 2008 | Minimizing Wide Range Regret with Time Selection Functions. | Subhash Khot, Ashok Kumar Ponnuswami |
| 2008 | Learning from Collective Behavior. | Michael J. Kearns, Jennifer Wortman |
| 2008 | Online Learning of Maximum p-Norm Margin Classifiers with Bias. | Kosuke Ishibashi, Kohei Hatano, Masayuki Takeda |
| 2008 | Teaching Dimensions based on Cooperative Learning. | Sandra Zilles, Steffen Lange, Robert Holte, Martin Zinkevich |
| 2008 | Extracting Certainty from Uncertainty: Regret Bounded by Variation in Costs. | Elad Hazan, Satyen Kale |
| 2008 | Combinatorial Prediction Markets. | Robin Hanson |
| 2008 | On-line Sequential Bin Packing. | Andrs Gyrgy, Gbor Lugosi, Gyrgy Ottucsk |
| 2008 | The Catch-Up Phenomenon in Bayesian Inference. | Peter Grunwald |
| 2008 | More Efficient Internal-Regret-Minimizing Algorithms. | Amy Greenwald, Zheng Li, Warren Schudy |
| 2008 | A Query Algorithm for Agnostically Learning DNF?. | Parikshit Gopalan, Adam Kalai, Adam R. Klivans |
| 2008 | The Learning Power of Evolution. | Vitaly Feldman, Leslie G. Valiant |
| 2008 | On the Power of Membership Queries in Agnostic Learning. | Vitaly Feldman |
| 2008 | Dimension and Margin Bounds for Reflection-invariant Kernels. | Thorsten Doliwa, Michael Kallweit, Hans Ulrich Simon |
| 2008 | Stochastic Linear Optimization under Bandit Feedback. | Varsha Dani, Thomas P. Hayes, Sham M. Kakade |
| 2008 | Almost Tight Upper Bound for Finding Fourier Coefficients of Bounded Pseudo- Boolean Functions. | Sung-Soon Choi, Kyomin Jung, Jeong Han Kim |