COLT 2011

42 papers

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

A Finite-Time Analysis of Multi-Armed Bandits Problems with Kullback-Leibler Divergences Odalric-Ambrym Maillard, Rémi Munos, Gilles Stoltz

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

A Simple Multi-Armed Bandit Algorithm with Optimal Variation-Bounded Regret Elad Hazan, Satyen Kale

Adaptive Density Level Set Clustering Ingo Steinwart

Agnostic KWIK Learning and Efficient Approximate Reinforcement Learning István Szita, Csaba Szepesvári

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

Beyond the Regret Minimization Barrier: An Optimal Algorithm for Stochastic Strongly-Convex Optimization Elad Hazan, Satyen Kale

Blackwell Approachability and No-Regret Learning Are Equivalent Jacob Abernethy, Peter L. Bartlett, Elad Hazan

Bounds on Individual Risk for Log-Loss Predictors Peter D. Grünwald, Wojciech Kotłowski

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

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

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

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

Contextual Bandits with Similarity Information Aleksandrs Slivkins

Distribution-Independent Evolvability of Linear Threshold Functions Vitaly Feldman

Does an Efficient Calibrated Forecasting Strategy Exist? Jacob Abernethy, Shie Mannor

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

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

Maximum Likelihood vs. Sequential Normalized Maximum Likelihood in On-Line Density Estimation Wojciech Kotłowski, Peter Grünwald

Minimax Algorithm for Learning Rotations Wojciech Kotłowski, Manfred K. Warmuth

Minimax Policies for Combinatorial Prediction Games Jean-Yves Audibert, Sébastien Bubeck, Gábor Lugosi

Minimax Regret of Finite Partial-Monitoring Games in Stochastic Environments Gábor Bartók, Dávid Pál, Csaba Szepesvári

Missing Information Impediments to Learnability Loizos Michael

Mixability Is Bayes Risk Curvature Relative to Log Loss Tim Erven, Mark D. Reid, Robert C. Williamson

Monotone Multi-Armed Bandit Allocations Aleksandrs Slivkins

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

Neyman-Pearson Classification Under a Strict Constraint Philippe Rigollet, Xin Tong

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

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

Optimal Aggregation of Affine Estimators Joseph Salmon, Arnak Dalalyan

Oracle Inequalities for Computationally Budgeted Model Selection Alekh Agarwal, John C. Duchi, Peter L. Bartlett, Clement Levrard

Regret Bounds for the Adaptive Control of Linear Quadratic Systems Yasin Abbasi-Yadkori, Csaba Szepesvári

Robust Approachability and Regret Minimization in Games with Partial Monitoring Shie Mannor, Vianney Perchet, Gilles Stoltz

Safe Learning: Bridging the Gap Between Bayes, MDL and Statistical Learning Theory via Empirical Convexity Peter Grünwald

Sample Complexity Bounds for Differentially Private Learning Kamalika Chaudhuri, Daniel Hsu

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

Sparsity Regret Bounds for Individual Sequences in Online Linear Regression Sébastien Gerchinovitz

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

The Rate of Convergence of Adaboost Indraneel Mukherjee, Cynthia Rudin, Robert E. Schapire

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

Tight Conditions for Consistent Variable Selection in High Dimensional Nonparametric Regression Laëtitia Comminges, Arnak S. Dalalyan