For Participants


For authors



COLT 2009 Proceedings


Algorithms I

Adam Kalai and Ravi Sastry

The Isotron Algorithm: High-Dimensional Isotonic Regression

Nader H. Bshouty and Phil Long.

Linear classifiers are nearly optimal when hidden variables have diverse effect

Yishay Mansour, Mehryar Mohri and Afshin Rostamizadeh.

Domain Adaptation: Learning Bounds and Algorithms

Nader Bshouty.

Optimal Algorithms for the Coin Weighing Problem with a Spring Scale

Online Learning I

Eyal Even-Dar, Robert Kleinberg, Shie Mannor and Yishay Mansour.

Online Learning for Global Cost Functions

Yisong Yue, Josef Broder, Robert Kleinberg and Thorsten Joachims.

The K-armed Dueling Bandits Problem

Gabor Lugosi, Omiros Papaspiliopoulos and Gilles Stoltz.

Online Multi-task Learning with Hard Constraints

Sparsity and Algorithms

Karim Lounici, Massimiliano Pontil, Alexandre B. Tsybakov and Sara A. van de Geer.

Taking Advantage of Sparsity in Multi-Task Learning

Arnak Dalalyan and Alexandre Tsybakov.

Sparse Regression Learning by Aggregation and Langevin Monte-Carlo

Sivan Sabato and Naftali Tishby.

Homogeneous Multi-Instance Learning with Arbitrary Dependence

Daniel Hsu, Sham M. Kakade and Tong Zhang.

A Spectral Algorithm for Learning Hidden Markov Models

Generalization I

Andreas Maurer and Massimiliano Pontil.

Empirical Bernstein Bounds and Sample-Variance Penalization

Mark Reid and Robert Williamson.

Generalised Pinsker Inequalities

Sanjay Jain and Frank Stephan.

Consistent Partial Identification


Algorithms II

Nicolo' Cesa-Bianchi, Claudio Gentile and Fabio Vitale.

Fast and Optimal Prediction on a Labeled Tree

Mark Herbster and Guy Lever.

Predicting the Labelling of a Graph via Minimum $p$-Seminorm Interpolation

Maria Florina Balcan and Mark Braverman.

Finding low error clusterings

Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro and Karthik Sridharan.

Stochastic Convex Optimization

Dimensionality and Optimization

Samory Kpotufe.

Escaping the curse of dimensionality with a tree-based regressor

Hariharan Narayanan and Partha Niyogi.

On the sample complexity of learning smooth cuts on a manifold

Hans Simon and Nikolas List.

SVM-Optimization and Steepest-Descent Line Search


Jean-Yves Audibert and Sebastien Bubeck.

Minimax policies for adversarial and stochastic bandits

H. Brendan McMahan and Matthew Streeter.

Tighter Bounds for Multi-Armed Bandits with Expert Advice

Nicolo Cesa-Bianchi and Gabor Lugosi.

Combinatorial Bandits

Jacob Abernethy and Alexander Rakhlin.

Beating the Adaptive Bandit with High Probability

Jacob Abernethy, Alekh Agarwal, Peter Bartlett and Alexander Rakhlin.

A Stochastic View of Optimal Regret through Minimax Duality


Complexity I

Jeffrey Jackson and Karl Wimmer.

New results for random walk learning

Vitaly Feldman.

Robustness of Evolvability

Hayato Kobayashi and Ayumi Shinohara.

Complexity of Teaching by a Restricted Number of Examples

Luis Rademacher and Navin Goyal.

Learning convex bodies is hard


Adam Tauman Kalai, Varun Kanade and Yishay Mansour.

Reliable Agnostic Learning

Shai Ben-David, David Pal and Shai Shalev-Shwartz.

Agnostic Online Learning

Alessandro Lazaric and Remi Munos.

Hybrid Stochastic-Adversarial On-line Learning

Active Learning and Stability

Eric Friedman.

Active Learning for Smooth Problems

Steve Hanneke.

Adaptive Rates of Convergence in Active Learning

Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro and Karthik Sridharan.

Learnability and Stability in the General Learning Setting

Ofer Dekel and Ohad Shamir.

Vox Populi: Collecting High-Quality Labels from a Crowd

Generalization II

Ingo Steinwart, Don Hush and Clint Scovel.

Optimal Rates for Regularized Least Squares Regression

Lorenzo Rosasco, Mikhail Belkin and Ernesto De Vito.

A Note on Learning with Integral Operators

Yiming Ying and Colin Campbell.

Generalization Bounds for Learning the Kernel Problem

Open problems

Jacob Abernethy and Alexander Rakhlin.

An Efficient Bandit Algorithm for sqrt(T) Regret in Online Multiclass Prediction?

Maria-Florina Balcan.

Better Guarantees for Sparsest Cut Clustering

Jacob Abernethy and Manfred Warmuth.

Minimax Games with Bandits

Shai Shalev-Shwartz, Ohad Shamir and Karthik Sridharan.

The Complexity of Improperly Learning Large Margin Halfspaces