COLT 2011 Accepted Papers

Yasin Abbasi-Yadkori and Csaba Szepesvari
Regret Bounds for the Adaptive Control of Linear Quadratic Systems

Jacob Abernethy, Peter Bartlett and Elad Hazan
Blackwell Approachability and No-Regret Learning are Equivalent

Alekh Agarwal, John Duchi, Peter Bartlett and Clement Levrard.
Oracle inequalities for computationally budgeted model selection

Kareem Amin, Michael Kearns and Umar Syed.
Bandits, Query Learning, and the Haystack Dimension

Jean-Yves Audibert, Sébastien Bubeck and Gabor Lugosi.
Minimax Policies for Combinatorial Prediction Games

Gabor Bartok, David Pal and Csaba Szepesvari.
Minimax Regret of Finite Partial-Monitoring Games in Stochastic Environments

Kamalika Chaudhuri and Daniel Hsu.
Sample Complexity Bounds for Differentially Private Learning

Arnak Dalalyan and Joseph Salmon.
Optimal aggregation of affine estimators

Arnak Dalalyan and Laëtitia Comminges.
Tight conditions for consistent variable selection in high dimensional nonparametric regression

Amit Daniely, Sivan Sabato, Shai Ben-David and Shai Shalev-Shwartz.
Multiclass Learnability and the ERM principle

Hirakendu Das, Alon Orlitsky, Shengjun Pan, Jayadev Acharya and Ashkan Jafarpour.
Competitive Closeness Testing

Vitaly Feldman.
Distribution-Independent Evolvability of Linear Threshold Functions

Dean Foster, Alexander Rakhlin, Karthik Sridharan and Ambuj Tewari
Complexity-Based Approach to Calibration with Checking Rules

Rina Foygel and Nathan Srebro
Concentration-Based Guarantees for Low-Rank Matrix Reconstruction

Wei Gao and Zhi-Hua Zhou
On the Consistency of Multi-Label Learning

Aurélien Garivier and Olivier Cappé
The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond

Sebastien Gerchinovitz
Sparsity regret bounds for individual sequences in online linear regression

Peter Grünwald
Safe Learning: bridging the gap between Bayes, MDL and statistical learning theory via empirical convexity

Elad Hazan and Satyen Kale
Beyond the regret minimization barrier: an optimal algorithm for stochastic strongly-convex optimization

Michael Kallweit and Hans Simon
A Close Look to Margin Complexity and Related Parameters

Wojciech Kotlowski and Peter Grunwald
Maximum Likelihood vs. Sequential Normalized Maximum Likelihood in On-line Density Estimation

Homin Lee, Vitaly Feldman and Rocco Servedio
Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas

Ping Li and Cun-Hui Zhang
A New Algorithm for Compressed Counting with Applications in Shannon Entropy Estimation in Dynamic Data

Odalric-Ambrym Maillard, Gilles Stoltz and Remi Munos
A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler Divergences

Shie Mannor, Vianney Perchet and Gilles Stoltz
Robust approachability and regret minimization in games with partial monitoring

Indraneel Mukherjee, Cynthia Rudin and Robert Schapire
The Rate of Convergence of AdaBoost

Alexander Rakhlin, Karthik Sridharan and Ambuj Tewari
Online Learning: Beyond Regret

Philippe Rigollet and Xin Tong
Neyman-Pearson classification under a strict constraint

Cynthia Rudin, Ansaf Salleb-Aouissi, Eugene Kogan and David Madigan
Sequential Event Prediction with Association Rules

Ohad Shamir and Shai Shalev-Shwartz
Collaborative Filtering with the Trace Norm: Learning, Bounding, and Transducing

Aleksandrs Slivkins
Contextual Bandits with Similarity Information

Ingo Steinwart
Adaptive Density Level Set Clustering

Istvan Szita and Csaba Szepesvari
Agnostic KWIK learning and efficient approximate reinforcement learning

Daniel Vainsencher, Shie Mannor and Alfred Bruckstein.
The Sample Complexity of Dictionary Learning

Tim Van Erven, Mark Reid and Robert Williamson.
Mixability is Bayes Risk Curvature Relative to Log Loss

Liu Yang, Steve Hanneke and Jaime Carbonell
Identifiability of Priors from Bounded Sample Sizes with Applications to Transfer Learning