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

• URL: http://arxiv.org/abs/2605.31309v1
• Date: Fri, 29 May 2026 13:41:01 GMT
• Title: Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework
• Abstract summary: We survey Lyapunov-based techniques for the finitetime analysis of iterative algorithms.<n>We show how generalized envelopes serve as universal Lyapunov functions, regardless of the underlying norm.<n>We discuss extensions to Markovian noise, semi-contractive operators, dissipative and high-probability bounds, and conclude with open problems.
• Score: 9.210053545945886
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Stochastic simultaneous optimistic optimization [70.50540950403109]
  We study the problem of evaluations of a function f given a finite number of perturbed by noise.<n>Our algorithm, StoSOO, follows an optimistic strategy to construct upper confidence bounds over the hierarchical partitions of the function domain to decide which point to sample next.<n>A finite-time analysis of StoSOO shows that it performs almost as well as the best specifically-tuned algorithms even though the local smoothness of the function is not known.
  arXiv  Detail & Related papers  (2026-04-27T14:34:24Z)
• A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging [2.378735224874938]
  Polyak-Rt averaging is a widely used technique to achieve the optimal variance of approximation algorithms.<n>We present a general framework for establishing non-asymptotic concentration bounds for the error of averaged SA iterates.
  arXiv  Detail & Related papers  (2025-05-27T21:58:35Z)
• Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noise [5.7071219882414885]
  Two-time-scale Approximation (SA) is an iterative algorithm with applications in reinforcement learning and optimization.<n>Motivated by applications in reinforcement learning, we give the first mean square bound on non linear two-time-scale SA.
  arXiv  Detail & Related papers  (2025-03-24T07:03:23Z)
• Stochastic Approximation with Unbounded Markovian Noise: A General-Purpose Theorem [4.769747792846004]
  We consider average-reward Reinforcement Learning with unbounded state space and reward function.<n>Recent works studied this problem in the actor-critic framework.<n>We study Temporal Difference (TD) learning with linear function approximation.
  arXiv  Detail & Related papers  (2024-10-29T03:40:53Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  We introduce an observation-matrix-based framework for fully asynchronous online Federated Learning with adversaries. Our main result is that the proposed algorithm almost surely converges to the desired mean $mu.$ We derive this convergence using a novel differential-inclusion-based two-timescale analysis.
  arXiv  Detail & Related papers  (2023-04-04T04:32:29Z)
• Stochastic Approximation Beyond Gradient for Signal Processing and Machine Learning [40.636276521022474]
  Approximation (SA) is a classical algorithm that has had since the early days a huge impact on signal processing. This article introduces the non-stochastic-gradient perspectives of SA to the signal processing and machine learning audiences. We build our analysis framework based on classes of Lyapunov functions that satisfy a variety of mild conditions.
  arXiv  Detail & Related papers  (2023-02-22T05:00:51Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  Many real-world problems have complicated non functional constraints and use a large number of data points. Our proposed method outperforms an existing method with the previously best-known result.
  arXiv  Detail & Related papers  (2022-12-19T14:48:54Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  We propose a model-free reinforcement learning algorithm inspired by the popular randomized least squares value iteration (RLSVI) algorithm. Our algorithm drives exploration by simply perturbing the training data with judiciously chosen i.i.d. scalar noises. We complement the theory with an empirical evaluation across known difficult exploration tasks.
  arXiv  Detail & Related papers  (2021-06-15T02:23:07Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants [39.28675942566465]
  This paper develops a framework to study finite-sample convergence guarantees of a class of value-based asynchronous RL algorithms. As a by-product, we provide theoretical insights into the bias-variance trade-off, i.e., efficiency of bootstrapping in RL.
  arXiv  Detail & Related papers  (2021-02-02T15:48:19Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  adversary-resilient distributed optimization, in which. machines can independently compute gradients, and cooperate. Our algorithm is based on a new concentration technique, and its sample complexity. It is very practical: it improves upon the performance of all prior methods when no. setting machines are present.
  arXiv  Detail & Related papers  (2020-12-28T17:19:32Z)
• Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes [40.31139355952393]
  We construct a smooth Lyapunov function using the generalized envelope, and show that the iterates of SA have negative drift with respect to that Lyapunov function. In particular, we use it to establish the first-known convergence rate of the V-trace algorithm for off-policy TD-learning. We also use it to study TD-learning in the on-policy setting, and recover the existing state-of-the-art results for $Q$-learning.
  arXiv  Detail & Related papers  (2020-02-03T16:42:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.