COLT 2026 Papers

Offline policy learning has received growing attention in causal inference. The primary objective is to learn a policy (individualized treatment rule) as a mapping from covariates to treatment that maximizes the empirical welfare defined as the mean of scalar-valued potential outcomes. In this paper, we study offline policy learning with distribution-valued outcomes, where each potential outcome is a probability measure on ℝ and the reward is defined through a utility functional applied to the Wasserstein barycenter of induced outcome distributions. We establish statistical guarantees for the policy learning framework based on both Inverse Probability Weighting (IPW) and Doubly Robust (DR) estimators. By handling the challenging uniform deviation over the product of the combinatorial policy class and the infinite-dimensional quantile domain, we prove that the finite-sample regret has leading dependence 𝒪(√(N-dim(Π)/N)). In the one-dimensional Wasserstein setting and under the stated regularity conditions, the leading regret rate is still governed by the policy-class complexity. Moreover, we provide a minimax lower bound establishing the sharpness of the leading dependence on N and N-dim(Π).

Multicalibration (Hébert-Johnson et al., 2018) is an algorithmic fairness perspective which demands that the predictions of a predictor are correct conditional on themselves and membership in a collection of potentially overlapping subgroups of a population. The work of Noarov and Roth (2023) established a surprising connection between multicalibration for an arbitrary property Γ (e.g., mean or median) and property elicitation: a property Γ can be multicalibrated if and only if it is elicitable, where elicitability is the notion that the true property value of a distribution can be obtained by solving a regression problem over the distribution. In the adversarial (online) setting, Noarov and Roth (2023) proposed an inefficient algorithm that achieves 𝒪̃(√(T)) ℓ_2-multicalibration error for a hypothesis class of group membership functions and an elicitable property Γ, after T rounds of interaction between a forecaster and adversary. In this paper, we generalize multicalibration for an elicitable property Γ from group membership functions to arbitrary bounded hypothesis classes and introduce a stronger notion—swap multicalibration, following Gopalan et al. (2023b). Subsequently, we propose an oracle-efficient algorithm which when given access to an online agnostic learner, achieves 𝒪̃(T^1/r+1) ℓ_r-swap multicalibration error with high probability (r ≥ 2) for a hypothesis class with bounded sequential Rademacher complexity and an elicitable property Γ. For the special case of r = 2, this implies an oracle-efficient algorithm that achieves 𝒪̃(T^1/3) ℓ_2-swap multicalibration error, which significantly improves on the previously established bounds for the problem (Noarov and Roth, 2023; Ghuge et al., 2025; Luo et al., 2025a), and completely resolves an open question raised in Garg et al. (2024) on the possibility of an oracle-efficient algorithm that achieves 𝒪̃(√(T)) ℓ_2-mean multicalibration error by answering it in a strongly affirmative sense.

We give a randomized online algorithm that guarantees near-optimal O(√(T)) expected swap regret against any sequence of T adaptively chosen Lipschitz convex losses on the unit interval. This improves the previous best bound of O(T^2/3) and answers an open question from prior work. In addition, our algorithm is efficient: it runs in polynomial time. A key technical idea we develop to obtain this result is to discretize the unit interval into bins at multiple scales of granularity and simultaneously use all scales to make randomized predictions, which we call multi-scale binning and may be of independent interest. A direct corollary of our result is an efficient online algorithm for minimizing the calibration error for general elicitable properties. This result does not require the Lipschitzness assumption of the identification function needed in prior work, making it applicable to median calibration, for which we achieve the first O(√(T)) calibration error guarantee.

Recovering structural information from noisy high-dimensional data is a fundamental task in statistical inference. We investigate the information-theoretic recovery thresholds for a graph hidden in a randomly weighted complete graph. Specifically, an unknown graph H^* ∈ℋ_n is chosen uniformly at random, and hidden in a complete graph of n vertices through edge weights: for an edge e ∈ H^*, its weight is distributed independently according to 𝒫_n; otherwise the edge weight is distributed independently according to 𝒬_n. The goal is to recover the hidden edge set from these noisy observations. Our primary focus on almost exact recovery, where all but a vanishing fraction of the edges of H^* must be identified. By choosing 𝒫 = Bern(1), 𝒬 = Bern(q), this model captures the well-studied planted Erdős-Rényi recovery setting, and other weighted formulations such as Gaussian and Exponential distributions. Assuming a local Lipschitzness of the Rényi divergence between distributions 𝒫_n and 𝒬_n, and a mild density condition for the graphs ℋ_n, we give a unified characterization of the information-theoretic limit for recovering almost all of H (also known as almost exact recovery). Our characterization uses the KL divergence D_KL(𝒫_n𝒬_n) as the signal-to-noise metric. We show that there is a critical threshold D_c governed by the logarithm of the first moment threshold of ℋ_n in the Erdős-Rényi random graph model G(n,p). For any constant η, if D_KL≥ (1+η)D_c, the maximum likelihood estimator (MLE) achieves almost exact recovery; conversely if D_KL≤ (1-η)D_c, almost exact recovery is information-theoretically impossible. Our MLE analysis is based on an extension of (Jian Ding, Yihong Wu, Jiaming Xu, Dana Yang, 2020); While our lower bound involves deriving a distance-based Fano-type inequality based on Sibson’s α-mutual information, and it also extends to the task of partial recovery, in which only a constant λ-fraction of the hidden graph is required to be recovered. As a result, if D_KL≤ (λ-η)D_c, we also proved that the recovery of any λ-fraction must fail with high probability. Another interesting phenomenon exhibited by some of these models is the “All-or-Nothing” (AoN), where one can either recover almost all of the hidden graph or essentially nothing at all. For several natural distributional families, including certain Gaussian, Bernoulli and Exponential regimes, we establish an All-or-Nothing (AoN) threshold phenomenon at the exponential scale. For Gaussians, we obtained an AoN by lifting the sharp almost exact recovery threshold through the I-MMSE relation; For the others, we combine a second-moment argument inspired by planted subgraph recovery (Elchanan Mossel, Jonathan Niles-Weed, Youngtak Sohn, Nike Sun, Ilias Zadik, 2023) with the second-order Rényi divergence. We also provide distributional examples where AoN is not universal at this level of generality, and our partial recovery lower bound is already the best possible.

Uniform laws of large numbers form a cornerstone of Vapnik–Chervonenkis theory, where they are characterized by the finiteness of the VC dimension. In this work, we study uniform convergence phenomena in cartesian product spaces, under assumptions on the underlying distribution that are compatible with the product structure. Specifically, we assume that the distribution is absolutely continuous with respect to the product of its marginals, a condition that captures many natural settings, including product distributions, sparse mixtures of product distributions, distributions with low mutual information, and more. We show that, under this assumption, a uniform law of large numbers holds for a family of events if and only if the linear VC dimension of the family is finite. The linear VC dimension is defined as the maximum size of a shattered set that lies on an axis-parallel line, namely, a set of vectors that agree on all but at most one coordinate. This dimension is always at most the classical VC dimension, yet it can be arbitrarily smaller. For instance, the family of convex sets in ℝ^d has linear VC dimension 2, while its VC dimension is infinite already for d ≥ 2. Our proofs rely on an estimator that departs substantially from the standard empirical mean estimator and exhibits a more intricate structure. We show that such deviations from the standard empirical mean estimator are unavoidable in this setting. Throughout the paper, we propose several open questions, with a particular focus on quantitative sample complexity bounds.

Calibration requires that predictions are conditionally unbiased and, therefore, reliably interpretable as probabilities. A calibration measure quantifies how far a predictor is from perfect calibration. A calibration measure is truthful if it is minimized in expectation when a predictor outputs the ground-truth probabilities. Predicting the true probabilities guarantees perfect calibration, but in reality, when calibration is evaluated on a random sample, all known calibration measures incentivize predictors to lie in order to appear more calibrated. This lack of truthfulness motivated approximately truthful calibration measures in the sequential prediction setting, but no perfectly truthful calibration measure was known to exist even in the more basic batch setting. We design a simple, perfectly and strictly truthful, sound, and complete calibration measure in the batch setting: Averaged Two-Bin Calibration Error (ATB). ATB is quadratically related to two existing calibration measures: the smooth calibration error and the lower distance to calibration. The simplicity of our definition of ATB makes it efficient and straightforward to compute, allowing us to give the first linear-time calibration testing algorithm. We also introduce a general recipe for constructing truthful measures based on the variance additivity of independent random variables, which proves the truthfulness of ATB as a special case and allows us to construct other truthful calibration measures, such as quantile-binned ℓ_2 Expected Calibration Error (ECE).

Data collection is a critical component of modern statistical and machine learning pipelines, particularly when data must be gathered from multiple heterogeneous sources to study a target population of interest. In many use cases, such as medical studies or political polling, different sources incur different sampling costs. Observations often have associated group identities—for example, health markers, demographics, or political affiliations—and the relative composition of these groups may differ substantially, both among the source populations and between sources and target population. Moreover, while group proportions are often known at the source and population levels, individual group membership may only be revealed after data collection. In this work, we study multi-source data collection under a fixed budget, focusing on the estimation of population means and group-conditional means. We show that naive data collection strategies (e.g. attempting to “match” the target distribution) or relying on standard estimators (e.g. sample mean) can be highly suboptimal. Instead, we develop a sampling plan which maximizes the <em>effective sample size</em>—the total sample size divided by D_χ^2(q||p) + 1, where q is the target distribution, p is the aggregated source distribution, and D_χ^2 is the χ^2-divergence. We pair this sampling plan with a classical post-stratified estimator, which is able to leverage large but systematically biased datasets, and upper bound its risk. We provide lower bounds with exactly matching leading terms, proving that our approach achieves the budgeted minimax-optimal risk up to additive lower order terms. Our techniques also extend to prediction problems when minimizing the excess risk. In this setting, we pair the effective-sample-size-maximizing sampling plan with a weighted empirical risk minimzer and upper bound its risk. A key contribution to this end is the development of a general information-theoretic lower bound framework for prediction problems under possibly differing source and target distributions, which may be of independent interest outside of this work. We apply this framework to the case of binary classification to establish a lower bound which matches the upper bound of our proposed approach up to a √(K/q_min)-factor, where K is the number of groups and q_min is the smallest group identity probability under the target distribution q. Our framework enables us to respect the information geometry of the problem via dependence on D_χ^2(q||p) that matches the upper bound, which was not possible with existing techniques.

Fast computation of a matrix product W^⊤ X is a workhorse of modern LLMs. To make their deployment more efficient, a popular approach is that of using a low-precision approximation W in place of true W (“weight-only quantization”). Information theory demonstrates that an optimal algorithm for reducing precision of W depends on the (second order) statistics of X and requires a careful alignment of vector quantization codebook with PCA directions of X (a process known as “waterfilling allocation”). Dependence of the codebook on statistics of X, however, is highly impractical. This paper proves that there exist a universal codebook that is simultaneously near-optimal for all possible statistics of X, in the sense of being at least as good as an X-adapted waterfilling codebook with rate reduced by 0.11 bit per dimension in the case when W is Gaussian. Such universal codebook would be an ideal candidate for the low-precision storage format, a topic of active modern research, but alas the existence proof is non-constructive. Equivalently, our result shows existence of a net in ℝ^n that is a nearly-optimal covering of a sphere simultaneously with respect to all Hilbert norms.

Towards understanding the statistical complexity of learning from heterogeneous sources, we study the problem of multi-distribution learning. Given k data sources, the goal is to output a classifier for each source by exploiting shared structure to reduce sample complexity. We focus on the bounded label noise setting to determine whether the fast 1/ϵ rates achievable in single-task learning extend to this regime with minimal dependence on k. Surprisingly, we show that this is not the case. We demonstrate that learning across k distributions inherently incurs slow rates scaling with k/ϵ^2, even under constant noise levels, unless each distribution is learned separately. A key technical contribution is a structured hypothesis-testing framework that captures the statistical cost of certifying near-optimality under bounded noise–a cost we show is unavoidable in the multi-distribution setting. Finally, we prove that when competing with the stronger benchmark of each distribution’s optimal Bayes error, the sample complexity incurs a multiplicative penalty in k. This establishes a statistical separation between random classification noise and Massart noise, highlighting a fundamental barrier unique to learning from multiple sources.

Towards understanding the fundamental limits of estimation from data of varied quality, we study the problem of estimating a mean parameter from heteroskedastic Gaussian observations where the variances are unknown and may vary across observations. While, with known variances, a simple linear estimator attains the smallest mean squared error, estimation without this knowledge is challenging due to the large number of nuisance parameters. We propose a simple and principled approach based on empirical Bayes: model the observations as if they were i.i.d. from a normal scale mixture and compute the profile maximum likelihood estimator (MLE) for the mean, treating the nonparametric mixing distribution as nuisance. Our result shows that this estimator achieves near-optimal error bounds across various heteroskedastic models in the literature. In particular, for the subset-of-signals problem where an unknown subset of observations has small variance, our estimator adaptively achieves the minimax rate for all signal sizes, including the sharp phase transition, without any tuning parameters. One of our key technical steps is a sharper metric entropy bound for normal scale mixtures, obtained via generalized moment matching and Chebyshev approximation. This approach yields an improved polylogarithmic, rather than polynomial, dependence on problem parameters, which could be of independent interest.

Nonconvex min-max optimization is a cornerstone of modern machine learning. However, its theoretical foundations remain largely limited to in-expectation convergence guarantees, which fail to capture the failure probability of individual training trajectories, particularly in the presence of heavy-tailed noise. In this work, we bridge this gap by establishing the first high-probability convergence guarantees of stochastic gradient descent-ascent (SGDA) in structured nonconvex games, specifically nonconvex-PL (NC-PL) and nonconvex-concave (NC-C) problems. We derive high-probability convergence rates of SGDA matching the best known in-expectation rates in the subgaussian noise regime. Then, we investigate the heavy-tailed noise regime and prove that SGDA cannot guarantee high-probability convergence in general. Finally, we analyze a gradient-clipped variant, SGDAClip, and show that it recovers high-probability convergence guarantees in both NC-PL and NC-C games. Our analysis is based on novel progress quantities that simultaneously bound stationarity and primal-dual martingale terms, which yield self-bounding concentration bounds.

Eldan’s stochastic localization is a probabilistic construction that has proved instrumental to modern breakthroughs in high-dimensional geometry and the design of sampling algorithms. Motivated by sampling under non-Euclidean geometries and the mirror descent algorithm in optimization, we develop a functional generalization of Eldan’s process that replaces Gaussian regularization with regularization by any positive integer multiple of a log-Laplace transform. We further give a mixing time bound on the Markov chain induced by our localization process, which holds if our target distribution satisfies a functional Poincaré inequality. Finally, we apply our framework to differentially private convex optimization in ℓ_p norms for p ∈ [1, 2), where we improve state-of-the-art query complexities in a zeroth-order model.

We study the query complexity of Boolean functions f: 0, 1^n →0, 1 in the noisy query model introduced by Feige, Raghavan, Peleg and Upfal [SICOMP 1994]. In this model, an algorithm can adaptively query the bits of an input vector, but each query result is independently flipped with constant probability p ∈ (0, 1/2); repeated queries are allowed. The noisy query complexity 𝖭_p(f) of a function f is defined as the minimum expected number of queries needed to compute f(x) with error probability at most 1/3, for the worst case input x. We prove a general lower bound on 𝖭_p(f) based on degree statistics of certain subgraphs of the Boolean hypercube. This is the first general lower bound beyond those implied by the simple observation that 𝖭_p(f) is lower bounded by the randomized query complexity. We show that this recovers (up to a constant factor) most previously known lower bounds on the noisy query complexity of Boolean functions, providing a unified framework for understanding these results and simplifying the proofs in several cases. Furthermore, this resolves in the affirmative an open problem of Gu, Li and Xu [COLT 2025] that 𝖭_p(f) = Ω(𝖨(f) log𝖨(f)), where 𝖨(f) denotes the total influence of f. We also apply our general lower bound to obtain tight bounds on the noisy query complexity for several new functions.

We provide algorithms that compute ϵ-estimates of the ℓ_p-Lewis weights of a matrix A ∈ℝ^m × n for p ≥ 4 using O(p^2 log(m/ϵ)) rounds of leverage score computation, where ℓ_p-Lewis weights and leverage scores are both standard measures of row importance. This improves upon the state-of-the-art round complexity of O(p^3 log(m/ϵ)) due to Fazel, Lee, Padmanabha, and Sidford (2022). We obtain our results by carefully applying a local variant of relatively smooth gradient descent to primal and dual forms of the ℓ_p-Lewis weight optimization problem and providing tools to convert between different notions of approximate ℓ_p-Lewis weights. This work subsumes the note “On computing approximate Lewis weights” by Apers, Gribling, and Sidford.

We provide faster running times for exactly solving discounted Markov Decision Processes (DMDPs) in strongly polynomial time. We obtain our results by efficiently reducing computing optimal values and policies in DMDPs to the easier tasks of policy evaluation and computing approximately optimal values. We provide both a straightforward deterministic reduction and a more efficient randomized variant that, together with advances in approximately solving DMDPs, yield our results.

Computing geometric representations of data is a cornerstone of modern machine learning, typically achieved by training dual encoders which map queries and documents into a shared embedding space. Recent work of You et al. [NeurIPS ’25] has extended this approach to hierarchical retrieval, where relevance is determined by the ancestor-descendant relationships in a Directed Acyclic Graph (DAG). While previous work has shown that valid embeddings exist when the number of descendants is small, these bounds degrade significantly for deep hierarchies, requiring dimensions as large as the total number of nodes. In this paper, we investigate compact reachability embeddings for more general graph classes and provide theoretical guarantees for representing hierarchies using embeddings whose dimension depends on structural graph parameters. We prove that for any directed tree, there exists a reachability embedding in constant dimension 3, independent of the tree’s size or depth. We generalize this result to graphs characterized by treewidth t, constructing embeddings of dimension O(t log n), where n is the number of nodes. Complementing these upper bounds, we provide matching or near-matching lower bounds, showing that dimension Ω(n) is necessary for general DAGs and Ω(t / log(n/t)) is required for graphs of treewidth t. We also obtain upper and lower bounds parameterized by the number of cross-edges in the DAG. We additionally show that our embeddings can be constructed on real-world datasets, and that they give much smaller dimensions in high recall regimes compared to prior embeddings with theoretical guarantees.

We pose the following question in computational learning theory: can we efficiently test whether a training set satisfies the assumptions of a given noise model? This question has remained unaddressed despite decades of research on learning in the presence of noise. In this work, we show that this task is tractable and present the first efficient algorithm to test various noise assumptions on the training data. To model this question, we extend the recently proposed testable learning framework of Rubinfeld and Vasilyan (2023) and require a learner to run an associated test that satisfies the following two conditions: (1) whenever the test accepts, the learner outputs a classifier along with a certificate of optimality, and (2) the test must pass for any dataset drawn according to a specified modeling assumption on both the marginal distribution and the noise model. We then consider the problem of learning halfspaces over Gaussian marginals with Massart noise (where each label can be flipped with probability less than 1/2 depending on the input features), and give a fully-polynomial time testable learning algorithm. We also show a separation between the classical setting of learning in the presence of structured noise and testable learning. In fact, for the simple case of random classification noise (where each label is flipped with fixed probability η = 1/2), we show that testable learning requires super-polynomial time while classical learning is trivial.

We study information-theoretic phase transitions for the detectability of latent geometry in bipartite random geometric graphs (RGGs) with Gaussian d-dimensional latent vectors, while only a subset of edges carries latent information, determined by a random mask with i.i.d. 𝖡𝖾𝗋𝗇(q) entries. For any fixed edge density p ∈ (0,1), we determine essentially tight thresholds for this problem as a function of d and q. Our results show that the detection problem is substantially easier if the mask is known up-front, compared to the case where the mask is hidden. Our analysis is built upon a novel Fourier-analytic framework for bounding signed subgraph counts in Gaussian random geometric graphs that exploits cancellations. The resulting bounds are applicable to much larger sub-graphs, which enables tight information-theoretic bounds for all noise levels instead, while the bounds considered in previous works only lead to lower bounds from the lens of low-degree polynomials. As a consequence, we identify the optimal information-theoretic thresholds and rule out computational–statistical gaps. Our bounds further improve upon the bounds on Fourier coefficients of random geometric graphs recently given by Bangachev and Bresler [STOC’24] in the dense bipartite case. We believe the techniques to extend to sparser and non-bipartite settings as well, at least if the considered sub-graphs are sufficiently small, and that they might help resolve open questions in related sparse or noisy detection problems.

We study efficient algorithms for recovering cliques in dense random intersection graphs (RIGs). In this model, d = n^Ω(1) cliques of size approximately k are randomly planted by choosing the vertices to participate in each clique independently with probability δ. While there has been extensive work on recovering one, or multiple disjointly planted cliques in random graphs, the natural extension of this question to recovering overlapping cliques has been, surprisingly, largely unexplored. Moreover, because every vertex can be part of polynomially many cliques, this task is significantly harder than in case of disjointly planted cliques (as recently studied by Kothari, Vempala, Wein and Xu [COLT’23]). In this work we obtain the first efficient algorithms for recovering the community structure of RIGs both from the perspective of exact and approximate recovery. Our algorithms are further robust to noise, monotone adversaries, a certain, optimal number of edge corruptions, and work whenever k ≫√(n log(n)). Our techniques follow the proofs-to-algorithms framework utilizing the sum-of-squares hierarchy. An essential component are certificates for the absence of large cliques outside of the ground-truth. Instead of spectral certificates, a central ingredient are modified versions of the biclique certificates, recently used for semi-random planted clique by Buhai, Kothari and Steurer [STOC’23]. To turn these certificates into robust and efficient algorithms that do not produce “false positives”, we rely on an extremely sharp concentration property for pseudo-distributions which might be of independent interest. Our techniques further extend to the related task of efficient refutation, and lead to algorithms that can not only recover the ground-truth, but also certify the optimality of this clustering.