Volume 75: Conference On Learning Theory, 6-9 July 2018,


Editors: Sébastien Bubeck, Vianney Perchet, Philippe Rigollet




Conference on Learning Theory 2018: Preface

Sébastien Bubeck, Philippe Rigollet; PMLR 75:1-1

Best Paper Awards

Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations

Yuanzhi Li, Tengyu Ma, Hongyang Zhang; PMLR 75:2-47

Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure

Matthew Brennan, Guy Bresler, Wasim Huleihel; PMLR 75:48-166

Logistic Regression: The Importance of Being Improper

Dylan J. Foster, Satyen Kale, Haipeng Luo, Mehryar Mohri, Karthik Sridharan; PMLR 75:167-208

Regular Papers

Actively Avoiding Nonsense in Generative Models

Steve Hanneke, Adam Tauman Kalai, Gautam Kamath, Christos Tzamos; PMLR 75:209-227

A Faster Approximation Algorithm for the Gibbs Partition Function

Vladimir Kolmogorov; PMLR 75:228-249

Exponential Convergence of Testing Error for Stochastic Gradient Methods

Loucas Pillaud-Vivien, Alessandro Rudi, Francis Bach; PMLR 75:250-296

Size-Independent Sample Complexity of Neural Networks

Noah Golowich, Alexander Rakhlin, Ohad Shamir; PMLR 75:297-299

Underdamped Langevin MCMC: A non-asymptotic analysis

Xiang Cheng, Niladri S. Chatterji, Peter L. Bartlett, Michael I. Jordan; PMLR 75:300-323

Online Variance Reduction for Stochastic Optimization

Zalan Borsos, Andreas Krause, Kfir Y. Levy; PMLR 75:324-357

Information Directed Sampling and Bandits with Heteroscedastic Noise

Johannes Kirschner, Andreas Krause; PMLR 75:358-384

Testing Symmetric Markov Chains From a Single Trajectory

Constantinos Daskalakis, Nishanth Dikkala, Nick Gravin; PMLR 75:385-409

Detection limits in the high-dimensional spiked rectangular model

Ahmed El Alaoui, Michael I. Jordan; PMLR 75:410-438

Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification

Max Simchowitz, Horia Mania, Stephen Tu, Michael I. Jordan, Benjamin Recht; PMLR 75:439-473

Active Tolerant Testing

Avrim Blum, Lunjia Hu; PMLR 75:474-497

Polynomial Time and Sample Complexity for Non-Gaussian Component Analysis: Spectral Methods

Yan Shuo Tan, Roman Vershynin; PMLR 75:498-534

Calibrating Noise to Variance in Adaptive Data Analysis

Vitaly Feldman, Thomas Steinke; PMLR 75:535-544

Accelerating Stochastic Gradient Descent for Least Squares Regression

Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, Aaron Sidford; PMLR 75:545-604

Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints

Wenlong Mou, Liwei Wang, Xiyu Zhai, Kai Zheng; PMLR 75:605-638

Optimal approximation of continuous functions by very deep ReLU networks

Dmitry Yarotsky; PMLR 75:639-649

Averaging Stochastic Gradient Descent on Riemannian Manifolds

Nilesh Tripuraneni, Nicolas Flammarion, Francis Bach, Michael I. Jordan; PMLR 75:650-687

Fitting a Putative Manifold to Noisy Data

Charles Fefferman, Sergei Ivanov, Yaroslav Kurylev, Matti Lassas, Hariharan Narayanan; PMLR 75:688-720

Private Sequential Learning

John Tsitsiklis, Kuang Xu, Zhi Xu; PMLR 75:721-727

Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models

Jean Barbier, Florent Krzakala, Nicolas Macris, Léo Miolane, Lenka Zdeborová; PMLR 75:728-731

Exact and Robust Conformal Inference Methods for Predictive Machine Learning with Dependent Data

Victor Chernozhukov, Kaspar Wüthrich, Zhu Yinchu; PMLR 75:732-749

Nonstochastic Bandits with Composite Anonymous Feedback

Nicolò Cesa-Bianchi, Claudio Gentile, Yishay Mansour; PMLR 75:750-773

Lower Bounds for Higher-Order Convex Optimization

Naman Agarwal, Elad Hazan; PMLR 75:774-792

Log-concave sampling: Metropolis-Hastings algorithms are fast!

Raaz Dwivedi, Yuansi Chen, Martin J Wainwright, Bin Yu; PMLR 75:793-797

Incentivizing Exploration by Heterogeneous Users

Bangrui Chen, Peter Frazier, David Kempe; PMLR 75:798-818

Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms

Ilias Diakonikolas, Jerry Li, Ludwig Schmidt; PMLR 75:819-842

Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials

Paul Beame, Shayan Oveis Gharan, Xin Yang; PMLR 75:843-856

Local Optimality and Generalization Guarantees for the Langevin Algorithm via Empirical Metastability

Belinda Tzen, Tengyuan Liang, Maxim Raginsky; PMLR 75:857-875

Hardness of Learning Noisy Halfspaces using Polynomial Thresholds

Arnab Bhattacharyya, Suprovat Ghoshal, Rishi Saket; PMLR 75:876-917

Best of both worlds: Stochastic & adversarial best-arm identification

Yasin Abbasi-Yadkori, Peter Bartlett, Victor Gabillon, Alan Malek, Michal Valko; PMLR 75:918-949

Learning Patterns for Detection with Multiscale Scan Statistics

James Sharpnack; PMLR 75:950-969

Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk

Paul Hand, Vladislav Voroninski; PMLR 75:970-978

Small-loss bounds for online learning with partial information

Thodoris Lykouris, Karthik Sridharan, Éva Tardos; PMLR 75:979-986

Empirical bounds for functions with weak interactions

Andreas Maurer, Massimiliano Pontil; PMLR 75:987-1010

Restricted Eigenvalue from Stable Rank with Applications to Sparse Linear Regression

Shiva Prasad Kasiviswanathan, Mark Rudelson; PMLR 75:1011-1041

Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent

Chi Jin, Praneeth Netrapalli, Michael I. Jordan; PMLR 75:1042-1085

Convex Optimization with Unbounded Nonconvex Oracles using Simulated Annealing

Oren Mangoubi, Nisheeth K. Vishnoi; PMLR 75:1086-1124

Learning Mixtures of Linear Regressions with Nearly Optimal Complexity

Yuanzhi Li, Yingyu Liang; PMLR 75:1125-1144

Detecting Correlations with Little Memory and Communication

Yuval Dagan, Ohad Shamir; PMLR 75:1145-1198

Finite Sample Analysis of Two-Timescale Stochastic Approximation with Applications to Reinforcement Learning

Gal Dalal, Gugan Thoppe, Balázs Szörényi, Shie Mannor; PMLR 75:1199-1233

Near-Optimal Sample Complexity Bounds for Maximum Likelihood Estimation of Multivariate Log-concave Densities

Timothy Carpenter, Ilias Diakonikolas, Anastasios Sidiropoulos, Alistair Stewart; PMLR 75:1234-1262

More Adaptive Algorithms for Adversarial Bandits

Chen-Yu Wei, Haipeng Luo; PMLR 75:1263-1291

Efficient Convex Optimization with Membership Oracles

Yin Tat Lee, Aaron Sidford, Santosh S. Vempala; PMLR 75:1292-1294

A General Approach to Multi-Armed Bandits Under Risk Criteria

Asaf Cassel, Shie Mannor, Assaf Zeevi; PMLR 75:1295-1306

An Optimal Learning Algorithm for Online Unconstrained Submodular Maximization

Tim Roughgarden, Joshua R. Wang; PMLR 75:1307-1325

The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity

Vishesh Jain, Frederic Koehler, Elchanan Mossel; PMLR 75:1326-1347

Approximation beats concentration? An approximation view on inference with smooth radial kernels

Mikhail Belkin; PMLR 75:1348-1361

Non-Convex Matrix Completion Against a Semi-Random Adversary

Yu Cheng, Rong Ge; PMLR 75:1362-1394

The Vertex Sample Complexity of Free Energy is Polynomial

Vishesh Jain, Frederic Koehler, Elchanan Mossel; PMLR 75:1395-1419

Efficient Algorithms for Outlier-Robust Regression

Adam Klivans, Pravesh K. Kothari, Raghu Meka; PMLR 75:1420-1430

Action-Constrained Markov Decision Processes With Kullback-Leibler Cost

Ana Bušić, Sean Meyn; PMLR 75:1431-1444

Fundamental Limits of Weak Recovery with Applications to Phase Retrieval

Marco Mondelli, Andrea Montanari; PMLR 75:1445-1450

Cutting plane methods can be extended into nonconvex optimization

Oliver Hinder; PMLR 75:1451-1454

An Analysis of the t-SNE Algorithm for Data Visualization

Sanjeev Arora, Wei Hu, Pravesh K. Kothari; PMLR 75:1455-1462

Adaptivity to Smoothness in X-armed bandits

Andrea Locatelli, Alexandra Carpentier; PMLR 75:1463-1492

Black-Box Reductions for Parameter-free Online Learning in Banach Spaces

Ashok Cutkosky, Francesco Orabona; PMLR 75:1493-1529

A Data Prism: Semi-verified learning in the small-alpha regime

Michela Meister, Gregory Valiant; PMLR 75:1530-1546

A Direct Sum Result for the Information Complexity of Learning

Ido Nachum, Jonathan Shafer, Amir Yehudayoff; PMLR 75:1547-1568

Online learning over a finite action set with limited switching

Jason Altschuler, Kunal Talwar; PMLR 75:1569-1573

Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent

Niangjun Chen, Gautam Goel, Adam Wierman; PMLR 75:1574-1594

Faster Rates for Convex-Concave Games

Jacob Abernethy, Kevin A. Lai, Kfir Y. Levy, Jun-Kun Wang; PMLR 75:1595-1625

$\ell_1$ Regression using Lewis Weights Preconditioning and Stochastic Gradient Descent

David Durfee, Kevin A. Lai, Saurabh Sawlani; PMLR 75:1626-1656

Optimal Single Sample Tests for Structured versus Unstructured Network Data

Guy Bresler, Dheeraj Nagaraj; PMLR 75:1657-1690

A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation

Jalaj Bhandari, Daniel Russo, Raghav Singal; PMLR 75:1691-1692

Privacy-preserving Prediction

Cynthia Dwork, Vitaly Feldman; PMLR 75:1693-1702

An Estimate Sequence for Geodesically Convex Optimization

Hongyi Zhang, Suvrit Sra; PMLR 75:1703-1723

The Externalities of Exploration and How Data Diversity Helps Exploitation

Manish Raghavan, Aleksandrs Slivkins, Jennifer Vaughan Wortman, Zhiwei Steven Wu; PMLR 75:1724-1738

Efficient Contextual Bandits in Non-stationary Worlds

Haipeng Luo, Chen-Yu Wei, Alekh Agarwal, John Langford; PMLR 75:1739-1776

Langevin Monte Carlo and JKO splitting

Espen Bernton; PMLR 75:1777-1798

Subpolynomial trace reconstruction for random strings \{and arbitrary deletion probability

Nina Holden, Robin Pemantle, Yuval Peres; PMLR 75:1799-1840

An explicit analysis of the entropic penalty in linear programming

Jonathan Weed; PMLR 75:1841-1855

Efficient active learning of sparse halfspaces

Chicheng Zhang; PMLR 75:1856-1880

Marginal Singularity, and the Benefits of Labels in Covariate-Shift

Samory Kpotufe, Guillaume Martinet; PMLR 75:1882-1886

Learning Single-Index Models in Gaussian Space

Rishabh Dudeja, Daniel Hsu; PMLR 75:1887-1930

Hidden Integrality of SDP Relaxations for Sub-Gaussian Mixture Models

Yingjie Fei, Yudong Chen; PMLR 75:1931-1965

Counting Motifs with Graph Sampling

Jason M. Klusowski, Yihong Wu; PMLR 75:1966-2011

Approximate Nearest Neighbors in Limited Space

Piotr Indyk, Tal Wagner; PMLR 75:2012-2036

Breaking the $1/\sqrt{n}$ Barrier: Faster Rates for Permutation-based Models in Polynomial Time

Cheng Mao, Ashwin Pananjady, Martin J. Wainwright; PMLR 75:2037-2042

Unleashing Linear Optimizers for Group-Fair Learning and Optimization

Daniel Alabi, Nicole Immorlica, Adam Kalai; PMLR 75:2043-2066

The Many Faces of Exponential Weights in Online Learning

Dirk Hoeven, Tim Erven, Wojciech Kotłowski; PMLR 75:2067-2092

Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem

Andre Wibisono; PMLR 75:2093-3027

Online Learning: Sufficient Statistics and the Burkholder Method

Dylan J. Foster, Alexander Rakhlin, Karthik Sridharan; PMLR 75:3028-3064

Minimax Bounds on Stochastic Batched Convex Optimization

John Duchi, Feng Ruan, Chulhee Yun; PMLR 75:3065-3162

Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints

Yanjun Han, Ayfer Özgür, Tsachy Weissman; PMLR 75:3163-3188

Local moment matching: A unified methodology for symmetric functional estimation and distribution estimation under Wasserstein distance

Yanjun Han, Jiantao Jiao, Tsachy Weissman; PMLR 75:3189-3221

Iterate Averaging as Regularization for Stochastic Gradient Descent

Gergely Neu, Lorenzo Rosasco; PMLR 75:3222-3242

Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form

Srinadh Bhojanapalli, Nicolas Boumal, Prateek Jain, Praneeth Netrapalli; PMLR 75:3243-3270

Certified Computation from Unreliable Datasets

Themis Gouleakis, Christos Tzamos, Manolis Zampetakis; PMLR 75:3271-3294

Open Problems

Open Problem: The Dependence of Sample Complexity Lower Bounds on Planning Horizon

Nan Jiang, Alekh Agarwal; PMLR 75:3395-3398

Open problem: Improper learning of mixtures of Gaussians

Elad Hazan, Livni Roi; PMLR 75:3399-3402

subscribe via RSS