# Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ball

Source: [Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ball](<https://www.sota2.com/research/paper/68fa57c81e209131ce9a83b8>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T14:55:35.481Z

Authors: Othmane Sebbouh, Robert M. Gower, Aaron Defazio

Published: 2020-06-14T11:12:05.000Z

## Abstract

We study stochastic gradient descent (SGD) and the stochastic heavy ball method (SHB, otherwise known as the momentum method) for the general stochastic approximation problem.   For SGD, in the convex and smooth setting, we provide the first \\emph{almost sure} asymptotic convergence \\emph{rates} for a weighted average of the iterates . More precisely, we show that the convergence rate of the function values is arbitrarily close to $o(1/\\sqrt{k})$, and is exactly $o(1/k)$ in the so-called overparametrized case. We show that these results still hold when using stochastic line search and stochastic Polyak stepsizes, thereby giving the first proof of convergence of these methods in the non-overparametrized regime.   Using a substantially different analysis, we show that these rates hold for SHB as well, but at the last iterate. This distinction is important because it is the last iterate of SGD and SHB which is used in practice. We also show that the last iterate of SHB converges to a minimizer \\emph{almost surely}. Additionally, we prove that the function values of the deterministic HB converge at a $o(1/k)$ rate, which is faster than the previously known $O(1/k)$.   Finally, in the nonconvex setting, we prove similar rates on the lowest gradient norm along the trajectory of SGD.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Image Classification on CIFAR-10 (Runtime)](<https://www.sota2.com/research/sota/image-classification-on-cifar-10-runtime.md>): Image Classification; CIFAR-10; Runtime (s): 2.28.

- [Image Classification on ImageNet (Runtime)](<https://www.sota2.com/research/sota/image-classification-on-imagenet-runtime.md>): Image Classification; ImageNet; Runtime (s): 2.48.

- [Binary Classification on CIFAR-10 (val)](<https://www.sota2.com/research/sota/binary-classification-on-cifar-10-val.md>): Binary Classification; CIFAR-10 (val); Peak Validation Range: 50.04.

- [Binary Classification on ImageNet (val)](<https://www.sota2.com/research/sota/binary-classification-on-imagenet-val.md>): Binary Classification; ImageNet (val); Peak Validation Range: 50.87.

- [Image Classification on Fashion-MNIST (val)](<https://www.sota2.com/research/sota/image-classification-on-fashion-mnist-val.md>): Image Classification; Fashion-MNIST (val); Accuracy: not recorded.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2006.07867>)

[PDF](<https://arxiv.org/pdf/2006.07867.pdf>)