COLT 2013

50 papers

Complexity Theoretic Lower Bounds for Sparse Principal Component Detection

Quentin Berthet, Philippe Rigollet

Efficient Learning of Simplices

Joseph Anderson, Navin Goyal, Luis Rademacher

Online Learning with Predictable Sequences

Alexander Rakhlin, Karthik Sridharan

Competing With Strategies

Wei Han, Alexander Rakhlin, Karthik Sridharan

Boosting with the Logistic Loss is Consistent

Matus Telgarsky

Adaptive Crowdsourcing Algorithms for the Bandit Survey Problem

Ittai Abraham, Omar Alonso, Vasilis Kandylas, Aleksandrs Slivkins

A Tensor Spectral Approach to Learning Mixed Membership Community Models

Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham Kakade

Learning a set of directions

Wouter M. Koolen, Jiazhong Nie, Manfred Warmuth

Differentially Private Feature Selection via Stability Arguments, and the Robustness of the Lasso

Abhradeep Guha Thakurta, Adam Smith

Polynomial Time Optimal Query Algorithms for Finding Graphs with Arbitrary Real Weights

Sung-Soon Choi

Optimal Probability Estimation with Applications to Prediction and Classification

Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, Ananda Theertha Suresh

A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret

Lachlan Andrew, Siddharth Barman, Katrina Ligett, Minghong Lin, Adam Meyerson

Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees

Vitaly Feldman, Pravesh Kothari, Jan Vondrak

A near-optimal algorithm for finite partial-monitoring games against adversarial opponents

Gabor Bartok

Claudio Gentile, Mark Herbster, Stephen Pasteris

Horizon-Independent Optimal Prediction with Log-Loss in Exponential Families

Peter Bartlett, Peter Grünwald, Peter Harremoës, Fares Hedayati, Wojciech Kotlowski

Regret Minimization for Branching Experts

Eyal Gofer, Nicolò Cesa-bianchi, Claudio Gentile, Yishay Mansour

Divide and Conquer Kernel Ridge Regression

Yuchen Zhang, John Duchi, Martin Wainwright

Consistency of Robust Kernel Density Estimators

Robert Vandermeulen, Clayton Scott

Subspace Embeddings and \ell_p-Regression Using Exponential Random Variables

David Woodruff, Qin Zhang

Learning Halfspaces Under Log-Concave Densities: Polynomial Approximations and Moment Matching

Daniel Kane, Adam Klivans, Raghu Meka

General Oracle Inequalities for Gibbs Posterior with Application to Ranking

Cheng Li, Wenxin Jiang, Martin Tanner

Classification with Asymmetric Label Noise: Consistency and Maximal Denoising

Clayton Scott, Gilles Blanchard, Gregory Handy

Approachability, fast and slow

Vianney Perchet, Shie Mannor

Prediction by random-walk perturbation

Luc Devroye, Gabor Lugosi, Gergely Neu

Sparse Adaptive Dirichlet-Multinomial-like Processes

Marcus Hutter

Learning Using Local Membership Queries

Pranjal Awasthi, Vitaly Feldman, Varun Kanade

PLAL: Cluster-based active learning

Ruth Urner, Sharon Wulff, Shai Ben-David

Algorithms and Hardness for Robust Subspace Recovery

Moritz Hardt, Ankur Moitra

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

Shivani Agarwal

Randomized partition trees for exact nearest neighbor search

Sanjoy Dasgupta, Kaushik Sinha

Active and passive learning of linear separators under log-concave distributions

Maria-Florina Balcan, Phil Long

Blind Signal Separation in the Presence of Gaussian Noise

Mikhail Belkin, Luis Rademacher, James Voss

Passive Learning with Target Risk

Mehrdad Mahdavi, Rong Jin

Information Complexity in Bandit Subset Selection

Emilie Kaufmann, Shivaram Kalyanakrishnan

Beating Bandits in Gradually Evolving Worlds

Chao-Kai Chiang, Chia-Jung Lee, Chi-Jen Lu

Sharp analysis of low-rank kernel matrix approximations

Francis Bach

Online Learning for Time Series Prediction

Oren Anava, Elad Hazan, Shie Mannor, Ohad Shamir

Opportunistic Strategies for Generalized No-Regret Problems

Andrey Bernstein, Shie Mannor, Nahum Shimkin

Recovering the Optimal Solution by Dual Random Projection

Lijun Zhang, Mehrdad Mahdavi, Rong Jin, Tianbao Yang, Shenghuo Zhu

Bounded regret in stochastic multi-armed bandits

Sébastien Bubeck, Vianney Perchet, Philippe Rigollet

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

Stanislav Minsker

The price of bandit information in multiclass online classification

Amit Daniely, Tom Helbertal

Honest Compressions and Their Application to Compression Schemes

Roi Livni, Pierre Simon

Excess risk bounds for multitask learning with trace norm regularization

Massimiliano Pontil, Andreas Maurer

A Theoretical Analysis of NDCG Type Ranking Measures

Yining Wang, Liwei Wang, Yuanzhi Li, Di He, Tie-yan Liu

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

Ohad Shamir

Open Problem: Lower bounds for Boosting with Hadamard Matrices

Jiazhong Nie, Manfred K. Warmuth, S.v.n. Vishwanathan, Xinhua Zhang

Open Problem: Fast Stochastic Exp-Concave Optimization

Tomer Koren

Open Problem: Adversarial Multiarmed Bandits with Limited Advice

Yevgeny Seldin, Koby Crammer, Peter Bartlett