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

Regret Minimization with Adaptive Opponents in Repeated Games

Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu, Kaiqing Zhang

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.

COLT 2026

Online Learning for Uninformed Markov Games: Empirical Nash-Value Regret and Non-Stationarity Adaptation

Junyan Liu, Haipeng Luo, Zihan Zhang, Lillian J. Ratliff

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.

COLT 2026

Fast algorithms for learning a Gaussian under halfspace truncation with optimal sample complexity

Haitong LIU, Deepak Narayanan Sridharan, David Steurer, Manuel Wiedmer

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.

COLT 2026

Optimal Learning Rate Schedules under Functional Scaling Laws: Power Decay and Warmup–Stable–Decay (Extended Abstract)

Binghui Li, Zilin Wang, Fengling Chen, Shiyang Zhao, Ruiheng Zheng, Lei Wu

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.

COLT 2026

Second-Order Bounds for [0,1]-Valued Regression via Betting Loss

Yinan Li, Sungjoon Yoon, Ethan Huang, Kwang-Sung Jun

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.

COLT 2026

Self-Concordant Perturbations for Linear Bandits

Lucas Lévy, Jean-Lou Valeau, Arya Akhavan, Patrick Rebeschini

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.

COLT 2026

A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak–Ruppert Averaging

Wei-Cheng Lee, Francesco Orabona

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.

COLT 2026

Blackwell Approachability and Gradient Equilibrium are Equivalent

Brian W. Lee, Nika Haghtalab, Michael I. Jordan, Ryan J. Tibshirani

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.

COLT 2026

Unified Framework of Distributional Regret in Multi-Armed Bandits and Reinforcement Learning

Harin Lee, Min-hwan Oh

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.

COLT 2026

Adaptive Learning Rates with Surrogate Probability for Follow-the-Perturbed-Leader

Jongyeong Lee, Junya Honda, Shinji Ito, Chansoo Kim

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.

COLT 2026

How Does the ReLU Activation Affect the Implicit Bias of Gradient Descent on High-dimensional Neural Network Regression?

Kuo-Wei Lai, Guanghui Wang, Molei Tao, Vidya Muthukumar

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.

COLT 2026

On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA

Syamantak Kumar, Shourya Pandey, Purnamrita Sarkar, Kevin Tian

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.

COLT 2026

A Distribution Testing Approach to Clustering Distributions

Gunjan Kumar, Yash Pote, Jonathan Scarlett

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.

COLT 2026

Clipping the Price of Adaptivity at the Tail

Itai Kreisler, Yair Carmon, Oliver Hinder

Adaptive stochastic convex optimization (SCO) methods face a fundamental “price of adaptivity” barrier: under the standard set of assumptions, they cannot efficiently adapt to large uncertainty in both the initial distance to optimality and the Lipschitz constant. We circumvent this barrier by requiring a small amount of additional structure common to many learning problems. Specifically, we assume that the objective decomposes into a model and a loss function, enabling us to intervene by modifying the model’s output before it passes to the loss function. Under this assumption, we design a method that clips the learned model output in tail events where it deviates too much from the output of a fixed reference model. Our method matches the optimal bounds for known-parameter SCO up to logarithmic factors in the uncertainty in the distance and Lipschitz parameters, thus efficiently adapting to large uncertainty in both.

COLT 2026

Ambiguous Online Learning

Vanessa Kosoy

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

COLT 2026

Overlap Analysis of the Shortest Path Problem: Local Search, Landscapes, and Franz-Parisi Potential

Frederic Koehler, Joonhyung Shin

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.

COLT 2026

Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift

Shyamal Patel, Adam Klivans, Konstantinos Stavropoulos, Arsen Vasilyan

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.

COLT 2026

Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension

Adam Klivans, Konstantinos Stavropoulos, Arsen Vasilyan

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.

COLT 2026

Spectral Valleys and Sharp Failures in Greedy Determinant Maximization

Rajiv Khanna

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.

COLT 2026

Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning

David Kattermann, Lothar Sebastian Krapp

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.

Keep browsing

More papers from top AI conferences

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