Convergence Analysis

Follow this topic Ask about this topic

Convergence analysis asks whether repeated updates in optimization, learning, sampling, and dynamical systems approach a solution, and how fast. Common tools include Lyapunov functions, contraction and coupling arguments, potential functions, and finite-time error bounds, often paired with lower bounds to identify what rates are achievable. Guarantees are studied in settings such as stochastic gradient methods, reinforcement learning, game dynamics, Langevin and Markov-chain sampling, and neural-network training. A central tension is that strong rates can depend on restrictive assumptions, while practical concerns such as noise, dimension, delayed information, and last-iterate behavior can change what is provable.

Latest papers

42 papers4 papers in the last four weeks, level with the four weeks before. 0.0% of all new papers.

The Cost of an Unknown Horizon for the Last Iterate of Clipped SGD under Heavy-Tailed Noise
Oct 24, 2026Yuxing Peng, Zhiqing Tang, Weijia JiaLast-Iterate Convergence Convergence Analysis
Faculty of Arts and Sciences, Beijing Normal University, Zhuhai 519087, China · Institute of Artificial Intelligence and Future Networks, Faculty of Arts and Sciences, Beijing Normal University, Zhuhai 519087, China · Guangdong Key Lab of AI and Multi-Modal Data Processing, Beijing Normal-Hong Kong Baptist University, Zhuhai 519087, China
Lifting Finite-Sample Gaussian Approximation of Wide Neural Networks to Functional Convergence
Oct 13, 2026Luis Wiederhold, Nil Ayday, Debarghya GhoshdastidarConvergence Analysis Neural Network Approximation Theory
School of Computation, Information and Technology Technical University of Munich
Near-Linear Accuracy Bounds for Moreau--Yosida Unadjusted Langevin Sampling
Sep 30, 2026Yuchen Xin, Zhihua ZhangMarkov Chain Monte Carlo Langevin Dynamics
School of Mathematical Sciences, Peking University
Adam under Generalized Smoothness with Second-Moment-Type Stochastic Gradients
Sep 29, 2026Ruinan Jin, Difei Cheng, Ling Chen +3Convergence Analysis Stochastic Optimization Convergence
Mohamed bin Zayed University of Artificial Intelligence · Aerospace Information Technology University · The Ohio State University +2
Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds
Sep 26, 2026Weiming Ou, Xiao WangConvergence Analysis Adaptive Gradient Methods
Shanghai University of Finance and Economics · MoE Key Laboratory of Interdisciplinary Research of Computation and Economics, Shanghai University of Finance and Economics
Convergent Plug-and-Play Image Restoration with Annealed Noise Levels
Sep 26, 2026Samuel HuraultConvergence Analysis Image Restoration
LIGM, CNRS, Univ. Gustave Eiffel
The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives
Sep 8, 2026Ruijie Li, Kang Chen, Tianyu WangLearning Rate Scheduling Last-Iterate Convergence
School of Data Science, Fudan University · Shanghai Center for Mathematical Sciences, Fudan University
Algorithmic Optimality Guarantees for Nonsmooth $H_\infty$ Output-Feedback Policy Search
Sep 5, 2026Ashkan Soleymani, Patrick JailletPolicy Optimization Feedback Control
Department of Electrical Engineering and Computer Science and the Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA 02139, USA.
Distributed Model-Based Diffusion: Finite Horizon Contraction under Bounded Delay
Aug 27, 2026Seth Golembeski, Keith L. Gibson, Alexander Gross +2Multi-Agent Control Multi-Agent Coordination
School of Aerospace Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA · Sandia National Laboratories · School of Mechanical Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA
Active-Trace Complexity Bounds for Moreau--Yosida Unadjusted Langevin Sampling
Aug 13, 2026Yuchen Xin, Zhihua ZhangLangevin Dynamics Sample Complexity
School of Mathematical Sciences, Peking University
A Direct Route to Markov Chain Convergence via Asymptotic Equivalence with the Target
Aug 4, 2026Patrick ForréMarkov Chain Monte Carlo Convergence Analysis
AI4Science Lab Korteweg-de Vries Institute for Mathematics University of Amsterdam
Contraction Analysis of Holomorphic Dynamical Systems via the Intrinsic Kobayashi Metric
Aug 1, 2026Soumic SarkarDynamical Systems Convergence Analysis
Narva College, University of Tartu, Raekoja plats 2-319, Narva, 20307, Estonia
Learning Asymptotics with Convergence-Rate Guarantees using Linear Least Squares
Jul 25, 2026Christos N. EfremConvergence Analysis
Per-Token Fixed-Point Convergence in Depth-Recurrent Transformers
Jul 15, 2026Joe LoganTransformer Inference Recurrent Transformers
Independent researcher
Stability and Convergence of Optimistic Exponential Weights with Asymmetric Step Sizes in Bimatrix Games
Jul 8, 2026Hédi Hadiji, Sarah SachsNash Equilibrium Last-Iterate Convergence
Laboratoire des Signaux et Systèmes, CentraleSupélec, Paris, France · School of Mathematics, University of Bristol, Bristol, United Kingdom
Non-Asymptotic Error Bounds for SMC with Biased Proposals: Application to Conditional Diffusion Sampling
Jul 6, 2026Stanislas Strasman, Gabriel Victorino Cardoso, Sylvain Le Corff +2Markov Chain Monte Carlo Markov Models
SU, LPSM · Sorbonne Université and Université Paris Cité, CNRS, LPSM, F-75005 Paris, France · LPSM +2
Unified convergence analysis for gradient descent optimization methods in the training of deep neural networks
Jul 5, 2026Shokhrukh Ibragimov, Arnulf JentzenDeep Learning Optimization Neural Network Optimization
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
New Bounds for the Last Iterate of the Stochastic subGradient Method
Jun 23, 2026Guglielmo Beretta, Tommaso Cesari, Roberto Colomboni +1Stochastic Optimization Last-Iterate Convergence
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
GARIP: A Running-Average Moving Reference for Last-Iterate Self-Play in Two-Player Zero-Sum Games
Jun 21, 2026Can SavcıNash Equilibrium Last-Iterate Convergence
Independent Researcher İzmir, Türkiye
Last-Iterate Convergence of Optimistic Multiplicative Weight Update
Jun 10, 2026Francesco OrabonaLast-Iterate Convergence Optimization Convergence Analysis
King Abdullah University of Science and Technology (KAUST) Thuwal, 23955-6900, Kingdom of Saudi Arabia
Non-Vacuous Certification of Transport MCMC via Oscillation-Controlled Normalizing Flows
May 31, 2026Jun HuMarkov Chain Monte Carlo Normalizing Flows
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
Improved Guarantees for Langevin Monte Carlo with Average Smoothness
May 29, 2026Arnak S. Dalalyan, Avetik KaragulyanMarkov Chain Monte Carlo Stochastic Gradient Langevin Dynamics
CREST, ENSAE Paris, Institut Polytechnique de Paris and MBZUAI · L2S, CNRS, Centrale Supélec, Université Paris-Saclay
Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework
May 29, 2026Zaiwei Chen, Siva Theja MaguluriControl Lyapunov Functions Lyapunov Stability
Purdue IE · Georgia Tech IE
Local linear convergence of gradient methods for overparameterized Gaussian mixtures
May 29, 2026Jingxing Wang, Vasileios Charisopoulos, Maryam FazelGradient Descent Gaussian Mixture Models
Electrical & Computer Engineering, University of Washington, Seattle, WA · National Institute for Theory and Mathematics in Biology, Chicago, IL · Amazon, Inc.
Self-Certifying Transport MCMC via Dual Spectral-Gap Certificates
May 29, 2026Jun HuMarkov Chain Monte Carlo Convergence Analysis
Wuhan University of Technology, Wuhan, China
Stability and Discretization Error of State Space Model Neural Operators
May 17, 2026Abderrahim Bendahi, Adrien Fradin, Johan Peralez +2Fourier Neural Operator Convergence Analysis
École polytechnique Paris, France · Université Claude Bernard Lyon 1, CNRS, LAGEPP UMR 5007 Villeurbanne, France · CNRS, UniversitéJulieLyonDigne1, INSA Lyon, LIRIS Lyon, France +1
Sign-Separated Asymmetric Finite-Time Error Analysis of Q-Learning
May 15, 2026Donghwan LeeQ-Learning Convergence Analysis
Department of Electrical Engineering Korea Advanced Institute of Science and Technology (KAIST) Daejeon 34141, South Korea
When and Why is Optimistic Multiplicative Weights Slow? The Geometry of Energy Dissipation
May 13, 2026John Lazarsfeld, Anas Barakat, Georgios Piliouras +2Nash Equilibrium Last-Iterate Convergence
SUTD · Google DeepMind · NUS CQT +2
Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs
May 12, 2026Michael Lu, Max Qiushi Lin, Mo Chen +1Markov Decision Processes Last-Iterate Convergence
Simon Fraser University
On Uniform Error Bounds for Kernel Regression under Non-Gaussian Noise
May 10, 2026Johannes Teutsch, Oleksii Molodchyk, Marion Leibold +2Kernel Regression Uncertainty Quantification
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

Oct 24, 2026J/K move · Enter open · S save

The Cost of an Unknown Horizon for the Last Iterate of Clipped SGD under Heavy-Tailed Noise

Yuxing Peng, Zhiqing Tang, Weijia Jia

Faculty of Arts and Sciences, Beijing Normal University, Zhuhai 519087, China · Institute of Artificial Intelligence and Future Networks, Faculty of Arts and Sciences, Beijing Normal University, Zhuhai 519087, China · Guangdong Key Lab of AI and Multi-Modal Data Processing, Beijing Normal-Hong Kong Baptist University, Zhuhai 519087, China

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

Open paper AskPDF arXiv

Training is often stopped at a data-dependent time, so guarantees for the last iterate must hold at all times simultaneously. We determine the optimal time-uniform rate for the last iterate of clipped SGD on smooth convex objectives under heavy-tailed noise with a bounded central

p

th moment,

1<p\le2

. A schedule without horizon or confidence inputs attains

\tilde O(t^{-β_p})

at all times, with

β_p=2(p-1)/(3p-1)

, also almost surely, and no rule that steps along the stochastic gradient at its current iterate attains

\tilde O(t^{-r})

for any

r>β_p

, even with adaptive step sizes and thresholds. This rate lies between the optimal rate

O(T^{-α_p})

for a known horizon

T

α_p=(p-1)/p

, and the previous time-uniform rate

\tilde O(t^{-2(p-1)/(3p)})

(Chezhegov et al., ICLR 2026); under finite variance, the exponents are

1/2

2/5

, and

1/3

. Their conjecture that a better schedule reaches the optimal rate thus holds with a known horizon (Liu; Jiang et al.) but fails without one. Querying gradients at the running average attains

\tilde O(t^{-α_p})

at all times, whereas heavy-ball momentum with geometric forgetting and polynomially bounded steps cannot improve on

β_p