# ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Aug 2020.

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

- [Optimal variance-reduced stochastic approximation in Banach spaces](https://mlsanity.com/paper/2201.08518/) (2022)
- [High Confidence Level Inference is Almost Free using Parallel Stochastic Optimization](https://mlsanity.com/paper/2401.09346/) (2024)
- [Instance-Dependent Confidence and Early Stopping for Reinforcement Learning](https://mlsanity.com/paper/2201.08536/) (2022)
- [Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning](https://mlsanity.com/paper/2206.00796/) (2022)
- [Covariance Estimators for the ROOT-SGD Algorithm in Online Learning](https://mlsanity.com/paper/2212.01259/) (2022)
- [Enhancing Stochastic Optimization for Statistical Efficiency Using ROOT-SGD with Diminishing Stepsize](https://mlsanity.com/paper/2407.10955/) (2024)

## Abstract (arXiv)

We study the problem of solving strongly convex and smooth unconstrained optimization problems using stochastic first-order algorithms. We devise a novel algorithm, referred to as Recursive One-Over-T SGD (ROOT-SGD), based on an easily implementable, recursive averaging of past stochastic gradients. We prove that it simultaneously achieves state-of-the-art performance in both a finite-sample, nonasymptotic sense and an asymptotic sense. On the non-asymptotic side, we prove risk bounds on the last iterate of ROOT-SGD with leading-order terms that match the optimal statistical risk with a unity pre-factor, along with a higher-order term that scales at the sharp rate of O(n-3/2) under the Lipschitz condition on the Hessian matrix. On the asymptotic side, we show that when a mild, one-point Hessian continuity condition is imposed, the rescaled last iterate of (multi-epoch) ROOT-SGD converges asymptotically to a Gaussian limit with the Cram'er-Rao optimal asymptotic covariance, for a broad range of step-size choices.