# Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applications

arXiv: https://arxiv.org/abs/2312.02828 · HTML: https://mlsanity.com/paper/2312.02828/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 86 references that are in the map.
- First posted on arXiv 5 Dec 2023.

## Builds on (most cited first, 21 of 21)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning](https://mlsanity.com/paper/2002.00260/) (2020)
- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (2021)
- [Q-learning with Nearest Neighbors](https://mlsanity.com/paper/1802.03900/) (2018)
- [On Almost Sure Convergence Rates of Stochastic Gradient Methods](https://mlsanity.com/paper/2202.04295/) (2022)
- [Sharp Analysis of Stochastic Optimization under Global Kurdyka-Lojasiewicz Inequality](https://mlsanity.com/paper/2210.01748/) (2022)
- [Asymptotic Bias of Stochastic Gradient Search](https://mlsanity.com/paper/1709.00291/) (2017)
- [Accelerated stochastic approximation with state-dependent noise](https://mlsanity.com/paper/2307.01497/) (2023)
- [Convergence of sequences: a survey](https://mlsanity.com/paper/2111.11374/) (2021)
- [Convergence of Stochastic Approximation via Martingale and Converse Lyapunov Methods](https://mlsanity.com/paper/2205.01303/) (2022)
- [Simultaneous perturbation stochastic approximation: towards one-measurement per iteration](https://mlsanity.com/paper/2203.03075/) (2022)
- [Generalized Simultaneous Perturbation-based Gradient Search with Reduced Estimator Bias](https://mlsanity.com/paper/2212.10477/) (2022)
- [Convergence of the Stochastic Heavy Ball Method With Approximate Gradients and/or Block Updating](https://mlsanity.com/paper/2303.16241/) (2023)

## Built on by (most cited first, 15 of 15)

- [Towards Weaker Variance Assumptions for Stochastic Optimization](https://mlsanity.com/paper/2504.09951/) (2025)
- [Towards Formalizing Reinforcement Learning Theory: A Robbins-Siegmund Approach](https://mlsanity.com/paper/2511.03618/) (2025)
- [Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning](https://mlsanity.com/paper/2509.26442/) (2025)
- [A quantitative Robbins-Siegmund theorem](https://mlsanity.com/paper/2410.15986/) (2024)
- [Neural Implicit Solution Formula for Efficiently Solving Hamilton-Jacobi Equations](https://mlsanity.com/paper/2501.19351/) (2025)
- [Statistical Inference for Online Algorithms](https://mlsanity.com/paper/2505.17300/) (2025)
- [High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noise](https://mlsanity.com/paper/2603.14514/) (2026)
- [Stochastic approximation in infinite dimensions](https://mlsanity.com/paper/2402.17258/) (2024)
- [Convergence of Momentum-Based Optimization Algorithms with Time-Varying Parameters](https://mlsanity.com/paper/2506.11904/) (2025)
- [Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift](https://mlsanity.com/paper/2605.07104/) (2026)
- [Revisiting Stochastic Approximation and Stochastic Gradient Descent](https://mlsanity.com/paper/2505.11343/) (2025)
- [Convergence Rate in Nonlinear Two-Time-Scale Stochastic Approximation with State (Time)-Dependence](https://mlsanity.com/paper/2509.11039/) (2025)
- [Convergence of Two Time-Scale Stochastic Approximation: A Martingale Approach](https://mlsanity.com/paper/2603.14481/) (2026)
- [Energy Shields for Fairness](https://mlsanity.com/paper/2605.24926/) (2026)
- [High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence](https://mlsanity.com/paper/2606.26316/) (2026)

## Abstract (arXiv)

In this paper, we study the convergence properties of the Stochastic Gradient Descent (SGD) method for finding a stationary point of a given objective function J(·). The objective function is not required to be convex. Rather, our results apply to a class of ``invex'' functions, which have the property that every stationary point is also a global minimizer. First, it is assumed that J(·) satisfies a property that is slightly weaker than the Kurdyka-Lojasiewicz (KL) condition, denoted here as (KL'). It is shown that the iterations J(boldsymbolθt) converge almost surely to the global minimum of J(·). Next, the hypothesis on J(·) is strengthened from (KL') to the Polyak-Lojasiewicz (PL) condition. With this stronger hypothesis, we derive estimates on the rate of convergence of J(boldsymbolθt) to its limit. Using these results, we show that for functions satisfying the PL property, the convergence rate of both the objective function and the norm of the gradient with SGD is the same as the best-possible rate for convex functions. While some results along these lines have been published in the past, our contributions contain two distinct improvements. First, the assumptions on the stochastic gradient are more general than elsewhere, and second, our convergence is almost sure, and not in expectation. We also study SGD when only function evaluations are permitted. In this setting, we determine the ``optimal'' increments or the size of the perturbations. Using the same set of ideas, we establish the global convergence of the Stochastic Approximation (SA) algorithm under more general assumptions on the measurement error, compared to the existing literature. We also derive bounds on the rate of convergence of the SA algorithm under appropriate assumptions.