Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909727571574784 |
|---|---|
| author | Sheshukova, Marina Belomestny, Denis Durmus, Alain Moulines, Eric Naumov, Alexey Samsonov, Sergey |
| author_facet | Sheshukova, Marina Belomestny, Denis Durmus, Alain Moulines, Eric Naumov, Alexey Samsonov, Sergey |
| contents | 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 $\mathcal{O}(n^{-1/2})$ with explicit dependence on a minimax-optimal asymptotic covariance matrix, and a second-order term of order $\mathcal{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_05106 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation Sheshukova, Marina Belomestny, Denis Durmus, Alain Moulines, Eric Naumov, Alexey Samsonov, Sergey Optimization and Control Machine Learning 62L20 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 $\mathcal{O}(n^{-1/2})$ with explicit dependence on a minimax-optimal asymptotic covariance matrix, and a second-order term of order $\mathcal{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. |
| title | Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation |
| topic | Optimization and Control Machine Learning 62L20 |
| url | https://arxiv.org/abs/2410.05106 |