Conference on Learning Theory 2020: Preface

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

[abs][Download PDF]

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

[abs][Download PDF]

Distributed Signal Detection under Communication Constraints

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

[abs][Download PDF]

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

[abs][Download PDF]

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

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

[abs][Download PDF]

From Nesterov’s Estimate Sequence to Riemannian Acceleration

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

[abs][Download PDF]

Closure Properties for Private Classification and Online Prediction

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

[abs][Download PDF]

Hierarchical Clustering: A 0.585 Revenue Approximation

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

[abs][Download PDF]

Winnowing with Gradient Descent

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

[abs][Download PDF]

Pan-Private Uniformity Testing

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

[abs][Download PDF]

Dimension-Free Bounds for Chasing Convex Functions

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

[abs][Download PDF]

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

[abs][Download PDF]

Data-driven confidence bands for distributed nonparametric regression

Valeriy Avanesov; PMLR 125:300-322

[abs][Download PDF]

Estimating Principal Components under Adversarial Perturbations

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

[abs][Download PDF]

Active Local Learning

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

[abs][Download PDF]

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

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

[abs][Download PDF]

Calibrated Surrogate Losses for Adversarially Robust Classification

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

[abs][Download PDF]

Complexity Guarantees for Polyak Steps with Momentum

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

[abs][Download PDF]

Free Energy Wells and Overlap Gap Property in Sparse PCA

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

[abs][Download PDF]

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

[abs][Download PDF]

Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models

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

[abs][Download PDF]

Selfish Robustness and Equilibria in Multi-Player Bandits

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

[abs][Download PDF]

Proper Learning, Helly Number, and an Optimal SVM Bound

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

[abs][Download PDF]

Sharper Bounds for Uniformly Stable Algorithms

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

[abs][Download PDF]

The Gradient Complexity of Linear Regression

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

[abs][Download PDF]

Reducibility and Statistical-Computational Gaps from Secret Leakage

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

[abs][Download PDF]

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

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

[abs][Download PDF]

ID3 Learns Juntas for Smoothed Product Distributions

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

[abs][Download PDF]

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

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

[abs][Download PDF]

How to Trap a Gradient Flow

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

[abs][Download PDF]

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

[abs][Download PDF]

Highly smooth minimization of non-smooth problems

Brian Bullins; PMLR 125:988-1030

[abs][Download PDF]

Efficient, Noise-Tolerant, and Private Learning via Boosting

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

[abs][Download PDF]

The estimation error of general first order methods

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

[abs][Download PDF]

Bounds in query learning

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

[abs][Download PDF]

Learning Polynomials in Few Relevant Dimensions

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

[abs][Download PDF]

The Influence of Shape Constraints on the Thresholding Bandit Problem

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

[abs][Download PDF]

Gradient descent algorithms for Bures-Wasserstein barycenters

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

Pessimism About Unknown Unknowns Inspires Conservatism

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

[abs][Download PDF]

Optimal Group Testing

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

[abs][Download PDF]

PAC learning with stable and private predictions

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

[abs][Download PDF]

High probability guarantees for stochastic convex optimization

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

[abs][Download PDF]

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

Jelena Diakonikolas; PMLR 125:1428-1451

[abs][Download PDF]

Approximation Schemes for ReLU Regression

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

[abs][Download PDF]

Learning Halfspaces with Massart Noise Under Structured Distributions

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

[abs][Download PDF]

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

[abs][Download PDF]

Consistent recovery threshold of hidden nearest neighbor graphs

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

[abs][Download PDF]

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

[abs][Download PDF]

Embedding Dimension of Polyhedral Losses

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

[abs][Download PDF]

Efficient Parameter Estimation of Truncated Boolean Product Distributions

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

[abs][Download PDF]

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

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

[abs][Download PDF]

From tree matching to sparse graph alignment

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

[abs][Download PDF]

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

Dan Garber; PMLR 125:1666-1681

[abs][Download PDF]

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

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

[abs][Download PDF]

No-Regret Prediction in Marginally Stable Systems

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

[abs][Download PDF]

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

[abs][Download PDF]

Locally Private Hypothesis Selection

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

[abs][Download PDF]

Bessel Smoothing and Multi-Distribution Property Estimation

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

[abs][Download PDF]

Faster Projection-free Online Learning

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

[abs][Download PDF]

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

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

[abs][Download PDF]

A Greedy Anytime Algorithm for Sparse PCA

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

[abs][Download PDF]

Noise-tolerant, Reliable Active Classification with Comparison Queries

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

[abs][Download PDF]

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

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

[abs][Download PDF]

Extrapolating the profile of a finite population

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

[abs][Download PDF]

Precise Tradeoffs in Adversarial Training for Linear Regression

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

[abs][Download PDF]

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

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

[abs][Download PDF]

Efficient improper learning for online logistic regression

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

[abs][Download PDF]

Gradient descent follows the regularization path for general losses

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

[abs][Download PDF]

Provably efficient reinforcement learning with linear function approximation

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

[abs][Download PDF]

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

[abs][Download PDF]

Private Mean Estimation of Heavy-Tailed Distributions

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

[abs][Download PDF]

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

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

[abs][Download PDF]

Privately Learning Thresholds: Closing the Exponential Gap

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

[abs][Download PDF]

Online Learning with Vector Costs and Bandits with Knapsacks

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

[abs][Download PDF]

Universal Approximation with Deep Narrow Networks

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

[abs][Download PDF]

Information Directed Sampling for Linear Partial Monitoring

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

[abs][Download PDF]

New Potential-Based Bounds for Prediction with Expert Advice

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

[abs][Download PDF]

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

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

[abs][Download PDF]

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

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

[abs][Download PDF]

Exploration by Optimisation in Partial Monitoring

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

[abs][Download PDF]

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

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

[abs][Download PDF]

Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo

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

[abs][Download PDF]

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

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

[abs][Download PDF][Supplementary PDF]

Learning Over-Parametrized Two-Layer Neural Networks beyond NTK

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

[abs][Download PDF]

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

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

[abs][Download PDF]

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

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

[abs][Download PDF]

Near-Optimal Algorithms for Minimax Optimization

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

[abs][Download PDF]

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

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

[abs][Download PDF]

Tight Lower Bounds for Combinatorial Multi-Armed Bandits

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

[abs][Download PDF]

Lipschitz and Comparator-Norm Adaptivity in Online Learning

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

[abs][Download PDF]

Information Theoretic Optimal Learning of Gaussian Graphical Models

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

[abs][Download PDF]

Parallels Between Phase Transitions and Circuit Complexity?

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

[abs][Download PDF]

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

[abs][Download PDF]

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

Mikito Nanashima; PMLR 125:2998-3029

[abs][Download PDF]

Fast Rates for Online Prediction with Abstention

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

[abs][Download PDF]

Efficient and robust algorithms for adversarial linear contextual bandits

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

[abs][Download PDF]

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

[abs][Download PDF]

Costly Zero Order Oracles

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

[abs][Download PDF]

Adaptive Submodular Maximization under Stochastic Item Costs

Srinivasan Parthasarathy; PMLR 125:3133-3151

[abs][Download PDF]

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

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

[abs][Download PDF]

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

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

[abs][Download PDF]

List Decodable Subspace Recovery

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

[abs][Download PDF]

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

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

[abs][Download PDF]

How Good is SGD with Random Shuffling?

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

[abs][Download PDF]

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

Marco Schmalhofer; PMLR 125:3285-3295

[abs][Download PDF]

Logistic Regression Regret: What’s the Catch?

Gil I Shamir; PMLR 125:3296-3319

[abs][Download PDF]

Improper Learning for Non-Stochastic Control

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

[abs][Download PDF]

Reasoning About Generalization via Conditional Mutual Information

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

[abs][Download PDF]

Estimation and Inference with Trees and Forests in High Dimensions

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

[abs][Download PDF]

Balancing Gaussian vectors in high dimension

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

[abs][Download PDF]

Active Learning for Identification of Linear Dynamical Systems

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

[abs][Download PDF]

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

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

[abs][Download PDF]

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

[abs][Download PDF]

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

[abs][Download PDF]

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

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

[abs][Download PDF]

Non-asymptotic Analysis for Nonparametric Testing

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

[abs][Download PDF]

Learning a Single Neuron with Gradient Methods

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

[abs][Download PDF]

Nearly Non-Expansive Bounds for Mahalanobis Hard Thresholding

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

[abs][Download PDF]

Wasserstein Control of Mirror Langevin Monte Carlo

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

[abs][Download PDF]

Open Problem: Model Selection for Contextual Bandits

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

[abs][Download PDF]

Open Problem: Tight Convergence of SGD in Constant Dimension

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

[abs][Download PDF]

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

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

[abs][Download PDF]

Open Problem: Information Complexity of VC Learning

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

[abs][Download PDF]

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

[abs][Download PDF]