RECORD
Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ball
Machine Learning · Submitted 14 Jun 2020
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim 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 .
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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. | contribution 0.61 | 0.78 | 0.04 | asserted 0.82 |
| s1 | 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 . | contribution 0.63 | 0.96 | 0.43 | asserted 1.00 |
| s2 | 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. | result 1.00 | 0.95 | 0.36 | asserted 1.00 |
| s3 | 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. | result 0.79 | 0.96 | 0.12 | asserted 1.00 |
| s4 | Using a substantially different analysis, we show that these rates hold for SHB as well, but at the last iterate. | result 0.88 | 0.96 | 0.18 | asserted 1.00 |
| s5 | This distinction is important because it is the last iterate of SGD and SHB which is used in practice. | interpretation 0.99 | 0.17 | 0.06 | asserted 1.00 |
| s6 | We also show that the last iterate of SHB converges to a minimizer \emph{almost surely}. | result 0.99 | 0.96 | 0.13 | asserted 1.00 |
| s7 | 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)$. | result 0.97 | 0.93 | 0.08 | asserted 1.00 |
| s8 | Finally, in the nonconvex setting, we prove similar rates on the lowest gradient norm along the trajectory of SGD. | result 0.91 | 0.96 | 0.08 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original 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.
Human review
How the literature uses it
15 arXiv papers cite this in 21 sentences
Papers citing it · 13 sentences without a confident label
Compares with it 2 papers
-
Moreover, our result differs from [ref] due to the presence of bias $r_n$ in the stochastic gradient.
A stochastic gradient method for a class of nonlinear PDE-constrained optimal control problems under uncertainty · Asymptotic almost sure convergence rates · 0.85
-
Our result and proof technique has some similarities to [ref] , which shows almost sure convergence of standard SGD under general expected smoothness conditions on stochastic gradients.
A simplified convergence theory for Byzantine resilient stochastic gradient descent · Introduction · 1.00
Cites it as support 3 papers
-
Mathematically, this bias is proportional to the change in gradients along the update step: [equation] Without correcting this curvature-induced bias, momentum methods cannot achieve the optimal $𝒪(ϵ^-3)$ sample complexity required for non-convex optimization [ref] (see Figure [ref])..
RanSOM: Second-Order Momentum with Randomized Scaling for Constrained and Unconstrained Optimization · The Bias-Variance Bottleneck · 0.97
-
Firstly, it maintains an iterate $x_k+1$ obtained as a weighted average of the previous average $x_k$ and the current dual averaging iterate $z_k+1.$ It has been recently noticed that this averaging step can be interpreted as introducing momentum in the algorithm [ref] (more details in <ref>).
Dual Averaging is Surprisingly Effective for Deep Learning Optimization · Modernizing dual averaging · 0.96
-
Throughout the literature, there are examples for which (small batch size) stochastic momentum methods such as SHB and stochastic Nesterov's accelerated method (SNAG) achieve performances equal to (or even worse) than small batch size SGD (see e.g., [ref] for heavy-ball and [ref] for Nesterov).
Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Models · Motivation and related work · 0.98
Cites it as background 2 papers
-
The first historical example is the Heavy Ball with Friction optimization based on the seminal contribution [ref] and then translated into a stochastic framework (see e.g. [ref] ).
Asymptotic study of stochastic adaptive algorithm in non-convex landscape · Stochastic optimization · 0.95
-
Momentum and accelerated methods for convex stochastic optimization can be referred from [ref] .
Minibatch and Momentum Model-based Methods for Stochastic Weakly Convex Optimization · Introduction · 1.00
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.