A Rate Transfer Method: Convergence Rates in Stochastic Gradient Descent via Stochastic Calculus

Neil Walton

cs.LGOct 13, 2026

A Rate Transfer Method: Convergence Rates in Stochastic Gradient Descent via Stochastic Calculus

Authors: Neil Walton

Organizations: Durham University

Abstract

We develop a rate-transfer method that converts finite-time Lyapunov estimates for an associated stochastic differential equation (SDE) into finite-time convergence bounds for stochastic gradient algorithms. Under generic moment and smoothness conditions, the convergence analysis of the stochastic gradient method reduces to a calculus argument verifying a Lyapunov generator inequality for the SDE. The method recovers established rates for classical stochastic gradient methods and provides a way to establish convergence rates for new optimization algorithms through calculus arguments applied to their associated SDEs.

Control Lyapunov Functions

See all 12 papers

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
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
Distribution of hitting times for dissipative random dynamical systems on $\mathbb{R}^d$ , with application to stochastic gradient descent
Aug 11, 2026Stéphane Galatolo, Stéphane ChrétienStochastic Optimization Convergence Stochastic Gradient Descent
Dipartimento di Matematica, Università di Pisa, Largo Pontecorvo 5, 56127 Pisa, Italy · Laboratoire ERIC, Université Lumière Lyon 2, 5 av. Pierre Mendès-France, 69300 Bron, France

May 29, 2026J/K move · Enter open · S save

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

Zaiwei Chen, Siva Theja Maguluri

Purdue IE · Georgia Tech IE

Control Lyapunov Functions Lyapunov Stability Stochastic Approximation Temporal-Difference Learning Convergence Analysis

Open paper AskPDF arXiv

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.

Abstract

Control Lyapunov Functions

Explore similar work

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

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

Distribution of hitting times for dissipative random dynamical systems on Rd\mathbb{R}^dRd, with application to stochastic gradient descent

Distribution of hitting times for dissipative random dynamical systems on $\mathbb{R}^d$ , with application to stochastic gradient descent