COLT 2026

197 papers

Conference on Learning Theory 2026: Preface

Steve Hanneke, Tor Lattimore

Invited Open Problem: Does Differential Privacy Make PAC Learning Much Harder?

Kobbi Nissim, Uri Stemmer, Eliad Tsfadia

Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?

Ivan Lau, Jonathan Scarlett

Invited Open Problem: Is the Power of Deep Learning over Linear Models Inherently Distribution Dependent?

Vitaly Feldman, Pritish Kamath, Nathan Srebro

Invited Open Problem: Online Optimization of Piecewise-Lipschitz Functions with Applications to Data-Driven Algorithm Design

Maria-Florina Balcan, Wesley Pegden, Dravyansh Sharma

Open Problem: How much overparametrization is needed for ALS in tensor decomposition?

Dionysis Arvanitakis, Vaidehi Srinivas, Aravindan Vijayaraghavan

Gradient-Variation Regret Bounds for Unconstrained Online Learning

Yuheng Zhao, Andrew Jacobsen, Nicolò Cesa-bianchi, Peng Zhao

Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs

Guy Zamir, Matthew Zurek, Yudong Chen

Stable algorithms Lower Bounds for Estimation from MMSE Discontinuities: Extended Abstract

Xifan Yu, Ilias Zadik

Distribution-Free Sequential Prediction with Abstentions

Jialin Yu, Moise Blanchard

Learning Decision-Sufficient Representations for Linear Optimization

Yuhan Ye, Saurabh Amin, Asuman Ozdaglar

Tight Sample Complexity of Transformers

Chenxiao Yang, Nathan Srebro, Zhiyuan Li

Optimism Stabilizes Thompson Sampling for Adaptive Inference

Shunxing Yan, Han Zhong

Worst-case Error Bounds for Online Learning of Smooth Functions

Weian (Andrew) Xie

Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs (extended abstract)

Wu Tianhao, Matthew Zurek, Weina Wang, Qiaomin Xie

Risk Comparisons in Linear Regression: Implicit Regularization Dominates Explicit Regularization (Extended Abstract)

Jingfeng Wu, Peter L. Bartlett, Sham M. Kakade, Jason D. Lee, Bin Yu

Minimax Limits of k-Fold Cross-Validation via Majority

Ido Nachum, Ruediger Urbanke, Thomas Weinberger

Diffusion-Network Alignment: An Efficient Algorithm and Explicit Probability Bounds

Ziao Wang, Lei Ying

Accelerated Convex Optimization via Hamiltonian Dynamics with Deterministic Integration Time

Xiuyuan Wang, Vishwak Srinivasan, Qiang Fu, Siddharth Mitra, Ashia Wilson

A simple, optimal and efficient algorithm for online exp-concave optimization

Yi-Han Wang, Peng Zhao, Zhi-Hua Zhou

Almost sure null bankruptcy of testing-by-betting strategies

Hongjian Wang, Shubhada Agrawal, Aaditya Ramdas

Fast Score-Based Sampling via Log-Concave Reductions

Martin J. Wainwright

Learning with Simulators: No Regret in a Computationally Bounded World

Sasha Voitovych, Abhishek Shetty, Noah Golowich, Alexander Rakhlin

The Geometry of Efficient Nonconvex Sampling

Santosh S. Vempala, Andre Wibisono

On-Average Stability of Multipass Preconditioned SGD and Effective Dimension

Simon Vary, Tyler Farghly, Ilja Kuzborskij, Patrick Rebeschini

Spectral Recovery of a Planted Triangle-Dense Subgraph

Sam van der Poel, Cheng Mao, Benjamin McKenna

The Monotonicity of the Franz–Parisi Potential Is Equivalent to Low-Degree MMSE Lower Bounds: Extended Abstract

Konstantinos Tsirkas, Leda Wang, Ilias Zadik

Trajectory Data Suffices for Statistically Efficient Policy Evaluation in Fixed-Horizon Offline RL with Linear q^π-Realizability and Concentrability

Volodymyr Tkachuk, Csaba Szepesvári, Xiaoqi Tan

When Both Layers Learn: Training Dynamics of Representing Linear Models via ReLU Networks

Berk Tinaz, Changzhi Xie, Mahdi Soltanolkotabi

On the Asymptotics of Self-Supervised Pre-training: Two-Stage M-Estimation and Representation Symmetry

Mohammad Tinati, Stephen Tu

CONVERGENCE RATES FOR DISTRIBUTION MATCHING WITH SLICED OPTIMAL TRANSPORT

Gauthier Thurin, Claire Boyer, Kimia Nadjahi

Data Augmentation: A Fourier Analysis Perspective

Behrooz Tahmasebi, Melanie Weber, Stefanie Jegelka

Truly Adapting to Adversarial Constraints in Constrained MABs

Francesco Emanuele Stradi, Kalana Kalupahana, Matteo Castiglioni, Alberto Marchesi, Nicola Gatti

Privately Estimating Black-Box Statistics

Günter Steinke, Thomas Steinke

Revisiting the (Sub)Optimality of Best-of-N for Inference-Time Alignment

Ved Sriraman, Adam Block

Efficient Learning and Symmetry Discovery under Exact Invariances

Ashkan Soleymani, Behrooz Tahmasebi, Patrick Jaillet, Stefanie Jegelka

Finite Sample Bounds for Learning with Score Matching

Devin Smedira, Abhijith Jayakumar, Sidhant Misra, Marc Vuffray, Andrey Y. Lokhov

Testing for a Hidden Geometry in Random Graphs

Amit Silber, Mor Oren-Loberman, Wasim Huleihel

Optimal Sample Complexity Lower Bounds on Conditional Independence Testing

Jan Seyfried, Neelkanth Mishra, Sayantan Sen, Marco Tomamichel

The Hidden Cost of Approximation in Online Mirror Descent

Ofir Schlisselberg, Uri Sherman, Tomer Koren, Yishay Mansour

Convergence of Continual Learning in Homogeneous Deep Networks

Matan Schliserman, Gon Buzaglo, Itay Evron, Daniel Soudry

A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theory

Itay Safran

Private Linear Regression via a Down-Sensitivity to Privacy Reduction

Ittai Rubinstein, Chris Ge, Samuel B. Hopkins

Model Agreement via Anchoring

Eric Eaton, Surbhi Goel, Marcel Hussing, Michael Kearns, Aaron Roth

Continuous time policy evaluation is easier with noisy dynamics

Samuel Robertson, Thomas Newton, Csaba Szepesvári

Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chaining

Yunwei Ren, Yatin Dandi, Florent Krzakala, Jason D. Lee

Learning to Reason with Curriculum I: Provable Benefits of Autocurriculum

Nived Rajaraman, Audrey Huang, Miro Dudik, Rob Schapire, Dylan Foster

Near-Optimal Regret for Distributed Adversarial Bandits: A Black-Box Approach

Hao Qiu, Mengxiao Zhang, Nicolò Cesa-bianchi

Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Bandits

Hao Qin, Chicheng Zhang

Deep Q-Learning on Hölder Spaces

Qian Qi

Boosting with List-Decodable Codes

Addison Prairie, Li-Yang Tan

How Many Features Can a Language Model Store Under the Linear Representation Hypothesis?

Nikhil Garg, Jon Kleinberg, Kenny Peng

An Exponential Lower Bound for Spectral Density Estimation on Unweighted Graphs

Pan Peng, Yuyang Wang, Joy Qiping Yang, Yichun Yang

Graph neural networks extrapolate out-of-distribution for shortest paths

Robert R. Nerem, Samantha Chen, Sanjoy Dasgupta, Yusu Wang

Optimal Neural Network Approximation of Smooth Compositional Functions on Sets with Low Intrinsic Dimension

Thomas Nagler, Sophie Langer

On the Stability of Nonlinear Dynamics in GD and SGD: Beyond Quadratic Potentials

Rotem Mulayoff, Sebastian U. Stich

Steering diffusion models with quadratic rewards: a fine-grained analysis

Ankur Moitra, Andrej Risteski, Dhruv Rohatgi

On the implicit regularization of Langevin dynamics with projected noise

Govind Menon, Austin Stromme, Adrien Vacher

On the Gradient Complexity of Private Optimization with Private Oracles

Michael Menart, Aleksandar Nikolov

Differentially Private Language Generation and Identification in the Limit (Extended Abstract)

Anay Mehrotra, Grigoris Velegkas, Xifan Yu, Felix Zhou

Language Generation with Infinite Contamination

Anay Mehrotra, Grigoris Velegkas, Xifan Yu, Felix Zhou

On The Complexity of Best-Arm Identification in Non-Stationary Linear Bandits

Leo Maynard-Zhang, Zhihan Xiong, Kevin Jamieson, Maryam Fazel

Phase Transition in Convex Relaxations for Graph Alignment

Laurent Massoulié, Sushil Mahavir Varma, Louis Vassaux, Irène Waldspurger

Online Market Making and the Value of Observing the Order Book

Davide Maran, Marcello Restelli

On the Power of Adaptivity for ε-Best Arm Identification in Linear Bandits

Arnab Maiti, Yunbei Xu, Kevin Jamieson

Polynomial-time sampling despite disorder chaos

Eric Ma, Tselil Schramm

Wedge Sampling: Efficient Tensor Completion with Nearly-Linear Sample Complexity

Hengrui Luo, Anna Ma, Ludovic Stephan, Yizhe Zhu

Random Reshuffling Dominates Stochastic Gradient Descent

Zijian Liu

Regret Minimization with Adaptive Opponents in Repeated Games

Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu, Kaiqing Zhang

Online Learning for Uninformed Markov Games: Empirical Nash-Value Regret and Non-Stationarity Adaptation

Junyan Liu, Haipeng Luo, Zihan Zhang, Lillian J. Ratliff

Fast algorithms for learning a Gaussian under halfspace truncation with optimal sample complexity

Haitong Liu, Deepak Narayanan Sridharan, David Steurer, Manuel Wiedmer

Optimal Learning Rate Schedules under Functional Scaling Laws: Power Decay and Warmup–Stable–Decay (Extended Abstract)

Binghui Li, Zilin Wang, Fengling Chen, Shiyang Zhao, Ruiheng Zheng

Second-Order Bounds for $[0,1]$-Valued Regression via Betting Loss

Yinan Li, Sungjoon Yoon, Ethan Huang, Kwang-Sung Jun

Self-Concordant Perturbations for Linear Bandits

Lucas Lévy, Jean-Lou Valeau, Arya Akhavan, Patrick Rebeschini

A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak–Ruppert Averaging

Wei-Cheng Lee, Francesco Orabona

Blackwell Approachability and Gradient Equilibrium are Equivalent

Brian W. Lee, Nika Haghtalab, Michael I. Jordan, Ryan J. Tibshirani

Unified Framework of Distributional Regret in Multi-Armed Bandits and Reinforcement Learning

Harin Lee, Min-hwan Oh

Adaptive Learning Rates with Surrogate Probability for Follow-the-Perturbed-Leader

Jongyeong Lee, Junya Honda, Shinji Ito, Chansoo Kim

How Does the ReLU Activation Affect the Implicit Bias of Gradient Descent on High-dimensional Neural Network Regression?

Kuo-Wei Lai, Guanghui Wang, Molei Tao, Vidya Muthukumar

On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA

Syamantak Kumar, Shourya Pandey, Purnamrita Sarkar, Kevin Tian

A Distribution Testing Approach to Clustering Distributions

Gunjan Kumar, Yash Pote, Jonathan Scarlett

Clipping the Price of Adaptivity at the Tail

Itai Kreisler, Yair Carmon, Oliver Hinder

Ambiguous Online Learning

Vanessa Kosoy

Overlap Analysis of the Shortest Path Problem: Local Search, Landscapes, and Franz-Parisi Potential

Frederic Koehler, Joonhyung Shin

Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift

Shyamal Patel, Adam Klivans, Konstantinos Stavropoulos, Arsen Vasilyan

Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension

Adam Klivans, Konstantinos Stavropoulos, Arsen Vasilyan

Spectral Valleys and Sharp Failures in Greedy Determinant Maximization

Rajiv Khanna

Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning

David Kattermann, Lothar Sebastian Krapp

Fast, Parallel, Query-Efficient Binary Classification

Ishani Karmarkar, Liam O’Carroll, Aaron Sidford

Can SGD Select Good Fishermen? Local Convergence under Self-Selection Biases (Extended Abstract)

Alkis Kalavasis, Anay Mehrotra, Felix Zhou

Ripple Mechanisms for Discrete and Private Statistics

Matthew Joseph, Alex Kulesza, Yuyan Wang, Alexander Yu

Avoiding exp($k^*$) Scaling for Thompson Sampling in Combinatorial Semi-Bandits: From Multiple Seeds to a Single Seed

Tianyuan Jin, Heyang Zhao, Vincent Y. F. Tan, Quanquan Gu

Adaptive Matrix Online Learning through Smoothing with Guarantees for Nonsmooth Nonconvex Optimization

Ruichen Jiang, Zakaria Mhammedi, Mehryar Mohri, Aryan Mokhtari

Low-Degree Method Fails to Predict Robust Subspace Recovery

He Jia, Aravindan Vijayaraghavan

Sharp analysis of linear ensemble sampling

David Janz, Arya Akhavan, Csaba Szepesvári

On the Importance of Randomization in Discriminative Feature Feedback

Valentio Iverson, Tosca Lechner, Sivan Sabato

Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regret

Shinji Ito, Haipeng Luo, Arnab Maiti, Taira Tsuchiya, Yue Wu

On Randomized Algorithms in Online Strategic Classification

Chase Hutton, Adam Melrod, Han Shao

Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction

Lunjia Hu, Kevin Tian, Chutong Yang

Recovery of Planted Subgraphs

Wasim Huleihel