List of accepted papers for COLT 2011: 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, Sebastien 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 Laetitia 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, 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 Aurelien Garivier and Olivier Cappe The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond Sebastien Gerchinovitz Sparsity regret bounds for individual sequences in online linear regression Peter Grunwald 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