COLT 2009

The 22nd Annual Conference on Learning Theory (COLT 2009) took place in Montreal, Canada on June 18-21, 2009.

Conference website

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

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. 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

Noise

• 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