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

Learning from Biased and Costly Data Sources: Minimax-optimal Data Collection under a Budget (extended abstract)

Michael O Harding, Vikas Singh, Kirthevasan Kandasamy

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.

COLT 2026

Price of metric universality in vector quantization is at most 0.11 bit

Alina Harbuzova, Or Ordentlich, Yury Polyanskiy

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.

COLT 2026

Is Multi-Distribution Learning as Easy as PAC Learning: Sharp Rates with Bounded Label Noise

Rafael Hanashiro, Abhishek Shetty, Patrick Jaillet

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.

COLT 2026

An Empirical Bayes Perspective on Heteroskedastic Mean Estimation

Yanjun Han, Abhishek Shetty, Jacob Shkrob

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.

COLT 2026

High Probability Convergence Guarantees of Stochastic Gradient Descent Ascent in Structured Nonconvex Min-Max Games

Junsoo Ha

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.

COLT 2026

Functional Stochastic Localization

Anming Gu, Bobby Shi, Kevin Tian

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.

COLT 2026

A Unified Lower Bound on the Noisy Query Complexity of Boolean Functions

Yuzhou Gu, Xin Li, Yinzhan Xu

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.

COLT 2026

Computing Lewis weights to high precision using local relative smoothness

Sander Gribling, Aaron Sidford, Chenyi Zhang

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.

COLT 2026

Randomization for Faster Exact Optimization of Discounted Markov Decision Processes

Andrei Graur, Aaron Sidford, Ta-Wei Tu

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.

COLT 2026

Compact Geometric Representations of Hierarchies

Prashant Gokhale, Piotr Indyk, Yuhao Liu, Sandeep Silwal, Tony Wang, Haike Xu

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.

COLT 2026

Testing Noise Assumptions of Learning Algorithms

Surbhi Goel, Adam Klivans, Konstantinos Stavropoulos, Arsen Vasilyan

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.

COLT 2026

Information-Theoretic Thresholds for Bipartite Latent-Space Graphs Under Noisy Observations

Andreas Göbel, Marcus Pappik, Leon Schiller

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.

COLT 2026

Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares

Andreas Göbel, Janosch Ruff, Leon Schiller

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.

COLT 2026

Sample-Efficient Omniprediction for Proper Losses

Isaac Gibbs, Ryan J. Tibshirani

We study the problem of constructing probabilistic predictions that lead to effective decisions when employed by downstream users to inform actions. Given a single decision maker, developing an optimal predictor is equivalent to minimizing a proper loss function corresponding to the negative utility of that individual. For multiple decision makers, our problem can be viewed as a variant of omniprediction in which the goal is to develop a single predictor which simultaneously minimizes multiple losses. Existing algorithms for achieving omniprediction broadly fall into two categories: first, boosting methods, which optimize auxiliary targets such as multicalibration and obtain omniprediction as a corollary, and second, adversarial two-player game based approaches, which estimate and respond to the worst-case loss in an online fashion. We give lower bounds which demonstrate that multicalibration is a strictly more difficult problem than omniprediction and hence the first approach must incur suboptimal sample complexity. For the latter approach, we discuss how these ideas can be used to obtain a sample-efficient algorithm for our problem through an online-to-batch conversion. This conversion has the downside of returning a complex, randomized predictor. We therefore improve on this method by designing a more direct nonrandomized algorithm that exploits structural elements of the set of proper losses.

COLT 2026

On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach

George Giapitzakis, Kimon Fountoulakis, Eshaan Nichani, Jason D. Lee

Semiautomata form a rich class of sequence-processing algorithms with applications in natural language processing, robotics, computational biology, and data mining. We establish the first Statistical Query hardness result for semiautomata under the uniform distribution over input words and initial states. We show that Statistical Query hardness can be established when both the alphabet size and input length are polynomial in the number of states. Unlike the case of deterministic finite automata, where hardness typically arises through the hardness of the language they recognize (e.g., parity), our result is derived solely from the internal state-transition structure of semiautomata. Our analysis reduces the task of distinguishing the final states of two semiautomata to studying the behavior of a random walk on the group S_N× S_N. By applying tools from Fourier analysis and the representation theory of the symmetric group, we obtain tight spectral gap bounds, demonstrating that after a polynomial number of steps in the number of states, distinct semiautomata become nearly uncorrelated, yielding the desired hardness result.

COLT 2026

Universality of high-dimensional scaling limits of stochastic gradient descent (extended abstract)

Reza Gheissari, Aukosh Jagannath

We consider statistical tasks in high dimensions whose loss depends on the data only through its projection into a fixed-dimensional subspace spanned by the parameter vectors and certain ground truth vectors. This includes classifying mixture distributions with cross-entropy loss with one and two-layer networks, and learning single and multi-index models with one and two-layer networks. When the data is drawn from an isotropic Gaussian mixture distribution, it is known that the evolution of a finite family of summary statistics under stochastic gradient descent converges to an autonomous ordinary differential equation (ODE), as the dimension and sample size go to ∞ and the step size goes to 0 commensurately. Our main result is that these ODE limits are universal in that this limit is the same whenever the data is drawn from mixtures of arbitrary product distributions whose first two moments match the corresponding Gaussian distribution, provided the initialization and ground truth vectors are coordinate-delocalized. We complement this by proving two corresponding non-universality results. We provide a simple example where the ODE limits are non-universal if the initialization is coordinate aligned. We also show that the stochastic differential equation limits arising as fluctuations of the summary statistics around their ODE’s fixed points are not universal.

COLT 2026

Fixed-Parameter Tractability of Private Synthetic Data Generation

Badih Ghazi, Cristóbal Guzmán, Pritish Kamath, Alexander Knop, Ravi Kumar, Pasin Manurangsi

We study the problem of generating synthetic data under differential privacy. We establish fixed-parameter tractability (FPT) for this problem where the parameter is the treewidth of the query family’s incidence graph. Our algorithms attain optimal error rates across all regimes and are realized by two different approaches: the first is based on linear programming (LP) and the FPT of the separation problem for the LP dual; the second is based on a subsampled private multiplicative weights method, where we obtain FPT for sampling from Gibbs distributions. Both approaches are unified by a dynamic programming framework over a tree decomposition.

COLT 2026

Nearly Linear-Time User-Level DP-SCO with Optimal Rates

Badih Ghazi, Ravi Kumar, Daogao Liu, Pasin Manurangsi

User-level differentially private (DP) stochastic convex optimization has garnered significant attention due to the paramount importance of safeguarding user privacy in modern large-scale ML applications. Current methods, such as those based on DP stochastic gradient descent (SGD), often struggle with high gradient computation complexity or suboptimal utility due to the need to privatize every intermediate iterate. In this work, we introduce a new nearly linear-time algorithm that resolves this trade-off and achieves the optimal excess rates via an adaptive outlier removal framework. Our key innovation is integrating the sparse vector technique directly into the SGD loop, supported by a novel robust divergence analysis. This approach naturally bounds the sensitivity of gradient estimates without requiring privatization of all intermediate steps. Specifically, our mechanism computes a local concentration score to adaptively filter out users whose updates diverge from the population geometry. Crucially, this approach preserves the unbiasedness of the gradient estimate in well-concentrated regimes while strictly bounding sensitivity in the presence of outliers. We also explore extensions to the ℓ_∞ setting demonstrating the generality of our analysis.

COLT 2026

Fast and Large-Scale Unbalanced Optimal Transport via its Semi-Dual and Adaptive Gradient Methods

Ferdinand Genans

Unbalanced Optimal Transport (UOT) has emerged as a robust relaxation of standard Optimal Transport, particularly effective for handling outliers and mass variations. However, scalable algorithms for UOT, specifically those based on Gradient Descent (SGD), remain largely underexplored. In this work, we address this gap by analyzing the semi-dual formulation of Entropic UOT and demonstrating its suitability for adaptive gradient methods. While the semi-dual is a standard tool for large-scale balanced OT, its geometry in the unbalanced setting appears ill-conditioned under standard analysis. Specifically, worst-case bounds on the marginal penalties using χ^2 divergence suggest a condition number scaling with n/ε, implying poor scalability. In contrast, we show that the local condition number actually scales as 𝒪(1/ε), effectively removing the ill-conditioned dependence on n. Exploiting this property, we prove that SGD methods adapt to this local curvature, achieving a convergence rate of 𝒪(n/ε T) in the stochastic and online regimes, making it suitable for large-scale and semi-discrete applications. Finally, for the full batch discrete setting, we derive a nearly tight upper bound on local smoothness depending solely on the gradient. Using it to adapt step sizes, we propose a modified Adaptive Nesterov Accelerated Gradient (ANAG) method on the semi-dual functional and prove that it achieves a local complexity of 𝒪(n^2√(1/ε)ln(1/δ)).

COLT 2026

Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs

David Gamarnik, Miklos Z. Racz, Gabe Schoenbach

We study the problem of efficiently finding large common induced subgraphs of two independent Erdős–Rényi random graphs G_1, G_2 ∼𝔾(n,1/2). Recently, Chatterjee and Diaconis (2023) showed that the largest common induced subgraph of G_1 and G_2 has size (4-o(1))log_2 n with high probability. We first show that a simple greedy online algorithm finds a common induced subgraph of G_1 and G_2 of size (2-o(1)) log_2 n with high probability. Our main result shows that no online algorithm can find a common induced subgraph of G_1 and G_2 of size at least (2+ε) log_2 n with probability bounded away from 0 as n →∞. Together, these results provide evidence that this problem exhibits a computation-to-optimization gap. To prove the impossibility result, we show that the solution space of the problem exhibits a version of the (multi) overlap gap property (OGP), and utilize an interpolation argument recently developed by Gamarnik, Kızıldağ, and Warnke (2025) that connects OGP and online algorithms.

Keep browsing

More papers from top AI conferences

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