COLT 2025 Papers

The seminal work of (Daniely et al., COLT 2011) introduced the problem of multiclass learning under bandit feedback and provided a combinatorial characterization of its learnability within the framework of PAC learning. In multiclass learning under bandit feedback, there is an unknown data distribution over an instance space 𝒳 and a label space 𝒴 similar to classical multiclass learning, but the learner does not directly observe the correct labels of the i.i.d. training examples. Instead, during each round, the learner receives an example, makes a prediction for its label, and receives bandit feedback only indicating whether the prediction is correct. Despite this restriction, the goal remains the same as in classical multiclass learning. In the present work, we study the problem of multiclass learning under bandit feedback within the framework of universal learning (Bousquet et al., STOC 2021). This makes it possible to study the behavior of learning curves. In the uniform learning framework, no concept class 𝒞 is learnable when the effective label space is unbounded. In contrast, surprisingly, we demonstrate that the universal learnability of concept classes 𝒞 even when the effective label space is unbounded gives rise to a rich theory. More concretely, our primary contribution is a theory that reveals an inherent trichotomy governing instance optimal learning curves in the realizable setting. Moreover, the best achievable universal learning rate for any given concept class can only decay either at an exponential, a linear, or an arbitrarily slow rate. In particular, the trichotomy is combinatorially characterized by the absence of an infinite multiclass Littlestone tree and the combination of an infinite Natarajan Littlestone tree and an infinite progressive Littlestone tree. Furthermore, we introduce novel learning algorithms for achieving instance optimal universal rates.

The universal learning framework has been developed to obtain guarantees on the learning rates that hold for any fixed distribution, which can be much faster than the ones uniformly hold over all the distributions. Given that the Empirical Risk Minimization (ERM) principle being fundamental in the PAC theory and ubiquitous in practical machine learning, the recent work of Hanneke and Xu (2024) studied the universal rates of ERM for binary classification under the realizable setting. However, the assumption of realizability is too restrictive to hold in practice. Indeed, the majority of the literature on universal learning has focused on the realizable case, leaving the non-realizable case barely explored. In this paper, we consider the problem of universal learning by ERM for binary classification under the agnostic setting, where the ”learning curve" reflects the decay of the excess risk as the sample size increases. We explore the possibilities of agnostic universal rates and reveal a compact trichotomy: there are three possible agnostic universal rates of ERM, being either exponential, super-root, or arbitrarily slow. We provide a complete characterization of which concept classes fall into each of these categories. Moreover, we also establish complete characterizations for the target-dependent universal rates as well as the Bayes-dependent universal rates.

Learning theory has traditionally followed a model-centric approach, focusing on designing optimal algorithms for a fixed natural learning task (e.g., linear classification or regression). In this paper, we adopt a complementary data-centric perspective, whereby we fix a natural learning rule and focus on optimizing the training data. Specifically, we study the following question: given a learning rule 𝒜 and a data selection budget n, how well can 𝒜 perform when trained on at most n data points selected from a population of N points? We investigate when it is possible to select n ≪ N points and achieve performance comparable to training on the entire population. We address this question across a variety of empirical risk minimizers. Our results include optimal data-selection bounds for mean estimation, linear classification, and linear regression. Additionally, we establish two general results: a taxonomy of error rates in binary classification and in stochastic convex optimization. Finally, we propose several open questions and directions for future research.

Motivated by alternating learning dynamics in two-player games, a recent work by Cevher et al. (2024) shows that o(√(T)) alternating regret is possible for any T-round adversarial Online Linear Optimization (OLO) problem, and left as an open question whether the same is true for general Online Convex Optimization (OCO). We answer this question in the affirmative by showing that the continuous Hedge algorithm achieves 𝒪̃(d^2/3T^1/3) alternating regret for any adversarial d-dimensional OCO problems. We show that this implies an alternating learning dynamic that finds a Nash equilibrium for any convex-concave zero-sum games or a coarse correlated equilibrium for any convex two-player general-sum games at a rate of 𝒪̃(d^2/3/T^2/3). To further improve the time complexity and/or the dimension dependence, we propose another simple algorithm, Follow-the-Regularized-Leader with a regularizer whose convex conjugate is 3rd-order smooth, for OCO with smooth and self-concordant loss functions (such as linear or quadratic losses). We instantiate our algorithm with different regularizers and show that, for example, when the decision set is the ℓ_2 ball, our algorithm achieves 𝒪̃(T^2/5) alternating regret with no dimension dependence (and a better 𝒪̃(T^1/3) bound for quadratic losses). We complement our results by showing some algorithm-specific alternating regret lower bounds, including a somewhat surprising Ω(√(T)) lower bound for a Regret Matching variant that is widely used in alternating learning dynamics.

We consider the problem of learning an arbitrarily-biased ReLU activation (or neuron) over Gaussian marginals with the squared loss objective. Despite the ReLU neuron being the basic building block of modern neural networks, we still do not understand the basic algorithmic question of whether an arbitrary ReLU neuron is learnable in the non-realizable setting. In particular, all existing polynomial time algorithms only provide approximation guarantees for the better-behaved unbiased setting or restricted bias setting. Our main result is a polynomial time statistical query (SQ) algorithm that gives the first constant factor approximation for arbitrary bias. It outputs a ReLU activation that achieves a loss of O(OPT) + ε in time poly(d,1/ε), where OPT is the loss obtained by the optimal ReLU activation. Our algorithm presents an interesting departure from existing algorithms, which are all based on gradient descent and thus fall within the class of correlational statistical query (CSQ) algorithms. We complement our algorithmic result by showing that no polynomial time CSQ algorithm can achieve a constant factor approximation. Together, these results shed light on the intrinsic limitation of gradient descent, while identifying arguably the simplest setting (a single neuron) where there is a separation between SQ and CSQ algorithms.

In the noisy query model, the (binary) return value of every query (possibly repeated) is independently flipped with some fixed probability p ∈ (0, 1/2). In this paper, we obtain tight bounds on the noisy query complexity of several fundamental problems. Our first contribution is to show that any Boolean function with total influence Ω(n) has noisy query complexity Θ(nlog n). Previous works often focus on specific problems, and it is of great interest to have a characterization of noisy query complexity for general functions. Our result is the first noisy query complexity lower bound of this generality, beyond what was known for random Boolean functions (Reischuk and Schmeltz, FOCS 1991). Our second contribution is to prove that Graph Connectivity has noisy query complexity Θ(n^2 log n). In this problem, the goal is to determine whether an undirected graph is connected, where each query asks for the existence of an edge in the graph. A simple algorithm can solve the problem with error probability o(1) using O(n^2 log n) noisy queries, but no non-trivial lower bounds were known prior to this work. Last but not least, we determine the exact number of noisy queries (up to lower order terms) needed to solve the k-Threshold problem and the Counting problem. The k-Threshold problem asks to decide whether there are at least k ones among n bits, given noisy query access to the bits. We prove that (1± o(1)) nlog (min{k,n-k+1}/δ)/(1-2p)log1-p/p queries are both sufficient and necessary to achieve error probability δ = o(1). Previously, such a result was only known when min{k,n-k+1}=o(n) (Wang, Ghaddar, Zhu and Wang, ALT 2025). We also show a similar (1± o(1)) nlog (min{k+1,n-k+1}/δ)/(1-2p)log1-p/p bound for the Counting problem, where one needs to count the number of ones among n bits given noisy query access and k denotes the answer.

We study the approximation gap between the dynamics of a polynomial-width neural network and its infinite-width counterpart, both trained using projected gradient descent in the mean-field scaling regime. We demonstrate how to tightly bound this approximation gap through a differential equation governed by the mean-field dynamics. A key factor influencing the growth of this ODE is the local Hessian of each particle, defined as the derivative of the particle’s velocity in the mean- field dynamics with respect to its position. We apply our results to the canonical feature learning problem of estimating a well-specified single-index model; we permit the information exponent to be arbitrarily large, leading to convergence times that grow polynomially in the ambient dimension d. We show that, due to a certain "self-concordance" property in these problems - where the local Hessian of a particle is bounded by a constant times the particle’s velocity - polynomially many neurons are sufficient to closely approximate the mean-field dynamics throughout training.

We introduce 𝖯𝖱𝖤𝖬 (Private Relative Error Multiplicative weight update), a new framework for generating synthetic data that achieves a relative error guarantee for statistical queries under (ε, δ)-differential privacy (DP). Namely, for a domain X, a family F of queries f : X→{0, 1}, and ζ > 0, our framework yields a mechanism that on input dataset D ∈ X^n outputs a synthetic dataset D∈ X^n such that all statistical queries in F on D, namely ∑_x ∈ D f(x) for f ∈ F, are within a 1 ±ζ multiplicative factor of the corresponding value on D up to an additive error that is polynomial in log | F|, log | X|, log n, log(1/δ), 1/ε, and 1/ζ. In contrast, any (ε, δ)-DP mechanism is known to require worst-case additive error that is polynomial in at least one of n, | F|, or | X|. We complement our algorithm with nearly matching lower bounds.

This paper studies the problem of inferring a k-factor, specifically a spanning k-regular graph, planted within an Erdős–Rényi random graph 𝒢(n,λ/n). We uncover an interesting “all-something-nothing” phase transition. Specifically, we show that as the average degree λ surpasses the critical threshold of 1/k, the inference problem undergoes a transition from almost exact recovery (“all” phase) to partial recovery (“something” phase). Moreover, as λ tends to infinity, the accuracy of recovery diminishes to zero, leading to the onset of the “nothing” phase. This finding complements the recent result by Mossel, Niles-Weed, Sohn, Sun, and Zadik who established that for certain sufficiently dense graphs, the problem undergoes an “all-or-nothing” phase transition, jumping from near-perfect to near-zero recovery. In addition, we characterize the recovery accuracy of a linear-time iterative pruning algorithm and show that it achieves almost exact recovery when λ < 1/k. A key component of our analysis is a two-step cycle construction: we first build trees through local neighborhood exploration and then connect them by sprinkling using reserved edges. Interestingly, for proving impossibility of almost exact recovery, we construct Θ(n) many small trees of size Θ(1), whereas for establishing the algorithmic lower bound, a single large tree of size Θ(√(nlog n)) suffices.

We give a new algorithm for learning mixtures of k Gaussians (with identity covariance in ℝ^n) to TV error ε, with quasi-polynomial (O(n^poly log(n+k/ε))) time and sample complexity, under a minimum weight assumption. Our results extend to continuous mixtures of Gaussians where the mixing distribution is supported on a union of k balls of constant radius. In particular, this applies to the case of Gaussian convolutions of distributions on low-dimensional manifolds, or more generally sets with small covering number, for which no sub-exponential algorithm was previously known. Unlike previous approaches, most of which are algebraic in nature, our approach is analytic and relies on the framework of diffusion models. Diffusion models are a modern paradigm for generative modeling, which typically rely on learning the score function (gradient log-pdf) along a process transforming a pure noise distribution, in our case a Gaussian, to the data distribution. Despite their dazzling performance in tasks such as image generation, there are few end-to-end theoretical guarantees that they can efficiently learn nontrivial families of distributions; we give some of the first such guarantees. We proceed by deriving higher-order Gaussian noise sensitivity bounds for the score functions for a Gaussian mixture to show that that they can be inductively learned using piecewise polynomial regression (up to poly-logarithmic degree), and combine this with known convergence results for diffusion models.

Follow-the-Regularized-Leader (FTRL) algorithms are a popular class of learning algorithms for online linear optimization (OLO) that guarantee sub-linear regret. However, the choice of regularizer can significantly impact dimension-dependent factors in the regret bound. We present an algorithm that takes as input convex and symmetric action sets and loss sets for a specific OLO instance, and outputs a regularizer such that running FTRL with this regularizer guarantees regret within a universal constant factor of the best possible regret bound. In particular, for any choice of (convex, symmetric) action set and loss set we prove that there exists an instantiation of FTRL that achieves regret within a constant factor of the best possible learning algorithm, strengthening the universality result of Srebro et al., 2011. Our algorithm requires preprocessing time and space exponential in the dimension d of the OLO instance, but can be run efficiently online assuming a membership and linear optimization oracle for the action and loss sets, respectively (and is fully polynomial time for the case of constant dimension d). We complement this with a lower bound showing that even deciding whether a given regularizer is α-strongly-convex with respect to a given norm is NP-hard.

We consider the discrete time infinite horizon average reward restless markovian bandit (RMAB) problem. We propose a model predictive control based non-stationary policy with a rolling computational horizon τ. At each time-slot, this policy solves a τ horizon linear program whose first control value is kept as a control for the RMAB. Our solution requires minimal assumptions and quantifies the loss in optimality in terms of τ and the number of arms, N. We show that its sub-optimality gap is O(1/√(N)) in general, and exp(-Ω(N)) under a local-stability condition. Our proof is based on a framework from dynamic control known as dissipativity. Our solution is easy to implement and performs very well in practice when compared to the state of the art. Further, both our solution and our proof methodology can easily be generalized to more general constrained MDP settings and should thus be of great interest to the burgeoning RMAB community.

The Nyström method is a popular low-rank approximation technique for large matrices that arise in kernel methods and convex optimization. Yet, when the data exhibits heavy-tailed spectral decay, the effective dimension of the problem often becomes so large that even the Nyström method may be outside of our computational budget. To address this, we propose Block-Nyström, an algorithm that injects a block-diagonal structure into the Nyström method, thereby significantly reducing its computational cost while recovering strong approximation guarantees. We show that Block-Nyström can be used to construct improved preconditioners for second-order optimization, as well as to efficiently solve kernel ridge regression for statistical learning over Hilbert spaces. Our key technical insight is that, within the same computational budget, combining several smaller Nyström approximations leads to stronger tail estimates of the input spectrum than using one larger approximation. Along the way, we provide a novel recursive preconditioning scheme for efficiently inverting the Block-Nyström matrix, and provide new statistical learning bounds for a broad class of approximate kernel ridge regression solvers.

We revisit Blackwell’s celebrated approachability problem which considers a repeated vector-valued game between a player and an adversary. Motivated by settings in which the action set of the player or adversary (or both) is difficult to optimize over, for instance when it corresponds to the set of all possible solutions to some NP-Hard optimization problem, we ask what can the player guarantee efficiently, when only having access to these sets via approximation algorithms with ratios α_≥ 1 and 1 ≥α_ > 0, respectively. Assuming the player has monotone preferences, i.e., that he does not prefer a vector-valued loss ℓ_1 over ℓ_2 if ℓ_2 ≤ℓ_1, we establish that given a Blackwell instance with an approachable target set S, the downward closure of the appropriately-scaled set α_α_^-1S is efficiently approachable with optimal rate. In case only the player’s or adversary’s set is equipped with an approximation algorithm, we give simpler and more efficient algorithms.

We study the problem of learning a high-density region of an arbitrary distribution over ℝ^d. Given a target coverage parameter δ, and sample access to an arbitrary distribution 𝒟, we want to output a confidence set S ⊂ℝ^d such that S achieves δ coverage of 𝒟, i.e., ℙ_y ∼𝒟[ y ∈ S ] ≥δ, and the volume of S is as small as possible. This is a central problem in high-dimensional statistics with applications in high-dimensional analogues of finding confidence intervals, uncertainty quantification, and support estimation. In the most general setting, this problem is statistically intractable, so we restrict our attention to competing with sets from a concept class 𝒞 with bounded VC-dimension. An algorithm for learning confidence sets is competitive with class 𝒞 if, given samples from an arbitrary distribution 𝒟, it outputs in polynomial time a set that achieves δ coverage of 𝒟, and whose volume is competitive with the smallest set in 𝒞 with the required coverage δ. This problem is computationally challenging even in the basic setting when 𝒞 is the set of all Euclidean balls. Existing algorithms based on coresets find in polynomial time a ball whose volume is exp(Õ( d/ log d))-factor competitive with the volume of the best ball. Our main result is an algorithm that finds a confidence set whose volume is exp(Õ(d^1/2)) factor competitive with the optimal ball having the desired coverage. It is surprisingly simple and also extends to finding confidence sets competitive against unions of k balls, and improved guarantees under additional assumptions. The algorithm is improper (it outputs an ellipsoid). Combined with our computational intractability result for proper learning balls within an exp(Õ(d^1-o(1))) approximation factor in volume, our results provide an interesting separation between proper and (improper) learning of confidence sets.

We introduce a framework to accelerate the convergence of gradient-based methods with online learning. The framework learns to scale the gradient at each iteration through an online learning algorithm and provably accelerates gradient-based methods asymptotically. In contrast with previous literature, where convergence is established based on worst-case analysis, our framework provides a strong convergence guarantee with respect to the optimal stepsize for the iteration trajectory. For smooth strongly convex optimization, our framework provides an (κ^⋆log(1/ε)) asymptotic complexity result, where κ^⋆ is the condition number achievable by the optimal preconditioner, improving on the previous (√(n)κ^⋆log(1/ε)) result. For smooth convex optimization, we obtain the first convergence guarantee for the widely used hypergradient descent heuristic.

This paper investigates equilibrium computation and the price of anarchy for Bayesian games, which are the fundamental models of games with incomplete information. In normal-form games with complete information, it is known that efficiently computable no-regret dynamics converge to correlated equilibria, and the price of anarchy for correlated equilibria can be bounded for a broad class of games called smooth games. However, in Bayesian games, as surveyed by Forges (1993), several non-equivalent extensions of correlated equilibria exist, and it remains unclear whether they can be efficiently computed or whether their price of anarchy can be bounded. In this paper, we identify a natural extension of correlated equilibria that can be computed efficiently and is guaranteed to have bounds on the price of anarchy in various games. First, we propose a variant of regret called untruthful swap regret. If each player minimizes it in repeated play of Bayesian games, the empirical distribution of these dynamics is guaranteed to converge to communication equilibria, which is one of the extensions of correlated equilibria proposed by Myerson (1982). We present an efficient algorithm for minimizing untruthful swap regret with a sublinear upper bound, which we prove to be tight in terms of the number of types. As a result, by simulating the dynamics with our algorithm, we can approximately compute a communication equilibrium in polynomial time. Furthermore, we extend existing lower bounds on the price of anarchy based on the smoothness arguments from Bayes–Nash equilibria to equilibria obtained by the proposed dynamics.

Neural networks with ReLU activation play a key role in modern machine learning. Understanding the functions represented by ReLU networks is a major topic in current research as this enables a better interpretability of learning processes. Injectivity of a function computed by a ReLU network, that is, the question if different inputs to the network always lead to different outputs, plays a crucial role whenever invertibility of the function is required, such as, e.g., for inverse problems or generative models. The exact computational complexity of deciding injectivity was recently posed as an open problem (Puthawala et al. [JMLR 2022]). We answer this question by proving coNP-completeness. On the positive side, we show that the problem for a single ReLU-layer is still tractable for small input dimension; more precisely, we present a parameterized algorithm which yields fixed-parameter tractability with respect to the input dimension. In addition, we study the network verification problem which is to verify that certain inputs only yield specific outputs. This is of great importance since neural networks are increasingly used in safety-critical systems. We prove that network verification is coNP-hard for a general class of input domains. Our results also exclude constant-factor polynomial-time approximations for the maximum of a function computed by a ReLU network. In this context, we also characterize surjectivity of functions computed by ReLU networks with one-dimensional output which turns out to be the complement of a basic network verification task. We reveal interesting connections to computational convexity by formulating the surjectivity problem as a zonotope containment problem.

We consider linear recurrent neural networks, which have become a key building block of sequence modeling due to their ability for stable and effective long-range modeling. In this paper, we aim at characterizing this ability on the simple but core copy task, whose goal is to build a linear filter of order S that approximates the filter that looks K time steps in the past (which we refer to as the shift-K filter), where K is larger than S. Using classical signal models and quadratic cost, we fully characterize the problem by providing lower bounds of approximation, as well as explicit filters that achieve this lower bound up to constants. The optimal performance highlights an uncertainty principle for this task: the optimal filter has to average values around the K-th time step in the past with a range (width) that is proportional to K/S.