COLT 2025 Papers

In this paper, we study the online shortest path problem in directed acyclic graphs (DAGs) under bandit feedback against an adaptive adversary. Given a DAG G = (V, E) with a source node v_𝗌 and a sink node v_𝗍, let 𝒳⊆{0,1}^|E| denote the set of all paths from v_𝗌 to v_𝗍. At each round t, we select a path 𝐱_t ∈𝒳 and receive bandit feedback on our loss ⟨𝐱_t, 𝐲_t ⟩∈ [-1,1], where 𝐲_t is an adversarially chosen loss vector. Our goal is to minimize regret with respect to the best path in hindsight over T rounds. We propose the first computationally efficient algorithm to achieve a near-minimax optimal regret bound of 𝒪̃(√(|E|Tlog |𝒳|)) with high probability against any adaptive adversary, where 𝒪̃(·) hides logarithmic factors in the number of edges |E|. Our algorithm leverages a novel loss estimator and a centroid-based decomposition in a nontrivial manner to attain this regret bound. As an application, we show that our algorithm for DAGs provides state-of-the-art efficient algorithms for m-sets, extensive-form games, the Colonel Blotto game, shortest walks in directed graphs, hypercubes, and multi-task multi-armed bandits, achieving improved high-probability regret guarantees in all these settings.

This paper studies the problems of identifiability and estimation in high-dimensional nonparametric latent structure models. We introduce an identifiability theorem that generalizes existing conditions, establishing a unified framework applicable to diverse statistical settings. Our results rigorously demonstrate how increased dimensionality, coupled with diversity in variables, inherently facilitates identifiability. For the estimation problem, we establish near-optimal minimax rate bounds for the high-dimensional nonparametric density estimation under latent structures with smooth marginals. Contrary to the conventional curse of dimensionality, our sample complexity scales only polynomially with the dimension. Additionally, we develop a perturbation theory for component recovery and propose a recovery procedure based on simultaneous diagonalization.

We define “decision swap regret” which generalizes both prediction for downstream swap regret and omniprediction, and give algorithms for obtaining it for arbitrary multi-dimensional Lipschitz loss functions in online adversarial settings. We also give sample complexity bounds in the batch setting via an online-to-batch reduction. When applied to omniprediction, our algorithm gives the first polynomial sample-complexity bounds for Lipschitz loss functions—prior bounds either applied only to linear loss (or binary outcomes) or scaled exponentially with the error parameter even under the assumption that the loss functions were convex. When applied to prediction for downstream regret, we give the first algorithm capable of guaranteeing swap regret bounds for all downstream agents with non-linear loss functions over a multi-dimensional outcome space: prior work applied only to linear loss functions, modeling risk neutral agents. Our general bounds scale exponentially with the dimension of the outcome space, but we give improved regret and sample complexity bounds for specific families of multidimensional functions of economic interest: constant elasticity of substitution (CES), Cobb-Douglas, and Leontief utility functions.

Focusing on the expert problem in online learning, this paper studies the interpolation of several performance metrics via ϕ-regret minimization, which measures the total loss of an algorithm by its regret with respect to an arbitrary action modification rule ϕ. With d experts and T≫ d rounds in total, we present a single algorithm achieving the instance-adaptive ϕ-regret bound Õ{min{√(d-d^unif_ϕ+1),√(d-d^self_ϕ)}·√(T)}, where d^unif_ϕ is the maximum amount of experts modified identically by ϕ, and d^self_ϕ is the amount of experts that ϕ trivially modifies to themselves. By recovering the optimal O(√(Tlog d)) external regret bound when d^unif_ϕ=d, the standard Õ(√(T)) internal regret bound when d^self_ϕ=d-1 and the optimal Õ(√(dT)) swap regret bound in the worst case, we improve upon existing algorithms in the intermediate regimes. In addition, the computational complexity of our algorithm matches that of the standard swap-regret minimization algorithm due to Blum and Mansour (2007). Technically, building on the well-known reduction from ϕ-regret minimization to external regret minimization on stochastic matrices, our main idea is to further convert the latter to online linear regression using Haar-wavelet-inspired matrix features. Then, by associating the complexity of each ϕ instance with its sparsity under the feature representation, we apply techniques from comparator-adaptive online learning to exploit the sparsity in this regression subroutine.

The planted clique problem is a fundamental problem in the study of algorithms and has been extensively studied in various random and semirandom models. It is known that a clique planted in a random graph can be efficiently recovered if the size of the clique is above the conjectured computational threshold of Ω_p(√(n)). A natural question that arises then is: what other planted structures can be efficiently recovered? In this work, we investigate this question by considering random planted and semirandom models for the r-coloring problem. In our model, a subset S ⊆ V of size k is chosen, and an arbitrary r-colorable graph is planted on the subgraph induced by S. Edges between pairs in V ∖ S are added independently with probability p, and an adversary may add arbitrary edges between S and V ∖ S. Our main result is a polynomial-time algorithm that recovers most of the vertices of the planted r-colorable graph when k ≥ c r √(n/p), for some constant c. The key technical contribution is a novel semidefinite programming (SDP) relaxation and a rounding algorithm. Our algorithm is also robust to the presence of a monotone adversary that can insert edges within V ∖ S.

Recent work by Foster et al. (2021, 2022, 2023b) and Xu and Zeevi (2023) developed the framework of decision estimation coefficient (DEC) that characterizes the complexity of general online decision making problems and provides a general algorithm design principle. These works, however, either focus on the pure stochastic regime where the world remains fixed over time, or the pure adversarial regime where the world arbitrarily changes over time. For the hybrid regime where the dynamics of the world is fixed while the reward arbitrarily changes, they only give pessimistic bounds on the decision complexity. In this work, we propose a general extension of DEC that more precisely characterizes this case. Besides applications in special cases, our framework leads to a flexible algorithm design where the learner learns over subsets of the hypothesis set, trading estimation complexity with decision complexity, which could be of independent interest. Our work covers model-based learning and model-free learning in the hybrid regime, with a newly proposed extension of the bilinear classes (Du et al., 2021) to the adversarial-reward case. In addition, our method improves the best-known regret bounds for linear Q^⋆/V^⋆ MDPs in the pure stochastic regime.

The mixing time of a Markov chain determines how fast the iterates of the Markov chain converge to the stationary distribution; however, it does not control the dependencies between samples along the Markov chain. In this paper, we study the question of how fast the samples become approximately independent along popular Markov chains for continuous-space sampling: the Langevin dynamics in continuous time, and the Unadjusted Langevin Algorithm and the Proximal Sampler in discrete time. We measure the dependence between samples via Φ-mutual information, which is a broad generalization of the standard mutual information, and which is equal to 0 if and only if the the samples are independent. We show that along these Markov chains, the Φ-mutual information between the first and the k-th iterate decreases to 0 exponentially fast in k when the target distribution is strongly log-concave. Our proof technique is based on showing the Strong Data Processing Inequalities (SDPIs) hold along the Markov chains. To prove fast mixing of the Markov chains, we only need to show the SDPIs hold for the stationary distribution. In contrast, to prove the contraction of Φ-mutual information, we need to show the SDPIs hold along the entire trajectories of the Markov chains; we prove this when the iterates along the Markov chains satisfy the corresponding Φ-Sobolev inequality, which is implied by the strong log-concavity of the target distribution.

This paper presents new theoretical insights into how diffusion generative models adapt to low-dimensional structure in data distributions. We study two widely used samplers — the denoising diffusion probabilistic model (DDPM) and the denoising diffusion implicit model (DDIM) — and analyze their convergence behavior under the assumption of accurate score estimates. Our main result shows that both DDPM and DDIM require at most O(k/ε) iterations (up to logarithmic factors) to generate samples that are ε-close to the target distribution in total variation distance, where k captures an intrinsic low-dimensional structure of the distribution. Importantly, our theory holds without assuming smoothness or log-concavity. These results provide the first rigorous guarantees for the low-dimensional adaptation capability of DDIM-type samplers, and significantly improve upon prior TV-based convergence bounds for DDPM. Our analysis also highlights the role of discretization coefficients in exploiting low-dimensional structure, and establishes lower bounds that justify the optimality of commonly used parameter choices originally proposed by Ho et al. (2020); Song et al. (2020).

The realizable-to-agnostic transformation (Beimel et al., 2015; Alon et al., 2020) provides a general mechanism to convert a private learner in the realizable setting (where the examples are labeled by some function in the concept class) to a private learner in the agnostic setting (where no assumptions are imposed on the data). Specifically, for any concept class 𝒞 and error parameter α, a private realizable learner for 𝒞 can be transformed into a private agnostic learner while only increasing the sample complexity by O(VC(𝒞)/α^2), which is essentially tight assuming a constant privacy parameter ε = Θ(1). However, when ε can be arbitrary, one has to apply the standard privacy-amplification-by-subsampling technique (Kasiviswanathan et al., 2011), resulting in a suboptimal extra sample complexity of O(VC(𝒞)/α^2ε) that involves a 1/ε factor. In this work, we give an improved construction that eliminates the dependence on ε, thereby achieving a near-optimal extra sample complexity of O(VC(𝒞)/α^2) for any ε≤ 1. Moreover, our result reveals that in private agnostic learning, the privacy cost is only significant for the realizable part. We also leverage our technique to obtain a nearly tight sample complexity bound for the private prediction problem, resolving an open question posed by Dwork and Feldman (2018) and Dagan and Feldman (2020).

Space complexity in learning problems has received a lot of attention in recent years. In this direction, Brown, Bun, and Smith (COLT 2022) studied space complexity lower bounds for several natural learning problems under the one-pass streaming setting. Assuming that the examples are sampled from {0,1}^d and the optimal hypothesis can be encoded using κ bits, they showed learning algorithms with constant error using a near-minimal number of examples, O(κ), require Ω(dκ) bits of memory. Moreover, for a general number N of examples, their memory lower bound takes the form Ω(dκ·κ/N). However, as mentioned by Brown, Bun, and Smith (COLT 2022), the learning process often involves multiple passes over the data. Hence, it is equally important to study the space complexity in the multi-pass streaming setting. The authors conjectured that similar lower bounds should apply but left it as an open problem. In this paper, we resolve this open problem by proving that any L-pass streaming algorithm using N samples requires Ω(dκ·κ/NL) bits of memory. Intuitively, our lower bound shows that a stream of L· N fresh examples is at least as useful as L passes over N examples. A key component of our approach is a lower bound on the information complexity of the problem in the multi-pass streaming setting, a basic problem that may have independent significance. In the problem, one sees a stream of N i.i.d. random bits drawn from either or , and would like to distinguish the two cases. Our results not only extend the previous lower bound on by Brown, Bun, and Smith from the one-pass streaming setting to the more general multi-pass setting, but also cover more general values of p and q.

In this paper, we study the problem of online sparse linear regression (OSLR) where the algorithms are restricted to accessing only k out of d attributes per instance for prediction, which was proved to be NP-hard. Previous work gave polynomial-time algorithms assuming the data matrix satisfies the linear independence of features, the compatibility condition, or the restricted isometry property. We introduce a new polynomial-time algorithm, which significantly improves previous regret bounds (Ito et al., 2017) under the compatibility condition that is weaker than the other two assumptions. The improvements benefit from a tighter convergence rate of the ℓ_1-norm error of our estimators. Our algorithm leverages the well-studied Dantzig Selector, but importantly with several novel techniques, including an algorithm-dependent sampling scheme for estimating the covariance matrix, an adaptive parameter tuning scheme, and a batching online Newton step with careful initializations. We also give novel and non-trivial analyses, including an induction method for analyzing the ℓ_1-norm error, careful analyses on the covariance of non-independent random variables, and a decomposition on the regret. We further extend our algorithm to OSLR with additional observations where the algorithms can observe additional k_0 attributes after each prediction, and improve previous regret bounds (Kale et al., 2017; Ito et al., 2017).

We show that the shortest s-t path problem has the overlap-gap property in (i) sparse 𝔾(n,p) graphs and (ii) complete graphs with i.i.d. Exponential edge weights. Furthermore, we demonstrate that in sparse 𝔾(n,p) graphs, shortest path is solved by O(log n)-degree polynomial estimators, and a uniform approximate shortest path can be sampled in polynomial time. This constitutes the first example in which the overlap-gap property is not predictive of algorithmic intractability for a (non-algebraic) average-case optimization problem.

In this paper, we focus on the matching recovery problem between a pair of correlated Gaussian Wigner matrices with a latent vertex correspondence. Although Polynomial-time algorithms for graph matching have been studied in the line of work (Barak et al. (2019); Ding et al. (2021); Fan et al. (2023a,b); Ganassali and Massoulié (2020); Ganassali et al. (2024a); Mao et al. (2021, 2023a); Ganassali et al. (2024b); Mao et al. (2023b); Ding and Li (2025+, 2023)), many of the efficient algorithms used to achieve matching recovery are believed to be fragile in the sense that adversarially modifying a small fraction of edges could fool the algorithm into outputting a result which deviates strongly from the true underlying matching. Thus, we are particularly interested in a robust version of this problem such that our observation is a perturbed input (A+E,B+F) where (A,B) is a pair of correlated Gaussian Wigner matrices and E,F are adversarially chosen matrices supported on an unknown ϵ n * ϵ n principle minor of A,B, respectively. We propose a vector approximate message passing (vector AMP) algorithm that succeeds in polynomial time as long as the correlation ρ between (A,B) is a non-vanishing constant and ϵ = o( 1/(log n)^20). The main methodological inputs for our result are the iterative random graph matching algorithm proposed in Ding and Li (2025+, 2023) and the spectral cleaning procedure proposed in Ivkov and Schramm (2025). To the best of our knowledge, our algorithm is the first efficient random graph matching type algorithm that is robust under any adversarial perturbations of n^1-o(1) size.

Given an arbitrary subgraph H=H_n and p=p_n∈(0,1), the planted subgraph model is defined as follows. A statistician observes the union of the "signal," which is a random "planted" copy H^* of H, together with random "noise" in the form of an instance of an Erdös-Rényi graph G(n,p). The goal then of the statistician is to recover the planted H^* from the observed graph. Our focus in this work is to understand the minimum mean-squared error (MMSE) in terms of recovering the edges of H^*, as a function of p and H. A recent paper [MNSSZ23] characterizes the graphs for which this MMSE curve undergoes a sharp phase transition from 0 to 1 as p increases, a behavior known as the All-or-Nothing phenomenon, up to a mild density assumption on H. However, their techniques fail to describe the MMSE curves for graphs that do not display such a sharp phase transition. In this paper, we provide a formula for the limiting MMSE curve for any graph H=H_n, up to the same mild density assumption. This curve is expressed in terms of a variational formula over pairs of subgraphs of H, and is inspired by the celebrated subgraph expectation thresholds from probabilistic combinatorics [KK07]. Furthermore, we give a polynomial-time description of the optimizers of this variational problem. This allows one to efficiently compute the MMSE curve for any given dense graph H. The proof relies on a novel graph decomposition as well as a min-max duality theorem which may be of independent interest. Our results generalize to the setting of planting arbitrary monotone boolean properties, where the statistician observes the union of a planted minimal element A⊆[N] of a monotone property and a random Ber(p)^⊗ N vector. In this setting, we provide a variational formula inspired by the so-called "fractional" expectation threshold [Tal10], again describing the MMSE curve (in this case up to a multiplicative constant).

This paper investigates the sublinear regret gu rantees of two non-no-regret algorithms in zero-sum games:Fictitious Play, and Online Gradient Descent with constant stepsizes. In general adversarial online learning settings, both algorithms may exhibit instability and linear regret due to no regularization (Fictitious Play) or small amounts of regularization (Gradient Descent). However, their ability to obtain tighter regret bounds in two-player zero-sum games is less understood. In this work, we obtain strong new regret guarantees for both algorithms on a class of symmetric zero-sum games that generalize the classic three-strategy Rock-Paper-Scissors to a weighted, n-dimensional regime. Under symmetric initializations of the players’ strategies, we prove that Fictitious Play with any tiebreaking rule has O(√(T)) regret, establishing a new class of games for which Karlin’s Fictitious Play conjecture holds. Moreover, by leveraging a connection between the geometry of the iterates of Fictitious Play and Gradient Descent in the dual space of payoff vectors, we prove that Gradient Descent, for almost all symmetric initializations, obtains a similar O(√(T)) regret bound when its stepsize is a sufficiently large constant. For Gradient Descent, this establishes the first “fast and furious” behavior (i.e., sublinear regret without time-vanishing stepsizes) for zero-sum games larger than 2×2.

We study when low coordinate degree functions (LCDF)—linear combinations of functions depending on small subsets of entries of a vector—can test for the presence of categorical structure, including community structure and generalizations thereof, in high-dimensional data. This complements recent results studying the power of LCDF in testing for continuous structure like real-valued signals corrupted by additive noise. We study a general form of stochastic block model (SBM), where a population is assigned random labels and every p-tuple generates an observation according to an arbitrary probability measure associated to the p labels of its members. We show that the performance of LCDF admits a unified analysis for this class of models. As applications, we prove tight lower bounds against LCDF for broad families of previously studied graph and uniform hypergraph SBMs, always matching suitable generalizations of the Kesten-Stigum threshold. We also prove tight lower bounds for group synchronization and abelian group sumset problems under the “truth-or-Haar” noise model, and give an improved analysis of Gaussian multi-frequency group synchronization. In most of these models, for some parameter settings our lower bounds give new evidence for conjectural statistical-to-computational gaps. Finally, interpreting some of our findings, we propose a new analogy between categorical and continuous signals: a general SBM as above behaves qualitatively like a spiked p_*-tensor model of a certain order p_* depending on the parameters of the SBM.

Recent works have characterized the function-space inductive bias of infinite-width bounded-norm single-hidden-layer neural networks as a kind of bounded-variation-type space. This novel neural network Banach space encompasses many classical multivariate function spaces, including certain Sobolev spaces and the spectral Barron spaces. Notably, this Banach space also includes functions that exhibit less classical regularity, such as those that only vary in a few directions. On bounded domains, it is well-established that the Gaussian reproducing kernel Hilbert space (RKHS) strictly embeds into this Banach space, demonstrating a clear gap between the Gaussian RKHS and the neural network Banach space. It turns out that when investigating these spaces on unbounded domains, e.g., all of ℝ^d, the story is fundamentally different. We establish the following fundamental result: Certain functions that lie in the Gaussian RKHS have infinite norm in the neural network Banach space. This provides a nontrivial gap between kernel methods and neural networks by exhibiting functions that kernel methods easily represent, whereas neural networks cannot.

Posterior sampling with the spike-and-slab prior (Mitchell and Beauchamp, 1988), a popular multi-modal distribution used to model uncertainty in variable selection, is considered the theoretical gold standard method for Bayesian sparse linear regression (Carvalho et al., 2009; Rockova, 2018). However, designing provable algorithms for performing this sampling task is notoriously challenging. Existing posterior samplers for Bayesian sparse variable selection tasks either require strong assumptions about the signal-to-noise ratio (SNR) (Yang et al., 2016), only work when the measurement count grows at least linearly in the dimension (Montanari and Wu, 2024), or rely on heuristic approximations to the posterior. We give the first provable algorithms for spike-and-slab posterior sampling that apply for any SNR, and use a measurement count sublinear in the problem dimension. Concretely, assume we are given a measurement matrix X ∈^n × d and noisy observations y = Xθ^⋆ + ξ of a signal θ^⋆ drawn from a spike-and-slab prior π with a Gaussian diffuse density and expected sparsity k, where ξ∼𝒩(0_d, σ^2 I_n). We give a polynomial-time high-accuracy sampler for the posterior π(·| X, y), for any SNR σ^-1 > 0, as long as n ≥ k^3 ·polylog(d) and X is drawn from a matrix ensemble satisfying the restricted isometry property. We further give a sampler that runs in near-linear time ≈ nd in the same setting, as long as n ≥ k^5 ·polylog(d). To demonstrate the flexibility of our framework, we extend our result to spike-and-slab posterior sampling with Laplace diffuse densities, achieving similar guarantees when σ = O(1/k) is bounded.

We study Reinforcement Learning (RL) in environments with large state spaces, where function approximation is required for sample-efficient learning. Departing from a long history of prior work, we consider the weakest possible form of function approximation, called agnostic policy learning, where the learner seeks to find the best policy in a given class $\Pi$, with no guarantee that $\Pi$ contains an optimal policy for the underlying task. Although it is known that sample-efficient agnostic policy learning is not possible in the standard online RL setting without further assumptions, we investigate the extent to which this can be overcome with stronger forms of access to the environment. Specifically: 1) We show that even with a strong function approximation assumption called \emph{policy completeness}, and \emph{generative access}—perhaps the strongest possible access to the MDP—policy learning methods cannot achieve sample complexity guarantees that scale with the intrinsic complexity of exploration, as measured via the \emph{coverability coefficient}[XFB+22] of the MDP. This resolves an open problem posed by [JLR+23] and shows, in a strong, information-theoretic sense, that policy learning methods cannot explore. 2) We study the $\mu$-reset setting, where the learner can roll out from an exploratory reset distribution $\mu$, and investigate whether error amplification can be controlled without policy completeness (which is required for classical results of PSDP [BKSN03] and CPI [KL02]). We show that agnostic policy learning is information-theoretically impossible. We also show algorithm-specific lower bounds for PSDP and CPI under the weaker condition of \emph{policy class realizability}. 3) In light of these lower bounds, we introduce a new model of access called \emph{hybrid resets}, which subsumes both local simulators (which is weaker than generative access) and $\mu$-resets. We show that under hybrid resets, and when the reset distribution satisfies \emph{pushforward concentrability} [XJ21], sample-efficient policy learning is possible in Block MDPs [JKA+17, DKJ+19] via a new algorithm. Since all of our lower bound constructions are Block MDPs, this indicates the significant power of hybrid reset access in agnostic policy learning. On a technical level, we introduce a new algorithmic tool called a \emph{policy emulator} that allows us to efficiently evaluate various policies within a large class $\Pi$. Informally speaking, a policy emulator is the “minimal object” useful for solving policy learning. Instead of learning the Block MDP in a traditional model-based sense (which would require samples scaling with the observation space size), our algorithm leverages hybrid resets to construct a policy emulator in a statistically efficient manner. Taken together, our results reveal intriguing interplays between function approximation and environment access in RL. Extended abstract. Full version appears as \href{https://arxiv.org/abs/2504.05405}{[arXiv:2504.05405, v1]}. Authors are listed in alphabetical order of their last names.