COLT 2025

182 papers

Open Problem: Regret Minimization in Heavy-Tailed Bandits with Unknown Distributional Parameters

Gianmarco Genalti, Alberto Maria Metelli

Open Problem: Optimal Instance-Dependent Sample Complexity for finding Nash Equilibrium in Two Player Zero-Sum Matrix games

Arnab Maiti

Open Problem: Data Selection for Regression Tasks

Steve Hanneke, Shay Moran, Alexander Shlimovich, Amir Yehudayoff

Open Problem: Structure-Agnostic Minimax Risk for Partial Linear Model

Yihong Gu

Open Problem: Fixed-Parameter Tractability of Zonotope Problems

Vincent Froese, Moritz Grillo, Christoph Hertrich, Martin Skutella

Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RL

Matthew Zurek, Yudong Chen

Quantifying Overfitting along the Regularization Path for Two-Part-Code MDL in Supervised Classification

Xiaohan Zhu, Nathan Srebro

The Adaptive Complexity of Finding a Stationary Point

Zhou Huanjian, Han Andi, Takeda Akiko, Sugiyama Masashi

Towards Fundamental Limits for Active Multi-distribution Learning

Chicheng Zhang, Yihan Zhou

Linear Bandits on Ellipsoids: Minimax Optimal Algorithms

Raymond Zhang, Hadiji Hédi, Combes Richard

Fast and Multiphase Rates for Nearest Neighbor Classifiers

Pengkun Yang, Jingzhao Zhang

Anytime Acceleration of Gradient Descent

Zihan Zhang, Jason Lee, Simon Du, Yuxin Chen

Robustly Learning Monotone Generalized Linear Models via Data Augmentation

Nikos Zarifis, Puqian Wang, Ilias Diakonikolas, Jelena Diakonikolas

Improved Algorithms for Effective Resistance Computation on Graphs

Yang Yichun, Li Rong-Hua, Liao Meihao, Wang Guoren

Generalization error bound for denoising score matching under relaxed manifold assumption

Konstantin Yakovlev, Nikita Puchkin

Fundamental Limits of Matrix Sensing: Exact Asymptotics, Universality, and Applications

Yizhou Xu, Antoine Maillard, Lenka Zdeborová, Florent Krzakala

Taking a Big Step: Large Learning Rates in Denoising Score Matching Prevent Memorization

Yu-Han Wu, Pierre Marion, Gérard Biau, Claire Boyer

Mixing Time of the Proximal Sampler in Relative Fisher Information via Strong Data Processing Inequality (Extended Abstract)

Andre Wibisono

Time-Uniform Self-Normalized Concentration for Vector-Valued Processes (Extended Abstract)

Justin Whitehouse, Zhiwei Steven Wu, Aaditya Ramdas

Orthogonal Causal Calibration (Extended Abstract)

Justin Whitehouse, Christopher Jung, Vasilis Syrgkanis, Bryan Wilder, Zhiwei Steven Wu

Learning Compositional Functions with Transformers from Easy-to-Hard Data

Zixuan Wang, Eshaan Nichani, Alberto Bietti, Alex Damian, Daniel Hsu

Black-Box Reductions for Decentralized Online Convex Optimization in Changing Environments

Yuanyu Wan

Learning shallow quantum circuits with many-qubit gates

Francisca Vasconcelos, Hsin-Yuan Huang

Corrupted Learning Dynamics in Games

Taira Tsuchiya, Shinji Ito, Haipeng Luo

Optimal Scheduling of Dynamic Transport

Panos Tsimpos, Ren Zhi, Jakob Zech, Youssef Marzouk

Beyond propagation of chaos: A stochastic algorithm for mean field optimization

Chandan Tankala, Dheeraj Nagaraj, Anant Raj

Optimal Online Bookmaking for Any Number of Outcomes

Hadar Tal, Oron Sabag

Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexity Extended Abstract

Dominik Stöger, Yizhe Zhu

Community detection with the Bethe-Hessian

Ludovic Stephan, Yizhe Zhu

The Pitfalls of Imitation Learning when Actions are Continuous

Max Simchowitz, Daniel Pfrommer, Ali Jadbabaie

Testing (Conditional) Mutual Information - Extended Abstract

Jan Seyfried, Sayantan Sen, Marco Tomamichel

Testing Juntas and Junta Subclasses with Relative Error

Xi Chen, William Pires, Toniann Pitassi, R. A. Servedio

Private List Learnability vs. Online List Learnability

Steve Hanneke, Shay Moran, Hilla Schefler, Iska Tsubari

The late-stage training dynamics of (stochastic) subgradient descent on homogeneous neural networks

Sholom Schechtman, Nicolas Schreuder

Depth Separations in Neural Networks: Separating the Dimension from the Accuracy

Itay Safran, Daniel Reichman, Paul Valiant

New Lower Bounds for Non-Convex Stochastic Optimization through Divergence Decomposition

El Mehdi Saad, Wei-Cheng Lee, Francesco Orabona

Improved Offline Contextual Bandits with Second-Order Bounds: Betting and Freezing

J. Jon Ryu, Jeongyeol Kwon, Benjamin Koppe, Kwang-Sung Jun

Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs

Alexander Ryabchenko, Idan Attias, Daniel M. Roy

Can a calibration metric be both testable and actionable?

Raphael Rossellini, Jake A. Soloff, Rina Foygel Barber, Zhimei Ren, Rebecca Willett

Necessary and Sufficient Oracles: Toward a Computational Taxonomy for Reinforcement Learning

Dhruv Rohatgi, Dylan J. Foster

Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification (extended abstract)

Dhruv Rohatgi, Adam Block, Audrey Huang, Akshay Krishnamurthy, Dylan J. Foster

Metric Clustering and Graph Optimization Problems using Weak Comparison Oracles

Rahul Raychaudhury, Wen-Zhi Li, Syamantak Das, Sainyam Galhotra, Stavros Sintos

Generation through the lens of learning theory

Vinod Raman, Jiaxun Li, Ambuj Tewari

Truthfulness of Decision-Theoretic Calibration Measures

Mingda Qiao, Eric Zhao

Linear Convergence of Diffusion Models Under the Manifold Hypothesis

Peter Potaptchik, Iskander Azangulov, George Deligiannidis

Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimes

Victor S. Portella, Nicholas J. A. Harvey

Optimal Robust Estimation under Local and Global Corruptions: Stronger Adversary and Smaller Error

Thanasis Pittas, Ankit Pensia

Recovering Labels from Crowdsourced Data: an Optimal and Polynomial-Time Method

Emmanuel Pilliat

Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts

Pan Peng, Hangyu Xu

Learning Algorithms in the Limit

Hristo Papazov, Nicolas Flammarion

On the Hardness of Bandit Learning

Nataly Brukhim, Aldo Pacchiano, Miroslav Dudík, Robert Schapire

Data-dependent Bounds with T-Optimal Best-of-Both-Worlds Guarantees in Multi-Armed Bandits using Stability-Penalty Matching

Quan Nguyen, Shinji Ito, Junpei Komiyama, Mehta Nishant

Improved algorithms for learning quantum Hamiltonians, via flat polynomials

Shyam Narayanan

Estimating stationary mass, frequency by frequency

Milind Nakul, Vidya Muthukumar, Ashwin Pananjady

Sharper Bounds for Chebyshev Moment Matching, with Applications

Cameron Musco, Christopher Musco, Lucas Rosenblatt, Apoorv Vikram Singh

Are all models wrong? Fundamental limits in distribution-free empirical model falsification

Manuel M. Müller, Yuetian Luo, Rina Foygel Barber

Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learning

Antoine Moulin, Gergely Neu, Luca Viano

Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks

Omar Montasser, Abhishek Shetty, Nikita Zhivotovskiy

The Planted Spanning Tree Problems: Exact Overlap Characterization via Local Weak Convergence Extended Abstract

Mehrdad Moharrami, Cristopher Moore, Jiaming Xu

Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions

Zakaria Mhammedi

Online Convex Optimization with a Separation Oracle

Zakaria Mhammedi

Learning sparse generalized linear models with binary outcomes via iterative hard thresholding

Namiko Matsumoto, Arya Mazumdar

Efficient Near-Optimal Algorithm for Online Shortest Paths in Directed Acyclic Graphs with Bandit Feedback Against Adaptive Adversaries

Arnab Maiti, Zhiyuan Fan, Kevin Jamieson, Lillian J. Ratliff, Gabriele Farina

Identifiability and Estimation in High-Dimensional Nonparametric Latent Structure Models

Yichen Lyu, Pengkun Yang

Sample Efficient Omniprediction and Downstream Swap Regret for Non-Linear Losses

Jiuyao Lu, Aaron Roth, Mirah Shi

Sparsity-Based Interpolation of External, Internal and Swap Regret

Zhou Lu, Y Jennifer Sun, Zhiyu Zhang

Robust Algorithms for Recovering Planted r-Colorable Graphs

Anand Louis, Rameesh Paul, Prasad Raghavendra

Decision Making in Hybrid Environments: A Model Aggregation Approach

Haolin Liu, Chen-Yu Wei, Zimmert Julian

Characterizing Dependence of Samples along the Langevin Dynamics and Algorithms via Contraction of $Φ$-Mutual Information (Extended Abstract)

Jiaming Liang, Siddharth Mitra, Andre Wibisono

Low-dimensional adaptation of diffusion models: Convergence in total variation (extended abstract)

Jiadong Liang, Zhihan Huang, Yuxin Chen

Private Realizable-to-Agnostic Transformation with Near-Optimal Sample Complexity

Bo Li, Wei Wang, Peng Ye

Multi-Pass Memory Lower Bounds for Learning Problems

Qian Li, Shuo Wang, Jiapeng Zhang

A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions

Junfan Li, Shizhong Liao, Zenglin Xu, Liqiang Nie

Some easy optimization problems have the overlap-gap property

Shuangping Li, Tselil Schramm

Robust random graph matching in Gaussian models via vector approximate message passing

Zhangsong Li

The Fundamental Limits of Recovering Planted Subgraphs (extended abstract)

Daniel Z. Lee, Francisco Pernice, Amit Rajaraman, Ilias Zadik

Fast and Furious Symmetric Learning in Zero-Sum Games: Gradient Descent as Fictitious Play

John Lazarsfeld, Georgios Piliouras, Ryann Sim, Andre Wibisono

Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models

Dmitriy Kunisky

A Gap Between the Gaussian RKHS and Neural Networks: An Infinite-Center Asymptotic Analysis

Akash Kumar, Rahul Parhi, Mikhail Belkin

Spike-and-Slab Posterior Sampling in High Dimensions

Symantak Kumar, Purnamrita Sarkar, Kevin Tian, Yusong Zhu

The Role of Environment Access in Agnostic Reinforcement Learning (Extended Abstract)

Akshay Krishnamurthy, Gene Li, Ayush Sekhari

Spectral Estimators for Multi-Index Models: Precise Asymptotics and Optimal Weak Recovery

Filip Kovačević, Zhang Yihan, Marco Mondelli

The Oracle Complexity of Simplex-based Matrix Games: Linear Separability and Nash Equilibria

Guy Kornowski, Ohad Shamir

Efficiently learning and sampling multimodal distributions with data-based initialization

Frederic Koehler, Holden Lee, Thuy-Duong Vuong

Learning Constant-Depth Circuits in Malicious Noise Models

Adam Klivans, Konstantinos Stavropoulos, Arsen Vasilyan

Experimental Design for Semiparametric Bandits

Seok-Jin Kim, Gi-Soo Kim, Min-hwan Oh

The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraints

Hadi Kazemi, Ankit Pensia, Jog Varun

A Theory of Learning with Autoregressive Chain of Thought

Nirmit Joshi, Gal Vardi, Adam Block, Surbhi Goel, Zhiyuan Li

Structure-agnostic Optimality of Doubly Robust Learning for Treatment Effect Estimation (Extended Abstract)

Jikai Jin, Vasilis Syrgkanis

Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization

Ruichen Jiang, Devyani Maladkar, Aryan Mokhtari

Online Covariance Estimation in Nonsmooth Stochastic Approximation

Liwei Jiang, Abhishek Roy, Krishnakumar Balasubramanian, Damek Davis, Dmitriy Drusvyatskiy

Regularized Dikin Walks for Sampling Truncated Logconcave Measures, Mixed Isoperimetry and Beyond Worst-Case Analysis

Minhui Jiang, Yuansi Chen

On the Minimax Regret of Sequential Probability Assignment via Square-Root Entropy

Zeyu Jia, Alexander Rakhlin, Yury Polyanskiy

Local Regularizers Are Not Transductive Learners

Sky Jafar, Julian Asilis, Shaddin Dughmi

Optimal Differentially Private Sampling of Unbounded Gaussians

Valentio Iverson, Gautam Kamath, Argyris Mouzakis

Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback

Shinji Ito, Haipeng Luo, Taira Tsuchiya, Yue Wu

Polynomial low degree hardness for Broadcasting on Trees (Extended Abstract)

Han Huang, Elchanan Mossel

Improved Margin Generalization Bounds for Voting Classifiers

Mikael Høgsgaard Møller, Kasper Green Larsen

Noisy Group Testing in the Linear Regime: Exact Thresholds and Efficient

Lukas Hintze, Lena Krieg, Olga Scheftelowitsch, Haodong Zhu

Learning DNF through Generalized Fourier Representations

Mohsen Heidari, Roni Khardon