Nonasymptotic analysis of stochastic gradient descent with the richardson-romberg extrapolation
Sheshukova, Marina Belomestny, Denis Durmus, Alain Oliviero Moulines, Eric Naumov, Aleksei Samsonov, Sergey
Sheshukova, Marina
Belomestny, Denis
Durmus, Alain Oliviero
Moulines, Eric
Naumov, Aleksei
Samsonov, Sergey
Supervisor
Department
Machine Learning
Embargo End Date
Type
Conference proceeding
Date
2025
License
Language
English
Collections
Research Projects
Organizational Units
Journal Issue
Abstract
We address the problem of solving strongly convex and smooth minimization problems using stochastic gradient descent (SGD) algorithm with a constant step size. Previous works suggested to combine the Polyak-Ruppert averaging procedure with the Richardson-Romberg extrapolation to reduce the asymptotic bias of SGD at the expense of a mild increase of the variance. We significantly extend previous results by providing an expansion of the mean-squared error of the resulting estimator with respect to the number of iterations n. We show that the root mean-squared error can be decomposed into the sum of two terms: a leading one of order O(n−1/2) with explicit dependence on a minimax-optimal asymptotic covariance matrix, and a second-order term of order O(n−3/4), where the power 3/4 is best known. We also extend this result to the higher-order moment bounds. Our analysis relies on the properties of the SGD iterates viewed as a time-homogeneous Markov chain. In particular, we establish that this chain is geometrically ergodic with respect to a suitably defined weighted Wasserstein semimetric. © 2025 13th International Conference on Learning Representations, ICLR 2025. All rights reserved.
Citation
M. Sheshukova, D. Belomestny, A. Oliviero Durmus, E. Moulines, A. Naumov, and S. Samsonov, “Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson–Romberg Extrapolation,” International Conference on Representation Learning, vol. 2025, pp. 33019–33049, May 2025
Source
13th International Conference on Learning Representations, ICLR 2025
Conference
13th International Conference on Learning Representations, ICLR 2025
Keywords
Subjects
Source
13th International Conference on Learning Representations, ICLR 2025
Publisher
International Conference on Learning Representations, ICLR