COLT 2022

163 papers

Tracking Most Significant Arm Switches in Bandits

Joe Suk, Samory Kpotufe

Label noise (stochastic) gradient descent implicitly solves the Lasso for quadratic parametrisation

Loucas Pillaud Vivien, Julien Reygner, Nicolas Flammarion

Accelerated SGD for Non-Strongly-Convex Least Squares

Aditya Varre, Nicolas Flammarion

Optimal and instance-dependent guarantees for Markovian linear stochastic approximation

Wenlong Mou, Ashwin Pananjady, Martin Wainwright, Peter Bartlett

The query complexity of sampling from strongly log-concave distributions in one dimension

Sinho Chewi, Patrik R Gerber, Chen Lu, Thibaut Le Gouic, Philippe Rigollet

Generalization Bounds for Data-Driven Numerical Linear Algebra

Peter Bartlett, Piotr Indyk, Tal Wagner

Towards Optimal Algorithms for Multi-Player Bandits without Collision Sensing Information

Wei Huang, Richard Combes, Cindy Trinh

Private Convex Optimization via Exponential Mechanism

Sivakanth Gopi, Yin Tat Lee, Daogao Liu

Derivatives and residual distribution of regularized M-estimators with application to adaptive tuning

Pierre C Bellec, Yiwei Shen

Gardner formula for Ising perceptron models at small densities

Erwin Bolthausen, Shuta Nakajima, Nike Sun, Changji Xu

Smoothed Online Learning is as Easy as Statistical Learning

Adam Block, Yuval Dagan, Noah Golowich, Alexander Rakhlin

Strong Gaussian Approximation for the Sum of Random Vectors

Nazar Buzun, Nikolay Shvetsov, Dmitry V. Dylov

Community Recovery in the Degree-Heterogeneous Stochastic Block Model

Vincent Cohen-Addad, Frederik Mallmann-Trenn, David Saulpic

Statistical Estimation and Online Inference via Local SGD

Xiang Li, Jiadong Liang, Xiangyu Chang, Zhihua Zhang

Adaptive Bandit Convex Optimization with Heterogeneous Curvature

Haipeng Luo, Mengxiao Zhang, Peng Zhao

Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini’s Regret

Tor Lattimore

An Efficient Minimax Optimal Estimator For Multivariate Convex Regression

Gil Kur, Eli Putterman

Approximate Cluster Recovery from Noisy Labels

Buddhima Gamlath, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson

A Sharp Memory-Regret Trade-off for Multi-Pass Streaming Bandits

Arpit Agarwal, Sanjeev Khanna, Prathamesh Patil

Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds

Shinji Ito, Taira Tsuchiya, Junya Honda

Dimension-free convergence rates for gradient Langevin dynamics in RKHS

Boris Muzellec, Kanji Sato, Mathurin Massias, Taiji Suzuki

The Role of Interactivity in Structured Estimation

Jayadev Acharya, Clement L. Canonne, Ziteng Sun, Himanshu Tyagi

Trace norm regularization for multi-task learning with scarce data

Etienne Boursier, Mikhail Konobeev, Nicolas Flammarion

Computational-Statistical Gap in Reinforcement Learning

Daniel Kane, Sihan Liu, Shachar Lovett, Gaurav Mahajan

Width is Less Important than Depth in ReLU Neural Networks

Gal Vardi, Gilad Yehudai, Ohad Shamir

Lattice-Based Methods Surpass Sum-of-Squares in Clustering

Ilias Zadik, Min Jae Song, Alexander S Wein, Joan Bruna

Differential privacy and robust statistics in high dimensions

Xiyang Liu, Weihao Kong, Sewoong Oh

(Nearly) Optimal Private Linear Regression for Sub-Gaussian Data via Adaptive Clipping

Prateek Varshney, Abhradeep Thakurta, Prateek Jain

Universal Online Learning: an Optimistically Universal Learning Rule

Moise Blanchard

Private and polynomial time algorithms for learning Gaussians and beyond

Hassan Ashtiani, Christopher Liaw

Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise

Rajai Nasser, Stefan Tiegel

Policy Optimization for Stochastic Shortest Path

Liyu Chen, Haipeng Luo, Aviv Rosenberg

ROOT-SGD: Sharp Nonasymptotics and Asymptotic Efficiency in a Single Algorithm

Chris Junchi Li, Wenlong Mou, Martin Wainwright, Michael Jordan

Chasing Convex Bodies and Functions with Black-Box Advice

Nicolas Christianson, Tinashe Handina, Adam Wierman

Monotone Learning

Olivier J Bousquet, Amit Daniely, Haim Kaplan, Yishay Mansour, Shay Moran

Self-Consistency of the Fokker Planck Equation

Zebang Shen, Zhenfu Wang, Satyen Kale, Alejandro Ribeiro, Amin Karbasi

Stochastic Variance Reduction for Variational Inequality Methods

Ahmet Alacaoglu, Yura Malitsky

Private Robust Estimation by Stabilizing Convex Relaxations

Pravesh Kothari, Pasin Manurangsi, Ameya Velingker

Rate of Convergence of Polynomial Networks to Gaussian Processes

Adam Klukowski

Learning with metric losses

Dan Tsir Cohen, Aryeh Kontorovich

A bounded-noise mechanism for differential privacy

Yuval Dagan, Gil Kur

The Price of Tolerance in Distribution Testing

Clément L Canonne, Ayush Jain, Gautam Kamath, Jerry Li

A Private and Computationally-Efficient Estimator for Unbounded Gaussians

Gautam Kamath, Argyris Mouzakis, Vikrant Singhal, Thomas Steinke, Jonathan Ullman

Multi-Agent Learning for Iterative Dominance Elimination: Formal Barriers and New Algorithms

Jibang Wu, Haifeng Xu, Fan Yao

Negative curvature obstructs acceleration for strongly geodesically convex optimization, even with exact first-order oracles

Christopher Criscitiello, Nicolas Boumal

Universal Online Learning with Bounded Loss: Reduction to Binary Classification

Moise Blanchard, Romain Cosson

The Implicit Bias of Benign Overfitting

Ohad Shamir

Depth and Feature Learning are Provably Beneficial for Neural Network Discriminators

Carles Domingo-Enrich

Learning Low Degree Hypergraphs

Eric Balkanski, Oussama Hanguir, Shatian Wang

Beyond No Regret: Instance-Dependent PAC Reinforcement Learning

Andrew J Wagenmaker, Max Simchowitz, Kevin Jamieson

Optimal Mean Estimation without a Variance

Yeshwanth Cherapanamjeri, Nilesh Tripuraneni, Peter Bartlett, Michael Jordan

The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance

Matthew Faw, Isidoros Tziotis, Constantine Caramanis, Aryan Mokhtari, Sanjay Shakkottai

Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals

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

On the Benefits of Large Learning Rates for Kernel Methods

Gaspard Beugnot, Julien Mairal, Alessandro Rudi

Risk bounds for aggregated shallow neural networks using Gaussian priors

Laura Tinsi, Arnak Dalalyan

Pushing the Efficiency-Regret Pareto Frontier for Online Learning of Portfolios and Quantum States

Julian Zimmert, Naman Agarwal, Satyen Kale

Tight query complexity bounds for learning graph partitions

Xizhi Liu, Sayan Mukherjee

Robust Estimation for Random Graphs

Jayadev Acharya, Ayush Jain, Gautam Kamath, Ananda Theertha Suresh, Huanyu Zhang

Wasserstein GANs with Gradient Penalty Compute Congested Transport

Tristan Milne, Adrian I Nachman

Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variance

Nuri Mert Vural, Lu Yu, Krishna Balasubramanian, Stanislav Volgushev, Murat A Erdogdu

Optimization-Based Separations for Neural Networks

Itay Safran, Jason Lee

Analysis of Langevin Monte Carlo from Poincare to Log-Sobolev

Sinho Chewi, Murat A Erdogdu, Mufan Li, Ruoqi Shen, Shunshi Zhang

Conference on Learning Theory 2022: Preface

Po-ling Loh, Maxim Raginsky