Back to Search
Start Over
Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Streaming Data.
- Source :
-
ESAIM: Probability & Statistics . 2023, Vol. 27, p482-514. 33p. - Publication Year :
- 2023
-
Abstract
- 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 gradientbased 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 minibatches. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 12928100
- Volume :
- 27
- Database :
- Academic Search Index
- Journal :
- ESAIM: Probability & Statistics
- Publication Type :
- Academic Journal
- Accession number :
- 174787994
- Full Text :
- https://doi.org/10.1051/ps/2023006