📊 statistics

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

This paper presents a unified Lyapunov framework using generalized Moreau envelopes to provide non-asymptotic convergence guarantees for stochastic iterative algorithms across various settings, including i.i.d. and Markovian noise, with specific applications to reinforcement learning and stochastic gradient descent.

Original authors: Zaiwei Chen, Siva Theja Maguluri

Published 2026-06-01

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Zaiwei Chen, Siva Theja Maguluri

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Finding a Needle in a Noisy Haystack

Imagine you are trying to find the exact center of a dark room (the fixed point). You have a map, but it's a bit blurry, and every time you look at it, the room seems to shift slightly because of a shaky hand or a gust of wind (the noise).

In the world of math and computer science, this is called Stochastic Approximation (SA). It's the engine behind many modern AI systems, like Reinforcement Learning (where an agent learns by trial and error) and Stochastic Gradient Descent (how AI learns from massive datasets).

For a long time, mathematicians could only say, "If you keep trying forever, you will eventually find the center." This is called asymptotic convergence. But in the real world, we don't have infinite time. We need to know: How many steps will it take to get close enough? And how confident can we be that we won't wander off?

This paper provides a new, unified "roadmap" to answer those questions. It uses a mathematical tool called a Lyapunov function to prove exactly how fast these algorithms converge, even when the data is messy.

The Core Problem: The "Rough" Map

The paper starts by looking at a specific type of problem where the "map" (the operator) is contractive.

Analogy: Imagine a rubber sheet. If you stretch it out and then let it snap back, any two points on the sheet get closer together. A "contractive" operator is like that rubber sheet; it naturally pulls different guesses toward a single, unique solution.

However, in real life, we can't see the whole rubber sheet. We only get noisy, blurry glimpses of it. The challenge is that standard mathematical tools (like measuring distance with a ruler) often break down when the "ruler" itself is weird or the noise is unpredictable.

The Solution: The "Smoothed" Lyapunov Function

The authors introduce a clever trick to solve this. They use something called a Generalized Moreau Envelope.

The Metaphor: Imagine you are trying to roll a ball down a bumpy, jagged hill to reach the bottom (the solution). The jagged edges make it hard to predict exactly how the ball will roll.
The Trick: Instead of rolling the ball on the jagged hill, you pour a thick layer of honey over the hill. The honey smooths out the jagged rocks, creating a gentle, smooth slope.
The Result: This "honey-coated" hill is your Lyapunov function. It acts as a perfect guide. Because it is smooth, you can use calculus to predict exactly how fast the ball (your algorithm's guess) will roll down to the bottom.

The paper proves that this "honey" works for any type of measurement system (any norm), not just the standard straight-line distance. This is a huge deal because it unifies many different types of algorithms under one single mathematical umbrella.

What the Paper Achieves

Using this "smoothed" guide, the authors derive finite-time bounds. This means they can calculate:

The Speed: How quickly the error shrinks.
The Trade-off: They explain the balance between Bias (how far off your average guess is) and Variance (how much your guess jumps around due to noise).
- Analogy: If you take huge steps (large learning rate), you get to the bottom fast, but you might overshoot and bounce around wildly (high variance). If you take tiny steps, you are very steady, but it takes forever to get there (high bias). The paper tells you exactly how to tune your step size to get the best result in the shortest time.

Real-World Applications Mentioned

The paper explicitly connects this math to several famous algorithms:

Q-Learning: A method where an AI learns the best moves in a game (like Chess or Go) by trying things out. The paper shows how to guarantee it finds the best strategy quickly.
TD-Learning (Temporal Difference): Used for predicting future rewards, like a self-driving car predicting traffic.
Stochastic Gradient Descent (SGD): The workhorse of deep learning, used to train neural networks.
Robust RL: Learning when the environment might change or be uncertain.

Going Beyond the Basics

The paper doesn't stop at the "easy" cases. It extends this "honey-coated" logic to harder scenarios:

Markovian Noise: What if the noise isn't random, but follows a pattern (like a weather system)? The paper shows how to handle this by waiting for the pattern to "mix" or settle before measuring progress.
Seminorms: What if the "distance" you measure doesn't care about certain directions (like measuring the height of a mountain but ignoring its width)? The paper adapts the math to handle these partial measurements.
High-Probability Bounds: Instead of just saying "on average, you will be close," the paper provides guarantees like "99% of the time, you will be within this specific distance."

What's Still Unknown (Open Problems)

The authors are honest about what they haven't solved yet. They point out three areas where the "honey" isn't quite thick enough yet:

Multiple Time Scales: What if you have two balls rolling down hills at different speeds, and they are tied together? (This happens in "Actor-Critic" AI).
Rapidly Changing Noise: What if the "wind" changes direction instantly based on where you are? (This happens when an AI's own decisions change the data it sees).
Non-Expansive Operators: What if the rubber sheet doesn't pull things closer, but just keeps them the same distance apart? (This is a much harder mathematical puzzle).

Summary

In short, this paper builds a universal "GPS" for noisy, iterative algorithms. It takes a complex, jagged mathematical landscape and smooths it out with a "Generalized Moreau Envelope" (the honey). This allows researchers to predict exactly how fast AI algorithms will learn, how much data they need, and how to tune them to avoid getting stuck or bouncing around forever. It turns vague promises of "eventual success" into precise, time-bound guarantees.

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

Problem Statement

The paper addresses the finite-time (non-asymptotic) analysis of Stochastic Approximation (SA) algorithms used to solve fixed-point equations of the form $\bar{F}(x) = x$ . In many practical settings, such as large-scale optimization and reinforcement learning (RL), the operator $\bar{F}(\cdot)$ cannot be evaluated exactly. Instead, it is accessed via a noisy oracle $F(x, Y)$ , where $Y$ is a random variable. The goal is to characterize the convergence rate of the iterates $x_k$ generated by the SA recursion:
$x_{k+1} = x_k + \alpha_k (F(x_k, Y_k) - x_k)$
specifically in terms of the mean squared error (MSE) $\mathbb{E}[\|x_k - x^*\|_c^2]$ and high-probability bounds, where $x^*$ is the unique fixed point and $\|\cdot\|_c$ is a contraction norm.

While asymptotic convergence is well-understood via the Ordinary Differential Equation (ODE) method, finite-time guarantees are crucial for data-driven applications to determine sample complexity. A central challenge in this domain is constructing a valid Lyapunov function that induces a negative drift (ensuring stability) while simultaneously controlling errors arising from stochasticity and discretization, particularly when the contraction norm $\|\cdot\|_c$ is arbitrary (e.g., the $\ell_\infty$ -norm common in RL) and the associated squared-norm function is non-smooth.

Methodology

The paper proposes a unified framework based on Lyapunov-drift analysis utilizing generalized Moreau envelopes.

1. The Lyapunov Construction

The core technical contribution is the systematic construction of a smooth Lyapunov function to replace the non-smooth squared-norm function $f(x) = \frac{1}{2}\|x - x^*\|_c^2$ .

Generalized Moreau Envelope: The authors define a Lyapunov function $M(x)$ as the generalized Moreau envelope of the squared contraction norm $f(\cdot)$ with respect to a smooth auxiliary function $g(\cdot)$ (typically a squared $\ell_p$ -norm for $p \ge 2$ ):
$M_{\theta, g}^f(x) = \min_{u \in \mathbb{R}^d} \left\{ f(u) + \frac{1}{\theta} g(x - u) \right\}$
Properties: This construction ensures that $M(x)$ $M (x)$ is:
1. Smooth: It is $L/\theta$ -smooth with respect to the auxiliary norm, allowing the control of discretization and stochastic errors via Taylor expansions.
2. Equivalent to the Norm: It approximates the original squared norm within constant factors, ensuring that convergence in $M(x)$ implies convergence in the original metric.
3. Contractive: It induces a negative drift under the deterministic dynamics of the fixed-point iteration.

2. Analysis Steps

The analysis proceeds through the following steps:

One-Step Drift Inequality: Using the smoothness of $M(x)$ $M (x)$ , the authors derive a one-step inequality for the expected evolution of the Lyapunov function. This decomposes the error into:
- Deterministic Drift: A negative term proportional to the current error (due to the contraction property).
- Noise Term: A zero-mean term (under i.i.d. assumptions) arising from the stochastic oracle.
- Higher-Order Terms: Terms proportional to $\alpha_k^2$ arising from discretization and noise variance.
Recursion Solving: By bounding the noise and higher-order terms, a recursive inequality of the form $M_{k+1} \le (1 - O(\alpha_k))M_k + O(\alpha_k^2)$ is established. Solving this recursion yields explicit finite-time bounds for different stepsize schedules (constant, diminishing with $1/k$ , and general polynomial decay).
Extensions: The framework is extended to handle:
- Markovian Noise: Using conditioning arguments and mixing time bounds to control the bias introduced by dependent samples.
- Seminorm Contraction: Adapting the Moreau envelope to seminorms (e.g., span seminorms in average-reward RL).
- Dissipativity: Applying the framework to operators that satisfy a dissipativity condition rather than strict contraction.
- High-Probability Bounds: Utilizing the log-moment generating function (log-MGF) of the Moreau envelope and Ville's maximal inequality to derive super-polynomial tail bounds.

Key Contributions and Results

1. Unified Finite-Time Bounds for Contractive SA

The paper provides a general theorem (Theorem 2.1) establishing mean-square convergence rates for SA under contractive operators with i.i.d. noise.

Constant Stepsize ( $\alpha_k = \alpha$ ): The error converges geometrically to a steady-state error proportional to $\alpha$ .
Diminishing Stepsize ( $\alpha_k \propto 1/k$ ): The error converges at a rate of $O(1/k)$ , provided the stepsize coefficient is sufficiently large.
General Diminishing Stepsize ( $\alpha_k \propto 1/k^z, z \in (0,1)$ ): The bias decays almost geometrically, while the variance decays at $O(1/k^z)$ , resulting in an overall $O(1/k^z)$ rate.

2. Application to Reinforcement Learning

The framework is applied to unify the analysis of several RL algorithms:

Q-Learning: The paper reformulates Q-learning as a contractive SA problem under the $\ell_\infty$ -norm. It derives sample complexity bounds of $\tilde{O}(\epsilon^{-2}(1-\gamma)^{-5})$ for constant stepsizes.
TD-Learning: The analysis covers on-policy and off-policy TD-learning, including bootstrapping methods (n-step TD, TD( $\lambda$ )). It provides theoretical insights into the bias-variance trade-off in off-policy learning and the efficiency of bootstrapping.
Linear SA: The results recover known bounds for linear SA (e.g., linear regression, TD(0)) by showing they fit the contractive framework under a weighted norm.

3. Extensions to Complex Noise and Operators

Markovian Noise: The paper establishes finite-time bounds for SA with Markovian noise (Theorem 4.1), showing that the error bound holds after a mixing time $t_\alpha$ and includes an additional logarithmic factor $O(\log(1/\alpha))$ in the variance term.
Seminorms and Dissipativity: The framework is extended to average-reward RL (using seminorms) and control problems with dissipative operators, demonstrating the versatility of the Moreau envelope approach.
High-Probability Bounds: Theorem 5.1 provides high-probability bounds with sub-Gaussian tails for SA under additive sub-Gaussian noise, extending the analysis beyond mean-square guarantees.

Significance and Claims

The paper claims to present a unified and self-contained roadmap for the finite-time analysis of stochastic approximation algorithms. Its primary significance lies in:

Universality of the Lyapunov Function: By demonstrating that generalized Moreau envelopes serve as universal Lyapunov functions regardless of the underlying contraction norm, the paper resolves the difficulty of analyzing SA in non-Euclidean settings (specifically $\ell_\infty$ -norms prevalent in RL).
Bridging Theory and Practice: It moves beyond asymptotic ODE methods to provide concrete, non-asymptotic guarantees that characterize the bias-variance trade-off in stepsize selection, offering practical guidance for algorithm tuning.
Unification of RL Algorithms: It shows that diverse RL algorithms (Q-learning, TD-learning, linear regression) can be analyzed under a single theoretical umbrella, simplifying the understanding of their convergence properties.
Foundation for Future Work: The paper explicitly frames its results as a foundation for addressing open problems, such as the analysis of multiple time-scale algorithms, rapidly time-inhomogeneous Markovian noise (e.g., in $\epsilon$ -greedy exploration), and nonexpansive operators, noting that current results in these areas are fragmented or lack sharp finite-time rates.

The authors maintain a modest stance, acknowledging that while their framework provides tight upper bounds for contractive settings, it does not necessarily match statistical lower bounds for all specific algorithms (e.g., Q-learning sample complexity) without further algorithmic refinements like variance reduction. The paper serves as a survey and a methodological guide rather than a proposal for new experimental algorithms.