COLT 2009 Proceedings
DAY ONE
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
DAY TWO
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.
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
Bandits
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.
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
DAY THREE
Complexity I
Jeffrey Jackson and Karl Wimmer.
New results for random walk learning
Vitaly Feldman.
Hayato Kobayashi and Ayumi Shinohara.
Complexity of Teaching by a Restricted Number of Examples
Luis Rademacher and Navin Goyal.
Learning convex bodies is hard
Noise
Adam Tauman Kalai, Varun Kanade and Yishay Mansour.
Shai Ben-David, David Pal and Shai Shalev-Shwartz.
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.
Shai Shalev-Shwartz, Ohad Shamir and Karthik Sridharan.
The Complexity of Improperly Learning Large Margin Halfspaces