COLT 2021

140 papers

(Nearly) Dimension Independent Private ERM with AdaGrad Rates\{via Publicly Estimated Subspaces Peter Kairouz, Monica Ribero Diaz, Keith Rush, Abhradeep Thakurta

**Paper Retracted by Author Request (see Pdf for Retraction Notice from the Authors)** Nonparametric Regression with Shallow Overparameterized Neural Networks Trained by GD with Early Stopping Ilja Kuzborskij, Csaba Szepesvari

A Dimension-Free Computational Upper-Bound for Smooth Optimal Transport Estimation Adrien Vacher, Boris Muzellec, Alessandro Rudi, Francis Bach, Francois-Xavier Vialard

A Law of Robustness for Two-Layers Neural Networks Sebastien Bubeck, Yuanzhi Li, Dheeraj M Nagaraj

A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Network Mo Zhou, Rong Ge, Chi Jin

A Priori Generalization Analysis of the Deep Ritz Method for Solving High Dimensional Elliptic Partial Differential Equations Yulong Lu, Jianfeng Lu, Min Wang

A Statistical Taylor Theorem and Extrapolation of Truncated Densities Constantinos Daskalakis, Vasilis Kontonis, Christos Tzamos, Emmanouil Zampetakis

A Theory of Heuristic Learnability Mikito Nanashima

Adaptive Discretization for Adversarial Lipschitz Bandits Chara Podimata, Alex Slivkins

Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium Yu-Guan Hsieh, Kimon Antonakopoulos, Panayotis Mertikopoulos

Adaptivity in Adaptive Submodularity Hossein Esfandiari, Amin Karbasi, Vahab Mirrokni

Adversarially Robust Learning with Unknown Perturbation Sets Omar Montasser, Steve Hanneke, Nathan Srebro

Adversarially Robust Low Dimensional Representations Pranjal Awasthi, Vaggos Chatziafratis, Xue Chen, Aravindan Vijayaraghavan

Agnostic Proper Learning of Halfspaces Under Gaussian Marginals Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis

Almost Sure Convergence Rates for Stochastic Gradient Descent and Stochastic Heavy Ball Othmane Sebbouh, Robert M Gower, Aaron Defazio

Approximation Algorithms for Socially Fair Clustering Yury Makarychev, Ali Vakilian

Asymptotically Optimal Information-Directed Sampling Johannes Kirschner, Tor Lattimore, Claire Vernade, Csaba Szepesvari

Average-Case Communication Complexity of Statistical Problems Cyrus Rashtchian, David Woodruff, Peng Ye, Hanlin Zhu

Benign Overfitting of Constant-Stepsize SGD for Linear Regression Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, Sham Kakade

Black-Box Control for Linear Dynamical Systems Xinyi Chen, Elad Hazan

Boosting in the Presence of Massart Noise Ilias Diakonikolas, Russell Impagliazzo, Daniel M. Kane, Rex Lei, Jessica Sorrell, Christos Tzamos

Bounded Memory Active Learning Through Enriched Queries Max Hopkins, Daniel Kane, Shachar Lovett, Michal Moshkovitz

Breaking the Dimension Dependence in Sparse Distribution Estimation Under Communication Constraints Wei-Ning Chen, Peter Kairouz, Ayfer Ozgur

Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation Andrea Zanette, Ching-An Cheng, Alekh Agarwal

Concentration of Non-Isotropic Random Tensors with Applications to Learning and Empirical Risk Minimization Mathieu Even, Laurent Massoulie

Convergence Rates and Approximation Results for SGD and Its Continuous-Time Counterpart Xavier Fontaine, Valentin De Bortoli, Alain Durmus

Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret with Neither Communication nor Collisions Sebastien Bubeck, Thomas Budzinski, Mark Sellke

Corruption-Robust Exploration in Episodic Reinforcement Learning Thodoris Lykouris, Max Simchowitz, Alex Slivkins, Wen Sun

Deterministic Finite-Memory Bias Estimation Tomer Berg, Or Ordentlich, Ofer Shayevitz

Differentially Private Nonparametric Regression Under a Growth Condition Noah Golowich

Double Explore-Then-Commit: Asymptotic Optimality and Beyond Tianyuan Jin, Pan Xu, Xiaokui Xiao, Quanquan Gu

Efficient Algorithms for Learning from Coarse Labels Dimitris Fotakis, Alkis Kalavasis, Vasilis Kontonis, Christos Tzamos

Efficient Bandit Convex Optimization: Beyond Linear Losses Arun Sai Suggala, Pradeep Ravikumar, Praneeth Netrapalli

Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries Marco Bressan, Nicoló Cesa-Bianchi, Silvio Lattanzi, Andrea Paudice

Exponential Savings in Agnostic Active Learning Through Abstention Nikita Puchkin, Nikita Zhivotovskiy

Exponential Weights Algorithms for Selective Learning Mingda Qiao, Gregory Valiant

Exponentially Improved Dimensionality Reduction for L1: Subspace Embeddings and Independence Testing Yi Li, David Woodruff, Taisuke Yasuda

Fast Rates for Structured Prediction Vivien A Cabannes, Francis Bach, Alessandro Rudi

Fast Rates for the Regret of Offline Reinforcement Learning Yichun Hu, Nathan Kallus, Masatoshi Uehara

Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap Haike Xu, Tengyu Ma, Simon Du

Frank-Wolfe with a Nearest Extreme Point Oracle Dan Garber, Noam Wolf

From Local Pseudorandom Generators to Hardness of Learning Amit Daniely, Gal Vardi

Functions with Average Smoothness: Structure, Algorithms, and Learning Yair Ashlagi, Lee-Ad Gottlieb, Aryeh Kontorovich

Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora’s Problem Chenghao Guo, Zhiyi Huang, Zhihao Gavin Tang, Xinzhi Zhang

Group Testing and Local Search: Is There a Computational-Statistical Gap? Fotis Iliopoulos, Ilias Zadik

Hypothesis Testing with Low-Degree Polynomials in the Morris Class of Exponential Families Dmitriy Kunisky

Implicit Regularization in ReLU Networks with the Square Loss Gal Vardi, Ohad Shamir

Impossibility of Partial Recovery in the Graph Alignment Problem Luca Ganassali, Laurent Massoulie, Marc Lelarge

Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications Liyu Chen, Haipeng Luo, Chen-Yu Wei

Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov Noise Chicheng Zhang, Yinan Li

Improved Analysis of the Tsallis-INF Algorithm in Stochastically Constrained Adversarial Bandits and Stochastic Bandits with Adversarial Corruptions Saeed Masoudian, Yevgeny Seldin

Improved Regret for Zeroth-Order Stochastic Convex Bandits Tor Lattimore, Andras Gyorgy

Information-Theoretic Generalization Bounds for Stochastic Gradient Descent Gergely Neu, Gintare Karolina Dziugaite, Mahdi Haghifam, Daniel M. Roy

Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective Dylan Foster, Alexander Rakhlin, David Simchi-Levi, Yunzong Xu

Is Reinforcement Learning More Difficult than Bandits? a Near-Optimal Algorithm Escaping the Curse of Horizon Zihan Zhang, Xiangyang Ji, Simon Du

It Was “all” for “nothing”: Sharp Phase Transitions for Noiseless Discrete Channels Jonathan Niles-Weed, Ilias Zadik

Johnson-Lindenstrauss Transforms with Best Confidence Maciej Skorski

Kernel Thinning Raaz Dwivedi, Lester Mackey

Last-Iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-Horizon Competitive Markov Games Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang, Haipeng Luo

Lazy OCO: Online Convex Optimization on a Switching Budget Uri Sherman, Tomer Koren

Learning and Testing Junta Distributions with Sub Cube Conditioning Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten

Learning from Censored and Dependent Data: The Case of Linear Dynamics Orestis Plevrakis

Learning in Matrix Games Can Be Arbitrarily Complex Gabriel P. Andrade, Rafael Frongillo, Georgios Piliouras

Learning Sparse Mixtures of Permutations from Noisy Information Anindya De, Ryan O’Donnell, Rocco Servedio

Learning to Sample from Censored Markov Random Fields Ankur Moitra, Elchanan Mossel, Colin P Sandon

Learning to Stop with Surprisingly Few Samples Daniel Russo, Assaf Zeevi, Tianyi Zhang

Learning with Invariances in Random Features and Kernel Models Song Mei, Theodor Misiakiewicz, Andrea Montanari

Machine Unlearning via Algorithmic Stability Enayat Ullah, Tung Mai, Anup Rao, Ryan A. Rossi, Raman Arora

Majorizing Measures, Sequential Complexities, and Online Learning Adam Block, Yuval Dagan, Alexander Rakhlin

Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition Liyu Chen, Haipeng Luo, Chen-Yu Wei

Mirror Descent and the Information Ratio Tor Lattimore, Andras Gyorgy

Modeling from Features: A Mean-Field Framework for Over-Parameterized Deep Neural Networks Cong Fang, Jason Lee, Pengkun Yang, Tong Zhang

Moment Multicalibration for Uncertainty Estimation Christopher Jung, Changhwa Lee, Mallesh Pai, Aaron Roth, Rakesh Vohra

Multiplayer Bandit Learning, from Competition to Cooperation Simina Branzei, Yuval Peres

Near Optimal Distributed Learning of Halfspaces with Two Parties Mark Braverman, Gillat Kol, Shay Moran, Raghuvansh R. Saxena

Near-Optimal Entrywise Sampling of Numerically Sparse Matrices Vladimir Braverman, Robert Krauthgamer, Aditya R. Krishnan, Shay Sapir

Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes Dongruo Zhou, Quanquan Gu, Csaba Szepesvari

Non-Asymptotic Approximations of Neural Networks by Gaussian Processes Ronen Eldan, Dan Mikulincer, Tselil Schramm

Non-Euclidean Differentially Private Stochastic Convex Optimization Raef Bassily, Cristobal Guzman, Anupama Nandi

Non-Stationary Reinforcement Learning Without Prior Knowledge: An Optimal Black-Box Approach Chen-Yu Wei, Haipeng Luo

On Avoiding the Union Bound When Answering Multiple Differentially Private Queries Badih Ghazi, Ravi Kumar, Pasin Manurangsi

On Empirical Bayes Variational Autoencoder: An Excess Risk Bound Rong Tang, Yun Yang

On Query-Efficient Planning in MDPs Under Linear Realizability of the Optimal State-Value Function Gellert Weisz, Philip Amortila, Barnabás Janzer, Yasin Abbasi-Yadkori, Nan Jiang, Csaba Szepesvari

On the Approximation Power of Two-Layer Networks of Random ReLUs Daniel Hsu, Clayton H Sanford, Rocco Servedio, Emmanouil Vasileios Vlatakis-Gkaragkounis

On the Convergence of Langevin Monte Carlo: The Interplay Between Tail Growth and Smoothness Murat A Erdogdu, Rasa Hosseinzadeh

On the Minimal Error of Empirical Risk Minimization Gil Kur, Alexander Rakhlin

On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learning Alain Durmus, Eric Moulines, Alexey Naumov, Sergey Samsonov, Hoi-To Wai

Online Learning from Optimal Actions Omar Besbes, Yuri Fonseca, Ilan Lobel

Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games Steve Hanneke, Roi Livni, Shay Moran

Online Markov Decision Processes with Aggregate Bandit Feedback Alon Cohen, Haim Kaplan, Tomer Koren, Yishay Mansour

Open Problem: Are All VC-Classes CPAC Learnable? Sushant Agarwal, Nivasini Ananthakrishnan, Shai Ben-David, Tosca Lechner, Ruth Urner

Open Problem: Can Single-Shuffle SGD Be Better than Reshuffling SGD and GD? Chulhee Yun, Suvrit Sra, Ali Jadbabaie

Open Problem: Is There an Online Learning Algorithm That Learns Whenever Online Learning Is Possible? Steve Hanneke

Open Problem: Tight Online Confidence Intervals for RKHS Elements Sattar Vakili, Jonathan Scarlett, Tara Javidi

Optimal Dimension Dependence of the Metropolis-Adjusted Langevin Algorithm Sinho Chewi, Chen Lu, Kwangjun Ahn, Xiang Cheng, Thibaut Le Gouic, Philippe Rigollet

Optimal Dynamic Regret in Exp-Concave Online Learning Dheeraj Baby, Yu-Xiang Wang

Optimizing Optimizers: Regret-Optimal Gradient Descent Algorithms Philippe Casgrain, Anastasis Kratsios

Outlier-Robust Learning of Ising Models Under Dobrushin’s Condition Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart, Yuxin Sun

PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast Rate Bounds That Handle General VC Classes Peter Grunwald, Thomas Steinke, Lydia Zakynthinou

Parameter-Free Multi-Armed Bandit Algorithms with Hybrid Data-Dependent Regret Bounds Shinji Ito

Projected Stochastic Gradient Langevin Algorithms for Constrained Sampling and Non-Convex Learning Andrew Lamperski

Provable Memorization via Deep Neural Networks Using Sub-Linear Parameters Sejun Park, Jaeho Lee, Chulhee Yun, Jinwoo Shin

Quantifying Variational Approximation for Log-Partition Function Romain Cosson, Devavrat Shah

Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence Xue Chen, Michal Derezinski

Random Coordinate Langevin Monte Carlo Zhiyan Ding, Qin Li, Jianfeng Lu, Stephen J Wright

Random Graph Matching with Improved Noise Robustness Cheng Mao, Mark Rudelson, Konstantin Tikhomirov

Rank-One Matrix Estimation: Analytic Time Evolution of Gradient Descent Dynamics Antoine Bodin, Nicolas Macris

Reconstructing Weighted Voting Schemes from Partial Information About Their Power Indices Huck Bennett, Anindya De, Rocco Servedio, Emmanouil Vasileios Vlatakis-Gkaragkounis

Reduced-Rank Regression with Operator Norm Error Praneeth Kacham, David Woodruff

Regret Minimization in Heavy-Tailed Bandits Shubhada Agrawal, Sandeep K. Juneja, Wouter M. Koolen

Robust Learning Under Clean-Label Attack Avrim Blum, Steve Hanneke, Jian Qian, Han Shao

Robust Online Convex Optimization in the Presence of Outliers Tim van Erven, Sarah Sachs, Wouter M Koolen, Wojciech Kotlowski

Sequential Prediction Under Log-Loss and Misspecification Meir Feder, Yury Polyanskiy

SGD Generalizes Better than GD (And Regularization Doesn’t Help) Idan Amir, Tomer Koren, Roi Livni

SGD in the Large: Average-Case Analysis, Asymptotics, and Stepsize Criticality Courtney Paquette, Kiwon Lee, Fabian Pedregosa, Elliot Paquette

Shape Matters: Understanding the Implicit Bias of the Noise Covariance Jeff Z. HaoChen, Colin Wei, Jason Lee, Tengyu Ma

Size and Depth Separation in Approximating Benign Functions with Neural Networks Gal Vardi, Daniel Reichman, Toniann Pitassi, Ohad Shamir

SoftMax Policy Gradient Methods Can Take Exponential Time to Converge Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, Yuxin Chen

Source Identification for Mixtures of Product Distributions Spencer Gordon, Bijan H Mazaheri, Yuval Rabani, Leonard Schulman

Sparse Sketches with Small Inversion Bias Michal Derezinski, Zhenyu Liao, Edgar Dobriban, Michael Mahoney

Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs Afonso S. Bandeira, Jess Banks, Dmitriy Kunisky, Christopher Moore, Alex Wein

Statistical Query Algorithms and Low Degree Tests Are Almost Equivalent Matthew S Brennan, Guy Bresler, Sam Hopkins, Jerry Li, Tselil Schramm

Stochastic Approximation for Online Tensorial Independent Component Analysis Chris Junchi Li, Michael Jordan

Stochastic Block Model Entropy and Broadcasting on Trees with Survey Emmanuel Abbe, Elisabetta Cornacchia, Yuzhou Gu, Yury Polyanskiy

Streaming K-PCA: Efficient Guarantees for Oja’s Algorithm, Beyond Rank-One Updates De Huang, Jonathan Niles-Weed, Rachel Ward

Structured Logconcave Sampling with a Restricted Gaussian Oracle Yin Tat Lee, Ruoqi Shen, Kevin Tian

Survival of the Strictest: Stable and Unstable Equilibria Under Regularized Learning with Partial Information Angeliki Giannou, Emmanouil Vasileios Vlatakis-Gkaragkounis, Panayotis Mertikopoulos

The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford

The Connection Between Approximation, Depth Separation and Learnability in Neural Networks Eran Malach, Gilad Yehudai, Shai Shalev-Schwartz, Ohad Shamir

The Effects of Mild Over-Parameterization on the Optimization Landscape of Shallow ReLU Neural Networks Itay M Safran, Gilad Yehudai, Ohad Shamir

The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalities Waïss Azizian, Franck Iutzeler, Jérôme Malick, Panayotis Mertikopoulos

The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication Blake E Woodworth, Brian Bullins, Ohad Shamir, Nathan Srebro

The Optimality of Polynomial Regression for Agnostic Learning Under Gaussian Marginals in the SQ Model Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis

The Sample Complexity of Robust Covariance Testing Ilias Diakonikolas, Daniel M. Kane

The Sparse Vector Technique, Revisited Haim Kaplan, Yishay Mansour, Uri Stemmer

Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford

Towards a Dimension-Free Understanding of Adaptive Linear Control Juan C Perdomo, Max Simchowitz, Alekh Agarwal, Peter Bartlett

Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with a Faulty Oracle Pan Peng, Jiapeng Zhang

Weak Learning Convex Sets Under Normal Distributions Anindya De, Rocco Servedio

When Does Gradient Descent with Logistic Loss Interpolate Using Deep Networks with Smoothed ReLU Activations? Niladri S. Chatterji, Philip M. Long, Peter Bartlett