COLT 2023

170 papers

SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics

Emmanuel Abbe, Enric Boix Adsera, Theodor Misiakiewicz

A Pretty Fast Algorithm for Adaptive Private Mean Estimation

Rohith Kuditipudi, John Duchi, Saminul Haque

Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling

Jason Altschuler, Kunal Talwar

Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap

Raef Bassily, Cristóbal Guzmán, Michael Menart

Detection-Recovery Gap for Planted Dense Cycles

Cheng Mao, Alexander S. Wein, Shenduo Zhang

Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Sampler

Sivakanth Gopi, Yin Tat Lee, Daogao Liu, Ruoqi Shen, Kevin Tian

Semi-Random Sparse Recovery in Nearly-Linear Time

Jonathan Kelner, Jerry Li, Allen X. Liu, Aaron Sidford, Kevin Tian

Allocating Divisible Resources on Arms with Unknown and Random Rewards

Wenhao Li, Ningyuan Chen

SQ Lower Bounds for Learning Mixtures of Separated and Bounded Covariance Gaussians

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

Minimax Instrumental Variable Regression and L_2 Convergence Guarantees without Identification or Closedness

Andrew Bennett, Nathan Kallus, Xiaojie Mao, Whitney Newey, Vasilis Syrgkanis

Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noise

Zijian Liu, Jiawei Zhang, Zhengyuan Zhou

Inference on Strongly Identified Functionals of Weakly Identified Functions

Andrew Bennett, Nathan Kallus, Xiaojie Mao, Whitney Newey, Vasilis Syrgkanis

Tighter PAC-Bayes Bounds Through Coin-Betting

Kyoungseok Jang, Kwang-Sung Jun, Ilja Kuzborskij, Francesco Orabona

Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise

Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane, Puqian Wang, Nikos Zarifis

Geodesically convex M-estimation in metric spaces

Victor-Emmanuel Brunel

Provable Benefits of Representational Transfer in Reinforcement Learning

Alekh Agarwal, Yuda Song, Wen Sun, Kaiwen Wang, Mengdi Wang

A Lower Bound for Linear and Kernel Regression with Adaptive Covariates

Tor Lattimore

A Second-Order Method for Stochastic Bandit Convex Optimisation

Tor Lattimore, András György

Learning Hidden Markov Models Using Conditional Samples

Gaurav Mahajan, Sham Kakade, Akshay Krishnamurthy, Cyril Zhang

Exploring Local Norms in Exp-concave Statistical Learning

Nikita Puchkin, Nikita Zhivotovskiy

Online Learning Guided Curvature Approximation: A Quasi-Newton Method with Global Non-Asymptotic Superlinear Convergence

Ruichen Jiang, Qiujiang Jin, Aryan Mokhtari

InfoNCE Loss Provably Learns Cluster-Preserving Representations

Advait Parulekar, Liam Collins, Karthikeyan Shanmugam, Aryan Mokhtari, Sanjay Shakkottai

List Online Classification

Shay Moran, Ohad Sharon, Iska Tsubari, Sivan Yosebashvili

Quantum Channel Certification with Incoherent Measurements

Omar Fawzi, Nicolas Flammarion, Aurélien Garivier, Aadil Oufkir

Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms

Osama A Hanna, Lin Yang, Christina Fragouli

Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling

Antonio Blanca, Zongchen Chen, Daniel Stefankovic, Eric Vigoda

Universality of Langevin Diffusion for Private Optimization, with Applications to Sampling from Rashomon Sets

Arun Ganesh, Abhradeep Thakurta, Jalaj Upadhyay

Learning and Testing Latent-Tree Ising Models Efficiently

Vardis Kandiros, Constantinos Daskalakis, Yuval Dagan, Davin Choo

Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making

Adam Block, Max Simchowitz, Alexander Rakhlin

Exponential Hardness of Reinforcement Learning with Linear Function Approximation

Sihan Liu, Gaurav Mahajan, Daniel Kane, Shachar Lovett, Gellert Weisz

Private Covariance Approximation and Eigenvalue-Gap Bounds for Complex Gaussian Perturbations

Oren Mangoubi, Nisheeth K. Vishnoi

Improved dimension dependence of a proximal algorithm for sampling

Jiaojiao Fan, Bo Yuan, Yongxin Chen

Instance-Optimality in Interactive Decision Making: Toward a Non-Asymptotic Theory

Andrew J. Wagenmaker, Dylan J. Foster

A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs

Dirk van der Hoeven, Lukas Zierahn, Tal Lancewicki, Aviv Rosenberg, Nicolò Cesa-bianchi

Projection-free Online Exp-concave Optimization

Dan Garber, Ben Kretzu

Orthogonal Directions Constrained Gradient Method: from non-linear equality constraints to Stiefel manifold

Sholom Schechtman, Daniil Tiapkin, Michael Muehlebach, Eric Moulines

From high-dimensional & mean-field dynamics to dimensionless ODEs: A unifying approach to SGD in two-layers networks

Luca Arnaboldi, Ludovic Stephan, Florent Krzakala, Bruno Loureiro

Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuron

Weihang Xu, Simon Du

On the Existence of a Complexity in Fixed Budget Bandit Identification

Rémy Degenne

Repeated Bilateral Trade Against a Smoothed Adversary

Nicolò Cesa-bianchi, Tommaso R. Cesari, Roberto Colomboni, Federico Fusco, Stefano Leonardi

On Testing and Learning Quantum Junta Channels

Zongbo Bao, Penghui Yao

VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation

Alekh Agarwal, Yujia Jin, Tong Zhang

Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression

Gabriel Arpino, Ramji Venkataramanan

Weak Recovery Threshold for the Hypergraph Stochastic Block Model

Yuzhou Gu, Yury Polyanskiy

Uniqueness of BP fixed point for the Potts model and applications to community detection

Yuzhou Gu, Yury Polyanskiy

Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension

Yuval Filmus, Steve Hanneke, Idan Mehalel, Shay Moran

Multitask Learning via Shared Features: Algorithms and Hardness

Konstantina Bairaktari, Guy Blanc, Li-Yang Tan, Jonathan Ullman, Lydia Zakynthinou

Non-asymptotic convergence bounds for Sinkhorn iterates and their gradients: a coupling approach.

Giacomo Greco, Maxence Noble, Giovanni Conforti, Alain Durmus

Local Glivenko-Cantelli

Doron Cohen, Aryeh Kontorovich

Improved Bounds for Multi-task Learning with Trace Norm Regularization

Weiwei Liu

Private Online Prediction from Experts: Separations and Faster Rates

Hilal Asi, Vitaly Feldman, Tomer Koren, Kunal Talwar

Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithm

Fang Kong, Canzhe Zhao, Shuai Li

Online Reinforcement Learning in Stochastic Continuous-Time Systems

Mohamad Kazem Shirani Faradonbeh, Mohamad Sadegh Shirani Faradonbeh

Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures

Rares-Darius Buhai, David Steurer

Proper Losses, Moduli of Convexity, and Surrogate Regret Bounds

Han Bao

Find a witness or shatter: the landscape of computable PAC learning.

Valentino Delle Rose, Alexander Kozachinskiy, Cristobal Rojas, Tomasz Steifer

Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix

Julia Gaudio, Nirmit Joshi

Bagging is an Optimal PAC Learner

Kasper Green Larsen

Bregman Deviations of Generic Exponential Families

Sayak Ray Chowdhury, Patrick Saux, Odalric Maillard, Aditya Gopalan

Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties

David Martínez-Rubio, Sebastian Pokutta

Online Learning in Dynamically Changing Environments

Changlong Wu, Ananth Grama, Wojciech Szpankowski

Online Learning and Solving Infinite Games with an ERM Oracle

Angelos Assos, Idan Attias, Yuval Dagan, Constantinos Daskalakis, Maxwell K. Fishelson

The Sample Complexity of Approximate Rejection Sampling With Applications to Smoothed Online Learning

Adam Block, Yury Polyanskiy

Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problems

Yunwen Lei

Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptions

Bohan Wang, Huishuai Zhang, Zhiming Ma, Wei Chen

Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD

Matthew Faw, Litu Rout, Constantine Caramanis, Sanjay Shakkottai

The One-Inclusion Graph Algorithm is not Always Optimal

Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, Nikita Zhivotovskiy

Improved Discretization Analysis for Underdamped Langevin Monte Carlo

Shunshi Zhang, Sinho Chewi, Mufan Li, Krishna Balasubramanian, Murat A. Erdogdu

Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincaré Inequality

Alireza Mousavi-Hosseini, Tyler K. Farghly, Ye He, Krishna Balasubramanian, Murat A. Erdogdu

Conference on Learning Theory 2023: Preface

Gergely Neu, Lorenzo Rosasco