COLT 2020

126 papers

Reducibility and Statistical-Computational Gaps from Secret Leakage

Matthew Brennan, Guy Bresler

The Gradient Complexity of Linear Regression

Mark Braverman, Elad Hazan, Max Simchowitz, Blake Woodworth

Sharper Bounds for Uniformly Stable Algorithms

Olivier Bousquet, Yegor Klochkov, Nikita Zhivotovskiy

Proper Learning, Helly Number, and an Optimal SVM Bound

Olivier Bousquet, Steve Hanneke, Shay Moran, Nikita Zhivotovskiy

Selfish Robustness and Equilibria in Multi-Player Bandits

Etienne Boursier, Vianney Perchet

Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models

Antonio Blanca, Zongchen Chen, Daniel Stefankovic, Eric Vigoda

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

Guy Blanc, Neha Gupta, Gregory Valiant, Paul Valiant

Free Energy Wells and Overlap Gap Property in Sparse PCA

Gerard Ben Arous, Alexander S. Wein, Ilias Zadik

Complexity Guarantees for Polyak Steps with Momentum

Mathieu Barré, Adrien Taylor, Alexandre d’Aspremont

Calibrated Surrogate Losses for Adversarially Robust Classification

Han Bao, Clay Scott, Masashi Sugiyama

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

James P. Bailey, Gauthier Gidel, Georgios Piliouras

Active Local Learning

Arturs Backurs, Avrim Blum, Neha Gupta

Estimating Principal Components under Adversarial Perturbations

Pranjal Awasthi, Xue Chen, Aravindan Vijayaraghavan

Data-driven confidence bands for distributed nonparametric regression

Valeriy Avanesov

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

Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Ayush Sekhari

Dimension-Free Bounds for Chasing Convex Functions

C.J. Argue, Anupam Gupta, Guru Guruganesh

Pan-Private Uniformity Testing

Kareem Amin, Matthew Joseph, Jieming Mao

Winnowing with Gradient Descent

Ehsan Amid, Manfred K. Warmuth

Hierarchical Clustering: A 0.585 Revenue Approximation

Noga Alon, Yossi Azar, Danny Vainstein

Closure Properties for Private Classification and Online Prediction

Noga Alon, Amos Beimel, Shay Moran, Uri Stemmer

From Nesterov’s Estimate Sequence to Riemannian Acceleration

Kwangjun Ahn, Suvrit Sra

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

Alekh Agarwal, Sham Kakade, Lin F. Yang

Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes

Alekh Agarwal, Sham M Kakade, Jason D Lee, Gaurav Mahajan

Distributed Signal Detection under Communication Constraints

Jayadev Acharya, Clément L Canonne, Himanshu Tyagi

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

Jayadev Acharya, Clément L Canonne, Yanjun Han, Ziteng Sun, Himanshu Tyagi

Conference on Learning Theory 2020: Preface

Jacob Abernethy, Shivani Agarwal