AI conference papers

AI conference paper library

Search papers from 30+ top conferences, including NeurIPS, ICLR, ICML, CVPR, ACL and AAAI. Filter by keyword, then open any paper for its abstract, authors and links.

COLT 2026

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

Xifan Yu, Ilias Zadik

Recent works in average-case complexity have identified stable (noise-stable) algorithms as a central class. Specifically, in average-case optimization, the class is conjectured to capture the power of polynomial-time computation for many problems. This perspective has been supported by establishing variants of the Overlap Gap Property (OGP) phase transitions just below conjectured polynomial-time thresholds. Yet, it was recently challenged by Schramm and Li (2025), who showed that Shortest Path in random graphs exhibits the OGP—and hence all stable algorithms fail—despite being solvable in polynomial time. This counterexample has also been particularly curious as it appeared rather distinct from other classical “noiseless" counterexamples, such as solving random linear systems. By contrast, the power of stable methods in statistical estimation has remained unclear. A central difficulty is the absence of an OGP-type phenomenon that can uniformly exclude all stable methods. Instead, existing lower bounds largely focus on the related class of low-degree polynomials and are confined to restricted models, such as Gaussian additive models, reflecting the high technical difficulty of controlling the minimum mean-squared error (MMSE) of low-degree estimators. In this work, we show that for all statistical estimation problems, a natural MMSE instability (discontinuity) condition implies the failure of stable algorithms, serving as a version of OGP for estimation tasks. Using this criterion, we establish separations between stable and polynomial-time algorithms for the following MMSE-unstable tasks (i) Planted Shortest Path, where Dijkstra’s algorithm succeeds, (ii) random Parity Codes, where Gaussian elimination succeeds, and (iii) Gaussian Subset Sum, where lattice-based methods succeed. For all three, we further show that all low-degree polynomials are stable, yielding separations against low-degree methods and a new method to bound the low-degree MMSE. In particular, our technique highlights that MMSE instability is a common feature for Shortest Path and the noiseless Parity Codes and Gaussian subset sum. Last, we highlight that our work places rigorous algorithmic footing on the long-standing physics belief that first-order phase transitions—which in this setting translates to MMSE instability—impose fundamental limits on classes of efficient algorithms.

COLT 2026

Distribution-Free Sequential Prediction with Abstentions

Jialin Yu, Moise Blanchard

We study a sequential prediction problem in which an adversary is allowed to inject arbitrarily many adversarial instances in a stream of i.i.d. instances, but at each round, the learner may also abstain from making a prediction without incurring any penalty if the instance was indeed corrupted. This semi-adversarial setting naturally sits between the classical stochastic case with i.i.d. instances for which function classes with finite VC dimension are learnable; and the adversarial case with arbitrary instances, known to be significantly more restrictive. For this problem, Goel et al. (2023) showed that, if the learner knows the distribution μ of clean samples in advance, learning can be achieved for all VC classes without restrictions on adversary corruptions. This is, however, a strong assumption in both theory and practice: a natural question is whether similar learning guarantees can be achieved without prior distributional knowledge, as is standard in classical learning frameworks (e.g., PAC learning or asymptotic consistency) and other non-i.i.d. models (e.g., smoothed online learning). We therefore focus on the distribution-free setting where μ is unknown and propose an algorithm AbstainBoost based on a boosting procedure of weak learners, which guarantees sublinear error for general VC classes in distribution-free abstention learning for oblivious adversaries. These algorithms also enjoy similar guarantees for adaptive adversaries, for structured function classes including linear classifiers. These results are complemented with corresponding lower bounds, which reveal an interesting polynomial trade-off between misclassification error and number of erroneous abstentions.

COLT 2026

Learning Decision-Sufficient Representations for Linear Optimization

Yuhan Ye, Saurabh Amin, Asuman Ozdaglar

We study how to construct compressed datasets that suffice to recover optimal decisions in linear programs with unknown cost vector c lying in a prior set 𝒞. Recent work by Bennouna et al. (2025a) provides an exact geometric characterization of sufficient decision datasets (SDDs) via an intrinsic decision-relevant dimension d^⋆. However, their algorithm for constructing minimum-size SDDs requires solving mixed-integer programs. In this paper, we establish hardness results: computing d^⋆ is NP-hard and deciding whether a dataset is globally sufficient is coNP-hard, thereby resolving the open problem posed by Bennouna et al. (2026). To circumvent worst-case intractability, we introduce pointwise sufficiency, a relaxation that requires sufficiency for an individual cost vector. We provide a polynomial-time cutting-plane algorithm to construct pointwise-sufficient decision datasets under nondegeneracy. In a data-driven regime with i.i.d. costs, we propose a cumulative algorithm that aggregates decision-relevant directions across samples, yielding a stable compression scheme of size at most d^⋆. This leads to a distribution-free PAC guarantee: with high probability over the training sample, the pointwise sufficiency failure probability on a fresh draw is at most Õ(d^⋆/n), and this rate is tight up to logarithmic factors. Finally, we apply decision-sufficient representations to contextual linear optimization, obtaining compressed predictors with generalization bounds scaling as Õ(√(d^⋆/n)) rather than Õ(√(d/n)), where d is the ambient cost dimension.

COLT 2026

Tight Sample Complexity of Transformers

Chenxiao Yang, Nathan Srebro, Zhiyuan Li

We tightly characterize the VC dimension of depth-L Transformers with a total of W parameters, mapping an input sequence of length T to a single output, establishing an upper bound of O(L W log (T W)) and a nearly matching lower bound of Ω(L W log (T W / L)). We further tightly characterize the sample complexity of chain-of-thought learning using such a Transformer, showing teacher forcing (i.e. selecting a predictor consistent with the entire chain-of-thought on training data) learns with sample complexity O(L W log((T+T^') W)) and that any learning rule that uses chain-of-thought data requires at least Ω(L W log((T+T^') W / L)) examples, where T is the input length and T^' is the number of autoregressive steps.

COLT 2026

Optimism Stabilizes Thompson Sampling for Adaptive Inference

Shunxing Yan, Han Zhong

Thompson sampling (TS) is widely used for stochastic multi-armed bandits, yet its inferential behavior under adaptive data collection is subtle. Classical asymptotic theory for sample means can fail because arm-specific sample sizes are random, history-dependent, and coupled with the observed rewards through the action-selection rule. A useful sufficient condition for valid asymptotic inference is stability, which requires each arm’s pull count to concentrate around a deterministic scale. While stability is now understood for several UCB-type algorithms, vanilla TS can be unstable, leading to nonstandard asymptotics and potentially invalid Wald-type confidence intervals. We identify optimism as a general mechanism for stabilizing Thompson sampling. In the K-armed Gaussian bandit with any fixed K≥2, we study two optimistic TS variants. The first is TS with posterior variance inflation; the second keeps the posterior variance unchanged but adds an explicit optimism bonus to the posterior mean. For both variants, we prove stability: optimal arms asymptotically share the horizon uniformly, while each suboptimal arm is sampled on a sharp gap-dependent logarithmic scale. For variance-inflated TS, this resolves the open problem posed by Halder et al. (2025) by extending their two-armed stability theory to general K-armed bandits, including instances with multiple optimal arms. For the mean-bonus variant, our result shows that stability can also be achieved through a direct optimistic shift of the posterior center, without inflating the posterior variance. The main technical novelty lies in the treatment of variance-inflated TS with multiple optimal arms. In this regime, stability requires proving that the randomized competition among statistically indistinguishable optimal arms converges to a deterministic allocation. We isolate a limiting pure-noise competition and prove a negative-feedback property: over-sampled optimal arms become less likely to win future posterior draws, while under-sampled ones become more likely to be selected. This yields a contraction toward the uniform allocation over the optimal set. Concentration and rare-event estimates then control the perturbations caused by empirical-mean errors and occasional suboptimal selections. For the mean-bonus variant, we use a separate argument based on posterior-sampling concentration and UCB-type comparisons, since optimism enters through a deterministic shift of the posterior mean rather than through variance inflation. These stability results imply asymptotically valid adaptive inference. In particular, for either optimistic TS variant, the usual studentized sample mean is asymptotically standard normal, and standard Wald confidence intervals achieve the nominal coverage probability despite adaptive sampling. Thus, suitably implemented optimism stabilizes Thompson sampling and enables classical inference from adaptively collected bandit data, while incurring only a mild additional regret cost.

COLT 2026

Worst-case Error Bounds for Online Learning of Smooth Functions

Weian (Andrew) Xie

Online learning is a model of machine learning where the learner is trained on sequential feedback. We investigate worst-case error for the online learning of real functions that have certain smoothness constraints. Suppose that ℱ_q is the class of all absolutely continuous functions f: [0,1] →ℝ such that f’_q ≤ 1, and opt_p(ℱ_q) is the best possible upper bound on the sum of the p^th powers of absolute prediction errors for any number of trials guaranteed by any learner. We show that for any δ, ϵ∈ (0,1), opt_1+δ(ℱ_1+ϵ) = O(min(δ,ϵ)^-1). Combined with the previous results of Kimber and Long (1995) and Geneson and Zhou (2023), we achieve a complete characterization of the values of p, q ≥ 1 that result in opt_p(ℱ_q) being finite, a problem open for nearly 30 years. We study the learning scenarios of smooth functions that also belong to certain special families of functions, such as polynomials. We prove a conjecture by Geneson and Zhou (2023) that it is not any easier to learn a polynomial in ℱ_q than it is to learn any general function in ℱ_q. We also define a noisy model for the online learning of smooth functions, where the learner may receive incorrect feedback up to η≥ 1 times, denoting the worst-case error bound as opt^nf_p,η(ℱ_q). We prove that opt^nf_p,η(ℱ_q) is finite if and only if opt_p(ℱ_q) is. Moreover, we prove for all p, q ≥ 2 and η≥ 1 that opt^nf_p,η(ℱ_q) = Θ(η).

COLT 2026

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

Wu Tianhao, Matthew Zurek, Weina Wang, Qiaomin Xie

We study the sample complexity of learning in average-reward weakly-coupled Markov decision processes (WCMDPs) and Restless Bandits (RBs) under a generative model. Naive reduction to a tabular MDP leads to high complexity bounds as the state-action space is exponentially large in the number of arms N. By exploiting the weakly coupled structure, we show that near-optimal policies can be learned with sample and computational complexities that are polynomial in N. Specifically, we analyze the plug-in approach, which applies an efficient planning algorithm to an empirical model estimated from data. For fully heterogeneous WCMDPs, we establish the first finite-sample PAC guarantee with polynomial complexity and an O(1/√(N)) optimality gap. For homogeneous RBs, we further prove that a smaller optimality gap is achievable under mild structural assumptions. A primary technical contribution of our work is a novel Lyapunov-based analysis framework. Unlike classical approaches that rely on the difficult-to-control bias function, our framework uses an explicitly constructed Lyapunov function along with a drift transfer technique between the true and empirical models. A key step of independent interest in our framework is a fine-grained perturbation analysis for the underlying linear programming (LP) relaxation, which provides a general tool for analyzing LP-based policies and weakly-coupled systems.

COLT 2026

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

Existing theory suggests that for linear regression problems categorized by capacity and source conditions, gradient descent (GD) is always minimax optimal, while both ridge regression and online stochastic gradient descent (SGD) are polynomially suboptimal for certain categories of such problems. Moving beyond minimax theory, this work provides instance-wise comparisons of the finite-sample risks for these algorithms on any well-specified linear regression problem. Our analysis yields three key findings. First, GD dominates ridge regression: with comparable regularization, the excess risk of GD is always within a constant factor of ridge, but ridge can be polynomially worse even when tuned optimally. Second, GD is incomparable with SGD. While it is known that for certain problems GD can be polynomially better than SGD, the reverse is also true: we construct problems, inspired by benign overfitting theory, where optimally stopped GD is polynomially worse. Finally, GD dominates SGD for a significant subclass of problems—those with fast and continuously decaying covariance spectra—which includes all problems satisfying the standard capacity condition.

COLT 2026

Minimax Limits of k-Fold Cross-Validation via Majority

Ido Nachum, Ruediger Urbanke, Thomas Weinberger

We study the mean-squared error of k-fold cross-validation as a risk estimator, with particular emphasis on how its accuracy depends on the number of folds k. Despite the widespread use of cross-validation, principled guidance for choosing k is largely absent, mainly due to the complex dependence between fold-wise error estimates. To obtain sharp and interpretable results, we focus on the majority algorithm in binary classification, a minimal yet nontrivial empirical risk minimization procedure. We provide a fine-grained analysis of its cross-validation behavior, showing that even this simple algorithm exhibits subtle and delicate phenomena for which existing theory provides loose and even vacuous bounds. Leveraging this analysis, we introduce a minimax framework for cross-validation risk estimation and prove that no empirical risk minimization algorithm can achieve an O(1/n) minimax mean-squared error when the number of folds grows with the number of samples n; instead, a lower bound of order Ω(√(k)/n) is unavoidable. Our results reveal fundamental limitations of cross-validation as a data-reuse strategy, clarify gaps and inaccuracies in prior theoretical work, and position the majority algorithm as a natural benchmark that any tight analysis of cross-validation should be able to explain.

COLT 2026

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

Ziao Wang, Lei Ying

This paper studies a variation of the classic network alignment problem, named diffusion-network alignment. The goal is to align the vertices of a rooted diffusion tree to the vertices of a network, where the diffusion tree could be from a communication trace or contact tracing, and the network could be an online or offline social network. Different from the classic network alignment where both networks are fully observed, this model captures the information asymmetry of two networks. To solve this problem, this paper presents an efficient algorithm based on tree correlation tests to extract alignment information from local neighborhoods. We analyze the performance of the algorithm in the sparse graph regime and show that with high probability, all matched pairs are correct. Furthermore, for each vertex on the diffusion tree, this paper establishes an explicit lower bound on the probability that the vertex is correctly matched. These lower bounds are depth-dependent and increase as vertices get closer to the root.

COLT 2026

Accelerated Convex Optimization via Hamiltonian Dynamics with Deterministic Integration Time

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

We develop Hamiltonian dynamics-based algorithms for smooth convex optimization that achieve accelerated rates of convergence. By exploiting contraction of averaged Hamiltonian flow trajectories rather than requiring contraction at trajectory endpoints, we show that Hamiltonian dynamics-based optimization methods admit deterministic and accelerated convergence guarantees, extending prior work that is limited to quadratic objectives or holds only in expectation. We analyze an idealized continuous-time algorithm and derive practical discrete-time implementations with optimal first-order complexity, thereby establishing Hamiltonian dynamics as a useful algorithmic primitive for deterministic accelerated optimization.

COLT 2026

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

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

Online eXp-concave Optimization (OXO) is a fundamental problem in online learning, where the goal is to minimize regret when loss functions are exponentially concave. The standard algorithm, Online Newton Step (ONS), guarantees an optimal O(d log T) regret, where d is the dimension and T is the time horizon. Despite its simplicity, ONS may face a computational bottleneck due to the Mahalanobis projection at each round. This step costs Ω(d^ω) arithmetic operations for bounded domains, even for simple domains such as the unit ball, where ω∈ (2,3] is the matrix-multiplication exponent. As a result, the total runtime can reach Õ(d^ω T), particularly when iterates frequently oscillate near the domain boundary. This paper proposes a simple variant of ONS, called LightONS, which reduces the total runtime to O(d^2 T + d^ω√(T log T)) while preserving the optimal regret. Deploying LightONS with the online-to-batch conversion implies a method for stochastic exp-concave optimization with runtime Õ(d^3/ε), thereby answering an open problem posed by Koren [2013]. The design leverages domain-conversion techniques from parameter-free online learning and defers expensive Mahalanobis projections until necessary, thereby preserving the elegant structure of ONS and enabling LightONS to act as an efficient plug-in replacement in broader scenarios, including gradient-norm adaptivity, parametric stochastic bandits, and memory-efficient OXO.

COLT 2026

Almost sure null bankruptcy of testing-by-betting strategies

Hongjian Wang, Shubhada Agrawal, Aaditya Ramdas

The bounded mean betting procedure serves as a crucial interface between the domains of (1) sequential, anytime-valid statistical inference, and (2) online learning and portfolio selection algorithms. While recent work in both domains has established the exponential wealth growth of numerous betting strategies under any alternative distribution, the tightness of the inverted confidence sets, and the pathwise minimax regret bounds, little has been studied regarding the asymptotics of these strategies under the null hypothesis. Under the null, a strategy induces a wealth martingale converging to some random variable that can be zero (bankrupt) or non-zero (non-bankrupt, e.g. when it eventually stops betting). In this paper, we show the conceptually intuitive but technically nontrivial fact that these strategies (universal portfolio, Krichevsky-Trofimov, GRAPA, hedging, etc.) all go bankrupt with probability one, under any non-degenerate null distribution. Part of our analysis is based on the subtle almost sure divergence of various sums of ∑_n O_p(n^-1) type, a result of independent interest. We also demonstrate the necessity of null bankruptcy by showing that non-bankrupt strategies are all improvable in some sense. Our results significantly deepen our understanding of these betting strategies as they qualify their behavior on “almost all paths”, whereas previous results are usually on “all paths” (e.g. regret bounds) or “most paths” (e.g. concentration inequalities and confidence sets).

COLT 2026

Fast Score-Based Sampling via Log-Concave Reductions

Martin J Wainwright

Sampling based on score diffusions has led to striking empirical results, and has attracted considerable attention from various research communities. It depends on the availability of (approximate) Stein score functions for various levels of additive noise. We show how, in some generality, the availability of scores allows the general problem to be “reduced” to sampling from an adaptively constructed sequence of K strongly log-concave (SLC) sub-problems. The reduction is simple, constructive and algorithm-independent, so that any SLC sampler can be used as a subroutine. Various bounds on score-based sampling complexity follow directly: for instance, high-accuracy SLC samplers yield Õ(√(d)polylog(1/ε)) guarantees for accuracy ε in dimension d, whereas randomized midpoint SLC schemes yield Õ( d^1/3poly(1/ε)) guarantees. When the original distribution itself is SLC, we prove that K ≤ 1 + log_2(κ), thereby obtaining the first efficient procedure with logarithmic dependence on the condition number κ; for general distributions, the quantity K depends on the geometry of the score Hessian across the trajectory. Our analysis is direct and simple, involving techniques and insights complementary to those in standard analyses of discretized diffusions.

COLT 2026

Learning with Simulators: No Regret in a Computationally Bounded World

Sasha Voitovych, Abhishek Shetty, Noah Golowich, Alexander Rakhlin

Understanding the minimal assumptions necessary for generalization is the fundamental question in learning theory. Unfortunately, most results rely heavily on independence (or some proxy thereof) of the data-generating process, while results for strongly dependent data are far more limited. Towards addressing this gap, we introduce the framework of simulatable processes, where the learner has access to a simulator that approximates the distribution generating the data (which may be an arbitrarily complex and dependent process). Surprisingly, given access to such a simulator, we show that we can recover the same learning guarantees as in the classical setting with independent data, namely, error bounds that depend on the VC dimension. Further, we use this framework to study the power of conditional sampling and show strict statistical and computational advantages in this setting. As a highlight of our framework, we exhibit a single algorithm that simultaneously learns any given VC class under all processes samplable in bounded polynomial time, with regret controlled by the time-bounded Kolmogorov complexity of the process. This provides a significant conceptual broadening of the classical PAC model.

COLT 2026

The Geometry of Efficient Nonconvex Sampling

Santosh S. Vempala, Andre Wibisono

We present an efficient algorithm for uniformly sampling from an arbitrary compact body 𝒳⊂ℝ^n from a warm start under isoperimetry and a natural volume growth condition. Our result provides a substantial common generalization of known results for convex bodies and star-shaped bodies. The complexity of the algorithm is polynomial in the dimension, the Poincaré constant of the uniform distribution on 𝒳 and the volume growth constant of the set 𝒳.

COLT 2026

On-Average Stability of Multipass Preconditioned SGD and Effective Dimension

Simon Vary, Tyler Farghly, Ilja Kuzborskij, Patrick Rebeschini

We study trade-offs between the population risk curvature, geometry of the noise, and preconditioning on the generalisation ability of the multipass Preconditioned Stochastic Gradient Descent (PSGD). Many practical optimisation heuristics implicitly navigate this trade-off in different ways — for instance, some aim to whiten gradient noise, while others aim to align updates with expected loss curvature. When the geometry of the population risk curvature and the geometry of the gradient noise do not match, an aggressive choice that improves one aspect can amplify instability along the other, leading to suboptimal statistical behavior. In this paper we employ on-average algorithmic stability to connect generalisation of PSGD to the effective dimension that depends on these sources of curvature. While existing techniques for on-average stability of SGD are limited to a single pass, as first contribution we develop a new on-average stability analysis for multipass SGD that handles the correlations induced by data reuse. This allows us to derive excess risk bounds that depend on the effective dimension. In particular, we show that an improperly chosen preconditioner can yield suboptimal effective dimension dependence in both optimisation and generalisation. Finally, we complement our upper bounds with matching, instance-dependent lower bounds.

COLT 2026

Spectral Recovery of a Planted Triangle-Dense Subgraph

Sam van der Poel, Cheng Mao, Benjamin McKenna

Given a simple graph on n vertices and a parameter k, the triangle-densest-k-subgraph problem is known to be computationally hard in the worst case. To circumvent the computational hardness, we study an average-case model where a triangle-dense subgraph on k vertices is planted in an Erdős–Rényi random graph on n vertices. For the recovery of the planted subgraph, we propose a simple spectral algorithm and a semidefinite program, both of which use a graph matrix whose entries are local signed triangle counts. Theoretical guarantees for these algorithms are established through spectral analysis of the graph matrix. Finally, we provide evidence showing a statistical-to-computational gap analogous to that for the planted clique problem. The computational threshold in terms of the subgraph size k is at least √(n) in the framework of low-degree polynomial algorithms, while the information-theoretic threshold is at most logarithmic in n.

COLT 2026

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

Konstantinos Tsirkas, Leda Wang, Ilias Zadik

Over the last decades, two distinct approaches have been instrumental to our understanding of the computational complexity of statistical estimation. The statistical physics literature predicts algorithmic hardness through local stability and monotonicity properties of the Franz–Parisi potential, while the rigorous average-case complexity literature characterizes hardness via the limitations of restricted algorithmic classes, most notably low-degree polynomial estimators. In this work, we show that for estimation problems the power of low-degree polynomials is governed by the monotonicity of the annealed Franz–Parisi potential for a broad family of Gaussian additive models. Subject to the low-degree conjecture for these Gaussian additive models, this identifies the polynomial-time estimation threshold with the monotonicity threshold of the annealed Franz–Parisi potential.

COLT 2026

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

Volodymyr Tkachuk, Csaba Szepesvari, Xiaoqi Tan

We study fixed-horizon offline reinforcement learning (RL) with function approximation for both policy evaluation and policy optimization. Prior work established that statistically efficient learning is impossible for either of these problems when the only assumptions are that the data has good coverage (concentrability) and the state-action value function of every policy is linearly realizable (q^π-realizability) [Foster et al., 2022]. Recently, Tkachuk et al. [2024] gave a statistically efficient learner for policy optimization, if in addition the data is assumed to be given as trajectories. In this work we present a statistically efficient learner for policy evaluation under the same assumptions, with the additional requirement that the behavior policy is known. Further, we show that the sample complexity of the learner used by Tkachuk et al. [2024] for policy optimization can be improved by a tighter analysis.

Keep browsing

More papers from top AI conferences

30+ top conferences, by conference, year, and topic.