# Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Streaming Data

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 59 references that are in the map.
- First posted on arXiv 15 Sep 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)

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

- [Non asymptotic analysis of Adaptive stochastic gradient algorithms and applications](https://mlsanity.com/paper/2303.01370/) (2023)
- [Data Sampling Affects the Complexity of Online SGD over Dependent Data](https://mlsanity.com/paper/2204.00006/) (2022)
- [Online estimation of the inverse of the Hessian for stochastic optimization with application to universal stochastic Newton algorithms](https://mlsanity.com/paper/2401.10923/) (2024)
- [Learning from time-dependent streaming data with online stochastic algorithms](https://mlsanity.com/paper/2205.12549/) (2022)
- [Beyond Propagation of Chaos: A Stochastic Algorithm for Mean Field Optimization](https://mlsanity.com/paper/2503.13115/) (2025)

## Abstract (arXiv)

We introduce a streaming framework for analyzing stochastic approximation/optimization problems. This streaming framework is analogous to solving optimization problems using time-varying mini-batches that arrive sequentially. We provide non-asymptotic convergence rates of various gradient-based algorithms; this includes the famous Stochastic Gradient (SG) descent (a.k.a. Robbins-Monro algorithm), mini-batch SG and time-varying mini-batch SG algorithms, as well as their iterated averages (a.k.a. Polyak-Ruppert averaging). We show i) how to accelerate convergence by choosing the learning rate according to the time-varying mini-batches, ii) that Polyak-Ruppert averaging achieves optimal convergence in terms of attaining the Cramer-Rao lower bound, and iii) how time-varying mini-batches together with Polyak-Ruppert averaging can provide variance reduction and accelerate convergence simultaneously, which is advantageous for many learning problems, such as online, sequential, and large-scale learning. We further demonstrate these favorable effects for various time-varying mini-batches.