Convergence Analysis

Follow this topic Ask about this topic

Momentum

4 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 33

Sep 30, 2026cs.LG

Near-Linear Accuracy Bounds for Moreau--Yosida Unadjusted Langevin Sampling

We establish near-linear accuracy bounds for the classical Moreau--Yosida unadjusted Langevin algorithm (MYULA). The target is

π\propto e^{-f-g}

, where

f\in C^2(\mathbb{R}^d)

is

m

-strongly convex with Lipschitz gradient and

g

is convex and globally Lipschitz. Under an explicit parameter-dependent step-size condition, we bound the invariant-measure bias relative to the Moreau-smoothed target by

\widetilde O(h)

, with only logarithmic dependence on the inverse smoothing parameter in the error coefficient. Combining this estimate with the Moreau approximation bias and Wasserstein contraction gives

\widetilde O(\varepsilon^{-1})

iterations to make the

N

th-iterate law

μ_N

satisfy

\sqrt m\,W_2(μ_N,π)\le\varepsilon

, for fixed model parameters and initialization. We bound the stationary error directly, without assuming third derivatives or a Lipschitz Hessian. Each iteration uses one gradient evaluation and one exact proximal evaluation. The key idea in our analysis is to convert a second-order stationary residual into a Wasserstein bound using a Poisson-based estimate.

Yuchen Xin, Zhihua Zhang

School of Mathematical Sciences, Peking University

Markov Chain Monte Carlo Langevin Dynamics Log-Concave Sampling Convergence Analysis

Sep 29, 2026cs.AI

Adam under Generalized Smoothness with Second-Moment-Type Stochastic Gradients

Adam is widely observed to remain stable even when the objective deviates significantly from global smoothness. Under the generalized smoothness framework, however, existing analyses rely on strong tail assumptions on the stochastic gradients, such as almost-sure boundedness or sub-Gaussianity. Whether Adam converges on generalized smooth objectives under only second moment information on the stochastic gradients, without such concentration assumptions, was identified as an important open direction by Li et al. (2023). This paper gives an affirmative answer under fairly general conditions: such tail assumptions are not necessary. Building on the Adam self-normalization framework of Jin et al. (2026), developed for classical smoothness and bounded variance, we extend the stopping-time and de-preconditioning strategy to the

L_0

-

L_p

generalized smoothness condition and a generalized second moment ABC condition. Even when the stochastic-gradient condition provides only second moment information that may grow along the trajectory, the stochastic trajectory of Adam remains in a locally well-behaved smoothness region, with stretched-exponential tail decay under bounded variance and global smoothness. Consequently, we establish high-probability convergence rate guarantees over the full range

p<2

, with confidence dependence of order

δ^{-1/2}

, while the stepsize prefactor depends on

δ

only through a single logarithmic factor. We further construct a hard instance showing that, under only second-moment information, this

δ^{-1/2}

-type confidence dependence is sharp. Finally, in the regime

p<1

, we combine the trajectory control with polynomial-growth estimates on rare events to obtain convergence rate guarantees in expectation.

Ruinan Jin, Difei Cheng, Ling Chen +3

Mohamed bin Zayed University of Artificial Intelligence · Aerospace Information Technology University · The Ohio State University +2

Convergence Analysis Stochastic Optimization Convergence Adaptive Gradient Methods

Sep 26, 2026math.OC

Convergent Plug-and-Play Image Restoration with Annealed Noise Levels

Plug-and-Play (PnP) methods solve imaging inverse problems by incorporating deep denoisers into iterative optimization algorithms. Although practical implementations often decrease the denoiser noise level

σ

along iterations, most existing convergence analyses assume a fixed denoiser. In this work, we establish convergence guarantees for a broad family of Plug-and-Play algorithms with annealed noise level, spanning deterministic methods (RED--GD and PnP--PGD) and stochastic methods (SNORE, equivariant RED, and a variant of PnP--Flow). For each method, we identify an explicit, nonconvex objective associated with the terminal denoising level and prove asymptotic stationarity of the iterates with respect to this objective. Our analysis does not prescribe any decay rate for the noise schedule, and our assumptions cover both learned gradient-step denoisers and exact MMSE denoisers. Overall, our theoretical results bridge the gap between existing PnP convergence theory and the decreasing-denoising practices used by state-of-the-art image restoration methods. We empirically demonstrate the benefits of such schedules and illustrate the predicted convergence behavior on several imaging inverse problems, including inpainting, super-resolution, demosaicing and tomography.

Samuel Hurault

LIGM, CNRS, Univ. Gustave Eiffel

Convergence Analysis Image Restoration Image Inverse Problems

Sep 8, 2026math.OC

The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives

We study the time-uniform convergence of the raw iterate of standard stochastic gradient descent (SGD) for unconstrained smooth convex objectives. We prove that, under standard noise assumptions, the time-uniform convergence rate gets arbitrarily close to

\sqrt{\log n / n}

but never reaches it. More specifically, we prove that for every positive, eventually nondecreasing sequence

h

satisfying

h(n) = o(\sqrt{n})

, a bound of order

h(n)/\sqrt{n}

, holding simultaneously for all

n

with probability at least

1-α

and uniformly over the problem class, is achievable if and only if

\sum_{j = 1}^{\infty} \frac{1}{h(2^j)^2} < \infty.

The constructive sufficiency result follows from a dyadic horizon-free schedule together with an additive conditional-restart inequality. The necessity counterpart applies to every deterministic nonnegative schedule and holds even for a one-dimensional analytic smooth convex objective with Gaussian noise.

Ruijie Li, Kang Chen, Tianyu Wang

School of Data Science, Fudan University · Shanghai Center for Mathematical Sciences, Fudan University

Learning Rate Scheduling Last-Iterate Convergence Convergence Analysis Stochastic Optimization Convergence Stochastic Gradient Descent

Aug 13, 2026cs.LG

Active-Trace Complexity Bounds for Moreau--Yosida Unadjusted Langevin Sampling

We study the Moreau--Yosida unadjusted Langevin algorithm (MYULA) for the nonsmooth composite target

π(dx)\propto \exp\{-f(x)-g(x)\}\,dx, \qquad x\in\mathbb R^d,

where

f

is

m

-strongly convex with

L_f

-Lipschitz gradient and

g

is convex and

G

-Lipschitz. Let

g_λ

be the Moreau envelope of

g

,

π_λ

the corresponding smoothed target, and

a_λ=\operatorname{tr}H_λ

, where

H_λ

is the a.e./weak Hessian of

g_λ

. We show that the leading MYULA discretization error is controlled by the reference active trace

B_{\mathrm{ref}}

, the average of

a_λ

along the heat substep of one MYULA update started from

π_λ

, rather than by the global curvature bound

d/λ

. If

M_λ

is an a.e. upper bound for

a_λ

, then, up to logarithmic factors,

N \lesssim \frac{1}{m} \left[ L_f + \frac{ τ_f+G^2+B_{\mathrm{ref}} }{ \varepsilon_{\mathrm{alg}}^2 } + \frac{M_λ}{\varepsilon_{\mathrm{alg}}} \right], \qquad τ_f:= \sup_x\operatorname{tr}\nabla^2 f(x),

iterations suffice to ensure

\sqrt m\,W_2(μ_N,π_λ)\leq\varepsilon_{\mathrm{alg}}

, where

μ_N

is the law of the

N

-th iterate and

W_2

is the quadratic Wasserstein distance. We also prove the Moreau-bias bound

\sqrt m\,W_2(π_λ,π) \leq \frac{G^2λ}{4}.

Thus, choosing

λ\asymp\varepsilon/G^2

gives an end-to-end guarantee for

π

. The universal estimate

B_{\mathrm{ref}}\leq d/λ

yields

\widetilde O(\varepsilon^{-3})

accuracy dependence. For the structured piecewise-linear, lasso-type, group, and total-variation penalties considered here, curvature--tube estimates make

B_{\mathrm{ref}}

independent of

λ

, yielding

\widetilde O(\varepsilon^{-2})

for the same classical MYULA kernel.

Yuchen Xin, Zhihua Zhang

School of Mathematical Sciences, Peking University

Langevin Dynamics Sample Complexity Convergence Analysis Nonsmooth Convex Optimization

Aug 4, 2026math.PR

A Direct Route to Markov Chain Convergence via Asymptotic Equivalence with the Target

For a Markov kernel

T

with an invariant probability measure

π

, we give a self-contained proof of the Markov chain convergence theorem via a criterion called asymptotic equivalence with the target. It assumes two parts about the Lebesgue decompositions of

T^{n}_{x}

and

π

for every starting point

x

: 1.) asymptotic absolute continuity: the singular mass sing

(T^{n}_{x}\midπ)

tends to

0

; 2.) asymptotic domination of the target: the singular mass sing

(π\mid T^{n}_{x})

tends to

0

, as

n \to \infty

. This criterion, on countably generated measurable spaces, is both sufficient and necessary for the Markov chain convergence. A density version of this criterion is verified on general measurable spaces in three cases: (i)

T

has a positive transition density wrt

π

; (ii)

T

consists of an absolutely continuous part with positive transition density together with an atom at the starting point, which covers the Metropolis--Hastings algorithm; (iii) the transition density is positive only after a finite number of steps that may depend on the starting point

x

. To demonstrate our general criterion, we investigate the Gibbs sampler with random scan and the parallel tempering algorithm. Furthermore, we show that in all mentioned settings Birkhoff's ergodic theorem applies, so as to obtain the strong law of large numbers. Throughout this paper, neither irreducibility, nor aperiodicity, nor recurrence, nor couplings, nor splitting constructions, nor small sets are used. In most results, the state space is a general measurable space, which carries no structure beyond a

σ

-algebra. Countable generation is only assumed where the density-free form of the criterion is stated. None of the theorems proved here is new; what is offered is a short route to a single, widely applicable Markov chain convergence criterion, which is both sufficient and necessary.

Patrick Forré

AI4Science Lab Korteweg-de Vries Institute for Mathematics University of Amsterdam

Markov Chain Monte Carlo Convergence Analysis Parallel Tempering

Aug 1, 2026math.DS

Contraction Analysis of Holomorphic Dynamical Systems via the Intrinsic Kobayashi Metric

This paper studies incremental stability of holomorphic dynamical systems through the infinitesimal Kobayashi metric, an intrinsic pseudometric on complex manifolds invariant under holomorphic transformations and free of the coordinate dependence inherent in auxiliary Riemannian or Hermitian formulations. Contraction is formalized as an upper Dini-derivative inequality on the Kobayashi metric along trajectories; the passage from this differential condition to exponential distance contraction follows the classical Finsler-metric contraction mechanism of Forni and Sepulchre, instantiated here for the case in which the Finsler structure is the Kobayashi metric itself. Since the intrinsic condition is difficult to verify directly, a practical criterion is developed through a smooth Hermitian metric, the complex-Hermitian analogue of the classical real matrix contraction inequality: contraction with respect to such a metric implies intrinsic contraction on forward-invariant compact subsets, the two notions related through explicit local equivalence constants. Building on this, a Nagumo-type invariance result is established for Laplacian-coupled holomorphic networks, giving verifiable conditions for forward invariance in a class of systems not previously treated this way, and the framework extends to feedback-controlled holomorphic systems, with consequences for equilibria and periodic orbits following directly from intrinsic contraction. Numerical experiments on a network of coupled holomorphic oscillators verify the Hermitian condition analytically on a proven invariant set, and reveal that the observed synchronization rate substantially exceeds this guaranteed rate; the gap matches, to three decimal places, a closed-form combination of the node-wise rate and the network graph-Laplacian spectral gap, identified here as a target for a network-aware extension rather than resolved in full.

Soumic Sarkar

Narva College, University of Tartu, Raekoja plats 2-319, Narva, 20307, Estonia

Dynamical Systems Convergence Analysis

Jul 25, 2026stat.ML

Learning Asymptotics with Convergence-Rate Guarantees using Linear Least Squares

We introduce a new research area that is called Asymptotics Learning Theory (ALT) and combines optimization with asymptotic analysis. In particular, ALT provides a unified approach for computing unknown constants/parameters in proven asymptotic expansions using optimization theory. In this paper, we focus on a general asymptotic form which includes a broad class of asymptotics. Furthermore, we study two powerful numerical methods, namely, sliding Linear Least Squares (sLLSQ) and sliding Tikhonov Linear Least Squares (sT-LLSQ). For these techniques we rigorously prove asymptotic estimates that lead to sufficient conditions for convergence (to the correct values of unknown parameters) and convergence-rate guarantees. Despite their strengths, both methods have also limitations, e.g., slow convergence---or even, counterintuitively, divergence---in some cases. Moreover, we present fundamental applications in analytic combinatorics, a beautiful field of mathematics that deals with asymptotic enumeration of discrete structures using complex analysis. The proposed techniques complement existing approaches, such as the ratio method and its variants. Numerical examples also verify the theoretical results. Finally, we discuss interesting research directions in ALT.

Christos N. Efrem

Convergence Analysis

Jul 15, 2026cs.AI

Per-Token Fixed-Point Convergence in Depth-Recurrent Transformers

A depth-recurrent transformer applies a weight-tied core a variable number of times, and prior work has shown that training with a randomized recursion count yields one checkpoint usable across a range of inference depths. We ask what such a model actually computes per token, and measure it directly. On a 135M-class model trained on FineWeb-Edu, the recurrent state converges to a per-token fixed point: mean successive-output KL divergence falls from 3.9e-1 at the second loop to 8.5e-6 by the sixteenth, and per-token state change decays in step. Crucially, this convergence is not uniform across tokens. The median token converges by loop six, while approximately 10 percent of tokens continue to update at the training-mean depth of eight, and mean convergence depth is ordered by token type (whitespace shallowest, content words deepest). This per-token variation is the central object of the paper. We show it is directly readable and that reading it outperforms learning to predict it: a training-free rule that halts each token once its output stabilizes attains uniform depth-8 quality at 4.94 average loops (a 38 percent reduction in average depth) and matches uniform depth across the average-depth range, whereas a linear router trained on convergence labels harvested from the same model requires nearly full depth and yields no reduction. The elasticity that makes this possible reproduces here as background (validation loss decreases monotonically from 3.80 at one loop to 3.20 at eight and remains stable to 32 loops). We report average depth as a FLOP proxy with a three-point wall-clock bracket rather than a realized speedup, make no FLOP-matched parity claim, and note that the allocation results are established at a single scale and seed. The complete study runs on a single RTX 4090 in approximately 100 GPU-hours.

Joe Logan

Independent researcher

Transformer Inference Recurrent Transformers Convergence Analysis Adaptive Computation

Jul 6, 2026stat.ML

Non-Asymptotic Error Bounds for SMC with Biased Proposals: Application to Conditional Diffusion Sampling

Sequential Monte Carlo (SMC) methods are a natural tool for post-hoc conditioning of pretrained generative models, but in many applications the mutation kernels used by the particle system are biased approximations of an ideal Feynman--Kac flow. This paper develops a non-asymptotic error analysis for such SMC samplers. Under forward-smoothing forgetting conditions, we decompose the total error into a kernel bias, measuring the effect of replacing the ideal transition kernels by approximate ones, and a finite-particle Monte Carlo error. Our approach relies on extending local Doeblin-type conditions and Lyapunov drift arguments for Markov kernels to conditional distributions, thereby enabling a principled control of the bias. We then instantiate this general framework for conditional sampling with score-based diffusion models, and derive the first non-asymptotic error bound that jointly controls initialization error, time discretization, and score approximation in the reverse diffusion dynamics as well as finite-particle Monte Carlo error.

Stanislas Strasman, Gabriel Victorino Cardoso, Sylvain Le Corff +2

SU, LPSM · Sorbonne Université and Université Paris Cité, CNRS, LPSM, F-75005 Paris, France · LPSM +2

Markov Chain Monte Carlo Markov Models Diffusion Sampling Convergence Analysis Score-Based Generative Modeling

Jul 5, 2026math.OC

Unified convergence analysis for gradient descent optimization methods in the training of deep neural networks

Gradient based optimization methods are nowadays the methods of choice for training deep neural networks (DNNs) in artificial intelligence (AI) systems. In practically relevant DNN training problems, one does usually not apply the standard gradient descent (GD) optimization method but instead one employs suitable sophisticated GD optimization methods, which incorporate adaptivity and/or acceleration techniques, such as the famous Adam optimizer. It is a key contribution of this work to provide a general unified convergence analysis for GD optimization methods in the training of DNNs with analytic activations such as the softplus and the popular Gaussian error linear unit (GeLU) activation. Our general unified convergence result applies to a large class of gradient based optimization methods such as the standard GD, the momentum, the Nesterov accelerated gradient (NAG), the RMSprop, the Adam, the Adamax, the Nadam, the Nadamax, the Adan, the AdaBelief, the AMSGrad, and the Yogi optimizers. Our analysis employs the theory of Kurdyka-Łojasiewicz (KL) inequalities to establish convergence to critical points in the training of DNNs. To the best of our knowledge, the generality of our convergence analysis is also just in the special situation of the Adam optimizer a new contribution to the literature on the analysis of AI optimization algorithms.

Shokhrukh Ibragimov, Arnulf Jentzen

Applied Mathematics: Institute for Analysis and Numerics, University of Münster, Germany · School of Data Science and School of Artificial Intelligence, The Chinese University of Hong Kong, Shenzhen (CUHK-Shenzhen), China

Deep Learning Optimization Neural Network Optimization Convergence Analysis Adaptive Gradient Methods Gradient Descent Dynamics

Jun 23, 2026math.OC

New Bounds for the Last Iterate of the Stochastic subGradient Method

We study the last iterate of the stochastic subgradient method for one-dimensional convex Lipschitz objectives. For a fixed horizon

n

, we consider the standard fixed stepsizes

η=Θ(1/\sqrt n)

. We prove that, for such stepsize policies, under additive i.i.d. subgradient noise with uniformly bounded variance, the last iterate features an optimization error of order

1/\sqrt n

, thereby removing the extra

(\log n)

factor present in existing generic bounds. On the other hand, we show that without the i.i.d. assumption, the optimization error can be of order

(\log n)/\sqrt n

. Thus, under the uniformly bounded variance assumption alone, the last iterate of SsGM is suboptimal even in dimension one, resolving negatively an open problem posed in Koren and Segal, COLT, 2020.

Guglielmo Beretta, Tommaso Cesari, Roberto Colomboni +1

Department of Computer Science, Aarhus University, Aarhus, Denmark · School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, Canada · School of Mathematics, University of Bristol, Bristol, United Kingdom

Stochastic Optimization Last-Iterate Convergence Convergence Analysis Stochastic Optimization Convergence Nonsmooth Convex Optimization

Jun 21, 2026cs.MA

GARIP: A Running-Average Moving Reference for Last-Iterate Self-Play in Two-Player Zero-Sum Games

Self-play with naive gradient ascent cycles in two-player zero-sum games: the last iterate orbits the equilibrium. Modern methods restore last-iterate convergence by regularizing toward a reference policy -- MMD a fixed one (reaching only the regularized equilibrium), R-NaD a periodic snapshot (the engine of DeepNash). We study GARIP, which anchors to the running average, and isolate what the choice of reference controls. Our central result is a mechanism: collapse tracks the peak lag of the reference, and among causal convex averages of a fixed mean lag the running average (flat profile, peak

=

mean) uniquely minimizes that peak, while a snapshot's sawtooth has peak

= 2\times

mean (a one-line theorem). Two consequences follow. Convergence: we prove local last-iterate convergence at constant anchor strength -- the anchor scales the base map's rotation by

1-β

, crossing the stability boundary and turning a recurrent base into a contraction (global convergence is conjectured at small

β

; we characterize a large-

β

consensus failure). Robustness: GARIP matches R-NaD's peak performance -- on matrix games, the Coin Game, and the board games Connect Four/Othello, both moving references are far more robust than fixed-magnet and magnet-free baselines -- but is the better hyperparameter default; we report it both ways: over the full grid collapse rates are statistically indistinguishable, yet at conventional parameterizations a matched-mean-lag setting collapses in 0/40 vs 10/40 seeds (a snapshot matches it only by knowing to shorten

K

). The boundaries: an anticipatory (negative-weight) reference does better still on the stale side, and the advantage appears only where naive self-play cycles (five deep self-play loops). All experiments are pure JAX and reproducible.

Can Savcı

Independent Researcher İzmir, Türkiye

Nash Equilibrium Last-Iterate Convergence Self-Play RL Zero-Sum Games Convergence Analysis Nash Equilibrium Computation

Jun 10, 2026math.OC

Last-Iterate Convergence of Optimistic Multiplicative Weight Update

Optimistic Gradient Descent Ascent (OGDA) and Optimistic Multiplicative-Weights Update (OMWU) are two very popular algorithms to solve convex/concave saddle-point problems, where OMWU is the non-Euclidean, entropic version of OGDA. It is known since the '80s that the last iterate of OGDA asymptotically converges to a saddle point in smooth problems. On the other hand, it is unknown if OMWU has the same property. In this paper, I show that OMWU converges asymptotically for smooth convex-concave saddle-point problems, with a small enough constant learning rate. The result does not require uniqueness, strict complementarity, an error bound, or initialization near a solution. The main new ingredient is a boundary argument showing that every cluster point satisfies the inactive-coordinate KKT inequalities. The boundary argument was discovered with assistance from ChatGPT and is documented in the appendix.

Francesco Orabona

King Abdullah University of Science and Technology (KAUST) Thuwal, 23955-6900, Kingdom of Saudi Arabia

Last-Iterate Convergence Optimization Convergence Analysis Min-Max Optimization Convergence Analysis

May 31, 2026cs.LG

Non-Vacuous Certification of Transport MCMC via Oscillation-Controlled Normalizing Flows

Transport MCMC trains a normalizing flow to precondition Metropolis--Hastings proposals, achieving high empirical efficiency on challenging posteriors; yet no prior work produces a numerically non-vacuous, rigorous spectral-gap bound for such samplers. We establish the first such bounds. For independence MH on the banana family we certify (γ^\ast = 0.828) at (D = 2) (covering in the original space) and (γ^\ast \ge 7.6\times 10^{-4}) at (D = 5) (covering in an analytically unwarped Gaussian space with a grid-certified gradient bound under the stated numerical Lipschitz certification), both rigorous at 95% confidence. The framework rests on three pillars: (i) spectral normalization with reduced scale clips constrains the flow Lipschitz constant from (10^{47}) to (10^4); (ii) a coverage-based empirical oscillation bound replaces the vacuous analytical bound with a data-dependent certificate; and (iii) oscillation-regularised training cuts the empirical oscillation by 60--90% at no cost to density fit, extending practical certificates through (D = 20) ((γ^\ast \ge 1.7\times 10^{-4})). Tests on four further targets (Gaussian mixture, shear-building, Neal's funnel, Bayesian logistic regression) identify three precise barriers: boundary curvature, target stiffness, and tail-coverage mismatch. An affine-vs-spline comparison shows that simpler architectures yield tighter certificates at identical NLL, inverting the usual expressiveness hierarchy.

Jun Hu

China Sanya Science and Education Innovation Park, Wuhan University of Technology, Sanya 572025, China · School of Civil Engineering and Architecture, Wuhan University of Technology, Wuhan 430070, China

Markov Chain Monte Carlo Normalizing Flows Bayesian Inference Convergence Analysis

May 29, 2026math.ST

Improved Guarantees for Langevin Monte Carlo with Average Smoothness

We establish improved nonasymptotic bounds for Langevin Monte Carlo in the strongly log-concave setting, when the error is measured by the Wasserstein distance. The main result shows that the discretization error is governed by an average coordinate-wise smoothness constant, rather than by the usual global smoothness constant. The proof is short and probabilistic, and relies on a refined use of the synchronous coupling. We further show that the same ideas lead to improved bounds for variable step sizes, for potentials whose Laplacian is Lipschitz-continuous, and for finite-sum problems sampled by stochastic-gradient Langevin dynamics with fixed point control variates. In the Laplacian-smooth case, the usual Hessian-Lipschitz contribution is replaced by a weaker trace-type third-order smoothness quantity. In the finite-sum setting, the resulting SGLD bound improves the dependence on the root mean square smoothness of the component functions. Applications to generalized linear models with Gaussian design show that these refinements can yield substantial, dimension-dependent improvements over previously known bounds, especially for correlated covariates.

Arnak S. Dalalyan, Avetik Karagulyan

CREST, ENSAE Paris, Institut Polytechnique de Paris and MBZUAI · L2S, CNRS, Centrale Supélec, Université Paris-Saclay

Markov Chain Monte Carlo Stochastic Gradient Langevin Dynamics Langevin Dynamics Log-Concave Sampling Convergence Analysis

May 29, 2026cs.LG

Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework

We survey Lyapunov-based techniques for the finite-time analysis of stochastic iterative algorithms, also known as stochastic approximation (SA) algorithms, for solving fixed-point equations

\bar{F}(x)=x

, where the operator

\bar{F}(\cdot)

can only be accessed through a noisy oracle. We first focus on the standard setting in which

\bar{F}(\cdot)

is contractive with respect to some norm and the noise is i.i.d., and explain how generalized Moreau envelopes serve as universal Lyapunov functions, regardless of the underlying norm. We then show how this framework yields mean-square convergence guarantees and applies to stochastic gradient descent, linear SA, and value-based reinforcement learning algorithms such as Q-learning and temporal-difference learning. Finally, we discuss extensions to Markovian noise, seminorm-contractive operators, dissipative operators, and high-probability bounds, and conclude with open problems. The goal is to present a unified and self-contained roadmap for the finite-time analysis of SA and its applications, especially in reinforcement learning.

Zaiwei Chen, Siva Theja Maguluri

Purdue IE · Georgia Tech IE

Lyapunov Stability Stochastic Approximation Temporal-Difference Learning Convergence Analysis

May 29, 2026cs.LG

Local linear convergence of gradient methods for overparameterized Gaussian mixtures

We study the problem of learning Gaussian mixture models under overparameterization. Prior work has shown that while overparameterization is essential for avoiding spurious local optima and enables global recovery of the ground-truth model using the gradient-EM (expectation-maximization) algorithm, it can dramatically slow down the local rate of convergence. Under certain assumptions on the mixture weights, we show that a standard divergence measure minimized by statistical learning procedures possesses a manifold of slow growth on which the well-known Polyak stepsize reduces the loss geometrically, and design a gradient-based method that converges to minimizers at a locally linear rate. Additionally, we show that our method converges to nearly optimal solutions -- up to a natural misspecification threshold -- for mixtures with arbitrary weights. At a high level, the method alternates between several "short" gradient descent steps that approach the manifold and "long" Polyak steps that contract the distance to minimizers. Our results suggest that slow convergence is not an intrinsic challenge of overparameterization, but can be overcome by exploiting the favorable structure of the loss landscape.

Jingxing Wang, Vasileios Charisopoulos, Maryam Fazel

Electrical & Computer Engineering, University of Washington, Seattle, WA · National Institute for Theory and Mathematics in Biology, Chicago, IL · Amazon, Inc.

Gradient Descent Gaussian Mixture Models Convergence Analysis

May 29, 2026cs.LG

Self-Certifying Transport MCMC via Dual Spectral-Gap Certificates

We propose CerT-MCMC, a framework that equips learned-transport Markov chain Monte Carlo with automatic, rigorous convergence certificates. A normalising flow maps a Gaussian reference to an approximation of the target posterior; the same flow then serves as both the independence Metropolis-Hastings proposal and the basis for a computable spectral-gap bound. We develop two complementary certificates. The covering certificate bounds the weight-ratio oscillation over the full proposal support via finite-sample covering arguments, yielding full-support spectral-gap bounds when a conservative gradient bound is available; its correction term scales as O(n^{-1/D}), making it rapidly weak and eventually vacuous as dimension increases. We prove a matching Omega(n^{-1/D}) lower bound, establishing that this barrier is intrinsic to pointwise Lipschitz certification. The quantile-core certificate restricts attention to a high-probability residual core on which the oscillation is controlled by one-dimensional empirical quantiles, with a finite-sample probability slack of O(n^{-1/2}), independent of the ambient dimension. On synthetic targets (D=2-20), structural-engineering posteriors (D=6,8), real-data logistic regression on the Heart Disease data set (D=13), and synthetic Bayesian logistic regression (D=20), the quantile-core certificate delivers non-vacuous spectral-gap bounds where the covering certificate is vacuous, and its spectral-gap proxy tracks empirical effective sample sizes within 7%. A negative control experiment confirms that the certificate discriminates flow quality by a factor exceeding 10x, whereas acceptance rates differ by only 1.15x. To our knowledge, the dual-certificate framework is the first to provide automatic, dimension-aware convergence certificates for learned-transport MCMC, distinguishing genuine transport failure from proof-technique limitations.

Jun Hu

Wuhan University of Technology, Wuhan, China

Markov Chain Monte Carlo Convergence Analysis

May 17, 2026cs.LG

Stability and Discretization Error of State Space Model Neural Operators

Neural operators have emerged as a powerful, discretization-invariant framework for solving partial differential equations (PDEs). Although established approaches like the Deep Operator Network (DeepONet) have successfully achieved universal approximation for operators, and architectures such as Fourier Neural Operators (FNOs) have shown algebraic convergence rates, a precise theoretical connection between the continuous theory and its discrete numerical implementation remains a challenge. Specifically, the relationship between the continuous formulation and the discrete numerical stability has yet to be fully explored. In this paper, we address this gap by establishing theoretical guarantees for the discretization error and stability of neural operator approximation schemes. We prove analytical bounds that link solution regularity to input discretization, providing a formal quantification of neural operator accuracy under real-world numerical constraints. We derive these bounds to the specific cases of State Space Model-based Neural Operators (SS-NOs) and FNOs, thus providing a new discretization error theorem for these models. Additionally, through an input-to-state stability (ISS) analysis, we formally assess the impact of discretization on the stability of SS-NOs results obtained in the continuous domain. Our empirical experiments on 1D and 2D benchmarks validate our theoretical bounds and show the robustness of SS-NOs under varying resolutions.

Abderrahim Bendahi, Adrien Fradin, Johan Peralez +2

École polytechnique Paris, France · Université Claude Bernard Lyon 1, CNRS, LAGEPP UMR 5007 Villeurbanne, France · CNRS, UniversitéJulieLyonDigne1, INSA Lyon, LIRIS Lyon, France +1

Fourier Neural Operator Convergence Analysis Neural Operators

May 15, 2026cs.AI

Sign-Separated Asymmetric Finite-Time Error Analysis of Q-Learning

Q-learning is known to suffer from overestimation bias: because the Bellman update maximizes noisy or imperfect action-value estimates, positive errors can be selected and propagated, causing learned values to exceed the true optimal values. This bias can slow learning, degrade policy quality, and make value estimates unreliable. Although the convergence of Q-learning has been studied extensively, convergence theory that explicitly reflects this overestimation mechanism remains limited. This paper studies the asymmetric convergence behavior of Q-learning induced by overestimation bias. We decompose the Q-learning error into its componentwise positive and negative parts and derive separate finite-time rates for the two components. The resulting certificates can assign a slower exponential envelope to the positive component than to the negative component. This rate separation provides indirect theoretical evidence for max-induced overestimation: positive errors can be amplified through the maximization step, whereas negative errors admit a sharper comparison with an optimal-policy system. The separation is a difference between upper bounds, so it need not hold for every realized Q-learning trajectory. Nevertheless, we construct examples in which the predicted asymmetry appears in the actual trajectory. The analysis gives deterministic and stochastic constant-step-size bounds and clarifies how overestimation enters the switching-system dynamics of Q-learning.

Donghwan Lee

Department of Electrical Engineering Korea Advanced Institute of Science and Technology (KAIST) Daejeon 34141, South Korea

Q-Learning Convergence Analysis

May 13, 2026cs.GT

When and Why is Optimistic Multiplicative Weights Slow? The Geometry of Energy Dissipation

This paper studies the convergence of the Optimistic Multiplicative Weights Update algorithm (OMWU) in two player zero-sum games. Recent works have identified instances on which the last-iterate of OMWU can converge arbitrarily slowly, but understanding when and why this slow convergence occurs has remained open. In this work, we develop a new analysis framework that gives sharp, quantitative explanations for this behavior. Our analysis is based on viewing the algorithm's dual iterates as an optimistic skew-gradient descent with respect to an energy function. We prove over the dual iterates that energy is dissipative, and by establishing tight bounds on the magnitude of dissipation, our analysis quantifies the geometric bottlenecks that arise when the corresponding primal iterates are close to the simplex boundary. This further translates into a new linear last-iterate convergence rate in KL divergence on games with a unique and interior Nash equilibrium. Compared to prior work, this new rate contains a much sharper dependence on game-specific constants, and we prove this dependence is optimal. Moreover, these geometric insights further translate into new separations on uniform convergence rates for OMWU. On the one hand, we prove constant lower bounds on the uniform best-iterate convergence rate in KL divergence and total variation distance from Nash. On the other hand, we establish for the

2\times 2

setting a new

{\widetilde O}(T^{-1/2})

best-iterate rate in duality gap, improving substantially over prior work. Together, this shows in general that uniform convergence rate guarantees do not transfer across different measures of distance to Nash.

John Lazarsfeld, Anas Barakat, Georgios Piliouras +2

SUTD · Google DeepMind · NUS CQT +2

Nash Equilibrium Last-Iterate Convergence Optimization Convergence Analysis Game Theory Zero-Sum Games Convergence Analysis+1

May 12, 2026cs.LG

Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs

We study policy optimization for infinite-horizon, discounted constrained Markov decision processes (CMDPs). While existing theoretical guarantees typically hold for the mixture policy, deploying such a policy is computationally and memory intensive. This leads to a practical mismatch where a single (last-iterate) policy must be deployed. Recent theoretical works have thus focused on proving last-iterate convergence, but are largely limited to the tabular setting or to algorithmic variants that are rarely used in practice. To address this, we use the classic inexact augmented Lagrangian (

\texttt{AL}

) method from constrained optimization, and propose a general framework with provable last-iterate convergence for CMDPs. We first focus on the tabular setting and propose to solve the

\texttt{AL}

sub-problem with projected Q-ascent (

\texttt{PQA}

). Combining the theoretical guarantees of

\texttt{PQA}

and the standard

\texttt{AL}

analysis enables us to establish global last-iterate convergence. We generalize these results to handle log-linear policies, and demonstrate that an efficient, projected variant of

\texttt{PQA}

can achieve last-iterate convergence with comparable guarantees as prior work. Finally, we demonstrate that our framework scales to complex non-linear policies, and evaluate it on continuous control tasks.

Michael Lu, Max Qiushi Lin, Mo Chen +1

Simon Fraser University

Markov Decision Processes Last-Iterate Convergence Policy Optimization Constrained RL Convergence Analysis Augmented Lagrangian Method+1

May 10, 2026cs.LG

On Uniform Error Bounds for Kernel Regression under Non-Gaussian Noise

Providing non-conservative uncertainty quantification for function estimates derived from noisy observations remains a fundamental challenge in statistical machine learning, particularly for applications in safety-critical domains. In this work, we propose novel non-asymptotic probabilistic uniform error bounds for kernel-based regression. Compared to related bounds in the literature that are restricted to (conditionally) independent sub-Gaussian noise, our bounds allow to consider a broad class of non-Gaussian distributions, such as sub-Gaussian, bounded, sub-exponential, and variance/moment-bounded noise. Moreover, our results apply to correlated and uncorrelated noise. We compare our proposed error bounds with existing results in terms of the induced uncertainty region and their performance in safe control, demonstrating the tightness of the proposed bounds.

Johannes Teutsch, Oleksii Molodchyk, Marion Leibold +2

Chair of Automatic Control Engineering, Department of Computer Engineering, Technical University of Munich, 80333 Munich, Germany · Institute of Control Systems, Hamburg University of Technology, 21073 Hamburg, Germany · Department of Electrical and Computer Engineering, National University of Singapore, 117583 Singapore

Kernel Regression Uncertainty Quantification Nonparametric Regression Convergence Analysis Kernel Methods Statistical Learning Theory

May 10, 2026cs.LG

Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions

Last-iterate convergence of learning dynamics in games has attracted significant recent attention. In two-player zero-sum games with bandit feedback, where only the loss of the selected action pair is observed, Fiegel et al. (2025) show a separation between average-iterate and last-iterate convergence in duality gap: while the optimal t^(-1/2) rate after t rounds is achievable for the former via standard no-regret algorithms, the latter cannot converge faster than t^(-1/3) in expectation or t^(-1/4) with high probability. However, in many practical settings, such as preference learning, the players observe not only their loss but also the opponent's action. This raises a natural question: can such additional information enable faster last-iterate convergence? We answer this question affirmatively, showing that t^(-1/2) last-iterate convergence is achievable with high probability in this setting, via an efficient algorithm that updates its strategy infrequently by solving an estimated log-barrier-regularized game. We identify fundamental obstacles preventing standard analysis for multi-armed bandits, the single-player case, from generalizing to games, and develop a novel analysis to overcome them. Experiments confirm that our algorithm indeed converges faster than naive baselines and prior methods that do not exploit opponent-action feedback. Finally, we note that our results also improve those for dueling bandits, a special case with skew-symmetric game matrices.

Soumita Hait, Ping Li, Haipeng Luo +1

University of Southern California · Shanghai University of Finance and Economics · University of Iowa

Last-Iterate Convergence Imperfect-Information Games Game Theory Zero-Sum Games Convergence Analysis

May 8, 2026cs.LG

Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift

Establishing almost sure convergence rates for stochastic approximation and reinforcement learning under Markovian noise is a fundamental theoretical challenge. We make progress towards this challenge for a class of stochastic approximation algorithms whose expected updates are contractive, a setting that arises in many reinforcement learning algorithms such as

Q

-learning and linear temporal difference learning. Specifically, for a power-law learning rate

O(n^{-η})

with

η\in (1/2, 1)

, we obtain an almost sure convergence rate arbitrarily close to

o(n^{1 - 2η})

. For a harmonic learning rate

O(n^{-1})

, we obtain an almost sure convergence rate arbitrarily close to

o(n^{-1})

, which we argue is a strong result because it is close to the optimal rate

O(n^{-1}\log\log n)

given by the law of the iterated logarithm (for a special case of i.i.d. noise). Key to our analysis is a novel Lyapunov drift construction that applies a Poisson-equation based correction for Markovian noise to the well-established Moreau-envelope smoothing for the contractive mapping.

Xinyu Liu, Zixuan Xie, Shangtong Zhang

University of Virginia

Reinforcement Learning Stochastic Approximation Convergence Analysis

Apr 30, 2026cs.LG

High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Tracking

We study high-probability (HP) convergence guarantees in decentralized stochastic optimization, where multiple agents collaborate to jointly train a model over a network. Existing HP results in decentralized settings almost exclusively focus on the Decentralized Stochastic Gradient Descent (

\mathtt{DSGD}

) algorithm, which requires strong assumptions, such as bounded data heterogeneity, or strong convexity of each agent's cost. This is contrary to the mean-squared error (MSE) results, where methods incorporating bias-correction techniques are known to converge under relaxed assumptions and achieve better practical performance. In this paper we provide the first step toward bridging the gap, by studying HP convergence of

\mathtt{DSGD}

incorporating the gradient tracking technique, in the presence of noise satisfying a relaxed sub-Gaussian condition. We show that the resulting method, dubbed

\mathtt{GT-DSGD}

, achieves order-optimal HP convergence rates for both non-convex and Polyak-Łojasiewicz costs, of order

\mathcal{O}\Big(\frac{\log(1/δ)}{\sqrt{nT}}\Big)

and

\mathcal{O}\Big(\frac{\log(1/δ)}{nT}\Big)

, respectively, where

n

is the number of agents,

T

is the time horizon and

δ\in (0,1)

is the confidence parameter. Our results establish that

\mathtt{GT-DSGD}

converges in the HP sense under the same conditions on the cost as in the MSE sense, while achieving comparable transient times. To the best of our knowledge, these are the first HP guarantees for decentralized optimization methods incorporating bias-correction. Numerical experiments on real and synthetic data verify our theoretical findings, underlining the superior performance of

\mathtt{GT-DSGD}

and highlighting that the benefits of incorporating bias-correction are also maintained in the HP sense.

Aleksandar Armacki, Haoyuan Cai, Ali H. Sayed

Ecole Polytechnique Fédérale de Lausanne, Lausanne, Switzerland

Convergence Analysis Stochastic Optimization Convergence Decentralized Optimization Gradient Descent Dynamics

Apr 27, 2026stat.ML

Identifiability and Stability of Generative Drifting with Companion-Elliptic Kernel Families

This paper studies the identifiability and stability of drifting fields in the framework of Generative Modeling via Drifting. The motivating question is whether a zero-drift equilibrium identifies the target distribution and whether an approximately vanishing drift implies weak distributional convergence. Since the original drifting model employs the Laplace kernel by default, we first analyze why Gaussian score-based arguments fail to apply. This analysis motivates the introduction of companion-elliptic kernel families, which are characterized by a companion potential satisfying an elliptic closure relation. We show that this class naturally contains the Laplace kernel and consists precisely of Gaussian and Matérn kernels with smoothness parameter

ν>0

. Within this class, we establish field identifiability for arbitrary Borel probability measures on

R^d

: if the drifting field between two such measures vanishes identically, then they must coincide. For stability, we demonstrate that convergence of the field alone does not guarantee weak convergence, since mass may escape to infinity while remaining invisible to the field. Although tightness directly removes this obstruction and restores weak stability, we prove that, even without tightness, every

C_0

-vague cluster point lies exactly on the defect ray

\{cp:0\le c\le1\}

. Consequently, a single scalar

C_0

observable suffices to detect the missing mass and recover weak convergence.

HakGeun Lee, Hyonho Chun

Department of Mathematical Sciences, Korea Advanced Institute of Science and Technology (KAIST), Daejeon, Republic of Korea.

Generative Modeling Convergence Analysis Kernel Methods Drifting Models

Apr 17, 2026cs.LG

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback

We study the problem of learning in zero-sum matrix games with repeated play and bandit feedback. Specifically, we focus on developing uncoupled algorithms that guarantee, without communication between players, the convergence of the last-iterate to a Nash equilibrium. Although the non-bandit case has been studied extensively, this setting has only been explored recently, with a bound of

\mathcal{O}(T^{-1/8})

on the exploitability gap. We show that, for uncoupled algorithms, guaranteeing convergence of the policy profiles to a Nash equilibrium is detrimental to the performance, with the best attainable rate being

Ω(T^{-1/4})

in contrast to the usual

Ω(T^{-1/2})

rate for convergence of the average iterates. We then propose two algorithms that achieve this optimal rate up to constant and logarithmic factors. The first algorithm leverages a straightforward trade-off between exploration and exploitation, while the second employs a regularization technique based on a two-step mirror descent approach.

Côme Fiegel, Pierre Ménard, Tadashi Kozuno +2

ENSAE Paris - CREST, Palaiseau, France · Inria - FairPlay · ENS Lyon, Lyon, France +3

Nash Equilibrium Last-Iterate Convergence Game Theory Zero-Sum Games Convergence Analysis Mirror Descent+1

Apr 16, 2026cs.LG

Optimal last-iterate convergence in matrix games with bandit feedback using the log-barrier

We study the problem of learning minimax policies in zero-sum matrix games. Fiegel et al. (2025) recently showed that achieving last-iterate convergence in this setting is harder when the players are uncoupled, by proving a lower bound on the exploitability gap of Omega(t^{-1/4}). Some online mirror descent algorithms were proposed in the literature for this problem, but none have truly attained this rate yet. We show that the use of a log-barrier regularization, along with a dual-focused analysis, allows this O-tilde(t^{-1/4}) convergence with high-probability. We additionally extend our idea to the setting of extensive-form games, proving a bound with the same rate.

Come Fiegel, Pierre Menard, Tadashi Kozuno +2

ENSAE Paris – CREST, France · ENS Lyon, France · Isara Labs +2

Last-Iterate Convergence Imperfect-Information Games Game Theory Zero-Sum Games Min-Max Optimization Convergence Analysis