Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation
<|reference_start|>Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation: 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 technique 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$. More precisely, we show that the 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$ can not be improved in general. We also extend this result to the $p$-th moment bound keeping optimal scaling of the remainders with respect to $n$. 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.<|reference_end|>
@article{sheshukova2024nonasymptotic,
    title={Nonasymptotic Analysis of Stochastic Gradient Descent with the
  Richardson-Romberg Extrapolation},
    author={Marina Sheshukova, Denis Belomestny, Alain Durmus, Eric Moulines,
  Alexey Naumov, Sergey Samsonov},
    journal={arXiv preprint arXiv:2410.05106},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.05106},
    primaryClass={math.OC cs.LG stat.ML}
}