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

Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Bandits

Hao Qin, Chicheng Zhang

We propose an algorithmic framework, Offline Estimation to Decisions (OE2D), that reduces contextual bandit learning with general reward function approximation to offline regression. The framework allows near-optimal regret for contextual bandits with large action spaces with O(log T) calls to an offline regression oracle over T rounds, and makes O(loglog T) calls when T is known. The design of OE2D generalizes Falcon and its linear-reward version in that it chooses an action distribution that we term the “exploitative F-design” that simultaneously guarantees low regret and good coverage that trades off exploration and exploitation. Central to our regret analysis is a new complexity measure, the Decision-Offline Estimation Coefficient (DOEC), which we show is bounded in the bounded Eluder dimension per-context and smoothed regret settings. We also establish a relationship between DOEC and the Decision Estimation Coefficient (DEC), bridging the design principles of offline- and online-oracle efficient contextual bandit algorithms for the first time.

COLT 2026

Deep Q-Learning on Hölder Spaces

Qian Qi

We study the operator-theoretic core of Q-learning in continuous-time stochastic control with continuous states and actions. In value-based reinforcement learning, each Q-learning or DQN update is built from a Bellman optimality target; our analysis isolates this target in a uniformly elliptic diffusion setting and studies its regularity and approximation complexity. Under Hölder-regular coefficients, we show that a Bellman update maps bounded inputs into an anisotropic regularity class: it smooths the state variable through parabolic regularization while preserving only Lipschitz dependence on the action variable. This identifies a compact family of Bellman iterates and motivates tensor-product neural-operator approximators adapted to the mixed regularity of the problem. We derive explicit approximation and resource bounds, including a stiffness–complexity trade-off as the time step δ→ 0. The result is an operator-level theory for the Bellman targets underlying Q-learning in continuous stochastic control, rather than a convergence theorem for practical sampled DQN training.

COLT 2026

Boosting with List-Decodable Codes

Addison Prairie, Li-Yang Tan

Boosting is a fundamental technique for generically improving the accuracy of learning algorithms (Schapire 1989). Existing boosting algorithms construct a strong learner using O(log(1/ϵ)/γ^2) calls to a γ-advantage weak learner, and this round complexity is known to be optimal for generic boosters that succeed on all concept classes (Freund 1995). We show that this lower bound can be circumvented for concept classes that satisfy a mild closure property. Specifically, we present a new boosting algorithm that, for any class ℱ closed under O(log1/γ)-Xor, strong learns ℱ using O(log1/ϵ) calls to a γ-advantage weak learner and a single batch of O(log(1/ϵ)/γ^2) additional samples. Our algorithm arises from a new and simple connection between boosting and list-decodable codes. Viewing the target function as a message, we run the weak learner on its encoding and view the resulting weak hypothesis as a corrupted codeword. Feeding this corrupted codeword to a list decoder, we obtain a small list of candidate hypotheses, at least one of which is a strong hypothesis for the original function. Using additional samples, we identify and output this strong hypothesis.

COLT 2026

How Many Features Can a Language Model Store Under the Linear Representation Hypothesis?

Nikhil Garg, Jon Kleinberg, Kenny Peng

We introduce a mathematical framework for the linear representation hypothesis (LRH), which asserts that intermediate layers of language models store features linearly. We separate the hypothesis into two claims: linear representation (features are linearly embedded in neuron activations) and linear accessibility (features can be linearly decoded). We then ask: How many neurons d suffice to both linearly represent and linearly access m features? Classical results in compressed sensing imply that for k-sparse inputs, d = O(klog (m/k)) suffices if we allow non-linear decoding algorithms (Candes and Tao, 2006; Candes et al., 2006; Donoho 2006). However, the additional requirement of linear decoding takes the problem out of the classical compressed sensing, into linear compressed sensing. Our main theoretical result establishes nearly-matching upper and lower bounds for linear compressed sensing. We prove that d = Ω_ϵ(k^2/log klog (m/k)) is required while d = O_ϵ(k^2log m) suffices. The lower bound establishes a quantitative gap between classical and linear compressed setting, illustrating how linear accessibility is a meaningfully stronger hypothesis than linear representation alone. The upper bound confirms that neurons can store an exponential number of features under the LRH, giving theoretical evidence for the “superposition hypothesis” (Elhage et al., 2022). The upper bound proof uses standard random constructions of matrices with approximately orthogonal columns. The lower bound proof uses rank bounds for near-identity matrices (Alon, 2003) together with Turán’s theorem (bounding the number of edges in clique-free graphs). We also show how our results do and do not constrain the geometry of feature representations and extend our results to allow decoders with an activation function and bias.

COLT 2026

An Exponential Lower Bound for Spectral Density Estimation on Unweighted Graphs

Pan Peng, Yuyang Wang, Joy Qiping Yang, Yichun Yang

We study lower bounds for estimating the spectral density of the normalized adjacency matrix of a graph. Previously, Cohen-Steiner et al. [KDD 2018] proposed an algorithm for ε-approximate spectral density estimation in the Wasserstein-1 distance, using 2^O(1/ε) random walks initiated from uniformly random nodes in the graph. Later, Jin et al. [COLT 2023] established a nearly matching exponential lower bound for weighted graphs, assuming the algorithm has access to samples from random walks started at random nodes. It was left open whether this lower bound could be extended to unweighted graphs. In this paper, we answer this question in the affirmative by proving an exponential lower bound for unweighted graphs. Specifically, we show that no algorithm can compute an ε-approximation to the spectrum of a normalized graph adjacency matrix with constant success probability, even when given the full transcripts of 2^Ω(1/ε^1/6) random walks, each of length 2^Ω(1/ε^1/6), started from uniformly random nodes.

COLT 2026

Graph neural networks extrapolate out-of-distribution for shortest paths

Robert R Nerem, Samantha Chen, Sanjoy Dasgupta, Yusu Wang

Neural networks (NNs), despite their success and wide adoption, still struggle to extrapolate out-of-distribution (OOD), i.e., to inputs that are not well-represented by their training dataset. Addressing the OOD generalization gap is crucial when models are deployed in environments significantly different from the training set, such as applying Graph Neural Networks (GNNs) trained on small graphs to large, real-world graphs. One promising approach for achieving robust OOD generalization is the framework of neural algorithmic alignment, which incorporates ideas from classical algorithms by designing neural architectures that resemble specific algorithmic paradigms (e.g. dynamic programming). The hope is that trained models of this form would have superior OOD capabilities, in much the same way that classical algorithms work for all instances. We employ sparsity regularization as a tool for analyzing the role of algorithmic alignment in achieving OOD generalization, focusing on graph neural networks (GNNs) applied to the canonical shortest path problem. We prove that if a trained GNN minimizes a sparsity-regularized loss over a small set of shortest-path instances, then the GNN implements K steps of the Bellman-Ford algorithm for shortest paths. In fact, if a trained GNN minimizes this loss within an error of ϵ, it computes K-step shortest path distances up to error O(ϵ). Our empirical results support our theory by showing that NNs trained by gradient descent are able to minimize this loss and extrapolate in practice.

COLT 2026

Optimal Neural Network Approximation of Smooth Compositional Functions on Sets with Low Intrinsic Dimension

Thomas Nagler, Sophie Langer

We study approximation and statistical learning properties of deep ReLU networks under structural assumptions that mitigate the curse of dimensionality. We prove minimax-optimal uniform approximation rates for s-Hölder smooth functions defined on sets with low Minkowski dimension using fully connected networks with flexible width and depth, improving existing results by logarithmic factors even in classical full-dimensional settings. A key technical ingredient is a new memorization result for deep ReLU networks that enables efficient point fitting with dense architectures. We further introduce a class of compositional models in which each component function is smooth and acts on a domain of low intrinsic dimension. This framework unifies two common assumptions in the statistical learning literature, structural constraints on the target function and low dimensionality of the covariates, within a single model. We show that deep networks can approximate such functions at rates determined by the most difficult function in the composition. As an application, we derive improved convergence rates for empirical risk minimization in nonparametric regression that adapt to smoothness, compositional structure, and intrinsic dimensionality.

COLT 2026

On the Stability of Nonlinear Dynamics in GD and SGD: Beyond Quadratic Potentials

Rotem Mulayoff, Sebastian U Stich

The dynamical stability of the iterates during training plays a key role in determining the minima obtained by optimization algorithms. For example, stable solutions of gradient descent (GD) correspond to flat minima, which have been associated with favorable features. While prior work often relies on linearization to determine stability, it remains unclear whether linearized dynamics faithfully capture the full nonlinear behavior. Recent work has shown that GD may stably oscillate near a linearly unstable minimum and still converge once the step size decays, indicating that linear analysis can be misleading. In this work, we explicitly study the effect of nonlinear terms. Specifically, we derive an exact criterion for stable oscillations of GD near minima in the multivariate setting. Our condition depends on high-order derivatives, generalizing existing results. Extending the analysis to stochastic gradient descent (SGD), we show that nonlinear dynamics can diverge in expectation even if a single batch is unstable. This implies that stability can be dictated by a single batch that oscillates unstably, rather than an average effect, as linear analysis suggests. Finally, we prove that if all batches are linearly stable, the nonlinear dynamics of SGD are stable in expectation.

COLT 2026

Steering diffusion models with quadratic rewards: a fine-grained analysis

Ankur Moitra, Andrej Risteski, Dhruv Rohatgi

Inference-time algorithms are an emerging paradigm in which pre-trained models are used as subroutines to solve downstream tasks. Such algorithms have been proposed for tasks ranging from inverse problems and guided image generation to reasoning. However, the methods currently deployed in practice are heuristics with a variety of failure modes—and we have very little understanding of when these heuristics can be efficiently improved. In this paper, we consider the task of sampling from a reward-tilted diffusion model—that is, sampling from p^⋆(x) ∝ p(x) exp(r(x))—given a reward function r and pre-trained diffusion oracle for p. We provide a fine-grained analysis of the computational tractability of this task for quadratic rewards r(x) = x^⊤ A x + b^⊤ x. We show that linear-reward tilts are always efficiently sampleable—a simple result that seems to have gone unnoticed in the literature. We use this as a building block, along with a conceptually new ingredient—the Hubbard-Stratonovich transform—to provide an efficient algorithm for sampling from low-rank positive-definite quadratic tilts, i.e. r(x) = x^⊤ A x where A is positive-definite and of rank O(1). For negative-definite tilts, i.e. r(x) = - x^⊤ A x where A is positive-definite, we prove that the problem is intractable even if A is of rank 1 (albeit with exponentially-large entries).

COLT 2026

On the implicit regularization of Langevin dynamics with projected noise

Govind Menon, Austin Stromme, Adrien Vacher

We study Langevin dynamics with noise projected onto the directions orthogonal to an isometric group action. This mathematical model is introduced to shed new light on the effects of symmetry on stochastic gradient descent for over-parametrized models. Our main result identifies a novel form of implicit regularization: when the initial and target density are both invariant under the group action, Langevin dynamics with projected noise is equivalent in law to Langevin dynamics with isotropic diffusion but with an additional drift term proportional to the negative log volume of the group orbit. We prove this result by constructing a coupling of the two processes via a third process on the group itself, and identify the additional drift as the mean curvature of the orbits.

COLT 2026

On the Gradient Complexity of Private Optimization with Private Oracles

Michael Menart, Aleksandar Nikolov

We study the running time, in terms of first order oracle queries, of differentially private empirical/population risk minimization of Lipschitz convex losses. We primarily consider the setting where the loss is non-smooth and the optimizer interacts with a private proxy oracle, which sends only private messages about a minibatch of gradients. In this setting, we show that expected running time Ω(min√(d)/α^2, d/log(1/α)) is necessary to achieve α excess risk on problems of dimension d when d ≥ 1/α^2. Upper bounds via DP-SGD show these results are tight when d>Ω̃(1/α^4). In fact, the lower bound nearly matches the best known upper bound for general private optimizers in this regime. A consequence of our results is that, in high dimensions, the ubiquitous DP-SGD algorithm necessarily suffers a dimension dependent runtime slowdown and further that DP-SGD is optimal among the subclass of DP optimizers that use private oracles. We further show our lower bound can be strengthened to Ω(mind/m̅α^2, d/log(1/α)) for algorithms which use minibatches of size at most m̅ < √(d). We next consider smooth losses, where we relax the private oracle assumption and give lower bounds under only the condition that the optimizer is private. Here, we lower bound the expected number of first order oracle calls by Ω̃(√(d)/α + min1/α^2, n), where n is the size of the dataset. Modifications to existing algorithms show this bound is nearly tight. To our knowledge, ours are the first oracle complexity lower bounds to leverage differential privacy beyond the local privacy model. Compared to non-private lower bounds, our results show that differentially private optimizers pay a dimension dependent runtime penalty. Finally, as a natural extension of our proof technique, we show lower bounds in the non-smooth setting for optimizers interacting with information limited oracles. If the proxy oracle transmits at most Γ-bits of information about the gradients in the minibatch, then Ω(mind/α^2Γ, d/log(1/α)) oracle calls are needed. This result shows fundamental limitations of gradient quantization techniques in optimization.

COLT 2026

Differentially Private Language Generation and Identification in the Limit (Extended Abstract)

Anay Mehrotra, Grigoris Velegkas, Xifan Yu, Felix Zhou

We initiate the study of language generation in the limit, a model recently introduced by Kleinberg and Mullainathan (2024), under the constraint of differential privacy. We consider the continual release model, where a generator must eventually output a stream of valid strings while protecting the privacy of the entire input sequence. Our first main result is that for countable collections of languages, privacy comes at no qualitative cost: we provide an ε-differentially-private algorithm that generates in the limit from any countable collection. This stands in contrast to many learning settings where privacy renders learnability impossible. However, privacy does impose a quantitative cost: there are finite collections of size k for which uniform private generation requires Ω(k/ε) samples, whereas just one sample suffices non-privately. We then turn to the harder problem of language identification in the limit. Here, we show that privacy creates fundamental barriers. We prove that no ε-DP algorithm can identify a collection containing two languages with an infinite intersection and a finite set difference, a condition far stronger than the classical non-private characterization of identification. Next, we turn to the stochastic setting where the sample strings are sampled i.i.d. from a distribution (instead of being generated by an adversary). Here, we show that private identification is possible if and only if the collection is identifiable in the adversarial model. Together, our results establish new dimensions along which generation and identification differ and, for identification, a separation between adversarial and stochastic settings induced by privacy constraints.

COLT 2026

Language Generation with Infinite Contamination

Anay Mehrotra, Grigoris Velegkas, Xifan Yu, Felix Zhou

A recent line of work studies language generation in the limit, a formal model of language learning where an algorithm observes an adversarially generated enumeration of strings from an unknown target language K and must eventually generate new, unseen strings from K. In this model, Kleinberg and Mullainathan (2024) proved that generation is achievable in surprisingly general settings; whenever K belongs to a known countable collection of languages. However, their generator, while quite general, suffers from “mode collapse:” it generates from an ever-smaller subset of the target. To address this, Kleinberg and Wei (2025a) introduced a stronger notion of dense generation, requiring the output to asymptotically cover a positive fraction of the target, and showed it remains achievable for all countable collections. Both of these works rely on the crucial assumption of perfect data: the adversary can neither insert strings from outside the target language (i.e., noise) nor omit strings from it (i.e., omissions). In practice, training data for language models is notoriously noisy, raising the fundamental question: How much contamination (either omissions or insertions) can language generation tolerate? Recent works have made partial progress on this question by studying (non-dense) generation with either finite amounts of noise (but no omissions) (Raman and Raman, 2025) or omissions (but no noise) (Bai et al., 2026). We characterize the contamination tolerance of both types of generation by proving the following results: * Generation under Contamination: Language generation in the limit is achievable for all countable collections if and only if the fraction of contaminated examples converges to zero. When this condition fails, we characterize the collections which remain generable. * Dense Generation under Contamination: Dense generation is achievable for all countable collections if and only if the amount of contamination is finite. For an infinite amount of contamination, we provide several characterizations of when dense generation is possible, showing it is strictly less robust than standard generation. As a byproduct, we also resolve an open question of (Raman and Raman, 2025) on generation with membership oracle access under finite contamination.

COLT 2026

On the Complexity of Best-Arm Identification in Non-Stationary Linear Bandits

Leo Maynard-Zhang, Zhihan Xiong, Kevin Jamieson, Maryam Fazel

We study the fixed-budget best-arm identification (BAI) problem in non-stationary linear bandits. Concretely, given a fixed time budget T∈ℕ, finite arm set 𝒳⊂ℝ^d, and a potentially adversarial sequence of unknown parameters {θ_t}_t=1^T (hence non-stationary), a learner aims to identify the arm with the largest cumulative reward x_* = max_x ∈𝒳 x^⊤∑_t=1^T θ_t with high probability. In this setting, it is well-known that i.i.d. sampling arms from the G-optimal design yields a minimax-optimal error probability of exp(-Θ(T / H_G)), where H_G scales proportionally with the dimension d. However, this notion of complexity is overly pessimistic, as it is derived from a lower bound in which the arm set consists only of the standard basis vectors, thus masking any potential advantages arising from arm sets with richer geometric structure. To address this, we establish an arm-set-dependent lower bound that, in contrast, holds for any arm set. Motivated by the ideas underlying our lower bound, we propose the Adjacent-optimal design, a specialization of the well-known 𝒳𝒴-optimal design, and develop the algorithm. We prove that the error probability of matches our lower bound up to constants, verifying the tightness of our lower bound, and establishing the arm-set-dependent complexity of this setting.

COLT 2026

Phase Transition in Convex Relaxations for Graph Alignment

Laurent Massoulie, Sushil Mahavir Varma, Louis Vassaux, Irène Waldspurger

We study the graph alignment problem for correlated Gaussian Orthogonal Ensemble (GOE) matrices, where the goal is to recover a hidden vertex permutation given two correlated symmetric Gaussian matrices (A,B) with correlation 1/√(1+σ^2). While the maximum likelihood estimator is information-theoretically optimal, its computation, which reduces to a quadratic assignment problem, is intractable. Motivated by this, we analyze convex relaxations based on minimizing AX - XB_F over the set of doubly stochastic matrices and the unit hypercube. We show that when the correlation parameter satisfies σ = o(n^-1/2/log^4 n), the solution of either relaxation (X^⋆) concentrates around the ground-truth permutation matrix (Π^⋆), i.e., X^⋆ - Π^⋆_F^2 = o(n), implying recovery of all but a vanishing fraction of vertices after simple post-processing. Combined with existing lower bounds, our results precisely characterize that X^⋆ - Π^⋆_F^2 transitions from o(n) for σ = õ(n^-1/2) to Ω(n) for σ = Ω̃(n^-1/2). In doing so, our analysis significantly tightens prior results and extends them beyond doubly stochastic relaxations.

COLT 2026

Online Market Making and the Value of Observing the Order Book

Davide Maran, Marcello Restelli

We study an online market-making problem in which a learner sequentially posts bid and ask prices for a single asset while interacting with traders holding private valuations. Unlike existing online learning formulations that assume fully censored feedback, we introduce an action-dependent feedback model inspired by real limit order books: when a trade occurs, the trader’s valuation remains hidden, whereas when no trade occurs, informative feedback about supply and demand is revealed. We show that this additional information fundamentally changes the learnability of the problem. In the stochastic setting with i.i.d. market prices, we propose an elimination-based algorithm that achieves O(√(T)) regret with high probability, without requiring any smoothness assumptions on the distribution of trader valuations. We then extend this result to a broad class of mean-reverting price processes by considering both local, autoregressive dynamics and a weaker global drift condition based on cumulative deviations from the mean. Under either assumption, we establish high-probability O(√(T)) regret bounds, relying on a new concentration inequality of independent interest. Finally, in the adversarial setting with oblivious prices, we design an explore-then-perturb algorithm that guarantees Õ(T^2/3) regret in expectation. Our results quantify the value of observing the order book in online market making and demonstrate that even limited, action-dependent feedback can substantially improve regret guarantees compared to standard bandit feedback models.

COLT 2026

On the Power of Adaptivity for ε-Best Arm Identification in Linear Bandits

Arnab Maiti, Yunbei Xu, Kevin Jamieson

We study the minimax sample complexity of ε-best arm identification in linear bandits, a classical pure-exploration problem. Given a compact action set 𝒳 that spans ℝ^d and an unknown reward vector θ∈ℝ^d, the goal is to output an arm x∈𝒳 such that ⟨x,θ⟩≥max_x∈𝒳 ⟨x,θ⟩- ε with probability at least 1-δ, using as few samples as possible. Our aim is to better understand the power and limitations of adaptivity in this setting. We begin with non-adaptive algorithms. We present a non-adaptive fixed-design method with sample complexity 𝒪(dlog(1/δ)/ε^2+w(𝒳)^2/ε^2), where w(𝒳) is a Gaussian width term dependent on 𝒳, and we prove a matching lower bound Ω(dlog(1/δ)/ε^2+w(𝒳)^2/ε^2) for all non-adaptive fixed-design methods. Moreover, w(𝒳)≤𝒪(d) for general 𝒳, which is tight for sets such as the unit ℓ_2 ball, and w(𝒳)≤𝒪(√(dlog|𝒳|)) when 𝒳 is finite, which is tight for the canonical basis e_1,…,e_d. We then turn to adaptive sampling. For any finite action set 𝒳, we prove the existence of an adaptive algorithm with sample complexity 𝒪(dlog(1/δ)/ε^2+dlog(|𝒳|/d)/ε^2) via a generalization of Median Elimination, which is known to yield a log d improvement for the canonical basis. This raises a structural question: beyond the canonical basis, are there structured action sets for which adaptivity yields only logarithmic-factor improvements over the optimal non-adaptive rate? We answer in the affirmative for several natural action sets, namely the hypercube, the ℓ_2 ball, m-sets, and multi-task multi-armed bandits. Finally, we show that logarithmic improvements are not the whole story. To our knowledge, we provide the first construction of an action set 𝒳 for which adaptivity yields a polynomial-factor improvement over every non-adaptive algorithm. A key ingredient behind this separation is an ℓ_2-norm estimation subroutine: we design an adaptive algorithm that uses 𝒪(dlog(1/δ)/ε^2) samples from the unit ℓ_2 ball in ℝ^d and outputs an estimate r satisfying |r-θ_2|≤ε with probability at least 1-δ, where θ is the unknown reward vector. Taken together, these results illustrate when adaptivity can offer only modest savings and when it can enable genuine polynomial gains, sharpening our understanding of the role of adaptivity and geometry in pure exploration and experimental design.

COLT 2026

Polynomial-time sampling despite disorder chaos

Eric Ma, Tselil Schramm

A distribution over instances of a sampling problem is said to exhibit transport disorder chaos if perturbing the instance by a small amount of random noise dramatically changes the stationary distribution (in Wasserstein distance). Seeking to provide evidence that some sampling tasks are hard on average, a recent line of work has demonstrated that disorder chaos is sufficient to rule out “stable” sampling algorithms, such as gradient methods and some diffusion processes. We demonstrate that disorder chaos does not preclude polynomial-time sampling by canonical algorithms in canonical models. We show that with high probability over a random graph 𝐆∼ G(n,1/2): (1) the hardcore model (at fugacity λ = 1) on 𝐆 exhibits disorder chaos, and (2) Glauber dynamics run for O(n) time can approximately sample from the hardcore model on 𝐆 (in Wasserstein distance).

COLT 2026

Wedge Sampling: Efficient Tensor Completion with Nearly-Linear Sample Complexity

Hengrui Luo, Anna Ma, Ludovic STEPHAN, Yizhe Zhu

We introduce Wedge Sampling, a new non-adaptive sampling scheme for low-rank tensor completion. We study recovery of an order-k low-rank tensor of dimension n×⋯× n from a subset of its entries. Unlike the standard uniform entry model (i.e., i.i.d. samples from [n]^k), wedge sampling allocates observations to structured length-two patterns (wedges) in an associated bipartite sampling graph. By directly promoting these length-two connections, the sampling design strengthens the spectral signal that underlies efficient initialization, in regimes where uniform sampling is too sparse to generate enough informative correlations. Our main result shows that this change in sampling paradigm enables polynomial-time algorithms to achieve both weak and exact recovery with nearly linear sample complexity in n. The approach is also plug-and-play: wedge-sampling–based spectral initialization can be combined with existing refinement procedures (e.g., spectral or gradient-based methods) using only an additional Õ(n) uniformly sampled entries, substantially improving over the Õ(n^k/2) sample complexity typically required under uniform entry sampling for efficient methods. Overall, our results suggest that the statistical-to-computational gap highlighted by Barak and Moitra [Mathematical Programming, 193(2):513–548, 2022] is, to a large extent, a consequence of the uniform entry sampling model for tensor completion, and alternative non-adaptive measurement designs that guarantee a strong initialization can overcome this barrier.

COLT 2026

Random Reshuffling Dominates Stochastic Gradient Descent

Zijian Liu

Stochastic Gradient Descent () is one of the most classical optimization algorithms with favorable theoretical guarantees, yet the practical implementation of differs subtly from its well-known form and is often referred to as Shuffling Stochastic Gradient Descent (). A particularly popular strategy in is Random Reshuffling (), which has achieved great empirical success across numerous experiments. Despite its strong performance, has long been considered a heuristic due to a lack of theoretical support. Over the last decade, people have finally established provable convergence rates for , thus justifying its observed superiority. However, for smooth convex optimization, two clouds over the convergence theory of remain to this day. More precisely, according to the current theory, under converges only when the stepsize is smaller than a threshold proportional to 1/n, where n is the number of summands in the objective (or the number of data points). Consequently, the optimally tuned theoretical rate of under is strictly worse than that of when the number of epochs is smaller than another threshold proportional to n. These two restrictions heavily limit the applicability of existing theories and leave a critical mismatch with practice. In this work, for the first time, we prove that dominates in smooth convex optimization under any reasonable stepsize after any finite number of epochs, thereby addressing a longstanding open question.

Keep browsing

More papers from top AI conferences

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