COLT 2026 Papers

We propose a new variant of online learning that we call “ambiguous online learning". In this setting, the learner is allowed to produce multiple predicted labels. Such an “ambiguous prediction" is considered correct when at least one of the labels is correct, and none of the labels are “predictably wrong". The definition of “predictably wrong" comes from a hypothesis class in which hypotheses are also multi-valued. Thus, a prediction is “predictably wrong" if it’s not allowed by the (unknown) true hypothesis. In particular, this setting is natural in the context of multivalued dynamical systems, recommendation algorithms and lossless compression. It is also strongly related to so-called “apple tasting". We show that in this setting, the asymptotic minimax mistake bound is controlled by a combination of the classical Littlestone dimension L and a new parameter that we call “ambiguous Littlestone dimension" (denoted AL). There is a trichotomy of behaviors: up to logarithmic factors, any hypothesis class has a mistake bound of either O(1) (when both AL and L are finite), Θ̃(√(N)) (when AL is infinite but L is finite) or Θ(N) (when both are infinite).

Two directions in algorithms and complexity involve: (1) classifying which optimization problems can be solved in polynomial time, and (2) understanding which computational problems are hard to solve on average in addition to the worst case. For many average-case problems, there does not currently exist strong evidence via reductions that they are hard. However, we can still attempt to predict their polynomial time tractability by proving lower bounds against restricted classes of algorithms. Geometric approaches to predicting tractability typically study the optimization landscape. For optimization problems with random objectives or constraints, ideas originating in statistical physics suggest we should study the overlap between approximately-optimal solutions. Formally, properties of Gibbs measures and the Franz–Parisi potential imply lower bounds against natural local search algorithms, such as Langevin dynamics. A related theory, the Overlap Gap Property (OGP), proves rigorous lower bounds against classes of algorithms which are stable functions of their input. A remarkable recent work of Li and Schramm [COLT 2025] showed that the shortest path problem in random graphs, which is polynomial-time tractable, admits lower bounds against a class of stable algorithms via the OGP. We further investigate and find that: (1) via the OGP and FPP, we can show stable algorithms and natural MCMC chains fail in the optimization landscape of shortest paths, but (2) stable algorithms and local search succeed in the optimization landscape for shortest path trees, which agrees with OGP and FPP predictions.

Recent work on provably efficient algorithms for learning with distribution shift has focused on two models: PQ learning (Goldwasser et al., 2020) and TDS learning (Klivans et al., 2024). Algorithms for TDS learning are allowed to reject a test set entirely if distribution shift is detected. In contrast, PQ learners may only reject points that are deemed out-of-distribution on an individual basis. Our main result is a surprising equivalence between these two models in the distribution-free setting. In particular, we give an efficient black-box reduction from PQ learning to TDS learning for any Boolean concept class. This equivalence implies the first hardness results for distribution-free TDS learning of basic concept classes such as halfspaces. The main technical contribution underlying our equivalence is a method for boosting, via branching programs, the weak distinguishing power of TDS learners that have rejected the target domain. We also show that giving a learner access to membership queries sidesteps these hardness results and allows for efficient, distribution-free PQ learnability of halfspaces. Our algorithm iteratively recovers large-margin separators obtained by applying successive Forster transforms on the training data.

Recent work has shown the surprising power of low-degree sandwiching polynomial approximators in the context of challenging learning settings such as learning with distribution shift, testable learning, and learning with contamination. A pair of sandwiching polynomials approximate a target function in expectation while also providing pointwise upper and lower bounds on the function’s values. In this paper, we give a new method for constructing low-degree sandwiching polynomials that yield greatly improved degree bounds for several fundamental function classes and marginal distributions. In particular, we obtain degree poly(k) sandwiching polynomials for functions of k halfspaces under the Gaussian distribution, improving exponentially over the prior 2^O(k) bound. More broadly, our approach applies to function classes that are low-dimensional and have smooth boundary. In contrast to prior work, our proof is relatively simple and directly uses the smoothness of the target function’s boundary to construct sandwiching Lipschitz functions, which are amenable to results from high-dimensional approximation theory. For low-dimensional polynomial threshold functions (PTFs) with respect to Gaussians, we obtain doubly exponential improvements without applying the FT-mollification method of Kane used in the best previous result.

The classic greedy algorithm is a widely used method for determinant maximization. Although worst-case theory predicts exponentially poor performance, greedy methods are often observed to perform substantially better in practice. This work explains this discrepancy through a finer spectrum-dependent analysis of the greedy algorithm. Specifically, we develop a sharp spectrum-dependent characterization of the greedy vs optimal determinant gap by analyzing greedy selection over structured spectral landscapes. Our main result is an upper bound that decomposes this gap in terms of stable-rank windows. When the target cardinality lies within a wide spectral valley, greedy admits guarantees exponentially stronger than the classical bound; when such valleys vanish due to sharp spectral drops, greedy necessarily encounters failure cliffs, matching known worst-case constructions. This yields a spectral-landscape-dependent characterization that explains sharp regime changes in greedy performance as the target cardinality varies for the input matrix. Finally, we show that several practical statistical models—including isotropic random features, near-identity kernels, and spiked-plus-noise spectra—provably induce these spectral success valleys, yielding strictly stronger guarantees than the worst-case theory. Together, our results provide a tight, beyond-worst-case understanding of greedy determinant maximization.

We study computable probably approximately correct (CPAC) learning, where learners are required to be computable functions. It had been previously observed that the Fundamental Theorem of Sta- tistical Learning, which characterizes PAC learnability by finiteness of the Vapnik-Chervonenkis (VC-)dimension, no longer holds in this framework. Recent works recovered analogs of the Funda- mental Theorem in the computable setting, for instance by introducing an effective VC-dimension. In this work, we investigate the relationship between CPAC learning and recursively enumerable representable (RER) classes, hypothesis classes whose members can be algorithmically listed, in the context of the Fundamental Theorem. We demonstrate that the RER property is deeply con- nected to CPAC learning by characterizing several notions of CPAC learnability via the existence of certain RER classes realizing the same samples. We further establish that the RER property alone is sufficient to guarantee nonuniform CPAC learnability and give a sufficient condition for CPAC learnable classes to be RER. Other results show that the effective VC-dimension can take arbitrary values above the traditional one and we note that the two dimensions coincide given the existence of a computable empirical risk minimizer. This recovers classical PAC bounds for most practically relevant classes and establishes a family of examples separating several notions of learnability.

We study the fundamental classification problem of computing a separating hyperplane for a binary-labeled dataset of size n with normalized d-dimensional features. Letting Φ∈ℝ^n × d denote the feature matrix and γ the margin of the maximum-margin separating hyperplane, we present a randomized algorithm that solves this problem in Õ(γ^-2/3 nnz(Φ) + γ^-2(ω+1)/3)-sequential running time (work), Õ(γ^-2/3)-parallel (computational) depth, and accesses Φ only through Õ(γ^-2/3)-matrix-vector queries (matvecs). We also present a second, faster randomized algorithm with a Õ(γ^-2/3 nnz(Φ) + γ^-2)-sequential running time that uses Õ(γ^-2/3)-matvecs to Φ, but achieves only Õ(γ^-4/3)-parallel depth. Both algorithms match the near-optimal deterministic matvec complexity recently established by Kornowski and Shamir [2025], Karmarkar et al. [2026] and achieve improved sequential runtime and parallel depth, albeit at the expense of using randomness.

We revisit the problem of estimating k linear regressors in d dimensions from samples affected by self-selection bias under the maximum selection rule. Our main result is an algorithm with sample complexity O(d)·poly(k,1/ε) and running time poly(d,k,1/ε)+(klog k)^O(k) for recovering the regressors up to joint squared error ε^2. The key ingredient is the first local-convergence algorithm for the maximum self-selection model. Our approach reduces self-selection to estimation from coarse observations, where the learner observes only the cell of a partition containing the latent sample. The self-selection reduction induces a structured non-convex partition. We prove that this partition preserves enough information locally and that the resulting negative log-likelihood is locally convex around the true parameters. These two geometric properties allow projected stochastic gradient descent, initialized from an existing warm start, to obtain the stated end-to-end guarantee.

We study ripple mechanisms for pure differentially private computation of discrete statistics. For each of three natural statistics – sum, count, and vote – we construct an efficient instance of the ripple mechanism and show that it is often more accurate than the previous state of the art. We also prove that ripple mechanisms are, in some settings, optimal among all discrete pure differentially private additive noise mechanisms.

The Combinatorial Multi-Armed Bandit (CMAB) framework extends classical multi-armed bandit theory to complex decision-making settings where agents select super arms to maximize a collective reward. While Thompson Sampling (TS) is widely favored for its robust empirical performance in these settings, its theoretical guarantees have historically suffered from a significant bottleneck: standard Combinatorial Thompson Sampling () incurs a regret bound with an exponential dependence on the size k^* of the optimal super-arm. This exponential term arises because standard independent posterior sampling fails to coordinate optimism across the base arms of the optimal super arm, causing the probability of exploration to vanish as k^* increases. Although recent advances have achieved polynomial regret for linear rewards, designing an efficient TS algorithm for general, non-linear CMABs remains an open challenge. In this paper, we resolve this open question by proposing Combinatorial Thompson Sampling with a Single Seed (). Unlike standard approaches that sample base arms independently, employs a comonotonic coupling strategy: it generates parameters for all base arms using a single shared random seed via the inverse CDF transform. This mechanism synchronizes sampling fluctuations across arms, ensuring concerted optimism and preventing the exploration probability from decaying exponentially. We prove that achieves a regret bound of O( m kk^*B^2/Δ_min(log(T,m,Δ_max/Δ_min))) for general reward functions satisfying monotonicity and bounded smoothness, where m is the number of total base arms, k is the largest super arm size, and k^* is size of the optimal arm. To the best of our knowledge, this is the first polynomial regret bound for Thompson Sampling in general CMAB settings. Empirical evaluations confirm that significantly outperforms standard independent TS, particularly in regimes with large super arms.

We study online linear optimization with matrix variables constrained by the operator norm, a setting where the geometry renders designing data-dependent and efficient adaptive algorithms challenging. The best-known adaptive regret bounds are achieved by Shampoo-like methods, but they require solving a costly quadratic projection subproblem. To address this, we extend the gradient-based prediction scheme to adaptive matrix online learning and cast algorithm design as constructing a family of smoothed potentials for the nuclear norm. We define a notion of admissibility for such smoothings and prove any admissible smoothing yields a regret bound matching the best-known guarantees of one-sided Shampoo. We instantiate this framework with two efficient methods that avoid quadratic projections. The first is an adaptive Follow-the-Perturbed-Leader (FTPL) method using Gaussian stochastic smoothing. The second is Follow-the-Augmented-Matrix-Leader (FAML), which uses a deterministic hyperbolic smoothing in an augmented matrix space. By analyzing the admissibility of these smoothings, we show both methods admit closed-form updates and match one-sided Shampoo’s regret up to a constant factor, while significantly reducing computational cost. Lastly, using the online-to-nonconvex conversion, we derive two matrix-based optimizers, Pion (from FTPL) and Leon (from FAML). We prove convergence guarantees for these methods in nonsmooth nonconvex settings, a guarantee that the popular Muon optimizer lacks.

The low-degree polynomial framework has been highly successful in predicting computational versus statistical gaps for high-dimensional problems in average-case analysis and machine learning. This success has led to the low-degree conjecture, which posits that this method captures the power and limitations of efficient algorithms for a wide class of high-dimensional statistical problems. We identify a natural and basic hypothesis testing problem in ℝ^n which is polynomial time solvable, but for which the low-degree polynomial method fails to predict its computational tractability even up to degree k=n^Ω(1). Moreover, the low-degree moments match exactly up to degree k=O(√(log n/loglog n)). Our problem is a special case of the well-studied robust subspace recovery problem. The lower bounds suggest that there is no polynomial time algorithm for this problem. In contrast, we give a simple and robust polynomial time algorithm that solves the problem (and noisy variants of it), leveraging anti-concentration properties of the distribution. Our results suggest that the low-degree method and low-degree moments fail to capture algorithms based on anti-concentration, challenging their universality as a predictor of computational barriers.

We analyse linear ensemble sampling (ES) with standard Gaussian perturbations in stochastic linear bandits. We show that for ensemble size m=Θ(dlog n), ES attains Õ(d^3/2√(n)) high-probability regret, closing the gap to the Thompson sampling benchmark while keeping computation comparable. The proof brings a new perspective on randomized exploration in linear bandits by reducing the analysis to a time-uniform exceedance problem for m independent Brownian motions. This continuous-time lens appears particularly natural here: it yields an exact representation of the relevant discrete-time processes, and we do not know another route to a sharp ES bound.

Discriminative Feature Feedback (DFF) (Dasgupta et al., 2018) is an interactive learning protocol in which a learner attempts to predict labels based on online feedback about previous correct labels, as well as discriminative features. Recent work (Bar Oz et al., 2025) studied DFF learning with general teacher classes and defined a dimension that characterizes the optimal mistake bound for deterministic algorithms in the realizable setting. In this work, we show that in sharp contrast to Online Learning, in DFF there can be an unbounded ratio between the optimal mistake bound of deterministic algorithms and that of randomized algorithms, even in the realizable setting. We further show that in this case, also non-realizable learning can have a mistake bound that does not depend on the dimension at all. This result relies on a new algorithmic technique that allows introducing new candidate hypotheses incrementally and could be of independent interest. We further show that in DFF, there can be a significant difference between the obtainable mistake bounds against an oblivious adversary and against an adaptive adversary, again in contrast to Online Learning. Our work shows that once richer feedback than labels is allowed, the landscape of randomized versus deterministic algorithms becomes significantly more involved, and raises new questions on characterizing the optimal mistake bound under differing randomization regimes.

Learning to play zero-sum games is a fundamental problem in game theory and machine learning. While significant progress has been made in minimizing external regret in the self-play settings or with full-information feedback, real-world applications often force learners to play against unknown, arbitrary opponents and restrict learners to bandit feedback where only the reward of the realized action is observable. In such challenging settings, it is well-known that Ω(√(T)) external regret is unavoidable (where T is the number of rounds). To overcome this barrier, we investigate adversarial learning in zero-sum games under bandit feedback, aiming to minimize the deficit against the maximin pure strategy — a metric we term Pure-Strategy Maximin Regret. We analyze this problem under two bandit feedback models: uninformed (only the realized reward is revealed) and informed (both the reward and the opponent’s action are revealed). For uninformed bandit learning of normal-form games, we show that the Tsallis-INF algorithm achieves 𝒪(c log T) instance-dependent regret with a game-dependent parameter c. Crucially, we prove an information-theoretic lower bound showing that the dependence on c is necessary. To overcome this hardness, we turn to the informed setting and introduce Maximin-UCB, which obtains another regret bound of the form 𝒪(c’ log T) for a different game-dependent parameter c’ that could potentially be much smaller than c. Finally, we generalize both results to bilinear games over an arbitrary, large action set, proposing Tsallis-FTRL-SPM and Maximin-LinUCB for the uninformed and informed settings respectively and establishing similar game-dependent logarithmic regret bounds.

Online strategic classification studies settings in which agents strategically modify their features to obtain favorable predictions. For example, given a classifier that determines loan approval based on credit scores, applicants may open or close credit cards and bank accounts to obtain a positive prediction. The learning goal is to achieve low mistake or regret bounds despite such strategic behavior. While randomized algorithms have the potential to offer advantages to the learner in strategic settings, they have been largely underexplored. In the realizable setting, no lower bound is known for randomized algorithms, and existing lower bound constructions for deterministic learners can be circumvented by randomization. In the agnostic setting, the best known regret upper bound is O(T^3/4log^1/4(T|ℋ|)) due to Ahmadi et al. (2023), which is far from the standard online learning rate of O(√(Tlog|ℋ|)). In this work, we provide refined upper and lower bounds for online strategic classification in both the realizable and agnostic settings; our bounds depend on the Littlestone dimension Ldim(ℋ) of the hypothesis class ℋ and the maximum degree Δ of the manipulation graph. In the realizable setting, using a new construction, we prove a lower bound that, for T > Ldim(ℋ) Δ^2, extends the existing deterministic lower bound of Ω(Ldim(ℋ) Δ) to all algorithms. This is the first lower bound that applies to randomized algorithms, resolving an open question of Ahmadi et al. (2023). We also give the first randomized algorithm that improves on the known deterministic upper bound of O(Ldim(ℋ)·ΔlogΔ), achieving O(√(T·Ldim(ℋ)logΔ)) expected mistakes, in the regime T < Ldim(ℋ) Δ^2logΔ. In the agnostic setting, we give an improper randomized algorithm with expected regret O(√(Tlog|ℋ|)) against adaptive adversaries, improving upon the previous O(T^3/4log^1/4(T|ℋ|)) bound and matching the standard online learning rate. We also prove that this optimal rate requires improper learning.

Omniprediction is a learning problem that requires suboptimality bounds for each of a family of losses ℒ against a family of comparator predictors 𝒞. We initiate the study of omniprediction in a multiclass setting, where the comparator family 𝒞 may be infinite. Our main result is an extension of the recent binary omniprediction algorithm of Okoroafor et al. (2025) to the multiclass setting, with sample complexity (in statistical settings) or regret horizon (in online settings) ≈ε^-(k+1), for ε-omniprediction in a k-class prediction problem. En route to proving this result, we design a framework of potential broader interest for solving Blackwell approachability problems where multiple sets must simultaneously be approached via coupled actions.

Understanding the fundamental limits of recovering planted subgraphs in random graphs is a central challenge in high-dimensional statistics and theoretical computer science. While existing work has largely focused on special subgraph families such as cliques, bicliques, or dense blocks, the exact recovery of a general planted subgraph in Erdős–Rényi random graphs remains poorly understood. In this paper, we study the exact recovery of an arbitrary planted subgraph Γ = Γ_n embedded in a dense Erdős–Rényi random graph 𝒢(n,q_n), where edges within Γ are present independently with probability p_n > q_n. Our main results identify sharp conditions under which exact recovery is possible with high probability, and we establish matching lower bounds showing the necessity of these conditions. The resulting statistical threshold is characterized by a new graph-theoretic quantity, which we term the minimal maximum subgraph density. This quantity is defined as the maximum subgraph density of the smallest induced balanced subgraph of Γ. We then turn to the problem of recovery under polynomial-time constraints. We propose a computationally efficient recovery algorithm that applies to arbitrary planted subgraphs and analyze its performance in terms of certain spectral properties of the adjacency matrix. In addition, we derive computational lower bounds for recovery using the low-degree polynomial framework, establishing regimes where recovery is statistically possible but computationally hard. Finally, we consider several extensions of our setting, including recovery in semi-random models and weaker notions of recovery.

Continuous diffusion models have demonstrated remarkable generative performance across diverse domains but are often constrained by the computational cost of simulating reverse Ornstein–Uhlenbeck processes via SDE/ODE solvers. Existing theoretical results typically establish query complexities that scale polynomially with both the dimension d and the error tolerance ϵ (e.g., 𝒪̃(d/ϵ)). This mirrors the limitations of unadjusted Langevin algorithm, where standard first-order score solvers lack access to zeroth-order density information, precluding natural error-correction mechanisms and thus preventing the fast ln(1/ϵ) convergence attainable by Metropolis-adjusted methods. In this paper, we develop an improved generative modeling method by introducing Quantized Transition Diffusion (QTD), a framework that reformulates continuous diffusion into a discrete generation problem through spatial quantization and the parameterization of zeroth-order information (e.g., density ratios). To sample from this discrete target, we propose a truncated uniformization algorithm that simulates the underlying continuous-time Markov chain of the discrete diffusion process without discretization error, while eliminating the restrictive bounded-score assumption required by prior uniformization-based approaches. Consequently, QTD attains ϵ-accuracy in total variation distance with a query complexity of 𝒪(d ln^2(d/ϵ)), yielding a notable improvement in ϵ-dependence compared to existing continuous diffusion samplers. Crucially, our analysis capitalizes on a novel proof technique based on the infinitesimal chain rule of KL divergence, providing a fresh perspective on unifying continuous and discrete diffusion paradigms.