Conference on Learning Theory 2018: Preface

Sébastien Bubeck, Philippe Rigollet; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1-1

[abs][Download PDF]

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

Yuanzhi Li, Tengyu Ma, Hongyang Zhang; Proceedings of the 31st Conference On Learning Theory, PMLR 75:2-47

[abs][Download PDF]

Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure

Matthew Brennan, Guy Bresler, Wasim Huleihel; Proceedings of the 31st Conference On Learning Theory, PMLR 75:48-166

[abs][Download PDF]

Logistic Regression: The Importance of Being Improper

Dylan J. Foster, Satyen Kale, Haipeng Luo, Mehryar Mohri, Karthik Sridharan; Proceedings of the 31st Conference On Learning Theory, PMLR 75:167-208

[abs][Download PDF]

Actively Avoiding Nonsense in Generative Models

Steve Hanneke, Adam Tauman Kalai, Gautam Kamath, Christos Tzamos; Proceedings of the 31st Conference On Learning Theory, PMLR 75:209-227

[abs][Download PDF]

A Faster Approximation Algorithm for the Gibbs Partition Function

Vladimir Kolmogorov; Proceedings of the 31st Conference On Learning Theory, PMLR 75:228-249

[abs][Download PDF]

Exponential Convergence of Testing Error for Stochastic Gradient Methods

Loucas Pillaud-Vivien, Alessandro Rudi, Francis Bach; Proceedings of the 31st Conference On Learning Theory, PMLR 75:250-296

[abs][Download PDF]

Size-Independent Sample Complexity of Neural Networks

Noah Golowich, Alexander Rakhlin, Ohad Shamir; Proceedings of the 31st Conference On Learning Theory, PMLR 75:297-299

[abs][Download PDF]

Underdamped Langevin MCMC: A non-asymptotic analysis

Xiang Cheng, Niladri S. Chatterji, Peter L. Bartlett, Michael I. Jordan; Proceedings of the 31st Conference On Learning Theory, PMLR 75:300-323

[abs][Download PDF]

Online Variance Reduction for Stochastic Optimization

Zalan Borsos, Andreas Krause, Kfir Y. Levy; Proceedings of the 31st Conference On Learning Theory, PMLR 75:324-357

[abs][Download PDF]

Information Directed Sampling and Bandits with Heteroscedastic Noise

Johannes Kirschner, Andreas Krause; Proceedings of the 31st Conference On Learning Theory, PMLR 75:358-384

[abs][Download PDF]

Testing Symmetric Markov Chains From a Single Trajectory

Constantinos Daskalakis, Nishanth Dikkala, Nick Gravin; Proceedings of the 31st Conference On Learning Theory, PMLR 75:385-409

[abs][Download PDF]

Detection limits in the high-dimensional spiked rectangular model

Ahmed El Alaoui, Michael I. Jordan; Proceedings of the 31st Conference On Learning Theory, PMLR 75:410-438

[abs][Download PDF]

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

Max Simchowitz, Horia Mania, Stephen Tu, Michael I. Jordan, Benjamin Recht; Proceedings of the 31st Conference On Learning Theory, PMLR 75:439-473

[abs][Download PDF]

Active Tolerant Testing

Avrim Blum, Lunjia Hu; Proceedings of the 31st Conference On Learning Theory, PMLR 75:474-497

[abs][Download PDF]

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

Yan Shuo Tan, Roman Vershynin; Proceedings of the 31st Conference On Learning Theory, PMLR 75:498-534

[abs][Download PDF]

Calibrating Noise to Variance in Adaptive Data Analysis

Vitaly Feldman, Thomas Steinke; Proceedings of the 31st Conference On Learning Theory, PMLR 75:535-544

[abs][Download PDF]

Accelerating Stochastic Gradient Descent for Least Squares Regression

Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, Aaron Sidford; Proceedings of the 31st Conference On Learning Theory, PMLR 75:545-604

[abs][Download PDF]

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

Wenlong Mou, Liwei Wang, Xiyu Zhai, Kai Zheng; Proceedings of the 31st Conference On Learning Theory, PMLR 75:605-638

[abs][Download PDF]

Optimal approximation of continuous functions by very deep ReLU networks

Dmitry Yarotsky; Proceedings of the 31st Conference On Learning Theory, PMLR 75:639-649

[abs][Download PDF]

Averaging Stochastic Gradient Descent on Riemannian Manifolds

Nilesh Tripuraneni, Nicolas Flammarion, Francis Bach, Michael I. Jordan; Proceedings of the 31st Conference On Learning Theory, PMLR 75:650-687

[abs][Download PDF]

Fitting a Putative Manifold to Noisy Data

Charles Fefferman, Sergei Ivanov, Yaroslav Kurylev, Matti Lassas, Hariharan Narayanan; Proceedings of the 31st Conference On Learning Theory, PMLR 75:688-720

[abs][Download PDF]

Private Sequential Learning

John Tsitsiklis, Kuang Xu, Zhi Xu; Proceedings of the 31st Conference On Learning Theory, PMLR 75:721-727

[abs][Download PDF]

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

Jean Barbier, Florent Krzakala, Nicolas Macris, Léo Miolane, Lenka Zdeborová; Proceedings of the 31st Conference On Learning Theory, PMLR 75:728-731

[abs][Download PDF]

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

Victor Chernozhukov, Kaspar Wüthrich, Zhu Yinchu; Proceedings of the 31st Conference On Learning Theory, PMLR 75:732-749

[abs][Download PDF]

Nonstochastic Bandits with Composite Anonymous Feedback

Nicolò Cesa-Bianchi, Claudio Gentile, Yishay Mansour; Proceedings of the 31st Conference On Learning Theory, PMLR 75:750-773

[abs][Download PDF]

Lower Bounds for Higher-Order Convex Optimization

Naman Agarwal, Elad Hazan; Proceedings of the 31st Conference On Learning Theory, PMLR 75:774-792

[abs][Download PDF]

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

Raaz Dwivedi, Yuansi Chen, Martin J Wainwright, Bin Yu; Proceedings of the 31st Conference On Learning Theory, PMLR 75:793-797

[abs][Download PDF]

Incentivizing Exploration by Heterogeneous Users

Bangrui Chen, Peter Frazier, David Kempe; Proceedings of the 31st Conference On Learning Theory, PMLR 75:798-818

[abs][Download PDF]

Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms

Ilias Diakonikolas, Jerry Li, Ludwig Schmidt; Proceedings of the 31st Conference On Learning Theory, PMLR 75:819-842

[abs][Download PDF]

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

Paul Beame, Shayan Oveis Gharan, Xin Yang; Proceedings of the 31st Conference On Learning Theory, PMLR 75:843-856

[abs][Download PDF]

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

Belinda Tzen, Tengyuan Liang, Maxim Raginsky; Proceedings of the 31st Conference On Learning Theory, PMLR 75:857-875

[abs][Download PDF]

Hardness of Learning Noisy Halfspaces using Polynomial Thresholds

Arnab Bhattacharyya, Suprovat Ghoshal, Rishi Saket; Proceedings of the 31st Conference On Learning Theory, PMLR 75:876-917

[abs][Download PDF]

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

Yasin Abbasi-Yadkori, Peter Bartlett, Victor Gabillon, Alan Malek, Michal Valko; Proceedings of the 31st Conference On Learning Theory, PMLR 75:918-949

[abs][Download PDF]

Learning Patterns for Detection with Multiscale Scan Statistics

James Sharpnack; Proceedings of the 31st Conference On Learning Theory, PMLR 75:950-969

[abs][Download PDF]

Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk

Paul Hand, Vladislav Voroninski; Proceedings of the 31st Conference On Learning Theory, PMLR 75:970-978

[abs][Download PDF]

Small-loss bounds for online learning with partial information

Thodoris Lykouris, Karthik Sridharan, Éva Tardos; Proceedings of the 31st Conference On Learning Theory, PMLR 75:979-986

[abs][Download PDF]

Empirical bounds for functions with weak interactions

Andreas Maurer, Massimiliano Pontil; Proceedings of the 31st Conference On Learning Theory, PMLR 75:987-1010

[abs][Download PDF]

Restricted Eigenvalue from Stable Rank with Applications to Sparse Linear Regression

Shiva Prasad Kasiviswanathan, Mark Rudelson; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1011-1041

[abs][Download PDF]

Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent

Chi Jin, Praneeth Netrapalli, Michael I. Jordan; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1042-1085

[abs][Download PDF]

Convex Optimization with Unbounded Nonconvex Oracles using Simulated Annealing

Oren Mangoubi, Nisheeth K. Vishnoi; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1086-1124

[abs][Download PDF]

Learning Mixtures of Linear Regressions with Nearly Optimal Complexity

Yuanzhi Li, Yingyu Liang; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1125-1144

[abs][Download PDF]

Detecting Correlations with Little Memory and Communication

Yuval Dagan, Ohad Shamir; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1145-1198

[abs][Download PDF]

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

Gal Dalal, Gugan Thoppe, Balázs Szörényi, Shie Mannor; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1199-1233

[abs][Download PDF]

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

Timothy Carpenter, Ilias Diakonikolas, Anastasios Sidiropoulos, Alistair Stewart; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1234-1262

[abs][Download PDF]

More Adaptive Algorithms for Adversarial Bandits

Chen-Yu Wei, Haipeng Luo; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1263-1291

[abs][Download PDF]

Efficient Convex Optimization with Membership Oracles

Yin Tat Lee, Aaron Sidford, Santosh S. Vempala; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1292-1294

[abs][Download PDF]

A General Approach to Multi-Armed Bandits Under Risk Criteria

Asaf Cassel, Shie Mannor, Assaf Zeevi; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1295-1306

[abs][Download PDF]

An Optimal Learning Algorithm for Online Unconstrained Submodular Maximization

Tim Roughgarden, Joshua R. Wang; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1307-1325

[abs][Download PDF]

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

Vishesh Jain, Frederic Koehler, Elchanan Mossel; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1326-1347

[abs][Download PDF]

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

Mikhail Belkin; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1348-1361

[abs][Download PDF]

Non-Convex Matrix Completion Against a Semi-Random Adversary

Yu Cheng, Rong Ge; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1362-1394

[abs][Download PDF]

The Vertex Sample Complexity of Free Energy is Polynomial

Vishesh Jain, Frederic Koehler, Elchanan Mossel; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1395-1419

[abs][Download PDF]

Efficient Algorithms for Outlier-Robust Regression

Adam Klivans, Pravesh K. Kothari, Raghu Meka; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1420-1430

[abs][Download PDF]

Action-Constrained Markov Decision Processes With Kullback-Leibler Cost

Ana Bušić, Sean Meyn; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1431-1444

[abs][Download PDF]

Fundamental Limits of Weak Recovery with Applications to Phase Retrieval

Marco Mondelli, Andrea Montanari; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1445-1450

[abs][Download PDF]

Cutting plane methods can be extended into nonconvex optimization

Oliver Hinder; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1451-1454

[abs][Download PDF]

An Analysis of the t-SNE Algorithm for Data Visualization

Sanjeev Arora, Wei Hu, Pravesh K. Kothari; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1455-1462

[abs][Download PDF]

Adaptivity to Smoothness in X-armed bandits

Andrea Locatelli, Alexandra Carpentier; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1463-1492

[abs][Download PDF]

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

Ashok Cutkosky, Francesco Orabona; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1493-1529

[abs][Download PDF]

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

Michela Meister, Gregory Valiant; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1530-1546

[abs][Download PDF]

A Direct Sum Result for the Information Complexity of Learning

Ido Nachum, Jonathan Shafer, Amir Yehudayoff; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1547-1568

[abs][Download PDF]

Online learning over a finite action set with limited switching

Jason Altschuler, Kunal Talwar; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1569-1573

[abs][Download PDF]

Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent

Niangjun Chen, Gautam Goel, Adam Wierman; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1574-1594

[abs][Download PDF]

Faster Rates for Convex-Concave Games

Jacob Abernethy, Kevin A. Lai, Kfir Y. Levy, Jun-Kun Wang; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1595-1625

[abs][Download PDF]

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

David Durfee, Kevin A. Lai, Saurabh Sawlani; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1626-1656

[abs][Download PDF]

Optimal Single Sample Tests for Structured versus Unstructured Network Data

Guy Bresler, Dheeraj Nagaraj; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1657-1690

[abs][Download PDF]

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

Jalaj Bhandari, Daniel Russo, Raghav Singal; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1691-1692

[abs][Download PDF]

Privacy-preserving Prediction

Cynthia Dwork, Vitaly Feldman; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1693-1702

[abs][Download PDF]

An Estimate Sequence for Geodesically Convex Optimization

Hongyi Zhang, Suvrit Sra; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1703-1723

[abs][Download PDF]

The Externalities of Exploration and How Data Diversity Helps Exploitation

Manish Raghavan, Aleksandrs Slivkins, Jennifer Vaughan Wortman, Zhiwei Steven Wu; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1724-1738

[abs][Download PDF]

Efficient Contextual Bandits in Non-stationary Worlds

Haipeng Luo, Chen-Yu Wei, Alekh Agarwal, John Langford; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1739-1776

[abs][Download PDF]

Langevin Monte Carlo and JKO splitting

Espen Bernton; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1777-1798

[abs][Download PDF]

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

Nina Holden, Robin Pemantle, Yuval Peres; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1799-1840

[abs][Download PDF]

An explicit analysis of the entropic penalty in linear programming

Jonathan Weed; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1841-1855

[abs][Download PDF]

Efficient active learning of sparse halfspaces

Chicheng Zhang; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1856-1880

[abs][Download PDF]

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

Samory Kpotufe, Guillaume Martinet; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1882-1886

[abs][Download PDF]

Learning Single-Index Models in Gaussian Space

Rishabh Dudeja, Daniel Hsu; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1887-1930

[abs][Download PDF]

Hidden Integrality of SDP Relaxations for Sub-Gaussian Mixture Models

Yingjie Fei, Yudong Chen; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1931-1965

[abs][Download PDF]

Counting Motifs with Graph Sampling

Jason M. Klusowski, Yihong Wu; Proceedings of the 31st Conference On Learning Theory, PMLR 75:1966-2011

[abs][Download PDF]

Approximate Nearest Neighbors in Limited Space

Piotr Indyk, Tal Wagner; Proceedings of the 31st Conference On Learning Theory, PMLR 75:2012-2036

[abs][Download PDF]

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

Cheng Mao, Ashwin Pananjady, Martin J. Wainwright; Proceedings of the 31st Conference On Learning Theory, PMLR 75:2037-2042

[abs][Download PDF]

Unleashing Linear Optimizers for Group-Fair Learning and Optimization

Daniel Alabi, Nicole Immorlica, Adam Kalai; Proceedings of the 31st Conference On Learning Theory, PMLR 75:2043-2066

[abs][Download PDF]

The Many Faces of Exponential Weights in Online Learning

Dirk Hoeven, Tim Erven, Wojciech Kotłowski; Proceedings of the 31st Conference On Learning Theory, PMLR 75:2067-2092

[abs][Download PDF]

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

Andre Wibisono; Proceedings of the 31st Conference On Learning Theory, PMLR 75:2093-3027

[abs][Download PDF]

Online Learning: Sufficient Statistics and the Burkholder Method

Dylan J. Foster, Alexander Rakhlin, Karthik Sridharan; Proceedings of the 31st Conference On Learning Theory, PMLR 75:3028-3064

[abs][Download PDF]

Minimax Bounds on Stochastic Batched Convex Optimization

John Duchi, Feng Ruan, Chulhee Yun; Proceedings of the 31st Conference On Learning Theory, PMLR 75:3065-3162

[abs][Download PDF]

Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints

Yanjun Han, Ayfer Özgür, Tsachy Weissman; Proceedings of the 31st Conference On Learning Theory, PMLR 75:3163-3188

[abs][Download PDF]

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

Yanjun Han, Jiantao Jiao, Tsachy Weissman; Proceedings of the 31st Conference On Learning Theory, PMLR 75:3189-3221

[abs][Download PDF]

Iterate Averaging as Regularization for Stochastic Gradient Descent

Gergely Neu, Lorenzo Rosasco; Proceedings of the 31st Conference On Learning Theory, PMLR 75:3222-3242

[abs][Download PDF]

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

Srinadh Bhojanapalli, Nicolas Boumal, Prateek Jain, Praneeth Netrapalli; Proceedings of the 31st Conference On Learning Theory, PMLR 75:3243-3270

[abs][Download PDF]

Certified Computation from Unreliable Datasets

Themis Gouleakis, Christos Tzamos, Manolis Zampetakis; Proceedings of the 31st Conference On Learning Theory, PMLR 75:3271-3294

[abs][Download PDF]

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

Nan Jiang, Alekh Agarwal; Proceedings of the 31st Conference On Learning Theory, PMLR 75:3395-3398

[abs][Download PDF]

Open problem: Improper learning of mixtures of Gaussians

Elad Hazan, Livni Roi; Proceedings of the 31st Conference On Learning Theory, PMLR 75:3399-3402

[abs][Download PDF]