COLT 2013

50 papers

A Near-Optimal Algorithm for Finite Partial-Monitoring Games Against Adversarial Opponents Gábor Bartók

A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret Lachlan L. H. Andrew, Siddharth Barman, Katrina Ligett, Minghong Lin, Adam Meyerson, Alan Roytman, Adam Wierman

A Tensor Spectral Approach to Learning Mixed Membership Community Models Animashree Anandkumar, Rong Ge, Daniel J. Hsu, Sham M. Kakade

A Theoretical Analysis of NDCG Type Ranking Measures Yining Wang, Liwei Wang, Yuanzhi Li, Di He, Tie-Yan Liu

Active and Passive Learning of Linear Separators Under Log-Concave Distributions Maria-Florina Balcan, Philip M. Long

Adaptive Crowdsourcing Algorithms for the Bandit Survey Problem Ittai Abraham, Omar Alonso, Vasilis Kandylas, Aleksandrs Slivkins

Algorithms and Hardness for Robust Subspace Recovery Moritz Hardt, Ankur Moitra

Approachability, Fast and Slow Vianney Perchet, Shie Mannor

Beating Bandits in Gradually Evolving Worlds Chao-Kai Chiang, Chia-Jung Lee, Chi-Jen Lu

Blind Signal Separation in the Presence of Gaussian Noise Mikhail Belkin, Luis Rademacher, James R. Voss

Boosting with the Logistic Loss Is Consistent Matus Telgarsky

Bounded Regret in Stochastic Multi-Armed Bandits Sébastien Bubeck, Vianney Perchet, Philippe Rigollet

Classification with Asymmetric Label Noise: Consistency and Maximal Denoising Clayton Scott, Gilles Blanchard, Gregory Handy

Competing with Strategies Wei Han, Alexander Rakhlin, Karthik Sridharan

Complexity Theoretic Lower Bounds for Sparse Principal Component Detection Quentin Berthet, Philippe Rigollet

Consistency of Robust Kernel Density Estimators Robert A. Vandermeulen, Clayton D. Scott

Differentially Private Feature Selection via Stability Arguments, and the Robustness of the Lasso Abhradeep Thakurta, Adam D. Smith

Divide and Conquer Kernel Ridge Regression Yuchen Zhang, John C. Duchi, Martin J. Wainwright

Efficient Learning of Simplices Joseph Anderson, Navin Goyal, Luis Rademacher

Estimation of Extreme Values and Associated Level Sets of a Regression Function via Selective Sampling Stanislav Minsker

Excess Risk Bounds for Multitask Learning with Trace Norm Regularization Massimiliano Pontil, Andreas Maurer

General Oracle Inequalities for Gibbs Posterior with Application to Ranking Cheng Li, Wenxin Jiang, Martin A. Tanner

Honest Compressions and Their Application to Compression Schemes Roi Livni, Pierre Simon

Horizon-Independent Optimal Prediction with Log-Loss in Exponential Families Peter L. Bartlett, Peter Grünwald, Peter Harremoës, Fares Hedayati, Wojciech Kotlowski

Information Complexity in Bandit Subset Selection Emilie Kaufmann, Shivaram Kalyanakrishnan

Learning a Set of Directions Wouter M. Koolen, Jiazhong Nie, Manfred K. Warmuth

Learning Halfspaces Under Log-Concave Densities: Polynomial Approximations and Moment Matching Daniel M. Kane, Adam R. Klivans, Raghu Meka

Learning Using Local Membership Queries Pranjal Awasthi, Vitaly Feldman, Varun Kanade

On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization Ohad Shamir

Online Learning for Time Series Prediction Oren Anava, Elad Hazan, Shie Mannor, Ohad Shamir

Online Learning with Predictable Sequences Alexander Rakhlin, Karthik Sridharan

Online Similarity Prediction of Networked Data from Known and Unknown Graphs Claudio Gentile, Mark Herbster, Stephen Pasteris

Open Problem: Adversarial Multiarmed Bandits with Limited Advice Yevgeny Seldin, Koby Crammer, Peter L. Bartlett

Open Problem: Fast Stochastic Exp-Concave Optimization Tomer Koren

Open Problem: Lower Bounds for Boosting with Hadamard Matrices Jiazhong Nie, Manfred K. Warmuth, S. V. N. Vishwanathan, Xinhua Zhang

Opportunistic Strategies for Generalized No-Regret Problems Andrey Bernstein, Shie Mannor, Nahum Shimkin

Optimal Probability Estimation with Applications to Prediction and Classification Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, Ananda Theertha Suresh

Passive Learning with Target Risk Mehrdad Mahdavi, Rong Jin

PLAL: Cluster-Based Active Learning Ruth Urner, Sharon Wulff, Shai Ben-David

Polynomial Time Optimal Query Algorithms for Finding Graphs with Arbitrary Real Weights Sung-Soon Choi

Prediction by Random-Walk Perturbation Luc Devroye, Gábor Lugosi, Gergely Neu

Randomized Partition Trees for Exact Nearest Neighbor Search Sanjoy Dasgupta, Kaushik Sinha

Recovering the Optimal Solution by Dual Random Projection Lijun Zhang, Mehrdad Mahdavi, Rong Jin, Tianbao Yang, Shenghuo Zhu

Regret Minimization for Branching Experts Eyal Gofer, Nicolò Cesa-Bianchi, Claudio Gentile, Yishay Mansour

Representation, Approximation and Learning of Submodular Functions Using Low-Rank Decision Trees Vitaly Feldman, Pravesh Kothari, Jan Vondrák

Sharp Analysis of Low-Rank Kernel Matrix Approximations Francis R. Bach

Sparse Adaptive Dirichlet-Multinomial-like Processes Marcus Hutter

Subspace Embeddings and \(\ell_p\)-Regression Using Exponential Random Variables David P. Woodruff, Qin Zhang

Surrogate Regret Bounds for the Area Under the ROC Curve via Strongly Proper Losses Shivani Agarwal

The Price of Bandit Information in Multiclass Online Classification Amit Daniely, Tom Helbertal