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

The matrix-vector complexity of Ax=b

Michał Dereziński, Ethan N. Epperly, Raphael A Meyer

Matrix–vector algorithms, particularly Krylov subspace methods, are widely viewed as the most effective algorithms for solving large systems of linear equations. This paper establishes lower bounds on the worst-case number of matrix–vector products needed by such an algorithm to approximately solve a general linear system. The first main result is that, for any matrix–vector algorithm which is allowed the use of randomization and can perform products with both a matrix and its transpose, Ω(κlog(1/ε)) matrix–vector products are necessary to solve a linear system with condition number κ to accuracy ε, matching an upper bound for conjugate gradient on the normal equations. The second main result is that one-sided algorithms, which lack access to the transpose, must use n matrix–vector products to solve an n × n linear system, even when the problem is perfectly conditioned. Both main results include explicit constants that match known upper bounds up to a factor of four. These results rigorously demonstrate the limitations of matrix–vector algorithms and confirm the optimality of widely used Krylov subspace algorithms.

COLT 2026

Stochastic Safe Action Model Learning

Zihao Deng, Brendan Juba

Hand-crafting models of interactive domains is challenging, especially when the dynamics of the domain are stochastic. We thus wish to automatically learn such models instead. In this work, we propose an algorithm to learn stochastic planning models where the distribution over the sets of effects for each action has a small support, but the sets may set values to an arbitrary number of attributes. This class captures many benchmark domains, in contrast to prior work that assumed independence of the effects on individual attributes. Our algorithm has polynomial time and sample complexity when the support size is bounded by a constant. Importantly, our method is safe in that we learn offline from example trajectories and we guarantee that actions are only permitted in states where our model of the dynamics is accurate. Moreover, we guarantee approximate completeness of the model, in the sense that if the examples are achieving goals from some distribution, then with high probability there will exist plans in our learned model that achieve goals from the same distribution

COLT 2026

Estimating Ising Models in Total Variation Distance

Constantinos Daskalakis, Vardis Kandiros, Rui Yao

We consider the problem of estimating Ising models over n variables in Total Variation (TV) distance, given l independent samples from the model. While the statistical complexity of the problem is well-understood Devroye et al. (2020), identifying computationally and statistically efficient algorithms has been challenging. In particular, remarkable progress has occurred in several settings, such as when the underlying graph is a tree Daskalakis and Pan (2021); Bhattacharyya et al. (2021), when the entries of the interaction matrix follow a Gaussian distribution Gaitonde and Mossel (2024); Chandrasekaran and Klivans (2024), or when the bulk of its eigenvalues lie in a small interval Anari et al. (2024a); Koehler et al. (2024), but no unified framework for polynomial-time estimation in TV exists so far. Our main contribution is a unified analysis of the Maximum Pseudo-Likelihood Estimator (MPLE) for two general classes of Ising models. The first class includes models whose interaction matrix has a bounded operator norm. In particular, we focus on the subclass of models that satisfy the Modified Log-Sobolev Inequality (MLSI), a functional inequality that was introduced to study the convergence of the associated Glauber dynamics to stationarity. In the second class of models, the interaction matrix has bounded infinity norm (or bounded width), which is the most common assumption in the literature for structure learning of Ising models. We show how our general results for these classes yield polynomial-time algorithms and optimal or near-optimal sample complexity guarantees in a variety of settings. Our proofs employ a variety of tools from tensorization inequalities to measure decompositions and concentration bounds

COLT 2026

Rigorous Asymptotics for First-Order Algorithms Through the Dynamical Cavity Method

Yatin Dandi, David Gamarnik, Francisco Pernice, Lenka Zdeborova

Dynamical Mean Field Theory (DMFT) provides an asymptotic description of the dynamics of macroscopic observables in certain disordered systems. Originally pioneered in the context of spin glasses, it has since been used to derive asymptotic dynamical equations for a wide range of models in physics, high-dimensional statistics and machine learning. One of the main tools used by physicists to obtain these equations is the dynamical cavity method, which has remained largely non-rigorous. In contrast, existing mathematical formalizations have relied on alternative approaches, including Gaussian conditioning, large deviations over paths, or Fourier analysis. In this work, we formalize the dynamical cavity method and use it to give a new proof of the DMFT equations for General First Order Methods, a broad class of dynamics encompassing algorithms such as Gradient Descent and Approximate Message Passing.

COLT 2026

Tight Bounds for Logistic Regression with Large Stepsize Gradient Descent in Low Dimension

Michael Crawshaw, Mingrui Liu

We consider the optimization problem of minimizing the logistic loss with gradient descent to train a linear model for binary classification with separable data. With a budget of T iterations, it was recently shown that an accelerated 1/T^2 rate is possible by choosing a large stepsize η = Θ(γ^2 T) (where γ is the dataset’s margin) despite the resulting non-monotonicity of the loss. In this paper, we provide a tighter analysis of gradient descent for this problem when the data is two-dimensional: we show that GD with a sufficiently large learning rate η finds a point with loss smaller than 𝒪(1/(ηγ^2 T)), as long as T ≥Ω(n/γ + 1/γ^2), where n is the dataset size. Our improved rate comes from a tighter bound on the time τ that it takes for GD to transition from unstable (non-monotonic loss) to stable (monotonic loss), via a fine-grained analysis of the oscillatory dynamics of GD in the subspace orthogonal to the max-margin classifier. We also provide a lower bound of τ matching our upper bound up to logarithmic factors, showing that our analysis is tight.

COLT 2026

Eigen-Spike Emergence and Quadratic Equivalents for Conjugate Kernels on Nonlinearly Separable Data

Collin Cranston, Zhichao Wang, Todd Kemp, W. Michael Mahoney

Recent work in random matrix theory (RMT) has developed the notion of deterministic equivalents: typically linear surrogate models that approximate the spectral behavior of large nonlinear random matrices, such as nonlinear feature maps in neural networks (NNs). Such equivalents make theoretical predictions tractable by reducing a complex model to a simpler one with properties that fall under the umbrella of classical RMT tools. However, this leaves open the question of whether this idealized linear equivalence remains meaningful when dealing with classification problems of high-dimensional nonlinearly separable data. Motivated by this, we consider the conjugate kernel (CK), which is the nonlinear feature map of a one-layer feedforward NN, under a canonical nonlinearly separable dataset for the XOR problem; and we use the study of informative outlier eigenvalues in the CK and whether their corresponding eigenvectors asymptotically align with XOR labels as a proxy for nonlinear learnability. We develop a robust quadratic equivalent of the CK matrix that enables a precise analysis of emergent informative spikes, as one modifies various knobs common in ML practice: sample complexity, signal-to-noise ratio (SNR), nonlinear activation choice, and pretrained features. We identify regimes in which these knobs move the CK beyond the linear equivalent and produce BBP-type transitions to label-aligned outlier eigenspaces. Our analysis helps bring deterministic-equivalence tools from RMT to bear on problems of practical relevance in ML.

COLT 2026

Density estimation for Hellinger via minimum-distance estimators: mixtures of Gaussians, log-concave, and more

Spencer Compton, Jerry Li

We study the task of density estimation, where we hope to accurately estimate a probability density from n samples. A textbook method for density estimation in total variation distance is the minimum-distance estimator approach, where we conclude both the algorithm and the analysis merely from bounding the VC dimension of a particular concept class (the so-called Yatracos class). While this technique has originally yielded sharp guarantees primarily for total variation distance, in this work we extend the minimum-distance estimator approach for learning within Hellinger distance. Our main observation is that we may produce an analogous recipe for Hellinger (where we only require bounding the VC dimension of a related concept class) by drawing connections to recent results yielding reverse data processing inequalities. This recipe is flexible enough to accommodate fast algorithms originally designed for total variation distance; by modifying the approach of Acharya et al. (2017) we conclude the first near-linear time algorithm for learning classes including univariate mixtures of log-concave densities and mixtures of Gaussians (with arbitrary variances), with near-optimal sample complexity.

COLT 2026

DDPM Score Matching and Distribution Learning (Extended Abstract)

Sinho Chewi, Alkis Kalavasis, Anay Mehrotra, Omar Montasser

Score estimation is the backbone of score-based generative models (SGMs), and particularly denoising diffusion probabilistic models (DDPMs). A fundamental theoretical result in this area is that, given access to accurate score estimates, SGMs can efficiently generate from any realistic data distribution (Chen, Chewi, Li, Li, Salim, and Zhang, ICLR’23; Lee, Lu, and Tan, ALT’23). This can be viewed as a result on distribution learning, where the learned distribution is implicit as the law of the output of a sampler. However, it is unclear how score estimation relates to more classical forms of distribution learning, such as parameter estimation and density estimation. We present a framework reducing the other two forms of distribution learning to score estimation, which has various implications in statistical and computational learning theory: parameter estimation, where denoising score matching in DDPMs is asymptotically efficient; density estimation, where estimated scores can be lifted to a (ϵ,δ)-PAC density estimator and yield minimax rates over Hölder classes and a quasi-polynomial PAC density estimation algorithm for Gaussian location mixtures; and lower bounds for score estimation, where PAC density estimation yields computational lower bounds for score estimation of general distribution families and cryptographic lower bounds for score estimation of general Gaussian mixture models.

COLT 2026

Is Memorization Helpful or Harmful? Prior Information Sets the Threshold

Chen Cheng, Rina Foygel Barber

We examine the connection between training error and generalization error for arbitrary estimating procedures, working in an overparameterized linear model under general priors in a Bayesian setup. We find determining factors inherent to the prior distribution π, giving explicit conditions under which optimal generalization necessitates that the training error be (i) near interpolating relative to the noise size (i.e., memorization is necessary), or (ii) close to the noise level (i.e., overfitting is harmful). Remarkably, these phenomena occur when the noise reaches thresholds determined by the Fisher information and the variance parameters of the prior π.

COLT 2026

Calibeating Made Simple

Yurong Chen, Zhiyi Huang, Michael I. Jordan, Haipeng Luo

We study calibeating, the problem of post-processing external forecasts online to minimize cumulative losses and match an informativeness-based benchmark. Unlike prior work, which analyzed calibeating for specific losses with specific arguments, we reduce calibeating to existing online learning techniques and obtain results for general proper losses. More concretely, we first show that calibeating is minimax-equivalent to regret minimization. This recovers the O(log T) calibeating rate of Foster and Hart (2023) for the Brier and log losses and its optimality, and yields new optimal calibeating rates for exp-concave losses and general bounded losses. Second, we prove that multi-calibeating is minimax-equivalent to the combination of calibeating and the classical expert problem. This yields new optimal multi-calibeating rates for exp-concave losses, including Brier and log losses, and general bounded losses. Finally, we obtain new bounds for achieving calibeating and calibration simultaneously for the Brier loss. For binary predictions, our result gives the first calibrated algorithm that at the same time also achieves the optimal O(log T) calibeating rate.

COLT 2026

High-Accuracy Log-Concave Sampling with Stochastic Queries

Fan Chen, Sinho Chewi, Constantinos Daskalakis, Alexander Rakhlin

We show that high-accuracy guarantees for log-concave sampling—that is, iteration and query complexities which scale as polylog(1/δ), where δ is the desired target accuracy—are achievable using stochastic gradients with sub-exponential tails. Notably, this exhibits a separation with the problem of convex optimization, where stochasticity (even additive Gaussian noise) in the gradient oracle incurs poly(1/δ) queries. We also give an information-theoretic argument that light-tailed stochastic gradients are necessary for high accuracy: for example, in the bounded variance case, we show that the minimax-optimal query complexity scales as Θ(1/δ). Our framework also provides similar high-accuracy guarantees under stochastic zeroth-order (value) queries, and an improved complexity result for sampling from finite-sum potentials.

COLT 2026

Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression

Fan Chen, Jian Qian, Alexander Rakhlin, Nikita Zhivotovskiy

Self-normalized martingale inequalities lie at the heart of confidence ellipsoids for online least squares and, more broadly, many bandit and reinforcement-learning results. Yet existing vector and scalar results typically rely on bounded covariates and an explicit regularization matrix, producing bounds that are not scale-invariant: although the self-normalized quantity is scale-invariant by definition, its standard upper bounds are not. We characterize when scale-invariant upper bounds on self-normalized martingales are possible. Without further assumptions, we prove that nontrivial scale-invariant bounds exist only in dimension d=1; moreover, in d=1 we obtain O(log T) scale-invariant self-normalized bounds without any assumptions on the covariates. In contrast, for d>1 we show that no nontrivial scale-invariant bound can hold in full generality. We then connect this dichotomy to doubly-uniform regret in online linear regression (i.e., regret bounds that are simultaneously independent of the covariate scale and the comparator norm) and use it to resolve the open question of Gaillard, Gerchinovitz, Huard, and Stoltz, “Uniform regret bounds over ℝ^d for the sequential linear regression problem with the square loss” (ALT 2019): in d=1 we give an explicit algorithm with O(log T) doubly-uniform regret, whereas for d>1 sublinear doubly-uniform regret is impossible. Finally, under a natural smoothness condition (bounded Radon–Nikodym derivatives of the conditional covariate laws with respect to a fixed base measure), we recover sublinear regret for d>1 without bounded covariates and derive a self-normalized concentration inequality free of the usual regularization penalties, yielding arguably a first natural scale-invariant bound for adaptive, non-i.i.d. vector martingales.

COLT 2026

Optimal Inference Schedules for Masked Diffusion Models

Sitan Chen, Kevin Cong, Jerry Li

A major bottleneck of standard auto-regressive large language models is that their inference process is inherently sequential, resulting in very long and costly inference times. To circumvent this, practitioners proposed a class of language models called diffusion language models, of which the masked diffusion model (MDM) is the most successful. The MDM is able to sample tokens out-of-order and, ostensibly, many tokens at once and in parallel. However, there is very limited rigorous understanding of how much parallel sampling these models can perform without noticeable degradation in their sampling performance. Prior work in Li and Cai (2025) obtained some preliminary bounds, but these are not tight for many natural classes of distributions. In this work, we give a new, exact characterization of the expected divergence between the true distribution and the sampled distribution, for any distribution and any unmasking schedule for the sampler, showing an elegant connection to the theory of univariate function approximation. By leveraging this connection, we then attain a number of novel lower and upper bounds for this problem. While the connection to function approximation in principle gives the optimal unmasking schedule for any distribution, we show that it is in general impossible to compete with it without strong a priori knowledge of the distribution, even in seemingly benign settings. However, we also demonstrate new upper bounds and new sampling schedules in terms of well-studied information-theoretic properties of the base distribution, namely, its total correlation and dual total correlation, which show that in some natural settings, one can sample in O(log n) steps without any visible loss in performance, where n is the total sequence length.

COLT 2026

Information-computation gaps in quantum learning via low-degree likelihood

Sitan Chen, Weiyuan Gong, Jonas Haferkamp, Yihui Quek

In a variety of physically relevant settings for learning from quantum data, there is an established recipe for measuring polynomially many copies of that data such that the resulting measurement readouts contain enough information to reconstruct the underlying system. Yet designing protocols that can computationally efficiently extract that information remains largely an art, and there are important cases where we believe this to be impossible, that is, where there is an information-computation gap. While there is a large array of tools in the classical literature for giving evidence for average-case hardness of statistical inference problems, the corresponding tools in the quantum literature are far more limited. One such framework in the classical literature, the low-degree method, makes predictions about hardness of inference problems based on the failure of estimators given by low-degree polynomials. In this work, we extend this framework to the quantum setting and show a number of new information-computation gaps for quantum learning. We establish a general connection between state designs and low-degree hardness. We use this to obtain the first information-computation gaps for learning Gibbs states of random, sparse, non-local Hamiltonians. We also use it to prove hardness for learning random shallow quantum circuit states in a challenging model where states can be measured in round-based adaptively chosen bases. To our knowledge, the ability to model adaptivity within the low-degree framework was open even in classical settings. In addition, we also obtain a low-degree hardness result for quantum error mitigation against strategies with single-qubit measurements. We define a new quantum generalization of the planted biclique problem and identify the threshold at which this problem becomes computationally hard for protocols that perform local measurements. Interestingly, the complexity landscape for this problem shifts when going from local measurements to more entangled single-copy measurements. We show average-case hardness for the “standard” variant of Learning Stabilizers with Noise (Poremba et al., 2024) and for agnostically learning product states (Bakshi et al., 2024a).

COLT 2026

Instance-optimal high-precision shadow tomography with few-copy measurements: A metrological approach

Senrui Chen, Weiyuan Gong, Sisi Zhou

We give the first instance-optimal sample complexity bounds for shadow tomography using few-copy measurements in the high-precision regime. More concretely, we study the problem of learning expectation values of a given set of observables of an unknown quantum state to precision ϵ in L_p-norm, using (possibly adaptive) measurements that act on one or a few copies at a time, and we are interested in the regime that ϵ is below some concrete and potentially dimension-dependent threshold. In this setup, we prove the necessary and sufficient number of copies, for any given set of observables, is characterized by a simple optimization formula involving a quadratic form of the inverse Fisher information matrix up to a logarithmic factor. Our results establish a rigorous correspondence between quantum learning and quantum metrology.

COLT 2026

Separating Oblivious and Adaptive Models of Variable Selection (Extended Abstract)

Ziyun Chen, Jerry Li, Kevin Tian, Yusong Zhu

Sparse recovery is among the most well-studied problems in learning theory and high-dimensional statistics. In this work, we investigate the statistical and computational landscapes of sparse recovery with ℓ_∞ error guarantees. This variant of the problem is motivated by variable selection tasks, where the goal is to estimate the support of a k-sparse signal in ^d. Our main contribution is a provable separation between the oblivious (“for each”) and adaptive (“for all”) models of ℓ_∞ sparse recovery. We show that under an oblivious model, the optimal ℓ_∞ error is attainable in near-linear time with ≈ klog d samples, whereas in an adaptive model, ≳ k^2 samples are necessary for any algorithm to achieve this bound. This establishes a surprising contrast with the standard ℓ_2 setting, where ≈ k log d samples suffice even for adaptive sparse recovery. We conclude with a preliminary examination of a partially-adaptive model, where we show nontrivial variable selection guarantees are possible with ≈ klog d measurements.

COLT 2026

Faster Newton Methods for Convex and Nonconvex Optimization in Gradient Complexity

Lesi Chen, Chengchang Liu, Luo Luo, Jingzhao Zhang

Second-order optimization methods are computationally expensive for large-scale problems. Recently, Doikov, Chayti, and Jaggi (ICML 2023) proposed the LazyCRN method that reduces computation by studying the gradient complexity of second-order methods. Their method can achieve a gradient complexity of 𝒪( d̅ + d̅^1/2ϵ^-3/2) and 𝒪( d̅ + d̅^1/2ϵ^-1/2) for nonconvex and convex optimization, respectively, where d̅ is the effective dimension and ϵ is the target precision. Very recently, Adil, Bullins, Sidford, and Zhang (NeurIPS 2025) improved the gradient complexity to 𝒪( d̅ + d̅^1/3ϵ^-3/2ln^18ϵ^-1) for nonconvex optimization. However, the tightness of these methods remains open. In this work, we propose new methods that achieve an improved complexity of 𝒪( d̅ + d̅^1/3ϵ^-3/2) and 𝒪( (d̅ + d̅^13/21ϵ^-2/7) lnd̅) for nonconvex and convex optimization, respectively, improving best-known results for both setups.

COLT 2026

A Tight Lower Bound for Non-stochastic Multi-armed Bandits with Expert Advice

Zachary Chase, Shinji Ito, Idan Mehalel

We determine the minimax optimal expected regret in the classic non-stochastic multi-armed bandit with expert advice problem, by proving a lower bound that matches the upper bound of [Kale ’14]. The two bounds determine the minimax optimal expected regret to be Θ( √(T K logN/K)), where K is the number of arms, N is the number of experts, and T is the time horizon.

COLT 2026

Language Identification with Succinct Machine-Independent Traces

Moses Charikar, Jon Kleinberg, Chirag Pabbaraju

Motivated by the power of large language models, there has been renewed interest in the Gold-Angluin model of language identification in the limit, with an eye toward variants of the model that might overcome the negative results for its original formulation. Recent papers on this question have proposed looking at computational traces and annotations of training strings as a source of additional power for a learner, reflecting empirical regularities such as the way that commented source code is easier to learn from than arbitrary source code, and text annotated with algorithmically generated chain-of-thought tokens can be easier to learn from than the raw text itself. This recent work has shown positive results for language identification in the presence of such computational traces, but the traces in these positive results come from explicit automata-theoretic machine models that generate the language, where the underlying vocabulary of tokens for the traces is very large. In this paper, we address two fundamental issues left open by this line of work: can we achieve positive results with traces that use only a small alphabet, and can we define traces directly from the language itself, without requiring an underlying machine model that generates it? We establish positive results for both of these questions: for an arbitrary collection of languages, we show how to define computational traces that enable identification in the limit, using an alphabet of tokens that is linear in the size of the alphabet that the languages are defined over, and independent of any other properties of the languages.

COLT 2026

A Characterization of List Language Identification in the Limit

Moses Charikar, Chirag Pabbaraju, Ambuj Tewari

We study the problem of language identification in the limit, where given a sequence of examples from a target language, the goal of the learner is to output a sequence of guesses for the target language such that all the guesses beyond some finite time are correct. Classical results of Gold showed that language identification in the limit is impossible for essentially any interesting collection of languages. Later, Angluin gave a precise characterization of language collections for which language identification is possible. Motivated by recent positive results for the related problem of language generation, we revisit the classic language identification problem in the setting where the learner is given the additional power of producing a list of k guesses at each time step. The goal is to ensure that beyond some finite time, one of the guesses is correct at each time step. Such list learning versions of several basic learning problems have been widely studied. We give an exact characterization of collections of languages that can be k-list identified in the limit, based on a recursive version of Angluin’s characterization (for language identification with a list of size 1). This further leads to a conceptually appealing characterization: A language collection can be k-list identified in the limit if and only if the collection can be decomposed into k collections of languages, each of which can be identified in the limit (with a list of size 1). We also use our characterization to establish rates for list identification in the statistical setting where the input is drawn as an i.i.d. stream from a distribution supported on some language in the collection. Our results show that if a collection is k-list identifiable in the limit, then the collection can be k-list identified at an exponential rate, and this is best possible. On the other hand, if a collection is not k-list identifiable in the limit, then it cannot be k-list identified at any rate that goes to zero.

Keep browsing

More papers from top AI conferences

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