Preface

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

Open Problem: The Statistical Query Complexity of Learning Sparse Halfspaces

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

[abs][Download PDF]

Open Problem: Online Local Learning

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

[abs][Download PDF]

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

[abs][Download PDF]

Open Problem: Efficient Online Sparse Regression

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

[abs][Download PDF]

Distribution-independent Reliable Learning

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

[abs][Download PDF]

Learning without concentration

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

[abs][Download PDF]

Uniqueness of Ordinal Embedding

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

[abs][Download PDF]

Bayes-Optimal Scorers for Bipartite Ranking

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

[abs][Download PDF]

Multiarmed Bandits With Limited Expert Advice

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

[abs][Download PDF]

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

[abs][Download PDF]

Community Detection via Random and Adaptive Sampling

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

Higher-Order Regret Bounds with Switching Costs

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

[abs][Download PDF]

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

[abs][Download PDF]

Optimal learners for multiclass problems

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

[abs][Download PDF]

Stochastic Regret Minimization via Thompson Sampling

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

Finding a most biased coin with fewest flips

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

Efficiency of conformalized ridge regression

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

[abs][Download PDF]

Most Correlated Arms Identification

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

[abs][Download PDF]

Fast matrix completion without the condition number

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

[abs][Download PDF]

Learning Coverage Functions and Private Release of Marginals

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

Localized Complexities for Transductive Learning

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

Compressed Counting Meets Compressed Sensing

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

[abs][Download PDF]

The Geometry of Losses

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

[abs][Download PDF]

Resourceful Contextual Bandits

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

[abs][Download PDF]

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

[abs][Download PDF]

Near-Optimal Herding

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

Online Non-Parametric Regression

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

[abs][Download PDF]