COLT 2026 Papers

We ask whether interaction is necessary for order-optimal 1-bit mean estimation over nonparametric finite-moment classes. Adaptive threshold-query protocols achieve the order-optimal 1-bit minimax rate, and the same rate is attainable with general 1-bit queries using only one adaptive transition (i.e., two stages of querying). In the non-adaptive setting, threshold and interval queries are known to be highly suboptimal, but the case of arbitrary non-adaptive quantizers remains unresolved. Can such quantizers match the adaptive rate, yielding an optimal one-shot protocol? Or is the known two-stage estimator stage-optimal, with a single adaptive transition being necessary and sufficient?

We ask whether distribution-independent SQ learning implies low dimension complexity, and whether anything learnable with (S)GD on a (benign) neural network under any input distribution is also learnable with a linear model.

Classical online optimization theory focuses on regret guarantees for convex Lipschitz functions. However, online optimization problems motivated by machine learning for algorithm design fall outside this regime, since typically an algorithm’s performance as a function of its hyperparameters is a highly volatile function. This has inspired recent work on online optimization of piecewise-Lipschitz functions with complex transition boundaries. We provide open questions in this direction. Resolving these questions would advance the learning-theoretic foundation for adaptive algorithm design by clarifying when desirable sublinear regret guarantees are possible for learning the algorithms from online problem instances.

We ask how much overparameterization is needed for simple iterative methods such as alternating least squares (ALS) and gradient descent to decompose a third-order tensor. This question can be viewed as a basic setting to study feature learning: when a rank-r tensor in ambient dimension n has r≪ n, the latent rank-one components are the features, and k is the amount of overparameterization used by the algorithm. For rank r tensors, recent work shows that overparametrized rank k=O(r^2) suffices for the popular ALS heuristic (with random initialization) to converge to a global optima. Is the quadratic dependence on r an inherent barrier for ALS-like methods? We pose the open problem of proving convergence to the global optimum for k=o(r^2), or proving that a lower bound on the overparametrized rank of k=Ω(r^1+c) for some absolute constant c>0 is necessary.

We develop parameter-free algorithms for unconstrained online learning with regret guarantees that scale with the gradient variation V_T(u) = ∑_t=2^T ∇ f_t(u)-∇ f_t-1(u)^2. For L-smooth convex losses, we provide fully-adaptive algorithms achieving regret of O(u√(V_T(u)) + Lu^2+G^4) without requiring prior knowledge of comparator norm u, Lipschitz constant G, or smoothness L. The update in each round can be computed efficiently via a closed-form expression. Our results extend to dynamic regret and find immediate implications for the stochastically-extended adversarial (SEA) model, which significantly improves upon the previous best-known result (Wang et al., 2025).

Online reinforcement learning in infinite-horizon Markov decision processes (MDPs) remains less theoretically and algorithmically developed than its episodic counterpart, with many algorithms suffering from high “burn-in” costs and failing to adapt to benign instance-specific complexity. In this work, we address these shortcomings for two infinite-horizon objectives: the classical average-reward regret and the γ-regret. We develop a single tractable UCB-style algorithm applicable to both settings, which achieves the first optimal variance-dependent regret guarantees. Our regret bounds in both settings take the form O( √(SA Var) + lower-order terms), where S,A are the state and action space sizes, and Var captures cumulative transition variance. This implies minimax-optimal average-reward and γ-regret bounds in the worst case but also adapts to easier problem instances, for example yielding nearly constant regret in deterministic MDPs. Furthermore, our algorithm enjoys significantly improved lower-order terms for the average-reward setting. With prior knowledge of the optimal bias span h^⋆_sp, our algorithm obtains lower-order terms scaling as h^⋆_spS^2 A, which we prove is optimal in both h^⋆_sp and A. Without prior knowledge, we prove that no algorithm can have lower-order terms smaller than h^⋆_sp^2SA, and we provide a prior-free algorithm whose lower-order terms scale as h^⋆_sp^2S^3A, nearly matching this lower bound. Taken together, these results completely characterize the optimal dependence on h^⋆_sp in both leading and lower-order terms, and reveal a fundamental gap in what is achievable with and without prior knowledge.

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.

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.

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.

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.

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.

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) = Θ(η).

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.

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.

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.

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.

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.

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.

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).