[edit]
Volume 125: Conference on Learning Theory, 9-12 July 2020,
[edit]
Editors: Jacob Abernethy, Shivani Agarwal
[bib][citeproc]
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]