[edit]

Volume 35: Conference on Learning Theory, 13-15 June 2014, Barcelona, Spain

[edit]

Editors: Maria Florina Balcan, Vitaly Feldman, Csaba Szepesvári

[bib][citeproc]

Contents:

Preface

Preface

Maria Florina Balcan, Csaba Szepesvári; Proceedings of The 27th Conference on Learning Theory, PMLR 35:1-2

Regular Papers

Open Problems

Open Problem: Tightness of maximum likelihood semidefinite relaxations

Afonso S. Bandeira, Yuehaw Khoo, Amit Singer; Proceedings of The 27th Conference on Learning Theory, PMLR 35:1265-1267

Open Problem: A (Missing) Boosting-type Convergence Result for AdaBoost.MH with Factorized Multi-class Classifiers

Balázs Kégl; Proceedings of The 27th Conference on Learning Theory, PMLR 35:1268-1275

Open Problem: Finding Good Cascade Sampling Processes for the Network Inference Problem

Manuel Gomez-Rodriguez, Le Song, Bernhard Schoelkopf; Proceedings of The 27th Conference on Learning Theory, PMLR 35:1276-1279

Open Problem: Tensor Decompositions: Algorithms up to the Uniqueness Threshold?

Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan; Proceedings of The 27th Conference on Learning Theory, PMLR 35:1280-1282

Open Problem: The Statistical Query Complexity of Learning Sparse Halfspaces

Vitaly Feldman; Proceedings of The 27th Conference on Learning Theory, PMLR 35:1283-1289

Open Problem: Online Local Learning

Paul Christiano; Proceedings of The 27th Conference on Learning Theory, PMLR 35:1290-1294

Open Problem: Shifting Experts on Easy Data

Manfred K. Warmuth, Wouter M. Koolen; Proceedings of The 27th Conference on Learning Theory, PMLR 35:1295-1298

Open Problem: Efficient Online Sparse Regression

Satyen Kale; Proceedings of The 27th Conference on Learning Theory, PMLR 35:1299-1301

Distribution-independent Reliable Learning

Varun Kanade, Justin Thaler; Proceedings of The 27th Conference on Learning Theory, PMLR 35:3-24

Learning without concentration

Shahar Mendelson; Proceedings of The 27th Conference on Learning Theory, PMLR 35:25-39

Uniqueness of Ordinal Embedding

Matthäus Kleindessner, Ulrike Luxburg; Proceedings of The 27th Conference on Learning Theory, PMLR 35:40-67

Bayes-Optimal Scorers for Bipartite Ranking

Aditya Krishna Menon, Robert C. Williamson; Proceedings of The 27th Conference on Learning Theory, PMLR 35:68-106

Multiarmed Bandits With Limited Expert Advice

Satyen Kale; Proceedings of The 27th Conference on Learning Theory, PMLR 35:107-122

Learning Sparsely Used Overcomplete Dictionaries

Alekh Agarwal, Animashree Anandkumar, Prateek Jain, Praneeth Netrapalli, Rashish Tandon; Proceedings of The 27th Conference on Learning Theory, PMLR 35:123-137

Community Detection via Random and Adaptive Sampling

Se-Young Yun, Alexandre Proutiere; Proceedings of The 27th Conference on Learning Theory, PMLR 35:138-175

A second-order bound with excess losses

Pierre Gaillard, Gilles Stoltz, Tim van Erven; Proceedings of The 27th Conference on Learning Theory, PMLR 35:176-196

Logistic Regression: Tight Bounds for Stochastic and Online Optimization

Elad Hazan, Tomer Koren, Kfir Y. Levy; Proceedings of The 27th Conference on Learning Theory, PMLR 35:197-209

Higher-Order Regret Bounds with Switching Costs

Eyal Gofer; Proceedings of The 27th Conference on Learning Theory, PMLR 35:210-243

The Complexity of Learning Halfspaces using Generalized Linear Methods

Amit Daniely, Nati Linial, Shai Shalev-Shwartz; Proceedings of The 27th Conference on Learning Theory, PMLR 35:244-286

Optimal learners for multiclass problems

Amit Daniely, Shai Shalev-Shwartz; Proceedings of The 27th Conference on Learning Theory, PMLR 35:287-316

Stochastic Regret Minimization via Thompson Sampling

Sudipto Guha, Kamesh Munagala; Proceedings of The 27th Conference on Learning Theory, PMLR 35:317-338

Approachability in unknown games: Online learning meets multi-objective optimization

Shie Mannor, Vianney Perchet, Gilles Stoltz; Proceedings of The 27th Conference on Learning Theory, PMLR 35:339-355

Belief propagation, robust reconstruction and optimal recovery of block models

Elchanan Mossel, Joe Neeman, Allan Sly; Proceedings of The 27th Conference on Learning Theory, PMLR 35:356-370

Sample Compression for Multi-label Concept Classes

Rahim Samei, Pavel Semukhin, Boting Yang, Sandra Zilles; Proceedings of The 27th Conference on Learning Theory, PMLR 35:371-393

Finding a most biased coin with fewest flips

Karthekeyan Chandrasekaran, Richard Karp; Proceedings of The 27th Conference on Learning Theory, PMLR 35:394-407

Volumetric Spanners: an Efficient Exploration Basis for Learning

Elad Hazan, Zohar Karnin, Raghu Meka; Proceedings of The 27th Conference on Learning Theory, PMLR 35:408-422

lil’ UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits

Kevin Jamieson, Matthew Malloy, Robert Nowak, Sébastien Bubeck; Proceedings of The 27th Conference on Learning Theory, PMLR 35:423-439

An Inequality with Applications to Structured Sparsity and Multitask Dictionary Learning

Andreas Maurer, Massimiliano Pontil, Bernardino Romera-Paredes; Proceedings of The 27th Conference on Learning Theory, PMLR 35:440-460

On the Complexity of A/B Testing

Emilie Kaufmann, Olivier Cappé, Aurélien Garivier; Proceedings of The 27th Conference on Learning Theory, PMLR 35:461-481

Elicitation and Identification of Properties

Ingo Steinwart, Chloé Pasin, Robert Williamson, Siyu Zhang; Proceedings of The 27th Conference on Learning Theory, PMLR 35:482-526

The sample complexity of agnostic learning under deterministic labels

Shai Ben-David, Ruth Urner; Proceedings of The 27th Conference on Learning Theory, PMLR 35:527-542

Density-preserving quantization with application to graph downsampling

Morteza Alamgir, Gábor Lugosi, Ulrike Luxburg; Proceedings of The 27th Conference on Learning Theory, PMLR 35:543-559

A Convex Formulation for Mixed Regression with Two Components: Minimax Optimal Rates

Yudong Chen, Xinyang Yi, Constantine Caramanis; Proceedings of The 27th Conference on Learning Theory, PMLR 35:560-604

Efficiency of conformalized ridge regression

Evgeny Burnaev, Vladimir Vovk; Proceedings of The 27th Conference on Learning Theory, PMLR 35:605-622

Most Correlated Arms Identification

Che-Yu Liu, Sébastien Bubeck; Proceedings of The 27th Conference on Learning Theory, PMLR 35:623-637

Fast matrix completion without the condition number

Moritz Hardt, Mary Wootters; Proceedings of The 27th Conference on Learning Theory, PMLR 35:638-678

Learning Coverage Functions and Private Release of Marginals

Vitaly Feldman, Pravesh Kothari; Proceedings of The 27th Conference on Learning Theory, PMLR 35:679-702

Computational Limits for Matrix Completion

Moritz Hardt, Raghu Meka, Prasad Raghavendra, Benjamin Weitz; Proceedings of The 27th Conference on Learning Theory, PMLR 35:703-725

Robust Multi-objective Learning with Mentor Feedback

Alekh Agarwal, Ashwinkumar Badanidiyuru, Miroslav Dudík, Robert E. Schapire, Aleksandrs Slivkins; Proceedings of The 27th Conference on Learning Theory, PMLR 35:726-741

Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability

Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan; Proceedings of The 27th Conference on Learning Theory, PMLR 35:742-778

New Algorithms for Learning Incoherent and Overcomplete Dictionaries

Sanjeev Arora, Rong Ge, Ankur Moitra; Proceedings of The 27th Conference on Learning Theory, PMLR 35:779-806

Online Linear Optimization via Smoothing

Jacob Abernethy, Chansoo Lee, Abhinav Sinha, Ambuj Tewari; Proceedings of The 27th Conference on Learning Theory, PMLR 35:807-823

Learning Mixtures of Discrete Product Distributions using Spectral Decompositions

Prateek Jain, Sewoong Oh; Proceedings of The 27th Conference on Learning Theory, PMLR 35:824-856

Localized Complexities for Transductive Learning

Ilya Tolstikhin, Gilles Blanchard, Marius Kloft; Proceedings of The 27th Conference on Learning Theory, PMLR 35:857-884

On the Consistency of Output Code Based Learning Algorithms for Multiclass Learning Problems

Harish G. Ramaswamy, Balaji Srinivasan Babu, Shivani Agarwal, Robert C. Williamson; Proceedings of The 27th Conference on Learning Theory, PMLR 35:885-902

Edge Label Inference in Generalized Stochastic Block Models: from Spectral Theory to Impossibility Results

Jiaming Xu, Laurent Massoulié, Marc Lelarge; Proceedings of The 27th Conference on Learning Theory, PMLR 35:903-920

Lower Bounds on the Performance of Polynomial-time Algorithms for Sparse Linear Regression

Yuchen Zhang, Martin J. Wainwright, Michael I. Jordan; Proceedings of The 27th Conference on Learning Theory, PMLR 35:921-948

Follow the Leader with Dropout Perturbations

Tim Van Erven, Wojciech Kotłowski, Manfred K. Warmuth; Proceedings of The 27th Conference on Learning Theory, PMLR 35:949-974

Lipschitz Bandits: Regret Lower Bound and Optimal Algorithms

Stefan Magureanu, Richard Combes, Alexandre Proutiere; Proceedings of The 27th Conference on Learning Theory, PMLR 35:975-999

Sample Complexity Bounds on Differentially Private Learning via Communication Complexity

Vitaly Feldman, David Xiao; Proceedings of The 27th Conference on Learning Theory, PMLR 35:1000-1019

Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations

H. Brendan McMahan, Francesco Orabona; Proceedings of The 27th Conference on Learning Theory, PMLR 35:1020-1039

Principal Component Analysis and Higher Correlations for Distributed Data

Ravi Kannan, Santosh Vempala, David Woodruff; Proceedings of The 27th Conference on Learning Theory, PMLR 35:1040-1057

Compressed Counting Meets Compressed Sensing

Ping Li, Cun-Hui Zhang, Tong Zhang; Proceedings of The 27th Conference on Learning Theory, PMLR 35:1058-1077

The Geometry of Losses

Robert C. Williamson; Proceedings of The 27th Conference on Learning Theory, PMLR 35:1078-1108

Resourceful Contextual Bandits

Ashwinkumar Badanidiyuru, John Langford, Aleksandrs Slivkins; Proceedings of The 27th Conference on Learning Theory, PMLR 35:1109-1134

The More, the Merrier: the Blessing of Dimensionality for Learning Large Gaussian Mixtures

Joseph Anderson, Mikhail Belkin, Navin Goyal, Luis Rademacher, James Voss; Proceedings of The 27th Conference on Learning Theory, PMLR 35:1135-1164

Near-Optimal Herding

Nick Harvey, Samira Samadi; Proceedings of The 27th Conference on Learning Theory, PMLR 35:1165-1182

Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians

Constantinos Daskalakis, Gautam Kamath; Proceedings of The 27th Conference on Learning Theory, PMLR 35:1183-1213

Online Learning with Composite Loss Functions

Ofer Dekel, Jian Ding, Tomer Koren, Yuval Peres; Proceedings of The 27th Conference on Learning Theory, PMLR 35:1214-1231

Online Non-Parametric Regression

Alexander Rakhlin, Karthik Sridharan; Proceedings of The 27th Conference on Learning Theory, PMLR 35:1232-1264

subscribe via RSS