## Volume 30: Conference on Learning Theory, 12-14 June 2013, Princeton, NJ, USA

[edit]

**Editors:
Shai Shalev-Shwartz,
Ingo Steinwart
**

[bib][citeproc]

### Preface

Preface

Shai Shalev-Shwartz,
Ingo Steinwart
;
PMLR 30:1-2

[abs]
[pdf]

### Regular Papers

### Open Problems

Open Problem: Adversarial Multiarmed Bandits with Limited Advice

Yevgeny Seldin,
Koby Crammer,
Peter Bartlett
;
PMLR 30:1067-1072

[abs]
[pdf]

Open Problem: Fast Stochastic Exp-Concave Optimization

Tomer Koren
;
PMLR 30:1073-1075

[abs]
[pdf]

Open Problem: Lower bounds for Boosting with Hadamard Matrices

Jiazhong Nie,
Manfred K. Warmuth,
S.V.N. Vishwanathan,
Xinhua Zhang
;
PMLR 30:1076-1079

[abs]
[pdf]

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

Ohad Shamir
;
PMLR 30:3-24

[abs]
[pdf]

A Theoretical Analysis of NDCG Type Ranking Measures

Yining Wang,
Liwei Wang,
Yuanzhi Li,
Di He,
Tie-Yan Liu
;
PMLR 30:25-54

[abs]
[pdf]

Excess risk bounds for multitask learning with trace norm regularization

Massimiliano Pontil,
Andreas Maurer
;
PMLR 30:55-76

[abs]
[pdf]

Honest Compressions and Their Application to Compression Schemes

Roi Livni,
Pierre Simon
;
PMLR 30:77-92

[abs]
[pdf]

The price of bandit information in multiclass online classification

Amit Daniely,
Tom Helbertal
;
PMLR 30:93-104

[abs]
[pdf]

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

Stanislav Minsker
;
PMLR 30:105-121

[abs]
[pdf]

Bounded regret in stochastic multi-armed bandits

Sébastien Bubeck,
Vianney Perchet,
Philippe Rigollet
;
PMLR 30:122-134

[abs]
[pdf]

Recovering the Optimal Solution by Dual Random Projection

Lijun Zhang,
Mehrdad Mahdavi,
Rong Jin,
Tianbao Yang,
Shenghuo Zhu
;
PMLR 30:135-157

[abs]
[pdf]

Opportunistic Strategies for Generalized No-Regret Problems

Andrey Bernstein,
Shie Mannor,
Nahum Shimkin
;
PMLR 30:158-171

[abs]
[pdf]

Online Learning for Time Series Prediction

Oren Anava,
Elad Hazan,
Shie Mannor,
Ohad Shamir
;
PMLR 30:172-184

[abs]
[pdf]

Sharp analysis of low-rank kernel matrix approximations

Francis Bach
;
PMLR 30:185-209

[abs]
[pdf]

Beating Bandits in Gradually Evolving Worlds

Chao-Kai Chiang,
Chia-Jung Lee,
Chi-Jen Lu
;
PMLR 30:210-227

[abs]
[pdf]

Information Complexity in Bandit Subset Selection

Emilie Kaufmann,
Shivaram Kalyanakrishnan
;
PMLR 30:228-251

[abs]
[pdf]

Passive Learning with Target Risk

Mehrdad Mahdavi,
Rong Jin
;
PMLR 30:252-269

[abs]
[pdf]

Blind Signal Separation in the Presence of Gaussian Noise

Mikhail Belkin,
Luis Rademacher,
James Voss
;
PMLR 30:270-287

[abs]
[pdf]

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

Maria-Florina Balcan,
Phil Long
;
PMLR 30:288-316

[abs]
[pdf]

Randomized partition trees for exact nearest neighbor search

Sanjoy Dasgupta,
Kaushik Sinha
;
PMLR 30:317-337

[abs]
[pdf]

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

Shivani Agarwal
;
PMLR 30:338-353

[abs]
[pdf]

Algorithms and Hardness for Robust Subspace Recovery

Moritz Hardt,
Ankur Moitra
;
PMLR 30:354-375

[abs]
[pdf]

PLAL: Cluster-based active learning

Ruth Urner,
Sharon Wulff,
Shai Ben-David
;
PMLR 30:376-397

[abs]
[pdf]

Learning Using Local Membership Queries

Pranjal Awasthi,
Vitaly Feldman,
Varun Kanade
;
PMLR 30:398-431

[abs]
[pdf]

Sparse Adaptive Dirichlet-Multinomial-like Processes

Marcus Hutter
;
PMLR 30:432-459

[abs]
[pdf]

Prediction by random-walk perturbation

Luc Devroye,
Gábor Lugosi,
Gergely Neu
;
PMLR 30:460-473

[abs]
[pdf]

Approachability, fast and slow

Vianney Perchet,
Shie Mannor
;
PMLR 30:474-488

[abs]
[pdf]

Classification with Asymmetric Label Noise: Consistency and Maximal Denoising

Clayton Scott,
Gilles Blanchard,
Gregory Handy
;
PMLR 30:489-511

[abs]
[pdf]

General Oracle Inequalities for Gibbs Posterior with Application to Ranking

Cheng Li,
Wenxin Jiang,
Martin Tanner
;
PMLR 30:512-521

[abs]
[pdf]

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

Daniel Kane,
Adam Klivans,
Raghu Meka
;
PMLR 30:522-545

[abs]
[pdf]

Subspace Embeddings and \ell_p-Regression Using Exponential Random Variables

David Woodruff,
Qin Zhang
;
PMLR 30:546-567

[abs]
[pdf]

Consistency of Robust Kernel Density Estimators

Robert Vandermeulen,
Clayton Scott
;
PMLR 30:568-591

[abs]
[pdf]

Divide and Conquer Kernel Ridge Regression

Yuchen Zhang,
John Duchi,
Martin Wainwright
;
PMLR 30:592-617

[abs]
[pdf]

Regret Minimization for Branching Experts

Eyal Gofer,
Nicolò Cesa-Bianchi,
Claudio Gentile,
Yishay Mansour
;
PMLR 30:618-638

[abs]
[pdf]

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

Peter Bartlett,
Peter Grünwald,
Peter Harremoës,
Fares Hedayati,
Wojciech Kotlowski
;
PMLR 30:639-661

[abs]
[pdf]

Online Similarity Prediction of Networked Data from Known and Unknown Graphs

Claudio Gentile,
Mark Herbster,
Stephen Pasteris
;
PMLR 30:662-695

[abs]
[pdf]

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

Gábor Bartók
;
PMLR 30:696-710

[abs]
[pdf]

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

Vitaly Feldman,
Pravesh Kothari,
Jan Vondrák
;
PMLR 30:711-740

[abs]
[pdf]

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

Lachlan Andrew,
Siddharth Barman,
Katrina Ligett,
Minghong Lin,
Adam Meyerson,
Alan Roytman,
Adam Wierman
;
PMLR 30:741-763

[abs]
[pdf]

Optimal Probability Estimation with Applications to Prediction and Classification

Jayadev Acharya,
Ashkan Jafarpour,
Alon Orlitsky,
Ananda Theertha Suresh
;
PMLR 30:764-796

[abs]
[pdf]

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

Sung-Soon Choi
;
PMLR 30:797-818

[abs]
[pdf]

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

Abhradeep Guha Thakurta,
Adam Smith
;
PMLR 30:819-850

[abs]
[pdf]

Learning a set of directions

Wouter M. Koolen,
Jiazhong Nie,
Manfred Warmuth
;
PMLR 30:851-866

[abs]
[pdf]

A Tensor Spectral Approach to Learning Mixed Membership Community Models

Animashree Anandkumar,
Rong Ge,
Daniel Hsu,
Sham Kakade
;
PMLR 30:867-881

[abs]
[pdf]

Adaptive Crowdsourcing Algorithms for the Bandit Survey Problem

Ittai Abraham,
Omar Alonso,
Vasilis Kandylas,
Aleksandrs Slivkins
;
PMLR 30:882-910

[abs]
[pdf]

Boosting with the Logistic Loss is Consistent

Matus Telgarsky
;
PMLR 30:911-965

[abs]
[pdf]

Competing With Strategies

Wei Han,
Alexander Rakhlin,
Karthik Sridharan
;
PMLR 30:966-992

[abs]
[pdf]

Online Learning with Predictable Sequences

Alexander Rakhlin,
Karthik Sridharan
;
PMLR 30:993-1019

[abs]
[pdf]

Efficient Learning of Simplices

Joseph Anderson,
Navin Goyal,
Luis Rademacher
;
PMLR 30:1020-1045

[abs]
[pdf]

Complexity Theoretic Lower Bounds for Sparse Principal Component Detection

Quentin Berthet,
Philippe Rigollet
;
PMLR 30:1046-1066

[abs]
[pdf]