COLT 2026 Papers

We study the graph alignment problem for correlated Gaussian Orthogonal Ensemble (GOE) matrices, where the goal is to recover a hidden vertex permutation given two correlated symmetric Gaussian matrices (A,B) with correlation 1/√(1+σ^2). While the maximum likelihood estimator is information-theoretically optimal, its computation, which reduces to a quadratic assignment problem, is intractable. Motivated by this, we analyze convex relaxations based on minimizing AX - XB_F over the set of doubly stochastic matrices and the unit hypercube. We show that when the correlation parameter satisfies σ = o(n^-1/2/log^4 n), the solution of either relaxation (X^⋆) concentrates around the ground-truth permutation matrix (Π^⋆), i.e., X^⋆ - Π^⋆_F^2 = o(n), implying recovery of all but a vanishing fraction of vertices after simple post-processing. Combined with existing lower bounds, our results precisely characterize that X^⋆ - Π^⋆_F^2 transitions from o(n) for σ = õ(n^-1/2) to Ω(n) for σ = Ω̃(n^-1/2). In doing so, our analysis significantly tightens prior results and extends them beyond doubly stochastic relaxations.

We study an online market-making problem in which a learner sequentially posts bid and ask prices for a single asset while interacting with traders holding private valuations. Unlike existing online learning formulations that assume fully censored feedback, we introduce an action-dependent feedback model inspired by real limit order books: when a trade occurs, the trader’s valuation remains hidden, whereas when no trade occurs, informative feedback about supply and demand is revealed. We show that this additional information fundamentally changes the learnability of the problem. In the stochastic setting with i.i.d. market prices, we propose an elimination-based algorithm that achieves O(√(T)) regret with high probability, without requiring any smoothness assumptions on the distribution of trader valuations. We then extend this result to a broad class of mean-reverting price processes by considering both local, autoregressive dynamics and a weaker global drift condition based on cumulative deviations from the mean. Under either assumption, we establish high-probability O(√(T)) regret bounds, relying on a new concentration inequality of independent interest. Finally, in the adversarial setting with oblivious prices, we design an explore-then-perturb algorithm that guarantees Õ(T^2/3) regret in expectation. Our results quantify the value of observing the order book in online market making and demonstrate that even limited, action-dependent feedback can substantially improve regret guarantees compared to standard bandit feedback models.

We study the minimax sample complexity of ε-best arm identification in linear bandits, a classical pure-exploration problem. Given a compact action set 𝒳 that spans ℝ^d and an unknown reward vector θ∈ℝ^d, the goal is to output an arm x∈𝒳 such that ⟨x,θ⟩≥max_x∈𝒳 ⟨x,θ⟩- ε with probability at least 1-δ, using as few samples as possible. Our aim is to better understand the power and limitations of adaptivity in this setting. We begin with non-adaptive algorithms. We present a non-adaptive fixed-design method with sample complexity 𝒪(dlog(1/δ)/ε^2+w(𝒳)^2/ε^2), where w(𝒳) is a Gaussian width term dependent on 𝒳, and we prove a matching lower bound Ω(dlog(1/δ)/ε^2+w(𝒳)^2/ε^2) for all non-adaptive fixed-design methods. Moreover, w(𝒳)≤𝒪(d) for general 𝒳, which is tight for sets such as the unit ℓ_2 ball, and w(𝒳)≤𝒪(√(dlog|𝒳|)) when 𝒳 is finite, which is tight for the canonical basis e_1,…,e_d. We then turn to adaptive sampling. For any finite action set 𝒳, we prove the existence of an adaptive algorithm with sample complexity 𝒪(dlog(1/δ)/ε^2+dlog(|𝒳|/d)/ε^2) via a generalization of Median Elimination, which is known to yield a log d improvement for the canonical basis. This raises a structural question: beyond the canonical basis, are there structured action sets for which adaptivity yields only logarithmic-factor improvements over the optimal non-adaptive rate? We answer in the affirmative for several natural action sets, namely the hypercube, the ℓ_2 ball, m-sets, and multi-task multi-armed bandits. Finally, we show that logarithmic improvements are not the whole story. To our knowledge, we provide the first construction of an action set 𝒳 for which adaptivity yields a polynomial-factor improvement over every non-adaptive algorithm. A key ingredient behind this separation is an ℓ_2-norm estimation subroutine: we design an adaptive algorithm that uses 𝒪(dlog(1/δ)/ε^2) samples from the unit ℓ_2 ball in ℝ^d and outputs an estimate r satisfying |r-θ_2|≤ε with probability at least 1-δ, where θ is the unknown reward vector. Taken together, these results illustrate when adaptivity can offer only modest savings and when it can enable genuine polynomial gains, sharpening our understanding of the role of adaptivity and geometry in pure exploration and experimental design.

A distribution over instances of a sampling problem is said to exhibit transport disorder chaos if perturbing the instance by a small amount of random noise dramatically changes the stationary distribution (in Wasserstein distance). Seeking to provide evidence that some sampling tasks are hard on average, a recent line of work has demonstrated that disorder chaos is sufficient to rule out “stable” sampling algorithms, such as gradient methods and some diffusion processes. We demonstrate that disorder chaos does not preclude polynomial-time sampling by canonical algorithms in canonical models. We show that with high probability over a random graph 𝐆∼ G(n,1/2): (1) the hardcore model (at fugacity λ = 1) on 𝐆 exhibits disorder chaos, and (2) Glauber dynamics run for O(n) time can approximately sample from the hardcore model on 𝐆 (in Wasserstein distance).

We introduce Wedge Sampling, a new non-adaptive sampling scheme for low-rank tensor completion. We study recovery of an order-k low-rank tensor of dimension n×⋯× n from a subset of its entries. Unlike the standard uniform entry model (i.e., i.i.d. samples from [n]^k), wedge sampling allocates observations to structured length-two patterns (wedges) in an associated bipartite sampling graph. By directly promoting these length-two connections, the sampling design strengthens the spectral signal that underlies efficient initialization, in regimes where uniform sampling is too sparse to generate enough informative correlations. Our main result shows that this change in sampling paradigm enables polynomial-time algorithms to achieve both weak and exact recovery with nearly linear sample complexity in n. The approach is also plug-and-play: wedge-sampling–based spectral initialization can be combined with existing refinement procedures (e.g., spectral or gradient-based methods) using only an additional Õ(n) uniformly sampled entries, substantially improving over the Õ(n^k/2) sample complexity typically required under uniform entry sampling for efficient methods. Overall, our results suggest that the statistical-to-computational gap highlighted by Barak and Moitra [Mathematical Programming, 193(2):513–548, 2022] is, to a large extent, a consequence of the uniform entry sampling model for tensor completion, and alternative non-adaptive measurement designs that guarantee a strong initialization can overcome this barrier.

Stochastic Gradient Descent () is one of the most classical optimization algorithms with favorable theoretical guarantees, yet the practical implementation of differs subtly from its well-known form and is often referred to as Shuffling Stochastic Gradient Descent (). A particularly popular strategy in is Random Reshuffling (), which has achieved great empirical success across numerous experiments. Despite its strong performance, has long been considered a heuristic due to a lack of theoretical support. Over the last decade, people have finally established provable convergence rates for , thus justifying its observed superiority. However, for smooth convex optimization, two clouds over the convergence theory of remain to this day. More precisely, according to the current theory, under converges only when the stepsize is smaller than a threshold proportional to 1/n, where n is the number of summands in the objective (or the number of data points). Consequently, the optimally tuned theoretical rate of under is strictly worse than that of when the number of epochs is smaller than another threshold proportional to n. These two restrictions heavily limit the applicability of existing theories and leave a critical mismatch with practice. In this work, for the first time, we prove that dominates in smooth convex optimization under any reasonable stepsize after any finite number of epochs, thereby addressing a longstanding open question.

In this paper, we study regret minimization in repeated games with adaptive opponents whose strategies may depend on the histories of play. The classical online learning metric of external regret does not fully capture such adaptivity, since it compares against decisions while treating the loss sequence as fixed. To account for the counterfactual reasoning of the players, we introduce a new metric, , specific to this game-theoretic setting, which measures the difference between the realized and the best-in-hindsight accumulated utility when all players can respond to the history of play. Compared with existing regret notions in adaptive environments, allows stronger dynamic comparators and less restricted opponents, while still enabling the learning of better equilibria when all players minimize it. We first identify necessary conditions for achieving sublinear . The comparator strategies must have sublinear accumulated variation, and both the comparator and the opponents must have imperfect recall. Without these conditions, sublinear is impossible to achieve in general. We then provide additional sufficient conditions and algorithms for minimizing . A key challenge is that is nonconvex in the strategy space by definition. We address this challenge through three approaches. The first approach uses a nonconvex optimization oracle, as in prior work on online nonconvex learning. The second approach minimizes a convex linearized surrogate at each iteration, which yields the minimization of a local variant of . The third approach directly minimizes when the opponents change their strategies slowly, by reformulating the repeated game as a Markov game and optimizing over occupancy measures. Finally, we show that when all players can run algorithms to minimize the or its linearized variant, certain subgame-perfect equilibria of the repeated game can be learned. We also provide experiments to show that these regret notions can lead to more cooperative outcomes with higher utility in games such as the Stag Hunt.

We study online learning in two-player uninformed Markov games, where the opponent’s actions and policies are unobserved. In this setting, Tian et al. (2021) show that achieving no-external-regret is impossible without incurring an exponential dependence on the episode length H. They then turn to the weaker notion of Nash-value regret and propose a V-learning algorithm with regret O(K^2/3) after K episodes. However, their algorithm and guarantee do not adapt to the difficulty of the problem: even in the case where the opponent follows a fixed policy and thus O(√(K)) external regret is well-known to be achievable, their result is still the worse rate O(K^2/3) on a weaker metric. In this work, we fully address both limitations. First, we introduce empirical Nash-value regret, a new regret notion that is strictly stronger than Nash-value regret and naturally reduces to external regret when the opponent follows a fixed policy. Moreover, under this new metric, we propose a parameter-free algorithm that achieves an O(min√(K) + (CK)^1/3, √(LK)) regret bound, where C quantifies the “variance” of the opponent’s policies and L denotes the number of policy switches (both at most O(K)). Therefore, our results not only recover the two extremes—O(√(K)) external regret when the opponent is fixed and O(K^2/3) Nash-value regret in the worst case—but also smoothly interpolate between these extremes by automatically adapting to the opponent’s non-stationarity. We achieve so by first providing a new analysis of the epoch-based V-learning algorithm by Mao et al. (2022), establishing an O(η C + √(K/η)) regret bound, where η is the epoch incremental factor. Next, we show how to adaptively restart this algorithm with an appropriate η in response to the potential non-stationarity of the opponent, eventually achieving our final results.

We study the fundamental problem of learning a high-dimensional Gaussian truncated to an unknown halfspace. Lee, Mehrotra and Zampetakis (FOCS’24) recently obtained the first polynomial time algorithm for this problem, but their resulting sample and time complexity bounds are not optimal. Under non-trivial truncation, for any target accuracy ε > 0 and dimension d we give an efficient algorithm that uses n = Õ(d^2/ε^2) samples and learns the underlying Gaussian to error ε in total variation distance. Our algorithm is also fast: its runtime is dominated by the cost of computing the empirical covariance matrix. Both our sample and time complexity are optimal in terms of d and ε even without truncation: in this regard, we can learn a Gaussian under halfspace truncation for free. The key ingredient behind our result is a novel reinterpretation of the low-degree moments of the truncated Gaussian in terms of a relative truncation parameter. This relative truncation parameter uniquely determines the parameters of the untruncated Gaussian and enables direct parameter recovery. This reinterpretation allows us to circumvent the time intensive projected stochastic gradient descent procedure that is widely used in learning under truncation.

We study optimal learning rate (LR) schedules under the functional scaling law (FSL) framework (Li et al., 2025), where loss dynamics are controlled by a source exponent s>0 for signal learning and a capacity exponent β>1 for noise forgetting. For a fixed training horizon N, we characterize the schedules that minimize the final-step loss under natural stability constraints and reveal a sharp phase transition. In the easy-task regime s ≥ 1 - 1/β, the optimal schedule takes the power-decay form η^*(z) = η_peak(1 - z/N)^2β - 1 with η_peak≍ N^-(s-1+1/β)/(s+1/β). In contrast, in the hard-task regime s < 1 - 1/β, the optimal schedule exhibits a warmup–stable–decay (WSD)-like (Hu et al., 2024) structure: it maintains the largest admissible LR for most of training and decays only near the end, with the decay phase occupying a vanishing fraction of the horizon. We next study the practical setting where the decay shape is fixed and only the peak LR is tuned. To separate these two design choices, we introduce a family of fractional LR schedules that decouple peak-LR tuning from decay-shape design. We prove that fixed-shape schedules suffer from capacity saturation: each shape can adapt to the capacity exponent only up to a shape-dependent threshold, beyond which the achievable convergence rate no longer improves. This yields a principled criterion for evaluating commonly used schedules such as cosine and linear decay, revealing both their strengths and limitations. We then apply the FSL-optimal power-decay schedule to one-pass stochastic gradient descent (SGD) for kernel regression and show that the last iterate attains the exact minimax-optimal convergence rate, eliminating the logarithmic gap in prior analyses. Finally, experiments validate our theoretical predictions in controlled settings and illustrate their usefulness for practical LR-schedule design in neural network training.

We consider the [0,1]-valued regression problem in the stochastic setting. In a related problem called cost-sensitive classification, Foster and Krishnamurthy (2021) have shown that the log loss minimizer achieves an improved generalization bound compared to that of the squared loss minimizer in the sense that the bound scales with the cost of the best classifier, which can be arbitrarily small depending on the problem instance. Such a result is often called a first-order bound. For [0,1]-valued regression, we first show that the log loss minimizer leads to a similar first-order bound. We then ask if there exists a loss function that achieves a variance-dependent bound, also known as a second-order bound, which is a strict improvement upon first-order bounds. We answer this question in the affirmative by proposing a novel loss function called betting loss. Our result is variance-adaptive in the sense that the bound is attained by an algorithm without any knowledge about the variance, which is in contrast to the existing works such as weighted least squares with known variances or those that model label variance or its distribution such as distributional reinforcement learning.

We consider the adversarial linear bandits setting and present a unified algorithmic framework that bridges Follow-the-Regularized-Leader (FTRL) and Follow-the-Perturbed-Leader (FTPL) methods, extending the known connection between them from the full-information setting. Within this framework, we introduce self-concordant perturbations, a family of probability distributions that mirror the role of self-concordant barriers previously employed in the FTRL-based SCRiBLe algorithm. Using this idea, we design a novel FTPL-based algorithm that combines self-concordant regularization with efficient stochastic exploration. Our approach achieves a regret of 𝒪(d√(n ln n)) on both the d-dimensional hypercube and the ℓ_2 ball. On the ℓ_2 ball, this matches the rate attained by SCRiBLe. For the hypercube, this represents a √(d) improvement over these methods and matches the optimal bound up to logarithmic factors.

We study linear TD(0) under Markovian sampling, where data are generated along a single trajectory. We provide high-probability guarantees for a plain unprojected TD(0) algorithm with Polyak–Ruppert (PR) averaging, using a single stepsize schedule η_t ∝ 1/(τ_mixlog(t) √(t)) that depends on mixing time but requires no prior knowledge of the curvature parameter ω. Our first result shows that such a choice of the stepsize guarantees that the TD(0) iterates are automatically and uniformly bounded with high probability, without projections and without any stability argument based on ω. Building on this result, we establish a simultaneous high-probability convergence guarantee for the PR average: the same stepsize yields both a robust curvature-free 𝒪(τ_mix/√(T)) rate and a fast curvature-dependent 𝒪(τ_mix^2/(ω T)) rate, with the bound taking the minimum of the two. The core technical ingredient is a Poisson-equation toolkit for geometrically mixing Markov chains, which decomposes Markov noise into a martingale term plus a controlled remainder and enables a new self-bounding inductive argument for pathwise stability.

Gradient equilibrium (GEQ) is a recently introduced online optimization framework that generalizes first-order stationarity from offline optimization, and abstracts problems like online conformal prediction. While GEQ has curious similarities with known online learning frameworks, such as regret minimization, prior work has shown that GEQ error and regret are incomparable as objectives, leaving open a precise understanding of how GEQ fits into the broader online learning landscape. In this work, we show that GEQ is equivalent to Blackwell approachability in the algorithmic sense. That is, a Blackwell approachability problem can always be solved using queries to a black-box GEQ oracle, with no asymptotic loss in the oracle’s error rate, and vice versa. Taken together with known equivalences between approachability, regret minimization, and calibration, these results imply an equivalence between GEQ and these frameworks, as well. Hence, while GEQ guarantees are semantically different from known online learning guarantees, GEQ algorithms are equally powerful primitives as classical regret minimization and calibration algorithms. Our reductions are efficient and can be used to transfer refined guarantees, such as optimism and strong adaptivity, from regret minimization to GEQ. Our techniques can also be used to identify necessary and sufficient conditions for GEQ, and to establish reductions between different notions of GEQ with unconstrained and constrained decision sets.

We study the distribution of regret in stochastic multi-armed bandits and episodic reinforcement learning through a unified framework. We formalize a distributional regret bound as a probabilistic guarantee that holds uniformly over all confidence levels δ∈ (0,1], thereby characterizing the regret distribution across the full range of δ. We present a simple UCBVI-style algorithm with exploration bonus minc_1,k/N, c_2,k/√(N), where N denotes the visit count and (c_1,k,c_2,k) are user-specified parameters. For arbitrary parameter sequences, we derive general gap-independent and gap-dependent distributional regret bounds, yielding a principled characterization of how the parameters control the trade-off between expected performance, tail risk, and instance-dependent behavior. In particular, our bounds achieve optimal trade-offs between expected and distributional regret in both minimax and instance-dependent regimes. As a special case, for multi-armed bandits with A arms and horizon T, we obtain a distributional regret bound of order 𝒪(√(AT)log(1/δ)), confirming the conjecture of Lattimore and Szepesvári (2020, Section 17.1) for the first time.

Follow-the-regularized-leader framework has shown effectiveness and flexibility in online learning problems, where the choice of learning rates are known to be crucial. Recently, adaptive learning rates defined in terms of the arm-selection probabilities, obtained by solving convex optimization, have achieved improved best-of-both-worlds (BOBW) guarantees in various bandit problems. In contrast, BOBW guarantees for its computationally efficient alternative, follow-the-perturbed-leader (FTPL), remain relatively limited since its optimization-free nature ironically makes the design of adaptive, probability-dependent learning rates non-trivial. To address this challenge, we propose an adaptive learning rate for FTPL by introducing surrogate probability functions that can be computed only from the available quantities, without requiring the exact probabilities. Based on these learning rates with surrogate functions, we provide the BOBW guarantee for FTPL with Pareto perturbations for any shape parameter α >1, generalizing prior results restricted to specific choices of α=2. We further show the BOBW guarantees for FTPL with adaptive learning rates in the bandit problem with expert advices. Our approach preserves the computational simplicity of FTPL while enabling probability-dependent adaptivity, and the surrogate-based methodology may be of independent interest in other algorithmic frameworks beyond FTPL and learning rate designs.

Overparameterized ML models, including neural networks, typically induce underdetermined training objectives with multiple global minima. The implicit bias refers to the limiting global minimum that is attained by a common optimization algorithm, such as gradient descent (GD). In this paper, we characterize the implicit bias of GD for training a shallow ReLU model with the squared loss on high-dimensional random features. Prior work (Vardi and Shamir, 2021) showed that the implicit bias does not exist in the worst-case, or corresponds exactly to the minimum-ℓ_2-norm interpolating solution under exactly orthogonal data (Boursier et al., 2022). Our work interpolates between these two extremes and shows that, for sufficiently high-dimensional random data, the implicit bias approximates the minimum-ℓ_2-norm solution with high probability with a gap on the order Θ(√(n/||λ||_1)), where n is the number of training examples and λ denotes the spectrum of the data covariance matrix. Our results are obtained through a novel primal-dual analysis that carefully tracks the evolution of predictions, data-span coefficients, as well as their interactions, and show that the ReLU activation pattern quickly stabilizes with high probability over random data.

We study high-dimensional differentially private (DP) covariance estimation in the operator norm, and principal component analysis (PCA), under k-row-column sparsity (k-RCS) of the covariance matrix. In the non-private setting, it is known that poly(k,log d) samples suffice to solve both of these problems. However, the only comparable result known under DP (Wang and Xu, 2021) requires Ω(d) samples under standard parameterizations of the problem. We investigate when this curse of dimensionality is inherent for sparse covariance estimation tasks under DP. On the upper bound front, we show that a poly(k,log d) sample complexity for PCA is possible under DP, if we also posit sparsity of the leading eigenvector. We complement this result with poly(d) lower bounds under DP for both sparse covariance estimation and PCA, establishing an exponential gap between the private and non-private variants of these problems when k=polylog(d). To our knowledge, no such separation has previously been demonstrated for any sparse estimation problem in private high-dimensional statistics. Our techniques are flexible enough that they imply stronger lower bounds even for the well-studied problem of standard DP PCA, without sparsity assumptions.

We study the following distribution clustering problem: Given a hidden partition of k distributions into 2 groups, such that the distributions within each group are the same, and the distributions associated with the clusters are pairwise ε-far in total variation, the goal is to recover the partition. We establish upper and lower bounds on the sample complexity for two fundamental cases: (1) when one of the cluster’s distributions is known, and (2) when both are unknown. Our upper and lower bounds characterize the sample complexity’s dependence on the domain size n, number of distributions k, size r of one of the clusters, and distance ε. In particular, we achieve tightness with respect to (n,k,r,ε) (up to an O(log k) factor) for all regimes. In addition, we show that this result extends to the case of d-clustering for any constant number of clusters d.