COLT 2021

141 papers

Open Problem: Can Single-Shuffle SGD be Better than Reshuffling SGD and GD?

Chulhee Yun, Suvrit Sra, Ali Jadbabaie

Open Problem: Tight Online Confidence Intervals for RKHS Elements

Sattar Vakili, Jonathan Scarlett, Tara Javidi

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

Steve Hanneke

Open Problem: Are all VC-classes CPAC learnable?

Sushant Agarwal, Nivasini Ananthakrishnan, Shai Ben-David, Tosca Lechner, Ruth Urner

Benign Overfitting of Constant-Stepsize SGD for Linear Regression

Difan Zou, Jingfeng Wu, Vladimir braverman, Quanquan Gu, Sham Kakade

A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Network

Mo Zhou, Rong Ge, Chi Jin

Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes

Dongruo Zhou, Quanquan Gu, Csaba Szepesvári

Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon

Zihan Zhang, Xiangyang Ji, Simon Du

Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov Noise

Chicheng Zhang, Yinan Li

Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation

Andrea Zanette, Ching-An Cheng, Alekh Agarwal

Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap

Haike Xu, Tengyu Ma, Simon Du

The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication

Blake E Woodworth, Brian Bullins, Ohad Shamir, Nathan Srebro

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

Non-stationary Reinforcement Learning without Prior Knowledge: an Optimal Black-box Approach

Chen-Yu Wei, Haipeng Luo

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

Implicit Regularization in ReLU Networks with the Square Loss

Gal Vardi, Ohad Shamir

Size and Depth Separation in Approximating Benign Functions with Neural Networks

Gal Vardi, Daniel Reichman, Toniann Pitassi, Ohad Shamir

Robust Online Convex Optimization in the Presence of Outliers

Tim van Erven, Sarah Sachs, Wouter M Koolen, Wojciech Kotlowski

A Dimension-free Computational Upper-bound for Smooth Optimal Transport Estimation

Adrien Vacher, Boris Muzellec, Alessandro Rudi, Francis Bach, Francois-Xavier Vialard

Machine Unlearning via Algorithmic Stability

Enayat Ullah, Tung Mai, Anup Rao, Ryan A. Rossi, Raman Arora

On Empirical Bayes Variational Autoencoder: An Excess Risk Bound

Rong Tang, Yun Yang

Efficient Bandit Convex Optimization: Beyond Linear Losses

Arun Sai Suggala, Pradeep Ravikumar, Praneeth Netrapalli

Johnson-Lindenstrauss Transforms with Best Confidence

Maciej Skorski

Lazy OCO: Online Convex Optimization on a Switching Budget

Uri Sherman, Tomer Koren

Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ball

Othmane Sebbouh, Robert M Gower, Aaron Defazio

The Effects of Mild Over-parameterization on the Optimization Landscape of Shallow ReLU Neural Networks

Itay M Safran, Gilad Yehudai, Ohad Shamir

Learning to Stop with Surprisingly Few Samples

Daniel Russo, Assaf Zeevi, Tianyi Zhang

Average-Case Communication Complexity of Statistical Problems

Cyrus Rashtchian, David Woodruff, Peng Ye, Hanlin Zhu

Exponential Weights Algorithms for Selective Learning

Mingda Qiao, Gregory Valiant

Exponential savings in agnostic active learning through abstention

Nikita Puchkin, Nikita Zhivotovskiy

Adaptive Discretization for Adversarial Lipschitz Bandits

Chara Podimata, Alex Slivkins

Learning from Censored and Dependent Data: The case of Linear Dynamics

Orestis Plevrakis

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

Provable Memorization via Deep Neural Networks using Sub-linear Parameters

Sejun Park, Jaeho Lee, Chulhee Yun, Jinwoo Shin

SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality

Courtney Paquette, Kiwon Lee, Fabian Pedregosa, Elliot Paquette

It was “all” for “nothing”: sharp phase transitions for noiseless discrete channels

Jonathan Niles-Weed, Ilias Zadik

Information-Theoretic Generalization Bounds for Stochastic Gradient Descent

Gergely Neu, Gintare Karolina Dziugaite, Mahdi Haghifam, Daniel M. Roy

A Theory of Heuristic Learnability

Mikito Nanashima

Adversarially Robust Learning with Unknown Perturbation Sets

Omar Montasser, Steve Hanneke, Nathan Srebro

Learning to Sample from Censored Markov Random Fields

Ankur Moitra, Elchanan Mossel, Colin P Sandon

Learning with invariances in random features and kernel models

Song Mei, Theodor Misiakiewicz, Andrea Montanari

Improved Analysis of the Tsallis-INF Algorithm in Stochastically Constrained Adversarial Bandits and Stochastic Bandits with Adversarial Corruptions

Saeed Masoudian, Yevgeny Seldin

Random Graph Matching with Improved Noise Robustness

Cheng Mao, Mark Rudelson, Konstantin Tikhomirov

The Connection Between Approximation, Depth Separation and Learnability in Neural Networks

Eran Malach, Gilad Yehudai, Shai Shalev-Schwartz, Ohad Shamir

Approximation Algorithms for Socially Fair Clustering

Yury Makarychev, Ali Vakilian

Corruption-robust exploration in episodic reinforcement learning

Thodoris Lykouris, Max Simchowitz, Alex Slivkins, Wen Sun

A Priori Generalization Analysis of the Deep Ritz Method for Solving High Dimensional Elliptic Partial Differential Equations

Yulong Lu, Jianfeng Lu, Min Wang

Exponentially Improved Dimensionality Reduction for l1: Subspace Embeddings and Independence Testing

Yi Li, David Woodruff, Taisuke Yasuda

Softmax Policy Gradient Methods Can Take Exponential Time to Converge

Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, Yuxin Chen

Stochastic Approximation for Online Tensorial Independent Component Analysis

Chris Junchi Li, Michael Jordan

Structured Logconcave Sampling with a Restricted Gaussian Oracle

Yin Tat Lee, Ruoqi Shen, Kevin Tian

Mirror Descent and the Information Ratio

Tor Lattimore, András György

Improved Regret for Zeroth-Order Stochastic Convex Bandits

Tor Lattimore, András György

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

Andrew Lamperski

**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 Szepesvári

On the Minimal Error of Empirical Risk Minimization

Gil Kur, Alexander Rakhlin

Hypothesis testing with low-degree polynomials in the Morris class of exponential families

Dmitriy Kunisky

Asymptotically Optimal Information-Directed Sampling

Johannes Kirschner, Tor Lattimore, Claire Vernade, Csaba Szepesvári

The Sparse Vector Technique, Revisited

Haim Kaplan, Yishay Mansour, Uri Stemmer

(Nearly) Dimension Independent Private ERM with AdaGrad Rates\{via Publicly Estimated Subspaces

Peter Kairouz, Monica Ribero Diaz, Keith Rush, Abhradeep Thakurta

Reduced-Rank Regression with Operator Norm Error

Praneeth Kacham, David Woodruff

Moment Multicalibration for Uncertainty Estimation

Christopher Jung, Changhwa Lee, Mallesh Pai, Aaron Roth, Rakesh Vohra

Double Explore-then-Commit: Asymptotic Optimality and Beyond

Tianyuan Jin, Pan Xu, Xiaokui Xiao, Quanquan Gu

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

Shinji Ito

Group testing and local search: is there a computational-statistical gap?

Fotis Iliopoulos, Ilias Zadik

Streaming k-PCA: Efficient guarantees for Oja’s algorithm, beyond rank-one updates

De Huang, Jonathan Niles-Weed, Rachel Ward

Fast Rates for the Regret of Offline Reinforcement Learning

Yichun Hu, Nathan Kallus, Masatoshi Uehara

On the Approximation Power of Two-Layer Networks of Random ReLUs

Daniel Hsu, Clayton H Sanford, Rocco Servedio, Emmanouil Vasileios Vlatakis-Gkaragkounis

Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium

Yu-Guan Hsieh, Kimon Antonakopoulos, Panayotis Mertikopoulos

Bounded Memory Active Learning through Enriched Queries

Max Hopkins, Daniel Kane, Shachar Lovett, Michal Moshkovitz

Shape Matters: Understanding the Implicit Bias of the Noise Covariance

Jeff Z. HaoChen, Colin Wei, Jason Lee, Tengyu Ma

Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games

Steve Hanneke, Roi Livni, Shay Moran

Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora’s Problem

Chenghao Guo, Zhiyi Huang, Zhihao Gavin Tang, Xinzhi Zhang

PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes

Peter Grünwald, Thomas Steinke, Lydia Zakynthinou

Source Identification for Mixtures of Product Distributions

Spencer Gordon, Bijan H Mazaheri, Yuval Rabani, Leonard Schulman

Differentially Private Nonparametric Regression Under a Growth Condition

Noah Golowich

Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information

Angeliki Giannou, Emmanouil Vasileios Vlatakis-Gkaragkounis, Panayotis Mertikopoulos

On Avoiding the Union Bound When Answering Multiple Differentially Private Queries

Badih Ghazi, Ravi Kumar, Pasin Manurangsi

Frank-Wolfe with a Nearest Extreme Point Oracle

Dan Garber, Noam Wolf

Impossibility of Partial Recovery in the Graph Alignment Problem

Luca Ganassali, Laurent Massoulié, marc lelarge

Efficient Algorithms for Learning from Coarse Labels

Dimitris Fotakis, Alkis Kalavasis, Vasilis Kontonis, Christos Tzamos

Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective

Dylan Foster, Alexander Rakhlin, David Simchi-Levi, Yunzong Xu

Convergence rates and approximation results for SGD and its continuous-time counterpart

Xavier Fontaine, Valentin De Bortoli, Alain Durmus

Sequential prediction under log-loss and misspecification

Meir Feder, Yury Polyanskiy

Modeling from Features: a Mean-field Framework for Over-parameterized Deep Neural Networks

Cong Fang, Jason Lee, Pengkun Yang, Tong Zhang

Concentration of Non-Isotropic Random Tensors with Applications to Learning and Empirical Risk Minimization

Mathieu Even, Laurent Massoulié

Adaptivity in Adaptive Submodularity

Hossein Esfandiari, Amin Karbasi, Vahab Mirrokni

On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness

Murat A Erdogdu, Rasa Hosseinzadeh

Non-asymptotic approximations of neural networks by Gaussian processes

Ronen Eldan, Dan Mikulincer, Tselil Schramm

Kernel Thinning

Raaz Dwivedi, Lester Mackey

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

Random Coordinate Langevin Monte Carlo

ZHIYAN DING, Qin Li, Jianfeng Lu, Stephen J Wright

Outlier-Robust Learning of Ising Models Under Dobrushin’s Condition

Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart, Yuxin Sun

Boosting in the Presence of Massart Noise

Ilias Diakonikolas, Russell Impagliazzo, Daniel M. Kane, Rex Lei, Jessica Sorrell

The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals in the SQ Model

Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis

Agnostic Proper Learning of Halfspaces under Gaussian Marginals

Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis

The Sample Complexity of Robust Covariance Testing

Ilias Diakonikolas, Daniel M. Kane

Sparse sketches with small inversion bias

Michal Derezinski, Zhenyu Liao, Edgar Dobriban, Michael Mahoney

Learning sparse mixtures of permutations from noisy information

Anindya De, Ryan O’Donnell, Rocco Servedio