Volume 125: Conference on Learning Theory, 9-12 July 2020,


Editors: Jacob Abernethy, Shivani Agarwal


Conference on Learning Theory 2020: Preface

Jacob Abernethy,  Shivani Agarwal ; PMLR 125:1-2

Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit

Jayadev Acharya,  Clément L Canonne,  Yanjun Han,  Ziteng Sun,  Himanshu Tyagi ; PMLR 125:3-40

Distributed Signal Detection under Communication Constraints

Jayadev Acharya,  Clément L Canonne,  Himanshu Tyagi ; PMLR 125:41-63

Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes

Alekh Agarwal,  Sham M Kakade,  Jason D Lee,  Gaurav Mahajan ; PMLR 125:64-66

Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal

Alekh Agarwal,  Sham Kakade,  Lin F. Yang ; PMLR 125:67-83

From Nesterov’s Estimate Sequence to Riemannian Acceleration

Kwangjun Ahn,  Suvrit Sra ; PMLR 125:84-118

Closure Properties for Private Classification and Online Prediction

Noga Alon,  Amos Beimel,  Shay Moran,  Uri Stemmer ; PMLR 125:119-152

Hierarchical Clustering: A 0.585 Revenue Approximation

Noga Alon,  Yossi Azar,  Danny Vainstein ; PMLR 125:153-162

Winnowing with Gradient Descent

Ehsan Amid,  Manfred K. Warmuth ; PMLR 125:163-182

Pan-Private Uniformity Testing

Kareem Amin,  Matthew Joseph,  Jieming Mao ; PMLR 125:183-218

Dimension-Free Bounds for Chasing Convex Functions

C.J. Argue,  Anupam Gupta,  Guru Guruganesh ; PMLR 125:219-241

Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations

Yossi Arjevani,  Yair Carmon,  John C. Duchi,  Dylan J. Foster,  Ayush Sekhari,  Karthik Sridharan ; PMLR 125:242-299

Data-driven confidence bands for distributed nonparametric regression

Valeriy Avanesov ; PMLR 125:300-322

Estimating Principal Components under Adversarial Perturbations

Pranjal Awasthi,  Xue Chen,  Aravindan Vijayaraghavan ; PMLR 125:323-362

Active Local Learning

Arturs Backurs,  Avrim Blum,  Neha Gupta ; PMLR 125:363-390

Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent

James P. Bailey,  Gauthier Gidel,  Georgios Piliouras ; PMLR 125:391-407

Calibrated Surrogate Losses for Adversarially Robust Classification

Han Bao,  Clay Scott,  Masashi Sugiyama ; PMLR 125:408-451

Complexity Guarantees for Polyak Steps with Momentum

Mathieu Barré,  Adrien Taylor,  Alexandre d’Aspremont ; PMLR 125:452-478

Free Energy Wells and Overlap Gap Property in Sparse PCA

Gérard Ben Arous,  Alexander S. Wein,  Ilias Zadik ; PMLR 125:479-482

Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process

Guy Blanc,  Neha Gupta,  Gregory Valiant,  Paul Valiant ; PMLR 125:483-513

Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models

Antonio Blanca,  Zongchen Chen,  Daniel Štefankovič,  Eric Vigoda ; PMLR 125:514-529

Selfish Robustness and Equilibria in Multi-Player Bandits

Etienne Boursier,  Vianney Perchet ; PMLR 125:530-581

Proper Learning, Helly Number, and an Optimal SVM Bound

Olivier Bousquet,  Steve Hanneke,  Shay Moran,  Nikita Zhivotovskiy ; PMLR 125:582-609

Sharper Bounds for Uniformly Stable Algorithms

Olivier Bousquet,  Yegor Klochkov,  Nikita Zhivotovskiy ; PMLR 125:610-626

The Gradient Complexity of Linear Regression

Mark Braverman,  Elad Hazan,  Max Simchowitz,  Blake Woodworth ; PMLR 125:627-647

Reducibility and Statistical-Computational Gaps from Secret Leakage

Matthew Brennan,  Guy Bresler ; PMLR 125:648-847

A Corrective View of Neural Networks: Representation, Memorization and Learning

Guy Bresler,  Dheeraj Nagaraj ; PMLR 125:848-901

ID3 Learns Juntas for Smoothed Product Distributions

Alon Brutzkus,  Amit Daniely,  Eran Malach ; PMLR 125:902-915

Coordination without communication: optimal regret in two players multi-armed bandits

Sébastien Bubeck,  Thomas Budzinski ; PMLR 125:916-939

How to Trap a Gradient Flow

Sébastien Bubeck,  Dan Mikulincer ; PMLR 125:940-960

Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without

Sébastien Bubeck,  Yuanzhi Li,  Yuval Peres,  Mark Sellke ; PMLR 125:961-987

Highly smooth minimization of non-smooth problems

Brian Bullins ; PMLR 125:988-1030

Efficient, Noise-Tolerant, and Private Learning via Boosting

Mark Bun,  Marco Leandro Carmosino,  Jessica Sorrell ; PMLR 125:1031-1077

The estimation error of general first order methods

Michael Celentano,  Andrea Montanari,  Yuchen Wu ; PMLR 125:1078-1141

Bounds in query learning

Hunter Chase,  James Freitag ; PMLR 125:1142-1160

Learning Polynomials in Few Relevant Dimensions

Sitan Chen,  Raghu Meka ; PMLR 125:1161-1227

The Influence of Shape Constraints on the Thresholding Bandit Problem

James Cheshire,  Pierre Menard,  Alexandra Carpentier ; PMLR 125:1228-1275

Gradient descent algorithms for Bures-Wasserstein barycenters

Sinho Chewi,  Tyler Maunu,  Philippe Rigollet,  Austin J. Stromme ; PMLR 125:1276-1304

Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss

Lénaïc Chizat,  Francis Bach ; PMLR 125:1305-1338

ODE-Inspired Analysis for the Biological Version of Oja’s Rule in Solving Streaming PCA

Chi-Ning Chou,  Mien Brabeeba Wang ; PMLR 125:1339-1343

Pessimism About Unknown Unknowns Inspires Conservatism

Michael K. Cohen,  Marcus Hutter ; PMLR 125:1344-1373

Optimal Group Testing

Amin Coja-Oghlan,  Oliver Gebhard,  Max Hahn-Klimroth,  Philipp Loick ; PMLR 125:1374-1388

PAC learning with stable and private predictions

Yuval Dagan,  Vitaly Feldman ; PMLR 125:1389-1410

High probability guarantees for stochastic convex optimization

Damek Davis,  Dmitriy Drusvyatskiy ; PMLR 125:1411-1427

Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities

Jelena Diakonikolas ; PMLR 125:1428-1451

Approximation Schemes for ReLU Regression

Ilias Diakonikolas,  Surbhi Goel,  Sushrut Karmalkar,  Adam R. Klivans,  Mahdi Soltanolkotabi ; PMLR 125:1452-1485

Learning Halfspaces with Massart Noise Under Structured Distributions

Ilias Diakonikolas,  Vasilis Kontonis,  Christos Tzamos,  Nikos Zarifis ; PMLR 125:1486-1513

Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks

Ilias Diakonikolas,  Daniel M. Kane,  Vasilis Kontonis,  Nikos Zarifis ; PMLR 125:1514-1539

Consistent recovery threshold of hidden nearest neighbor graphs

Jian Ding,  Yihong Wu,  Jiaming Xu,  Dana Yang ; PMLR 125:1540-1553

Root-n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank

Kefan Dong,  Jian Peng,  Yining Wang,  Yuan Zhou ; PMLR 125:1554-1557

Embedding Dimension of Polyhedral Losses

Jessie Finocchiaro,  Rafael Frongillo,  Bo Waggoner ; PMLR 125:1558-1585

Efficient Parameter Estimation of Truncated Boolean Product Distributions

Dimitris Fotakis,  Alkis Kalavasis,  Christos Tzamos ; PMLR 125:1586-1600

Rigorous Guarantees for Tyler’s M-Estimator via Quantum Expansion

William Cole Franks,  Ankur Moitra ; PMLR 125:1601-1632

From tree matching to sparse graph alignment

Luca Ganassali,  Laurent Massoulié ; PMLR 125:1633-1665

On the Convergence of Stochastic Gradient Descent with Low-Rank Projections for Convex Low-Rank Matrix Problems

Dan Garber ; PMLR 125:1666-1681

Asymptotic Errors for High-Dimensional Convex Penalized Linear Regression beyond Gaussian Matrices

Cédric Gerbelot,  Alia Abbara,  Florent Krzakala ; PMLR 125:1682-1713

No-Regret Prediction in Marginally Stable Systems

Udaya Ghai,  Holden Lee,  Karan Singh,  Cyril Zhang,  Yi Zhang ; PMLR 125:1714-1757

Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems

Noah Golowich,  Sarath Pattathil,  Constantinos Daskalakis,  Asuman Ozdaglar ; PMLR 125:1758-1784

Locally Private Hypothesis Selection

Sivakanth Gopi,  Gautam Kamath,  Janardhan Kulkarni,  Aleksandar Nikolov,  Zhiwei Steven Wu,  Huanyu Zhang ; PMLR 125:1785-1816

Bessel Smoothing and Multi-Distribution Property Estimation

Yi Hao,  Ping Li ; PMLR 125:1817-1876

Faster Projection-free Online Learning

Elad Hazan,  Edgar Minasyan ; PMLR 125:1877-1893

Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond

Oliver Hinder,  Aaron Sidford,  Nimit Sohoni ; PMLR 125:1894-1938

A Greedy Anytime Algorithm for Sparse PCA

Guy Holtzman,  Adam Soffer,  Dan Vilenchik ; PMLR 125:1939-1956

Noise-tolerant, Reliable Active Classification with Comparison Queries

Max Hopkins,  Daniel Kane,  Shachar Lovett,  Gaurav Mahajan ; PMLR 125:1957-2006

Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes

Yichun Hu,  Nathan Kallus,  Xiaojie Mao ; PMLR 125:2007-2010

Extrapolating the profile of a finite population

Soham Jana,  Yury Polyanskiy,  Yihong Wu ; PMLR 125:2011-2033

Precise Tradeoffs in Adversarial Training for Linear Regression

Adel Javanmard,  Mahdi Soltanolkotabi,  Hamed Hassani ; PMLR 125:2034-2078

Robust causal inference under covariate shift via worst-case subpopulation treatment effects

Sookyo Jeong,  Hongseok Namkoong ; PMLR 125:2079-2084

Efficient improper learning for online logistic regression

Rémi Jézéquel,  Pierre Gaillard,  Alessandro Rudi ; PMLR 125:2085-2108

Gradient descent follows the regularization path for general losses

Ziwei Ji,  Miroslav Dudík,  Robert E. Schapire,  Matus Telgarsky ; PMLR 125:2109-2136

Provably efficient reinforcement learning with linear function approximation

Chi Jin,  Zhuoran Yang,  Zhaoran Wang,  Michael I Jordan ; PMLR 125:2137-2143

Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise

Maxim Kaledin,  Eric Moulines,  Alexey Naumov,  Vladislav Tadic,  Hoi-To Wai ; PMLR 125:2144-2203

Private Mean Estimation of Heavy-Tailed Distributions

Gautam Kamath,  Vikrant Singhal,  Jonathan Ullman ; PMLR 125:2204-2235

Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity

Pritish Kamath,  Omar Montasser,  Nathan Srebro ; PMLR 125:2236-2262

Privately Learning Thresholds: Closing the Exponential Gap

Haim Kaplan,  Katrina Ligett,  Yishay Mansour,  Moni Naor,  Uri Stemmer ; PMLR 125:2263-2285

Online Learning with Vector Costs and Bandits with Knapsacks

Thomas Kesselheim,  Sahil Singla ; PMLR 125:2286-2305

Universal Approximation with Deep Narrow Networks

Patrick Kidger,  Terry Lyons ; PMLR 125:2306-2327

Information Directed Sampling for Linear Partial Monitoring

Johannes Kirschner,  Tor Lattimore,  Andreas Krause ; PMLR 125:2328-2369

New Potential-Based Bounds for Prediction with Expert Advice

Vladimir A. Kobzar,  Robert V. Kohn,  Zhilei Wang ; PMLR 125:2370-2405

On Suboptimality of Least Squares with Application to Estimation of Convex Bodies

Gil Kur,  Alexander Rakhlin,  Adityanand Guntuboyina ; PMLR 125:2406-2424

The EM Algorithm gives Sample-Optimality for Learning Mixtures of Well-Separated Gaussians

Jeongyeol Kwon,  Constantine Caramanis ; PMLR 125:2425-2487

Exploration by Optimisation in Partial Monitoring

Tor Lattimore,  Csaba Szepesvári ; PMLR 125:2488-2515

A Closer Look at Small-loss Bounds for Bandits with Graph Feedback

Chung-Wei Lee,  Haipeng Luo,  Mengxiao Zhang ; PMLR 125:2516-2564

Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo

Yin Tat Lee,  Ruoqi Shen,  Kevin Tian ; PMLR 125:2565-2597

A Fast Spectral Algorithm for Mean Estimation with Sub-Gaussian Rates

Zhixian Lei,  Kyle Luh,  Prayaag Venkat,  Fred Zhang ; PMLR 125:2598-2612

Learning Over-Parametrized Two-Layer Neural Networks beyond NTK

Yuanzhi Li,  Tengyu Ma,  Hongyang R. Zhang ; PMLR 125:2613-2682

On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels

Tengyuan Liang,  Alexander Rakhlin,  Xiyu Zhai ; PMLR 125:2683-2711

Learning Entangled Single-Sample Gaussians in the Subset-of-Signals Model

Yingyu Liang,  Hui Yuan ; PMLR 125:2712-2737

Near-Optimal Algorithms for Minimax Optimization

Tianyi Lin,  Chi Jin,  Michael I. Jordan ; PMLR 125:2738-2779

Better Algorithms for Estimating Non-Parametric Models in Crowd-Sourcing and Rank Aggregation

Allen Liu,  Ankur Moitra ; PMLR 125:2780-2829

Tight Lower Bounds for Combinatorial Multi-Armed Bandits

Nadav Merlis,  Shie Mannor ; PMLR 125:2830-2857

Lipschitz and Comparator-Norm Adaptivity in Online Learning

Zakaria Mhammedi,  Wouter M. Koolen ; PMLR 125:2858-2887

Information Theoretic Optimal Learning of Gaussian Graphical Models

Sidhant Misra,  Marc Vuffray,  Andrey Y. Lokhov ; PMLR 125:2888-2909

Parallels Between Phase Transitions and Circuit Complexity?

Ankur Moitra,  Elchanan Mossel,  Colin Sandon ; PMLR 125:2910-2946

On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration

Wenlong Mou,  Chris Junchi Li,  Martin J Wainwright,  Peter L Bartlett,  Michael I Jordan ; PMLR 125:2947-2997

Extending Learnability to Auxiliary-Input Cryptographic Primitives and Meta-PAC Learning

Mikito Nanashima ; PMLR 125:2998-3029

Fast Rates for Online Prediction with Abstention

Gergely Neu,  Nikita Zhivotovskiy ; PMLR 125:3030-3048

Efficient and robust algorithms for adversarial linear contextual bandits

Gergely Neu,  Julia Olkhovskaya ; PMLR 125:3049-3068

An $\widetilde\mathcal{O}(m/\varepsilon^3.5)$-Cost Algorithm for Semidefinite Programs with Diagonal Constraints

Yin Tat Lee,  Swati Padmanabhan ; PMLR 125:3069-3119

Costly Zero Order Oracles

Renato Paes Leme,  Jon Schneider ; PMLR 125:3120-3132

Adaptive Submodular Maximization under Stochastic Item Costs

Srinivasan Parthasarathy ; PMLR 125:3133-3151

Covariance-adapting algorithm for semi-bandits with application to sparse outcomes

Pierre Perrault,  Michal Valko,  Vianney Perchet ; PMLR 125:3152-3184

Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning

Guannan Qu,  Adam Wierman ; PMLR 125:3185-3205

List Decodable Subspace Recovery

Prasad Raghavendra,  Morris Yau ; PMLR 125:3206-3226

Tsallis-INF for Decoupled Exploration and Exploitation in Multi-armed Bandits

Chloé Rouyer,  Yevgeny Seldin ; PMLR 125:3227-3249

How Good is SGD with Random Shuffling?

Itay Safran,  Ohad Shamir ; PMLR 125:3250-3284

A Nearly Optimal Variant of the Perceptron Algorithm for the Uniform Distribution on the Unit Sphere

Marco Schmalhofer ; PMLR 125:3285-3295

Logistic Regression Regret: What’s the Catch?

Gil I Shamir ; PMLR 125:3296-3319

Improper Learning for Non-Stochastic Control

Max Simchowitz,  Karan Singh,  Elad Hazan ; PMLR 125:3320-3436

Reasoning About Generalization via Conditional Mutual Information

Thomas Steinke,  Lydia Zakynthinou ; PMLR 125:3437-3452

Estimation and Inference with Trees and Forests in High Dimensions

Vasilis Syrgkanis,  Manolis Zampetakis ; PMLR 125:3453-3454

Balancing Gaussian vectors in high dimension

Paxton Turner,  Raghu Meka,  Philippe Rigollet ; PMLR 125:3455-3486

Active Learning for Identification of Linear Dynamical Systems

Andrew Wagenmaker,  Kevin Jamieson ; PMLR 125:3487-3582

Taking a hint: How to leverage loss predictors in contextual bandits?

Chen-Yu Wei,  Haipeng Luo,  Alekh Agarwal ; PMLR 125:3583-3634

Kernel and Rich Regimes in Overparametrized Models

Blake Woodworth,  Suriya Gunasekar,  Jason D. Lee,  Edward Moroshko,  Pedro Savarese,  Itay Golan,  Daniel Soudry,  Nathan Srebro ; PMLR 125:3635-3673

Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium

Qiaomin Xie,  Yudong Chen,  Zhaoran Wang,  Zhuoran Yang ; PMLR 125:3674-3682

Tree-projected gradient descent for estimating gradient-sparse parameters on graphs

Sheng Xu,  Zhou Fan,  Sahand Negahban ; PMLR 125:3683-3708

Non-asymptotic Analysis for Nonparametric Testing

Yun Yang,  Zuofeng Shang,  Guang Cheng ; PMLR 125:3709-3755

Learning a Single Neuron with Gradient Methods

Gilad Yehudai,  Shamir Ohad ; PMLR 125:3756-3786

Nearly Non-Expansive Bounds for Mahalanobis Hard Thresholding

Xiao-Tong Yuan,  Ping Li ; PMLR 125:3787-3813

Wasserstein Control of Mirror Langevin Monte Carlo

Kelvin Shuangjian Zhang,  Gabriel Peyré,  Jalal Fadili,  Marcelo Pereyra ; PMLR 125:3814-3841

Open Problem: Model Selection for Contextual Bandits

Dylan J. Foster,  Akshay Krishnamurthy,  Haipeng Luo ; PMLR 125:3842-3846

Open Problem: Tight Convergence of SGD in Constant Dimension

Tomer Koren,  Shahar Segal ; PMLR 125:3847-3851

Open Problem: Average-Case Hardness of Hypergraphic Planted Clique Detection

Yuetian Luo,  Anru R Zhang ; PMLR 125:3852-3856

Open Problem: Information Complexity of VC Learning

Thomas Steinke,  Lydia Zakynthinou ; PMLR 125:3857-3863

Open Problem: Fast and Optimal Online Portfolio Selection

Tim Van Erven,  Dirk Van der Hoeven,  Wojciech Kotłowski,  Wouter M. Koolen ; PMLR 125:3864-3869

subscribe via RSS