For Participants


For authors



COLT 2009 Sessions

Friday, June 19

8:35 - 10:15 Algorithms I (Session chair: Claudio Gentile)
The Isotron Algorithm: High-Dimensional Isotonic Regression. Adam Kalai and Ravi Sastry.

Linear classifiers are nearly optimal when hidden variables have diverse effect. Nader H. Bshouty and Phil Long.

Domain Adaptation: Learning Bounds and Algorithms. Yishay Mansour, Mehryar Mohri and Afshin Rostamizadeh.

Optimal Algorithms for the Coin Weighing Problem with a Spring Scale. Nader Bshouty.
10:15 - 10:40 Coffee break
10:40 - 11:40 Invited talk (Session chair: Gabor Lugosi)
Towards Agnostic and Interactive Machine Learning. Adam Tauman Kalai
11:45 - 13:00 Online Learning I (Session chair: Sasha Rakhlin)
Online Learning for Global Cost Functions. Eyal Even-Dar, Robert Kleinberg, Shie Mannor and Yishay Mansour.

The K-armed Dueling Bandits Problem. Yisong Yue, Josef Broder, Robert Kleinberg and Thorsten Joachims.

Online Multi-task Learning with Hard Constraints. Gabor Lugosi, Omiros Papaspiliopoulos and Gilles Stoltz.
13:00 - 14:30 Lunch break (on your own)
14:30 - 16:15 Sparsity and Algorithms (Session chair: Shai Shalev-Shwartz)
Taking Advantage of Sparsity in Multi-Task Learning. Karim Lounici, Massimiliano Pontil, Alexandre B. Tsybakov and Sara A. van de Geer.

Sparse Regression Learning by Aggregation and Langevin Monte-Carlo. Arnak Dalalyan and Alexandre Tsybakov.

Homogeneous Multi-Instance Learning with Arbitrary Dependence. Sivan Sabato and Naftali Tishby.

A Spectral Algorithm for Learning Hidden Markov Models. Daniel Hsu, Sham M. Kakade and Tong Zhang.
16:15 - 16:40 Coffee break
16:40 - 17:55 Generalization I (Session chair: Sandra Zilles)
Empirical Bernstein Bounds and Sample-Variance Penalization. Andreas Maurer and Massimiliano Pontil.

Generalised Pinsker Inequalities. Mark Reid and Robert Williamson.

Consistent Partial Identification. Sanjay Jain and Frank Stephan.
18:00 - 20:00 Dinner break (on your own)
20:00 - 20:40 Open problems session (Session chair: Csaba Szepesvari)
An Efficient Bandit Algorithm for sqrt(T) Regret in Online Multiclass Prediction. Jacob Abernethy and Alexander Rakhlin.

Better Guarantees for Sparsest Cut Clustering. Maria-Florina Balcan

Minimax Games with Bandits. Jacob Abernethy and Manfred Warmuth.

The Complexity of Improperly Learning Large Margin Halfspaces. Shai Shalev-Shwartz, Ohad Shamir and Karthik Sridharan.
20:40 - 22:00 Business meeting

Saturday, June 20

8:35 - 10:15 Algorithms II (Session chair: Jacob Abernethy)
Fast and Optimal Prediction on a Labeled Tree. Nicolo Cesa-Bianchi, Claudio Gentile and Fabio Vitale.

Predicting the Labelling of a Graph via Minimum $p$-Seminorm Interpolation. Mark Herbster and Guy Lever.

Finding low error clusterings. Maria Florina Balcan and Mark Braverman.

Stochastic Convex Optimization. Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro and Karthik Sridharan.
10:15 - 10:40 Coffee break
10:40 - 11:40 Invited talk. (Session chair: Sanjoy Dasgupta)
Sparse recovery using sparse matrices.. Piotr Indyk
11:45 - 13:00 Dimensionality and Optimization (Session chair: Steve Hanneke)
Escaping the curse of dimensionality with a tree-based regressor. Samory Kpotufe.

On the sample complexity of learning smooth cuts on a manifold. Hariharan Narayanan and Partha Niyogi.

SVM-Optimization and Steepest-Descent Line Search. Hans Simon and Nikolas List.
13:00 - 14:30 Lunch break (on your own)
14:30 - 16:40 Bandits (Session chair: Eyal Even-Dar)
Minimax policies for adversarial and stochastic bandits. Jean-Yves Audibert and Sebastien Bubeck.

Tighter Bounds for Multi-Armed Bandits with Expert Advice. H. Brendan McMahan and Matthew Streeter.

Combinatorial Bandits. Nicolo Cesa-Bianchi and Gabor Lugosi.

Beating the Adaptive Bandit with High Probability. Jacob Abernethy and Alexander Rakhlin.

A Stochastic View of Optimal Regret through Minimax Duality. Jacob Abernethy, Alekh Agarwal, Peter Bartlett and Alexander Rakhlin.
16:40 - 17:10 Buses to banquet
17:10 - 21:30 Tour around Fort Chambly, followed by banquet

Sunday, June 21

8:35 - 10:15 Complexity (Session chair: Nader Bshouty)
New results for random walk learning. Jeffrey Jackson and Karl Wimmer.

Robustness of Evolvability. Vitaly Feldman.

Complexity of Teaching by a Restricted Number of Examples. Hayato Kobayashi and Ayumi Shinohara.

Learning convex bodies is hard. Luis Rademacher and Navin Goyal.
10:15 - 10:40 Coffee break
10:40 - 11:40 Impromptu session (Session chair: Jeffrey Jackson)
11:45 - 13:00 Noise (Session chair: Sham Kakade)
Reliable Agnostic Learning. Adam Tauman Kalai, Varun Kanade and Yishay Mansour.

Agnostic Online Learning. Shai Ben-David, David Pal and Shai Shalev-Shwartz.

Hybrid Stochastic-Adversarial On-line Learning. Alessandro Lazaric and Remi Munos.
13:00 - 14:30 Lunch break (on your own)
14:30 - 16:15 Active Learning and Stability (Session chair: Shai Ben-David)
Active Learning for Smooth Problems. Eric Friedman

Adaptive Rates of Convergence in Active Learning. Steve Hanneke.

Learnability and Stability in the General Learning Setting. Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro and Karthik Sridharan.

Vox Populi: Collecting High-Quality Labels from a Crowd. Ofer Dekel and Ohad Shamir.
16:15 - 16:40 Coffee break
16:40 - 17:55 Generalization II (Session chair: Shie Mannor)
Optimal Rates for Regularized Least Squares Regression. Ingo Steinwart, Don Hush and Clint Scovel.

A Note on Learning with Integral Operators. Lorenzo Rosasco, Mikhail Belkin and Ernesto De Vito.

Generalization Bounds for Learning the Kernel Problem. Yiming Ying and Colin Campbell.
18:00 Conference ends