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


Editors: Shai Shalev-Shwartz, Ingo Steinwart





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

Regular Papers

Open Problems

Open Problem: Adversarial Multiarmed Bandits with Limited Advice

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

Open Problem: Fast Stochastic Exp-Concave Optimization

Tomer Koren; PMLR 30:1073-1075

Open Problem: Lower bounds for Boosting with Hadamard Matrices

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

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

Ohad Shamir; PMLR 30:3-24

A Theoretical Analysis of NDCG Type Ranking Measures

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

Excess risk bounds for multitask learning with trace norm regularization

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

Honest Compressions and Their Application to Compression Schemes

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

The price of bandit information in multiclass online classification

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

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

Stanislav Minsker; PMLR 30:105-121

Bounded regret in stochastic multi-armed bandits

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

Recovering the Optimal Solution by Dual Random Projection

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

Opportunistic Strategies for Generalized No-Regret Problems

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

Online Learning for Time Series Prediction

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

Sharp analysis of low-rank kernel matrix approximations

Francis Bach; PMLR 30:185-209

Beating Bandits in Gradually Evolving Worlds

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

Information Complexity in Bandit Subset Selection

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

Passive Learning with Target Risk

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

Blind Signal Separation in the Presence of Gaussian Noise

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

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

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

Randomized partition trees for exact nearest neighbor search

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

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

Shivani Agarwal; PMLR 30:338-353

Algorithms and Hardness for Robust Subspace Recovery

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

PLAL: Cluster-based active learning

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

Learning Using Local Membership Queries

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

Sparse Adaptive Dirichlet-Multinomial-like Processes

Marcus Hutter; PMLR 30:432-459

Prediction by random-walk perturbation

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

Approachability, fast and slow

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

Classification with Asymmetric Label Noise: Consistency and Maximal Denoising

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

General Oracle Inequalities for Gibbs Posterior with Application to Ranking

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

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

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

Subspace Embeddings and \ell_p-Regression Using Exponential Random Variables

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

Consistency of Robust Kernel Density Estimators

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

Divide and Conquer Kernel Ridge Regression

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

Regret Minimization for Branching Experts

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

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

Online Similarity Prediction of Networked Data from Known and Unknown Graphs

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

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

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

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

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

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

Optimal Probability Estimation with Applications to Prediction and Classification

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

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

Sung-Soon Choi; PMLR 30:797-818

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

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

Learning a set of directions

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

A Tensor Spectral Approach to Learning Mixed Membership Community Models

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

Adaptive Crowdsourcing Algorithms for the Bandit Survey Problem

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

Boosting with the Logistic Loss is Consistent

Matus Telgarsky; PMLR 30:911-965

Competing With Strategies

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

Online Learning with Predictable Sequences

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

Efficient Learning of Simplices

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

Complexity Theoretic Lower Bounds for Sparse Principal Component Detection

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

subscribe via RSS