$\displaystyle\quad+\frac{\pi^{4}b}{32(1+a)T^{4}}\left(\left(\frac{8T^{2}}{\mu}\right)^{4/3}+\left(\frac{6T^{2}}{\mu}\right)^{\frac{5}{3}}\right)~{}.$

The original cosine stepsize was proposed with a restarting strategy, yet it
has been commonly used without restarting and achieves good results (e.g.,
Loshchilov and Hutter, 2017; Gastaldi, 2017; Zoph et al., 2018; He et al.,
2019; Cubuk et al., 2019; Liu et al., 2018; Zhao et al., 2020; You et al.,
2020; Chen et al., 2020; Grill et al., 2020). Indeed, the previous theorem has
confirmed that the cosine stepsize alone is well worth studying theoretically.
Yet for completeness, we also cover the analysis in a restart scheme for SGD
with cosine stepsize in the PL condition as following. We obtain the same
convergence rate $\mu$ and $T$ as that in the case of no restarts under the PL
condition.

Algorithm 2 SGD with Cosine Stepsize and Restarts

Input: Initial Step size $\eta_{0}$, time increase factor $r$, initial point
$\boldsymbol{x}_{1}$.

for $i=0,\dots,l$ do

Let $T_{i}=T_{0}\,r^{i}$

for $t=0,\dots,T_{i}-1$ do

Run SGD with cosine stepsize
$\frac{\eta_{0}}{2}\left(1+\cos\frac{t\pi}{T_{i}}\right)$

end for

end for

######  Theorem 10 (SGD with cosine step size and restart).

Under the same assumptions in Theorem 9. For a given $T_{0}$, $r>1$ ,
$T_{i}=T_{0}\,r^{i}$, $T\triangleq\sum_{i=0}^{l}T_{i}$, and
$\eta_{0}=(L(1+a))^{-1}$, Algorithm 2 guarantees (where $\tilde{O}$ hides the
$log$ terms)

$\displaystyle\mathbb{E}f(\boldsymbol{x}_{T})-f^{\star}$
$\displaystyle\leq\tilde{O}\left(\exp\left(-\frac{\mu(T-l-1)}{2L(1+a)}\right)+b\left(\frac{1}{\mu^{4/3}T^{4/3}}+\frac{1}{\mu^{5/3}T^{2/3}}\right)\right)~{}.$

##### Adaptivity to noise

From the above theorems, we can see that both the exponential step size and
the cosine step size have a provable advantage over polynomial ones:
_adaptivity to the noise_. Indeed, when $b=0$, namely there is only noise
relative to the distance from the optimum, they both guarantee a linear rate.
Meanwhile, if there is noise, using the _same step size without any tuning_ ,
the exponential step size recovers the rate of $O\left(1/(\mu^{2}T)\right)$
while the cosine step size achieves the rate of
$O(1/(\mu^{\frac{5}{3}}T^{\frac{2}{3}}))$ (up to poly-logarithmic terms). In
contrast, polynomial step sizes would require two different settings—decaying
vs constant—in the noisy vs no-noise situation (Karimi et al., 2016). It is
worth stressing that the rate in Theorem 8 is one of the first results in the
literature on stochastic optimization of smooth PL functions (Khaled and
Richtárik, 2020).

##### Optimality of the bounds

As far as we know, it is unknown if the rate we obtain for the optimization of
non-convex smooth functions under the PL condition is optimal or not. However,
up to poly-logarithmic terms, Theorem 8 matches at the same time the best-
known rates for the noisy and deterministic cases (Karimi et al., 2016). We
would remind the reader that this rate is not comparable with the one for
strongly convex functions which is $O(1/(\mu T))$. Meanwhile, cosine step size
achieves a rate slightly worse in $T$ (but better in $\mu$) under the same
assumptions.

##### Convergence without the PL condition

The PL condition tells us that all stationary points are optimal points
(Karimi et al., 2016), which is not always true for the parameter space in
deep learning (Jin et al., 2017). However, this condition might still hold
locally, for a considerable area around the local minimum. Indeed, as we said,
this is exactly what was proven for deep neural networks (Allen-Zhu et al.,
2019). The previous theorems tell us that once we reach the area where the
geometry of the objective function satisfies the PL condition, we can get to
the optimal point with an almost linear rate, depending on the noise.
Nevertheless, we still have to be able to reach that region. Hence, in the
following, we discuss the case where the PL condition is not satisfied and
show for both step sizes that they are still able to move to a critical point
at the optimal speed.

######  Theorem 11.

Assume $f$ is $L$-smooth and the variance of the noise on stochastic gradients
satisfies Assumption A2 and $c>1$. SGD with step sizes (3.1) with
$\eta_{0}=(cL(1+a))^{-1}$ guarantees

$\displaystyle\mathbb{E}\|\nabla
f(\tilde{\boldsymbol{x}}_{T})\|^{2}\leq\frac{3Lc(a+1)\ln\frac{T}{\beta}}{T-\beta}\cdot\left(f(\boldsymbol{x}_{1})-f^{\star}\right)+\frac{bT}{c(a+1)(T-\beta)},$

where $\tilde{\boldsymbol{x}}_{T}$ is a random iterate drawn from
$\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{T}$ with
$\mathbb{P}[\tilde{\boldsymbol{x}}_{T}=\boldsymbol{x}_{t}]=\frac{\eta_{t}}{\sum_{i=1}^{T}\eta_{i}}$.

######  Theorem 12.

Assume $f$ is $L$-smooth and the variance of the noise on stochastic gradients
satisfies Assumption A2 and $c>1$. SGD with step sizes (3.2) with
$\eta_{0}=(cL(1+a))^{-1}$ guarantees

$\displaystyle\mathbb{E}\|\nabla
f(\tilde{\boldsymbol{x}}_{T})\|^{2}\leq\frac{4Lc(a+1)}{T-1}\cdot\left(f(\boldsymbol{x}_{1})-f^{\star}\right)+\frac{21bT}{4\pi^{4}cL(a+1)(T-1)},$

where $\tilde{\boldsymbol{x}}_{T}$ is a random iterate drawn from
$\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{T}$ with
$\mathbb{P}[\tilde{\boldsymbol{x}}_{T}=\boldsymbol{x}_{t}]=\frac{\eta_{t}}{\sum_{i=1}^{T}\eta_{i}}$.

If $b\neq 0$ in Assumption A2, setting $c\propto\sqrt{T}$ and $\beta=O(1)$
would give the $\tilde{O}(1/\sqrt{T})$ rate111The $\tilde{O}$ notations hides
poly-logarithmic terms. and $O(1/\sqrt{T})$ for the exponential and cosine
step size respectively. Note that the optimal rate in this setting is
$O(1/\sqrt{T})$. On the other hand, if $b=0$, setting $c=O(1)$ and
$\beta=O(1)$ yields a $\tilde{O}(1/T)$ rate and $O(1/T)$ for the exponential
and cosine step size respectively. It is worth noting that the condition $b=0$
holds in many practical scenarios (Vaswani et al., 2019). Note that both
guarantees are optimal up to poly-logarithmic terms (Arjevani et al., 2019).

In the following, we present the proofs of these theorems. The proofs also
show the mathematical similarities between these two step sizes.

We first introduce some technical lemmas.

######  Lemma 16.

Assume $f$ is $L$-smooth and satisfies $\mu$-PL condition, and
$\eta_{t}\leq\frac{1}{L(1+a)}$. SGD guarantees

$\begin{split}\mathbb{E}f(\boldsymbol{x}_{t+1})-\mathbb{E}f(\boldsymbol{x}_{t})\leq-\frac{\eta_{t}}{2}\mathbb{E}\|\nabla
f(\boldsymbol{x}_{t})\|^{2}+\frac{L\eta_{t}^{2}b}{2}~{}.\end{split}$ (3.3)

###### Proof of Lemma 16.

By the property of smooth functions, we have

$f(\boldsymbol{x}_{t+1})\leq f(\boldsymbol{x}_{t})-\langle\nabla
f(\boldsymbol{x}_{t}),\eta_{t}\boldsymbol{g}_{t}\rangle+\frac{L}{2}\eta_{t}^{2}\|\boldsymbol{g}_{t}\|^{2}~{}.$
(3.4)

Taking expectation on both sides, we get

$\displaystyle\mathbb{E}f(\boldsymbol{x}_{t+1})-\mathbb{E}f(\boldsymbol{x}_{t})$
$\displaystyle\leq-\left(\eta_{t}-\frac{L(a+1)}{2}\eta_{t}^{2}\right)\mathbb{E}\|\nabla
f(\boldsymbol{x}_{t})\|^{2}+\frac{L}{2}\eta_{t}^{2}b$
$\displaystyle\leq-\frac{1}{2}\eta_{t}\mathbb{E}\|\nabla
f(\boldsymbol{x}_{t})\|^{2}+\frac{L}{2}\eta_{t}^{2}b,$

where in the last inequality we used the fact that
$\eta_{t}\leq\frac{1}{L(1+a)}$. ∎

######  Lemma 17.

Assume $X_{k},A_{k},B_{k}\geq 0,k=1,...$, and $X_{k+1}\leq A_{k}X_{k}+B_{k}$,
then we have

$X_{k+1}\leq\prod_{i=1}^{k}A_{i}X_{1}+\sum_{i=1}^{k}\prod_{j=i+1}^{k}A_{j}B_{i}~{}.$

###### Proof of Lemma 17.

When $k=1$, $X_{2}\leq A_{1}X_{1}+B_{1}$ satisfies. By induction, assume
$X_{k}\leq\prod_{i=1}^{k-1}A_{i}X_{1}+\sum_{i=1}^{k-1}\prod_{j=i+1}^{k-1}A_{j}B_{i}$,
and we have

$\displaystyle X_{k+1}$ $\displaystyle\leq
A_{k}\left(\prod_{i=1}^{k-1}A_{i}X_{1}+\sum_{i=1}^{k-1}\prod_{j=i+1}^{k-1}A_{j}B_{i}\right)+B_{k}=\prod_{i=1}^{k}A_{i}X_{1}+\sum_{i=1}^{k-1}\prod_{j=i+1}^{k}A_{j}B_{i}+A_{k}B_{k}$
$\displaystyle=\prod_{i=1}^{k}A_{i}X_{1}+\sum_{i=1}^{k}\prod_{j=i+1}^{k}A_{j}B_{i}~{}.\qed$

######  Lemma 18.

For $\forall T\geq 1$, we have $\sum_{t=1}^{T}\cos\frac{t\pi}{T}=-1$.

###### Proof of Lemma 18.

If $T$ is odd, we have

$\displaystyle\sum_{t=1}^{T}\cos\frac{t\pi}{T}=\cos\frac{T\pi}{T}+\sum_{t=1}^{(T-1)/2}\cos\frac{t\pi}{T}+\cos\frac{(T-t)\pi}{T}=\cos\pi=-1,$

where in the second inequality we used the fact that $\cos(\pi-x)=-\cos(x)$
for any $x$. If $T$ is even, we have

$\sum_{t=1}^{T}\cos\frac{t\pi}{T}=\cos\frac{T\pi}{T}+\cos\frac{T\pi}{2T}+\sum_{t=1}^{T/2-1}\cos\frac{t\pi}{T}+\cos\frac{(T-t)\pi}{T}=\cos\pi=-1~{}.\qed$

######  Lemma 19.

For $T\geq 3$, $\alpha\geq 0.69$ and
$\frac{\alpha^{T+1}}{(1-\alpha)}\leq\frac{2\beta}{\ln\frac{T}{\beta}}$.

###### Proof of Lemma 19.

We have

$\displaystyle\frac{\alpha^{T+1}}{(1-\alpha)}=\frac{\alpha\beta}{T(1-\alpha)}=\frac{\beta}{T\left(1-\exp\left(-\frac{1}{T}\ln\frac{T}{\beta}\right)\right)}\leq\frac{2\beta}{\ln\frac{T}{\beta}},$

where in the last inequality we used $\exp(-x)\leq 1-\frac{x}{2}$ for
$0<x<\frac{1}{e}$ and the fact that
$\frac{1}{T}\ln\left(\frac{T}{\beta}\right)\leq\frac{\ln
T}{T}\leq\frac{1}{e}$. ∎

######  Lemma 20.

$1-x\leq\ln\left(\frac{1}{x}\right),\forall x>0.$

###### Proof of Lemma 20.

It is enough to prove that $f(x):=x-1-\ln x\geq 0$. Observe that
$f^{\prime}(x)$ is increasing and $f^{\prime}(1)=0$, hence, we have $f(x)\geq
f(1)=0$. ∎

######  Lemma 21.

Let $a,b\geq 0$. Then

$\sum_{t=0}^{T}\exp(-bt)t^{a}\leq
2\exp(-a)\left(\frac{a}{b}\right)^{a}+\frac{\Gamma(a+1)}{b^{a+1}}~{}.$

###### Proof of Lemma 21.

Note that $f(t)=\exp(-bt)t^{a}$ is increasing for $t\in[0,a/b]$ and decreasing
for $t\geq a/b$. Hence, we have

$\displaystyle\sum_{t=0}^{T}\exp(-bt)t^{a}$
$\displaystyle\leq\sum_{t=0}^{\lfloor
a/b\rfloor-1}\exp(-bt)t^{a}+\exp(-b\lfloor a/b\rfloor)\lfloor
a/b\rfloor^{a}+\exp(-b\lceil a/b\rceil)\lceil a/b\rceil^{a}$
$\displaystyle\quad+\sum_{\lceil a/b\rceil+1}^{T}\exp(-bt)t^{a}$
$\displaystyle\leq 2\exp(-a)(a/b)^{a}+\int_{0}^{\lfloor
a/b\rfloor}\exp(-bt)t^{a}dt+\int_{\lceil a/b\rceil}^{T}\exp(-bt)t^{a}dt$
$\displaystyle\leq 2\exp(-a)(a/b)^{a}+\int_{0}^{T}\exp(-bt)t^{a}dt$
$\displaystyle\leq 2\exp(-a)(a/b)^{a}+\int_{0}^{\infty}\exp(-bt)t^{a}dt$
$\displaystyle=2\exp(-a)(a/b)^{a}+\frac{1}{b^{a+1}}\Gamma(a+1)~{}.\qed$

###### Proof of Theorem 11 and Theorem 12.

We observe that for exponential step sizes,

$\displaystyle\sum_{t=1}^{T}\eta^{2}_{t}\leq\frac{\alpha^{2}}{L^{2}c^{2}(a+1)^{2}(1-\alpha^{2})}~{}.$

and for cosine step sizes,

$\displaystyle\sum_{t=1}^{T}\eta_{t}^{2}$
$\displaystyle=\frac{\eta_{0}^{2}}{4}\sum_{t=1}^{T}\left(1+\cos\frac{t\pi}{T}\right)^{2}=\frac{\eta_{0}^{2}}{4}\sum_{t=0}^{T-1}\left(1-\cos\frac{t\pi}{T}\right)^{2}=\eta_{0}^{2}\sum_{t=1}^{T}\sin^{4}\frac{t\pi}{2T}$
$\displaystyle\leq\eta_{0}^{2}\sum_{t=1}^{T}\frac{t^{4}\pi^{4}}{16T^{4}}\leq\frac{21\eta_{0}^{2}T}{8\pi^{4}}~{}.$

Summing (3.3) over $t=1,\dots,T$ and dividing both sides by
$\sum_{t=1}^{T}\eta_{t}$, we get the stated bound. ∎

We can now prove both Theorem 8 and Theorem 9.

###### Proof of Theorem 8 and Theorem 9..

Denote $\mathbb{E}f(\boldsymbol{x}_{t})-f^{\star}$ by $\Delta_{t}$. From Lemma
16 and the PL condition, we get

$\Delta_{t+1}\leq(1-\mu\eta_{t})\Delta_{t}+\frac{L}{2}\eta_{t}^{2}b^{2}~{}.$
(3.5)

By Lemma 17 and $1-x\leq\exp(-x)$, we have

$\displaystyle\Delta_{T+1}\leq\prod_{t=1}^{T}(1-\mu\eta_{t})\Delta_{1}+\frac{L}{2}\sum_{t=1}^{T}\prod_{i=t+1}^{T}(1-\mu\eta_{i})\eta_{t}^{2}b$
(3.6)
$\displaystyle\leq\exp\left(-\mu\sum_{t=1}^{T}\eta_{t}\right)\Delta_{1}+\frac{Lb}{2}\sum_{t=1}^{T}\exp\left(-\mu\sum_{i=t+1}^{T}\eta_{i}\right)\eta_{t}^{2}.$
(3.7)

We then show that both the exponential step size and the cosine step size
satisfy $\sum_{t=1}^{T}\eta_{t}=\Omega(T)$, which guarantees a linear rate in
the noiseless case.

For the cosine step size (3.2), we observe that

$\displaystyle\sum_{t=1}^{T}\eta_{t}=\frac{\eta_{0}T}{2}+\frac{\eta_{0}}{2}\sum_{t=1}^{T}\cos\frac{t\pi}{T}=\frac{\eta_{0}(T-1)}{2},$

where in the last equality we used Lemma 18.

Also, for the exponential step size (3.1), we can show

$\displaystyle\sum_{t=1}^{T}\eta_{t}=\eta_{0}\frac{\alpha-\alpha^{T+1}}{1-\alpha}$
$\displaystyle\geq\frac{\eta_{0}\alpha}{1-\alpha}-\frac{2\eta_{0}\beta}{\ln\frac{T}{\beta}}$
$\displaystyle\geq
T\cdot\frac{0.69\eta_{0}}{\ln\frac{T}{\beta}}-\frac{2\eta_{0}\beta}{\ln\frac{T}{\beta}},$

where we used Lemma 19 in the first inequality and Lemma 20 in the second
inequality.

Next, we upper bound
$\sum_{t=1}^{T}\exp\left(-\mu\sum_{i=t+1}^{T}\eta_{i}\right)\eta_{t}^{2}$ for
these two kinds of step sizes respectively.

For the exponential step size, by Lemma 19, we obtain

$\displaystyle\sum_{t=1}^{T}\exp\left(-\mu\sum_{i=t+1}^{T}\eta_{i}\right)\eta_{t}^{2}$
$\displaystyle=\eta_{0}^{2}\sum_{t=1}^{T}\exp\left(-\mu\eta_{0}\frac{\alpha^{t+1}-\alpha^{T+1}}{1-\alpha}\right)\alpha^{2t}$
$\displaystyle\leq\eta_{0}^{2}C(\beta)\sum_{t=1}^{T}\exp\left(-\frac{\mu\eta_{0}\alpha^{t+1}}{1-\alpha}\right)\alpha^{2t}$
$\displaystyle\leq\eta_{0}^{2}C(\beta)\sum_{t=1}^{T}\left(\frac{e}{2}\frac{\mu\alpha^{t+1}}{L(1+a)(1-\alpha)}\right)^{-2}\alpha^{2t}$
$\displaystyle\leq\frac{4L^{2}(1+a)^{2}}{e^{2}\mu^{2}}\sum_{t=1}^{T}\frac{1}{\alpha^{2}}\ln^{2}\left(\frac{1}{\alpha}\right)\leq\frac{10L^{2}(1+a)^{2}\ln^{2}\frac{T}{\beta}}{e^{2}\mu^{2}T},$

where in the second inequality we used
$\exp(-x)\leq\left(\frac{\gamma}{ex}\right)^{\gamma},\forall x>0,\gamma>0$.

For the cosine step size, using the fact that $\sin x\geq\frac{2}{\pi}x$ for
$0\leq x\leq\frac{\pi}{2}$, we can lower bound $\sum_{i=t+1}^{T}\eta_{i}$ by

$\displaystyle\sum_{i=t+1}^{T}\eta_{i}$
$\displaystyle=\frac{\eta_{0}}{2}\sum_{i=t+1}^{T}\left(1+\cos\frac{i\pi}{T}\right)$
$\displaystyle=\frac{\eta_{0}}{2}\sum_{i=0}^{T-t-1}\sin^{2}\frac{i\pi}{2T}\geq\frac{\eta_{0}}{2T^{2}}\sum_{i=0}^{T-t-1}i^{2}$
$\displaystyle\geq\frac{\eta_{0}(T-t-1)^{3}}{6T^{2}}~{}.$

Then, we proceed

$\displaystyle\sum_{t=1}^{T}\exp\left(-\mu\sum_{i=t+1}^{T}\eta_{i}\right)\eta_{t}^{2}$
$\displaystyle\leq\frac{\eta_{0}^{2}}{4}\sum_{t=1}^{T}\left(1+\cos\frac{t\pi}{T}\right)^{2}\exp\left(-\frac{\mu\eta_{0}(T-t-1)^{3}}{6T^{2}}\right)$
$\displaystyle=\frac{\eta_{0}^{2}}{4}\sum_{t=1}^{T-1}\left(1-\cos\frac{t\pi}{T}\right)^{2}\exp\left(-\frac{\eta_{0}\mu(t-1)^{3}}{6T^{2}}\right)$
$\displaystyle=\eta_{0}^{2}\sum_{t=1}^{T-1}\sin^{4}\frac{t\pi}{2T}\exp\left(-\frac{\eta_{0}\mu(t-1)^{3}}{6T^{2}}\right)$
$\displaystyle\leq\frac{\eta_{0}^{2}\pi^{4}}{16T^{4}}\sum_{t=0}^{T-1}t^{4}\exp\left(-\frac{\eta_{0}\mu
t^{3}}{6T^{2}}\right)$
$\displaystyle\leq\frac{\eta_{0}\pi^{4}}{16T^{4}}\left(2\exp\left(-\frac{4}{3}\right)\left(\frac{8T^{2}}{\mu}\right)^{4/3}+\left(\frac{6T^{2}}{\mu}\right)^{\frac{5}{3}}\right),$

where in the third line we used $\cos(\pi-x)=-\cos(x)$, in the forth line we
used $1-\cos(2x)=2\sin^{2}(x)$, and in the last inequality we applied Lemma
21.

Putting things together, we get the stated bounds. ∎

###### Proof of Theorem 10.

Denote by $S_{i}=\sum_{j=0}^{i}T_{j}$ and $S_{-1}=1$. Given Theorem 9, it is
immediate to have $\forall i=0,\dots,l$:

$\displaystyle\mathbb{E}f(\boldsymbol{x}_{S_{i}})-f^{\star}$
$\displaystyle\leq\frac{\pi^{4}b}{32(1+a)T_{i}^{4}}\left(\left(\frac{8T_{i}^{2}}{\mu}\right)^{4/3}+\left(\frac{6T_{i}^{2}}{\mu}\right)^{\frac{5}{3}}\right)$
$\displaystyle\quad+\exp\left(-\frac{\mu(T_{i}-1)}{2L(1+a)}\right)(f(x_{S_{i-1}})-f^{\star})$
$\displaystyle\leq
C_{1}\left(\frac{1}{\mu^{4/3}T_{i}^{4/3}}+\frac{1}{\mu^{5/3}T_{i}^{2/3}}\right)+\exp\left(-C_{2}\mu(T_{i}-1)\right)(f(x_{S_{i-1}})-f^{\star})~{}.$

Repeatedly using the above inequality, we get

$\displaystyle\mathbb{E}f(\boldsymbol{x}_{S_{l}})-f^{\star}$
$\displaystyle\leq
C_{1}\sum_{i=0}^{l}\prod_{j=i+1}^{l}\exp(-C_{2}\mu(T_{j}-1))\left(\frac{1}{\mu^{4/3}T_{i}^{4/3}}+\frac{1}{\mu^{5/3}T_{i}^{2/3}}\right)$
$\displaystyle\quad+\exp\left(-C_{2}\mu(S_{l}-l-1)\right)(f(x_{1})-f^{\star})~{}.$

In the case of $r=1$, $T_{i}=T_{0}$, we have for any $i$ that

$\displaystyle\sum_{i=0}^{l}\prod_{j=i+1}^{l}\exp(-C_{2}\mu(T_{j}-1))\left(\frac{1}{\mu^{4/3}T_{i}^{4/3}}+\frac{1}{\mu^{5/3}T_{i}^{2/3}}\right)$
$\displaystyle=\left(\frac{1}{\mu^{4/3}T_{0}^{4/3}}+\frac{1}{\mu^{5/3}T_{0}^{2/3}}\right)\sum_{i=0}^{l}\exp\left(-C_{2}\mu(T_{0}-1)(l-i)\right)$
$\displaystyle=\left(\frac{1}{\mu^{4/3}T_{0}^{4/3}}+\frac{1}{\mu^{5/3}T_{0}^{2/3}}\right)\frac{1-\exp\left(-C_{2}\mu(T_{0}-1)(l+1)\right)}{1-\exp\left(-C_{2}\mu(T_{0}-1)\right)}~{}.$

In the case of $r>1$, denote by
$A_{i}=\prod_{j=i+1}^{l}\exp(-C_{2}\mu(T_{j}-1))\frac{1}{\mu^{p}T_{i}^{q}},p,q>0$.
For any $i=0,...,l$, $\frac{A_{i}}{A_{i+1}}=\exp(-C_{2}\mu(T_{i+1}-1))r^{q}$
is decreasing over $i$. Denote by
$i^{\star}=\min\\{i:\frac{A_{i}}{A_{i+1}}\leq 1\\}$. We have

$\displaystyle\sum_{i=0}^{l}A_{i}$ $\displaystyle\leq A_{0}\cdot
i^{\star}+(l-i^{\star}+1)\cdot A_{l}\leq(l+1)\cdot(A_{0}+A_{l})$
$\displaystyle=\frac{l+1}{\mu^{p}}\cdot\left(\frac{1}{T_{l}^{q}}+\frac{1}{T_{0}^{q}}\exp(-C_{2}\mu(T-T_{0}-l))\right),\quad
p,q>0~{}.$

Note that $T_{l}=T\cdot\frac{r^{l}(r-1)}{r^{l+1}-1}\geq\frac{r-1}{r}T$ and
$l=O\left(\ln T\right)$. Then, the stated bound follows. ∎

###  3.5 Conclusion

We have analyzed theoretically the exponential and cosine step size, two
successful step size decay schedules for the stochastic optimization of non-
convex functions. We have shown that, up to poly-logarithmic terms, both step
sizes guarantee convergence with the best-known rates for smooth non-convex
functions. Moreover, in the case of functions satisfying the PL condition, we
have also proved that they are both adaptive to the level of noise.

##  Chapter 4 Last Iterate of Momentum Methods

###  4.1 Introduction

In this chapter, we consider SGDM with the following updates

$\boldsymbol{x}_{t+1}=\boldsymbol{x}_{t}-\eta_{t}\boldsymbol{m}_{t},\quad\boldsymbol{m}_{t}=\beta_{t}\boldsymbol{m}_{t-1}+(1-\beta_{t})\boldsymbol{g}_{t},$
(4.1)

where $0\leq\beta_{t}\leq 1$.

Often an average is taken in the analysis of momentum, while in real world
applications, most of the time only the last iterate is taken. Hence, we are
interested in the performance of the last iterate of SGDM. In particular, we
study the convergence of the last iterate of SGDM for unconstrained
optimization of convex functions. Unfortunately, our first result is a
negative one: We show that the last iterate of SGDM can have a suboptimal
convergence rate for _any constant momentum setting_.

Motivated by the above result, we analyze yet another variant of SGDM. We
start from the very recent observation (Defazio, 2020) that SGDM can be seen
as a primal averaging procedure (Nesterov and Shikhman, 2015; Tao et al.,
2018; Cutkosky, 2019) applied to the iterates of Online Mirror Descent (OMD)
(Nemirovsky and Yudin, 1983; Warmuth and Jagota, 1997). Based on this fact, we
analyze SGDM algorithms based on the Follow-the-Regularized-Leader (FTRL)
framework111FTRL is known in the offline optimization literature as Dual
Averaging (DA) (Nesterov, 2009), but in reality DA is a special case of FTRL
when the functions are linearized. (Shalev-Shwartz, 2007; Abernethy et al.,
2008) and the primal averaging. The use of FTRL instead of OMD removes the
necessity of projections onto bounded domains, while the primal averaging acts
as a momentum term and guarantees the optimal convergence of the last iterate.
The resulting algorithm has an _increasing momentum_ and _shrinking updates_
that precisely allow to avoid our lower bound.

Table 4.1: Last iterate convergence of momentum methods in convex setting

!  Algorithm Assumption Bounded Domain Requires T Rate Reference Adaptive-HB
Assumption A5 Yes No $O(\frac{1}{\sqrt{T}})$ Tao et al. (2021) SHB-IMA Smooth
+ Assumption A3 No Yes $O(\frac{1}{\sqrt{T}})$ Sebbouh et al. (2021) No
$O(\frac{\ln T}{\sqrt{T}})$ AC-SA Lipschitz/Smooth + Assumption A5 No Yes
$O(\frac{1}{\sqrt{T}})$ Ghadimi and Lan (2012) FTRL-SGDM Assumption A4 No No
$O(\frac{1}{\sqrt{T}})$ Corollary 1 Smooth + Assumption A3, A5 No No
$O(\frac{\ln T}{T}+\frac{\sigma}{\sqrt{T}})$ Corollary 4

###  4.2 Related Work

##### Lower bound

Harvey et al. (2019a) prove the tight convergence bound $O(\ln T/\sqrt{T})$ of
the last iterate of SGD for convex and Lipschitz functions. Kidambi et al.
(2018) provide a lower bound for the Heavy Ball method for least square
regression problems. To the best of our knowledge, there is no lower bound for
the last iterate of SGDM in the general convex setting.

##### Last iterate convergence of SGDM

Nesterov and Shikhman (2015) introduces a quasi-monotone subgradient method,
which uses double averaging based on Dual Averaging, to achieve the optimal
convergence of the last iterate for the convex and Lipschitz functions.
However, they just considered the batch case. This approach was then
rediscovered and extended by Cutkosky (2019). Our FTRL-based SGDM is a
generalization of the approach in Nesterov and Shikhman (2015) with generic
regularizers and in the stochastic setting. Tao et al. (2018) extends Nesterov
and Shikhman (2015)’s method to Mirror Descent, calling it stochastic primal
averaging. They recover the same bound for convex functions, again with a
bounded domain assumption. They also get the optimal bound for strongly convex
functions and analyze them in the stochastic and regularized setting. Defazio
(2020) points out that the sequence generated by the stochastic primal
averaging (Tao et al., 2018) can be identical to that of stochastic gradient
descent with momentum for specific choices of the hyper-parameters.
Accordingly, they give a Lyapunov analysis in the nonconvex and smooth case.
Based on this work, Jelassi and Defazio (2020) introduce “Modernized dual
averaging method”, which is actually equal to the one by Nesterov and Shikhman
(2015). They also give a similar Lyapunov analysis as in Defazio (2020) with
specific choices of hyper-parameters in the non-convex and smooth optimization
setting. Recently, Tao et al. (2021) propose the very same algorithm as in Tao
et al. (2018) and analyze it as a modified Polyak’s Heavy-ball method (already
pointed out by Defazio (2020)). They give an analysis in the convex cases and
extend it to an adaptive version, obtaining in both cases an optimal
convergence of the last iterate. However, they all assume the use of
projections onto bounded domains.

##### Last iterate convergence rate $O(\frac{1}{\sqrt{T}})$

Ghadimi and Lan (2012) present the last iterate of AC-SA (Nemirovski et al.,
2009; Lan, 2012) for convex functions in the unconstrained setting, that in
Euclidean case reduces to SGD with an increasing Nesterov momentum, showing
that it can achieve a convergence rate $O(\frac{1}{\sqrt{T}})$ if the number
of iterations $T$ is known in advance. Sebbouh et al. (2021) analyze
Stochastic Heavy Ball-Iterave Moving Average method (SHB-IMA), which is equal
to Stochastic Heavy Ball method (SHB) with a specific choice of hyper-
parameters. They prove a convergence rate for the last iterate of of
$O(\frac{1}{\sqrt{T}})$ if $T$ is given in advance, and is $O(\frac{\log
T}{\sqrt{T}})$ if $T$ is unknown. Jain et al. (2021) conjecture that under the
assumption that the stochastic gradients are bounded“for any-time algorithm
(i.e., without apriori knowledge of $T$ ) expected error rate of $\frac{DG\ln
T}{\sqrt{T}}$ is information theoretically optimal”, where $D$ is the diameter
of the bounded domain. This was already disproved by the results in Tao et al.
(2021), but here we disprove it even in the more challenging unconstrained
setting.

###  4.3 Assumptions

We will use one or more of the following assumptions on the stochastic
gradients $\boldsymbol{g}_{t}$.

######  Assumption A3.

Bouned Variance: $\mathbb{E}_{t}\|\boldsymbol{g}_{t}-\nabla
f(\boldsymbol{x}_{t})\|^{2}\leq\sigma^{2},\quad\sigma>0$.

######  Assumption A4.

Bounded in expectation: $\mathbb{E}_{t}\|\boldsymbol{g}_{t}\|^{2}\leq
G^{2},\quad G>0$.

######  Assumption A5.

$\ell_{2}$ bounded: $\|\boldsymbol{g}_{t}\|\leq G,\quad G>0$.

######  Assumption A6.

$\ell_{\infty}$ bounded: $\|\boldsymbol{g}_{t}\|_{\infty}\leq G_{\infty},\quad
G_{\infty}>0$.

###  4.4 Lower bound for SGDM

In this section, we show the surprising result that for SGD with any constant
momentum, there exists a function for which the lower bound of the last
iterate is $\Omega\left(\log T/\sqrt{T}\right)$. Our proof extends the one in
Harvey et al. (2019a) to SGD with momentum.

We consider SGDM with constant momentum factor $\beta$ in (4.1), where
$\boldsymbol{g}_{t}\in\partial f(\boldsymbol{x}_{t})$ and a polynomial
stepsize $\eta_{t}=c\cdot t^{-\alpha},0\leq\alpha\leq\frac{1}{2}$.

For any fixed $\beta$ and $\alpha$ and $L>0$, we introduce the following
function. Define $f$: $\mathcal{X}\to\mathbb{R}$ and
$\boldsymbol{h}_{i}\in\mathbb{R}^{T}$ for $i\in[T+1]$ by

$f(\boldsymbol{x})=\max_{i\in[T+1]}\boldsymbol{h}_{i}^{T}\boldsymbol{x},\quad
h_{i,j}=\begin{cases}a_{j},&1\leq j<i\\\ -b_{j},&i=j<T\\\ 0,&i<j\leq
T\end{cases}$ (4.2)

where $b_{j}=\frac{Lj^{\alpha}}{2T^{\alpha}}$ and
$a_{j}=\frac{L(1-\beta)}{8(T-j+1)}$. We have that $\partial
f(\boldsymbol{x}_{t})$ is the convex hull of
$\boldsymbol{h}_{i}:i\in\mathcal{I}(\boldsymbol{x})$ where
$\mathcal{I}(\boldsymbol{x})=\\{i:\boldsymbol{h}_{i}^{T}\boldsymbol{x}=f(\boldsymbol{x})\\}$.
Note that $f$ is $L$-Lipschitz over $\mathbb{R}^{T}$ since

$\displaystyle\|\boldsymbol{h}_{i}\|^{2}\leq\sum_{i=1}^{T}a_{i}^{2}+b_{T}^{2}\leq\frac{L^{2}(1-\beta)^{2}}{64}\sum_{i=1}^{T}\frac{1}{i^{2}}+\frac{L^{2}}{4}\leq
L^{2}~{}.$ (4.3)

######  Claim 1.

For $f$ defined in (4.2), it satisfies that
$\inf_{\boldsymbol{x}\in\mathbb{R}^{T}}f(\boldsymbol{x})=0.$

###### Proof.

First, since $f(0)=0$, we have that $\inf_{\boldsymbol{x}\in\mathbb{R}^{T}}\
f(\boldsymbol{x})\leq 0$.
We continue to prove this claim by contradiction. Assume that there exists
$\boldsymbol{x}^{\star}=[x_{1}^{\star},x_{2}^{\star},\dots,x_{T}^{\star}]$
such that

$f(\boldsymbol{x}^{\star})<0~{}.$

By the definition of $f$, it satisfies that

$\boldsymbol{h}_{i}^{T}\boldsymbol{x}^{\star}<0,\quad\forall i\in[T+1]~{}.$
(4.4)

In particular,
$\boldsymbol{h}_{1}^{T}\boldsymbol{x}^{\star}=-b_{1}x^{\star}_{1}<0$. Since
that $b_{1}$ is positive, we know that $x_{1}^{\star}>0$. Also,
$\boldsymbol{h}_{2}^{T}\boldsymbol{x}^{\star}=a_{1}x^{\star}_{1}-b_{2}x^{\star}_{2}<0$.
Due to the positiveness of $a_{1},x^{\star}_{1}$, and $b_{2}$, $x^{\star}_{2}$
has to be positive. Similarly, we have that for any $x^{\star}_{j}$,
$j\in[T]$, $x^{\star}_{j}>0$.
Then, we have

$\boldsymbol{h}_{T+1}^{T}\boldsymbol{x}^{\star}=\sum_{j=1}^{T}a_{j}x^{\star}_{j}>0~{}.$

However, this is contradict with (4.4).
Thus, we conclude that
$\inf_{\boldsymbol{x}\in\mathbb{R}^{T}}f(\boldsymbol{x})=0.$ ∎

######  Theorem 13 (Lower bound of SGDM).

Fix a polynomial stepsize sequence $\eta_{t}=c\cdot t^{-\alpha}$, where
$0\leq\alpha\leq\frac{1}{2}$, a momentum factors $\beta\in[0,1)$, a Lipschitz
constant $L>0$ and a number of iterations $T$. Then, there exists a sequence
$\boldsymbol{z}_{t}$ generated by SGDM with stepsizes $\eta_{t}$ and momentum
factor $\beta$ on the function $f$ in (4.2), where the $T$-th iterate
satisfies

$f(\boldsymbol{z}_{T})-f^{\star}\geq\frac{L^{2}(1-\beta)^{2}c\ln
T}{4T^{\alpha}}~{}.$

We stress that $\ln T$ cannot be cancelled by any setting of $\beta$. Indeed,
the above lower bound can be instantiated by any $\beta$ and any $T$. Hence,
for a given $\beta$, there exists $T$ large enough such that $\ln T$ is
constant-times bigger than $\frac{1}{(1-\beta)^{2}}$.

When $\beta=1$, the algorithm is basically staying at the initial point. We
can choose arbitrary positive number $C>0$ and let $z_{1}=C$, then

$f(\boldsymbol{z}_{T})-f^{\star}\geq C,\quad C>0~{}.$

We will use the following lemma in the proof.

######  Lemma 22.

For any $1\leq j\leq t\leq T$ and $0<\alpha\leq\frac{1}{2}$, we have
$\frac{1}{T-j+1}\sum_{k=j+1}^{t}\frac{1}{j^{\alpha}}\leq\frac{2}{T^{\alpha}}$.

###### Proof.

First, we observe that

$\displaystyle\sum_{k=j+1}^{t}\frac{1}{k^{\alpha}}$
$\displaystyle\leq\int_{j}^{t}\frac{1}{x^{\alpha}}dx=\frac{t^{1-\alpha}-j^{1-\alpha}}{1-\alpha}=\frac{1}{1-\alpha}\frac{t^{2-2\alpha}-j^{2-2\alpha}}{t^{1-\alpha}+j^{1-\alpha}}$
$\displaystyle\leq\frac{1}{1-\alpha}\frac{(2-2\alpha)t^{1-2\alpha}(t-j)}{t^{1-\alpha}+j^{1-\alpha}}\leq\frac{2(t-j)}{t^{\alpha}},$

where in the second inequality we used the convexity of
$f(x)=x^{2-2\alpha},0<\alpha\leq\frac{1}{2}$.

Then, we claim
$\frac{1}{T-j+1}\frac{t-j}{t^{\alpha}}\leq\frac{1}{T^{\alpha}}$.

Let $g(x)=\frac{x-j}{x^{\alpha}}$. The derivative
$g^{\prime}(x)=\frac{1-\alpha+\frac{j}{\alpha x}}{x^{\alpha}}$ is positive for
all $x>0$ and $j\geq 0$. So it satisfies that
$\frac{t-j}{t^{\alpha}}\leq\frac{T-j}{T^{\alpha}}$, which implies the claim. ∎

###### Proof of Theorem 13.

Define a sequence $\boldsymbol{z}_{t}$ for $t\in[T+1]$ as follows:
$\boldsymbol{z}=0$, where $s$ is a positive number decided later, and

$\boldsymbol{z}_{t+1}=\boldsymbol{z}_{t}-(1-\beta)\eta_{t}\sum_{i=1}^{t}\beta^{t-i}\boldsymbol{h}_{i}~{}.$
(4.5)

We will show that $\boldsymbol{z}_{t}$ are exactly the updates of SGDM and
$f(\boldsymbol{z}_{T+1})\geq\Omega\left(\frac{\ln T}{T^{\alpha}}\right)$. We
will use the following two lemmas.

######  Lemma 23.

Let $b_{j}=\frac{Lj^{\alpha}}{2T^{\alpha}}$,
$a_{j}=\frac{L(1-\beta)}{8(T-j+1)}$, and $\eta_{j}=c\cdot j^{-\alpha}$.
$\boldsymbol{z}_{t}$ is defined as in (4.5). Then, for $1\leq t<j$,
$z_{t,j}=0$, and for $t>j$, $z_{t,j}\geq\frac{L(1-\beta)c}{4T^{\alpha}}$.

###### Proof of Lemma 23.

We first prove by induction that when $1\leq t\leq j$, $z_{t,j}=0$. First,
$\boldsymbol{z}_{1}=0$ Also, suppose it holds for $t$. Then, in the case of
$t+1$, for any $j\geq t+1$,

$z_{t+1,j}=z_{t,j}-(1-\beta)\eta_{t}\sum_{i=1}^{t}\beta^{t-i}h_{i,j}=0-0=0,$

which implies $t\leq j$, $z_{t,j}=0$ holds. Next, we claim that
$\boldsymbol{z}_{t}$ satisfies

$\displaystyle z_{t,j}$ $\displaystyle\geq
z_{j,j}+(1-\beta)b_{j}\eta_{j}-a_{j}\sum_{k=j+1}^{t-1}\eta_{k},\quad 1\leq
j<t\leq T~{}.$ (4.6)

We prove (4.6) by induction. For any $t$, $z_{t,t-1}$ satisfies (4.6) since

$\displaystyle
z_{t+1,t}=z_{t,t}-(1-\beta)\eta_{t}\sum_{i=1}^{t}\beta^{t-i}h_{i,t}=-(1-\beta)\eta_{t}h_{t,t}=(1-\beta)\eta_{t}b_{t}~{}.$

Then, suppose (4.6) holds for any $j<t$. We show that it holds for any
$j<t+1$. We already proved for $j=t$. For $j<t$,

$\displaystyle z_{t+1,j}$
$\displaystyle=z_{t,j}-(1-\beta)\eta_{t}\sum_{i=1}^{t}\beta^{t-i}h_{i,j}=z_{t,j}-(1-\beta)\eta_{t}\sum_{i=j}^{t}\beta^{t-i}h_{i,j}$
$\displaystyle=z_{t,j}+(1-\beta)\eta_{t}\beta^{t-j}b_{j}-(1-\beta)\eta_{t}\sum_{i=j+1}^{t}\beta^{t-i}h_{i,j}$
$\displaystyle\geq z_{t,j}-(1-\beta)\eta_{t}\sum_{i=j+1}^{t}\beta^{t-i}a_{j}$
$\displaystyle\geq(1-\beta)b_{j}\eta_{j}-a_{j}\sum_{k=j+1}^{t-1}\eta_{k}-(1-\beta)a_{j}\eta_{t}\sum_{i=j+1}^{t}\beta^{t-i}$
$\displaystyle\geq(1-\beta)b_{j}\eta_{j}-a_{j}\sum_{k=j+1}^{t}\eta_{k},$ (4.7)

where in the second inequality we used the induction hypothesis.

Using that $b_{j}=\frac{Lj^{\alpha}}{2T^{\alpha}}$,
$a_{j}=\frac{L(1-\beta)}{8(T-j+1)}$ and $\eta_{j}=\frac{c}{j^{\alpha}}$, we
have

$\displaystyle\eqref{eq:z_t}=\frac{L(1-\beta)c}{2T^{\alpha}}-\frac{L(1-\beta)c}{8(T-j+1)}\sum_{k=j+1}^{t}\frac{1}{k^{\alpha}}~{}.$
(4.8)

By Lemma 22 in the Appendix, we have that for $0<\alpha\leq\frac{1}{2}$,

$\eqref{eq:lower_alpha}\geq\frac{L(1-\beta)c}{2T^{\alpha}}-\frac{L(1-\beta)c}{4T^{\alpha}}\geq\frac{L(1-\beta)c}{4T^{\alpha}},$

and for $\alpha=0$,

$\eqref{eq:lower_alpha}\geq\frac{L(1-\beta)c}{2}-\frac{L(1-\beta)(t-j-1)c}{8(T-j+1)}\geq\frac{L(1-\beta)c}{4}~{}.$

Thus, we have
$z_{t,j}\geq\frac{L(1-\beta)c}{4T^{\alpha}}\geq\frac{L(1-\beta)c}{4T^{\alpha}}$.
∎

######  Lemma 24.

$f(\boldsymbol{z}_{t})=\boldsymbol{h}_{t}^{T}\boldsymbol{z}_{t}$ for any
$t\in[T+1]$. The subgradient oracle for $f$ at $\boldsymbol{z}_{t}$ returns
$\boldsymbol{h}_{t}$.

###### Proof of Lemma 24.

We claim that
$\boldsymbol{h}_{t}^{T}\boldsymbol{z}_{t}=\boldsymbol{h}_{i}^{T}\boldsymbol{z}_{t}$
for all $i>t\geq 1$ and
$\boldsymbol{h}_{t}^{T}\boldsymbol{z}_{t}>\boldsymbol{h}_{i}^{T}\boldsymbol{z}_{t}$
for all $1\leq i<t$.

When $i>t\geq 2$, $\boldsymbol{z}_{t}$ is supported on the first $t-1$
coordinates, while $\boldsymbol{h}_{t}$ and $\boldsymbol{h}_{i}$ agree on the
first $t-1$ coordinates.

In the case of $1\leq i<t$, by the definition of $\boldsymbol{z}_{t}$ and
$\boldsymbol{h}_{t}$, we have

$\boldsymbol{z}_{t}^{T}(\boldsymbol{h}_{t}-\boldsymbol{h}_{i})=\sum_{j=1}^{t-1}z_{t,j}(h_{t,j}-h_{i,j})=\sum_{j=i}^{t-1}z_{t,j}(h_{t,j}-h_{i,j})=z_{t,i}(a_{i}+b_{i})+\sum_{j=i+1}^{t-1}z_{t,j}a_{j}>0,$

where in the last inequality we used the fact that $a_{i}$, $b_{i}$ and
$z_{t,i}$ are at least non-negative.

Thus, we have proved
$f(\boldsymbol{z}_{t})=\boldsymbol{h}_{t}^{T}\boldsymbol{z}_{t}$ by the
definition. Moreover,
$\mathcal{I}(\boldsymbol{z}_{t})=\\{i:\boldsymbol{h}_{i}^{T}\boldsymbol{z}_{t}=f(\boldsymbol{z}_{t})\\}=\\{t,\dots,T+1\\}$.
So the subgradient evaluated at $\boldsymbol{z}_{t}$ is $\boldsymbol{h}_{t}$.
∎

Now, we first get a lower bound and an upper bound of $\boldsymbol{z}_{t}$
using Lemma 23. Then, by Lemma 24, we have shown that $\boldsymbol{z}_{t}$ are
exactly the updates of SGDM.

Thus, for $\beta\in[0,1)$, we have

$\displaystyle f(\boldsymbol{z}_{T+1})$
$\displaystyle=\boldsymbol{h}_{T+1}^{T}\boldsymbol{z}_{T+1}=\sum_{j=1}^{T}h_{T+1,j}z_{T+1,j}$
$\displaystyle\geq\frac{L^{2}(1-\beta)^{2}c}{4T^{\alpha}}\sum_{j=1}^{T}\frac{1}{T-j+1}\geq\frac{L^{2}(1-\beta)^{2}c\ln
T}{4T^{\alpha}}~{}.\qed$

###  4.5 FTRL-based SGDM

The lower bound for the last iterate in the previous Section motivates us to
study a different variant of SGDM. In particular, we aim to find a way to
remove the $\ln T$ term from the convergence rate.

Defazio (2020) points out that the stochastic primal averaging method (Tao et
al., 2018) (which is also an instance of Algorithm 1 in Cutkosky (2019) with
OMD):

$\displaystyle\boldsymbol{z}_{t+1}=\boldsymbol{z}_{t}-\gamma_{t}\boldsymbol{g}_{t},\quad\boldsymbol{x}_{t+1}=s_{t}\boldsymbol{x}_{t}+(1-s_{t})\boldsymbol{z}_{t}$

could be one-to-one mapped to the momentum method

$\displaystyle\boldsymbol{m}_{t+1}=\beta_{t}\boldsymbol{m}_{t}+\boldsymbol{g}_{t},\quad\boldsymbol{x}_{t+1}=\boldsymbol{x}_{t}-\alpha_{t}\boldsymbol{m}_{t}$

by setting $\gamma_{t+1}=\frac{\gamma_{t}-\alpha_{t}}{\beta_{t+1}}$. While
this is true, the convergence rate depends on the convergence rate of OMD with
time-varying stepsizes, that in turn requires to assume that
$\|\boldsymbol{x}_{t}-\boldsymbol{x}^{\star}\|^{2}\leq D^{2}$. This is
possible only by using a projection onto a bounded domain in each step.

Algorithm 3 FTRL-based SGDM

1: Input: A sequence $\alpha_{1},...,\alpha_{T}$, with $\alpha_{1}>0$. Non-
increasing sequence $\boldsymbol{\gamma}_{1},\dots,\boldsymbol{\gamma}_{T-1}$.
$\boldsymbol{m}_{0}=0$. $\boldsymbol{x}_{1}\in\mathbb{R}^{d}$.

2: for $t=1,\dots,T$ do

3: Get $\boldsymbol{g}_{t}$ at $\boldsymbol{x}_{t}$ such that
$\mathbb{E}_{t}\left[\boldsymbol{g}_{t}\right]=\nabla f(\boldsymbol{x}_{t})$

4: $\beta_{t}=\frac{\sum_{i=1}^{t-1}\alpha_{i}}{\sum_{i=1}^{t}\alpha_{i}}$
(Define $\sum_{i=1}^{0}\alpha_{i}=0$)

5:
$\boldsymbol{m}_{t}=\beta_{t}\boldsymbol{m}_{t-1}+(1-\beta_{t})\boldsymbol{g}_{t}$

6:
$\boldsymbol{\eta}_{t}=\frac{\alpha_{t+1}\sum_{i=1}^{t}\alpha_{i}}{\sum_{i=1}^{t+1}\alpha_{i}}\boldsymbol{\gamma}_{t}$

7:
$\boldsymbol{x}_{t+1}=\frac{\sum_{i=1}^{t}\alpha_{i}}{\sum_{i=1}^{t+1}\alpha_{i}}\boldsymbol{x}_{t}+\frac{\alpha_{t+1}}{\sum_{i=1}^{t+1}\alpha_{i}}\boldsymbol{x}_{1}-\boldsymbol{\eta}_{t}\boldsymbol{m}_{t}$

8: end for

Thus, to go beyond bounded domains, we propose to study a new variant of SGDM
which has the following form (details in Algorithm 3),

$\displaystyle\boldsymbol{m}_{t+1}=\beta_{t}\boldsymbol{m}_{t}+(1-\beta_{t})\boldsymbol{g}_{t},\quad\boldsymbol{x}_{t+1}=s_{t}\boldsymbol{x}_{t}-\alpha_{t}\boldsymbol{m}_{t}~{}.$

This variant comes naturally when using the primal averaging scheme with FTRL
(Algorithm 4) rather than to OMD. Hence, we just denote it by FTRL-based SGDM.

Algorithm 4 Follow-the-Regularized-Leader on Linearized Losses

1: Input: Regularizers
$\psi_{1},\dots,\psi_{T}:\mathbb{R}^{d}\to(-\infty,\infty]$.

2: for $t=1,\dots,T$ do

3:
$\boldsymbol{w}_{t}\in\mathop{\text{argmin}}_{\boldsymbol{w}\in\mathbb{R}^{d}}\
\psi_{t}(\boldsymbol{w})+\sum_{i=1}^{t-1}\langle\boldsymbol{g}_{i},\boldsymbol{w}\rangle$

4: Receive $\ell_{t}:\mathbb{R}^{d}\to(-\infty,\infty]$ and pay
$\ell_{t}(\boldsymbol{w}_{t})$

5: Set $\boldsymbol{g}_{t}\in\partial\ell_{t}(\boldsymbol{w}_{t})$

6: end for

####  4.5.1 Convergence Rates for FTRL-based SGDM

We first present a very general theorem for FTRL-based SGDM.

######  Theorem 14.

Assume $f$ is convex and $L$-smooth. Algorithm 3 guarantees

$\displaystyle\mathbb{E}\left[f(\boldsymbol{x}_{T})-f(\boldsymbol{x}^{\star})\right]\leq\frac{1}{\sum_{t=1}^{T}\alpha_{t}}\mathbb{E}\left[\left\|\frac{\boldsymbol{x}_{1}-\boldsymbol{x}^{\star}}{\sqrt{\boldsymbol{\gamma}_{T-1}}}\right\|^{2}+\sum_{t=1}^{T}\langle\boldsymbol{\gamma}_{t-1},\alpha_{t}^{2}\boldsymbol{g}_{t}^{2}\rangle\right]~{}.$

The above theorem is very general and it gives rise to a number of different
variations of the FTRL-based SGDM. In particular, we can instantiate it with
the following choices.

First, we consider the most used polynomial stepsize $\frac{c}{\sqrt{t}}$ for
convex and Lipschitz function, and the constant stepsize $\frac{c}{\sqrt{T}}$
if $T$ is given in advance.

######  Corollary 1.

Assume $\mathbb{E}\|\boldsymbol{g}_{t}\|^{2}\leq G^{2},G>0$ and set
$\alpha_{t}=1$ for all $t$. Algorithm 3 with either
$\boldsymbol{\gamma}_{t-1}=\frac{c}{G\sqrt{t}}\cdot\mathbf{1}$ or
$\boldsymbol{\gamma}_{t-1}=\frac{c}{G\sqrt{T}}\cdot\mathbf{1}$ guarantees

$\mathbb{E}\left[f(\boldsymbol{x}_{T})-f(\boldsymbol{x}^{\star})\right]\leq\frac{\|\boldsymbol{x}_{1}-\boldsymbol{x}^{\star}\|^{2}G}{c\sqrt{T}}+\frac{2cG}{\sqrt{T}}~{}.$

The above corollary tells that both of these two stepsizes give the optimal
bound $O(\frac{1}{\sqrt{T}})$ for the last iterate. Next, we will show that if
we use an adaptive222Even if widely used in the literature, it is a misnomer
to call these stepsize “adaptive”: an algorithm can be adaptive to some
unknown quantities (if proved so), not the stepsizes. stepsize, Algorithm 3
gives a data-dependent convergence rate for the last iterate. We first
consider a global version of the AdaGrad stepsize as in Streeter and McMahan
(2010); Ward et al. (2019).

######  Corollary 2.

Assume $\|\boldsymbol{g}_{t}\|\leq G,G>0$ and take
$\boldsymbol{\gamma}_{t}=\frac{\alpha\cdot\mathbf{1}}{\sqrt{G^{2}+\sum_{i=1}^{t}\alpha_{i}^{2}\|\boldsymbol{g}_{i}\|^{2}}},1\leq
t\leq T$ and $\alpha_{t}=1$. Then, Algorithm 3 guarantees

$\displaystyle\mathbb{E}\left[f(\boldsymbol{x}_{T})-f(\boldsymbol{x}^{\star})\right]\leq\frac{2}{T}\left(\frac{\|\boldsymbol{x}_{1}-\boldsymbol{x}^{\star}\|^{2}}{\alpha}+\alpha\right)\sqrt{\sum_{t=1}^{T-1}\|\boldsymbol{g}_{t}\|^{2}+G^{2}}~{}.$

We also state a result for the coordinate-wise AdaGrad stepsizes (McMahan and
Streeter, 2010; Duchi et al., 2011).

######  Corollary 3.

Assume $\|\boldsymbol{g}_{t}\|_{\infty}\leq G_{\infty},G_{\infty}>0$and set
$\boldsymbol{\gamma}_{t}=\frac{\alpha}{\sqrt{G_{\infty}^{2}+\sum_{i=1}^{t}\alpha_{i}^{2}\boldsymbol{g}_{i}^{2}}},1\leq
t\leq T$ and $\alpha_{t}=1$. Then, Algorithm 3 guarantees

$\displaystyle\mathbb{E}\left[f(\boldsymbol{x}_{T})-f(\boldsymbol{x}^{\star})\right]\leq\frac{2}{T}\left(\frac{\|\boldsymbol{x}_{1}-\boldsymbol{x}^{\star}\|_{1}^{2}}{\alpha}+\alpha\right)\sum_{j=1}^{d}\sqrt{\sum_{t=1}^{T-1}\boldsymbol{g}_{t,j}^{2}+G^{2}_{\infty}}~{}.$

They show that the convergence bounds are adaptive to the stochastic
gradients. When the stochastic gradients are small or sparse, the rate could
be much faster than $O(\frac{1}{\sqrt{T}})$. Moreover, the above results give
very simple ways to obtain optimal convergence for the last iterate of first-
order stochastic methods, that was still unclear if it could be obtained as
discussed in Jain et al. (2021).

Also, we now show that if in addition $f$ is smooth, the last iterate of FTRL-
based momentum with the global adaptive stepsize of Corollary 2 gives adaptive
rates of convergence that interpolate between $O(\frac{1}{\sqrt{T}})$ and
$O(\frac{\ln T}{T})$.

######  Corollary 4.

Assume $f$ is $L$-smooth. Then, under the same assumption and parameter
setting of Corollary 2, Algorithm 3 guarantees

$\displaystyle\mathbb{E}$
$\displaystyle\left[f(\boldsymbol{x}_{T})-f^{\star}\right]\leq\frac{2C}{T}\sqrt{16L^{2}C^{2}\ln^{2}T+8LGC\ln
T+G^{2}}+\frac{2\sqrt{2}C\sigma}{\sqrt{T}}~{}.$

where
$C\triangleq\left(\frac{\|\boldsymbol{x}_{1}-\boldsymbol{x}^{\star}\|^{2}}{\alpha}+\alpha\right)$.

Observe that when $\sigma=0$, namely when there is no noise on the gradients,
the rate of $O(\frac{\ln T}{T})$ is obtained. As far as we know, the above
theorems are the first convergence guarantees for the last iterate of adaptive
methods in unconstrained convex optimization.

First, we state some technical lemmas for the proofs.

The following lemma is a well-known result for FTRL (see, e.g., Orabona,
2019).

######  Lemma 25.

Let $\ell_{t}$ a sequence of convex loss functions. Set the sequence of
regularizers as
$\psi_{t}({\boldsymbol{x}})=\left\|\frac{\boldsymbol{x}_{1}-\boldsymbol{u}}{\sqrt{\boldsymbol{\gamma}_{t-1}}}\right\|^{2}$,
where $\boldsymbol{\gamma}_{t+1}\leq\boldsymbol{\gamma}_{t},\ t=1,\dots,T$.
Then, FTRL (Algorithm 4) guarantees

$\displaystyle\sum_{t=1}^{T}\ell_{t}(\boldsymbol{x}_{t})-\ell_{t}(\boldsymbol{u})\leq\left\|\frac{\boldsymbol{u}-\boldsymbol{x}_{1}}{\sqrt{\boldsymbol{\gamma}_{T-1}}}\right\|^{2}+\frac{1}{2}\sum_{t=1}^{T}\langle\boldsymbol{\gamma}_{t-1},\boldsymbol{g}_{t}^{2}\rangle~{}.$

######  Lemma 26.

(Gaillard et al., 2014, Lemma 14) Let $a_{0}>0$ and
$a_{1},\dots,a_{m}\in[0,A]$ be real numbers and let
$f:(0,+\infty)\rightarrow[0,+\infty)$ nonincreasing function. Then

$\sum_{i=1}^{m}a_{i}f(a_{0}+\dots+a_{i-1})\leq\int_{a_{0}}^{\sum_{i=0}^{m}a_{i}}f(u)du+Af(a_{0})~{}.$

###### Proof.

Denote by $s_{t}=\sum_{i=0}^{t}a_{i}$.

$\displaystyle\sum_{i=1}^{m}a_{i}f(s_{i-1})$
$\displaystyle=\sum_{i=1}^{m}a_{i}f(s_{i})+\sum_{i=1}^{m}a_{i}(f(s_{i-1})-f(s_{i}))$
$\displaystyle\leq\sum_{i=1}^{m}a_{i}f(s_{i})+A\sum_{i=1}^{m}(f(s_{i-1})-f(s_{i}))$
$\displaystyle\leq\sum_{i=1}^{m}\int_{s_{i-1}}^{s_{i}}f(x)dx+A\sum_{i=1}^{m}(f(s_{i-1})-f(s_{i}))$
$\displaystyle\leq\int_{a_{0}}^{\sum_{i=0}^{m}a_{i}}f(u)du+Af(a_{0}),$

where the first inequality holds because $f(x_{i-1})\geq f(s_{i})$ and
$a_{i}\leq A$, while the second inequality uses the fact that $f$ is
nonincreasing together with $s_{i}-s_{i-1}=a_{i}$. ∎

We can now present the proofs of the Corollaries 2-4.

###### Proof of Corollary 2 and Corollary 3.

By Lemma 26, for adaptive stepsize
$\boldsymbol{\gamma}_{t}=\frac{\alpha\cdot\mathbf{1}}{\sqrt{\epsilon+\sum_{i=1}^{t}\alpha_{i}^{2}\|\boldsymbol{g}_{i}\|^{2}}}$,
we have

$\displaystyle\sum_{t=1}^{T}\boldsymbol{\gamma}_{t-1}\|\boldsymbol{g}_{t}\|^{2}=\sum_{t=1}^{T}\frac{\alpha\|\boldsymbol{g}_{t}\|^{2}}{\sqrt{\epsilon+\sum_{i=1}^{t-1}\|\boldsymbol{g}_{i}\|^{2}}}\leq
2\alpha\sqrt{\sum_{t=1}^{T}\|\boldsymbol{g}_{t}\|^{2}}+\frac{\alpha
G^{2}}{\sqrt{\epsilon}}~{}.$

Similarly for
$\boldsymbol{\gamma}_{t}=\frac{\alpha}{\sqrt{\epsilon+\sum_{i=1}^{t}\alpha_{i}^{2}\boldsymbol{g}_{i}^{2}}}$,
we have

$\displaystyle\sum_{t=1}^{T}$
$\displaystyle\langle\boldsymbol{\gamma}_{t-1},\boldsymbol{g}_{t}^{2}\rangle=\sum_{j=1}^{d}\sum_{t=1}^{T}\frac{\alpha\boldsymbol{g}_{t,j}^{2}}{\sqrt{\epsilon+\sum_{i=1}^{t-1}\boldsymbol{g}_{i,j}^{2}}}\leq
2\alpha\sum_{j=1}^{d}\sqrt{\sum_{t=1}^{T}\boldsymbol{g}_{t,j}^{2}}+\frac{\alpha
dG_{\infty}^{2}}{\sqrt{\epsilon}}~{}.\qed$

###### Proof of Corollary 4.

By Corollary 2, we have

$\displaystyle\mathbb{E}\left[f(\boldsymbol{x}_{T})\right]-f^{\star}\leq\frac{1}{T}\left[\left(\frac{\|\boldsymbol{x}_{1}-\boldsymbol{x}^{\star}\|^{2}}{\alpha}+2\alpha\right)\sqrt{\epsilon+\mathbb{E}\sum_{t=1}^{T}\|\boldsymbol{g}_{t}\|^{2}}+\frac{\alpha
G^{2}}{\sqrt{\epsilon}}\right]~{}.$ (4.9)

From the unbiasedness of the gradients, we have

$\displaystyle\mathbb{E}\sum_{t=1}^{T}\|\boldsymbol{g}_{t}\|^{2}\leq\mathbb{E}\sum_{t=1}^{T}\|\nabla
f(\boldsymbol{x}_{t})\|^{2}+T\sigma^{2},$

and

$\displaystyle\mathbb{E}\sum_{t=1}^{T}\|\nabla f(\boldsymbol{x}_{t})\|^{2}$
$\displaystyle\leq
2L\sum_{t=1}^{T}\mathbb{E}\left[f(\boldsymbol{x}_{t})\right]-f^{\star}$
$\displaystyle\leq
2L\left(\frac{\|\boldsymbol{x}_{1}-\boldsymbol{x}^{\star}\|^{2}}{\alpha}+2\alpha\right)\sum_{t=1}^{T}\frac{\sqrt{\epsilon+\mathbb{E}\sum_{i=1}^{t}\|\boldsymbol{g}_{i}\|^{2}}}{t}$
$\displaystyle\leq
2L\left(\frac{\|\boldsymbol{x}_{1}-\boldsymbol{x}^{\star}\|^{2}}{\alpha}+2\alpha\right)\cdot\left(\sqrt{\mathbb{E}\sum_{t=1}^{T}\|\boldsymbol{g}_{t}\|^{2}+\epsilon}+\frac{\alpha
G^{2}}{\sqrt{\epsilon}}\right)\ln T,$

where in the second inequality we used Lemma 5 and Holder’s and Jensen’s
inequalities in the third inequality.

Solve for $\mathbb{E}\sum_{t=1}^{T}\|\boldsymbol{g}_{t}\|^{2}$ to have

$\displaystyle\mathbb{E}\sum_{t=1}^{T}\|\boldsymbol{g}_{t}\|^{2}$
$\displaystyle\leq
4L^{2}\left(\frac{\|\boldsymbol{x}_{1}-\boldsymbol{x}^{\star}\|^{2}}{\alpha}+2\alpha\right)^{2}\ln^{2}T+4L\sqrt{\epsilon}\left(\frac{\|\boldsymbol{x}_{1}-\boldsymbol{x}^{\star}\|^{2}}{\alpha}+2\alpha\right)\ln
T+\frac{2\alpha G^{2}}{\sqrt{\epsilon}}+2T\sigma^{2}~{}.$

Putting it back to (4.9), we get the stated bound. ∎

####  4.5.2 Convergence Rate in Interpolation Regime

Now we assume that $F(\boldsymbol{x})=\mathbb{E}_{\xi}[f(\boldsymbol{x},\xi)]$
and that the stochastic gradient is calculated drawing one function in each
time step and calculating its gradient: $\boldsymbol{g}_{t}=\nabla
f(\boldsymbol{x}_{t},\xi_{t})$. In this scenario, it makes sense to consider
the _interpolation_ condition (Needell et al., 2015; Ma et al., 2018)

$\boldsymbol{x}^{\star}\in\mathop{\text{argmin}}_{\boldsymbol{x}}\
F(\boldsymbol{x})\Rightarrow\boldsymbol{x}^{\star}\in\mathop{\text{argmin}}_{\boldsymbol{x}}\
f(\boldsymbol{x},\xi),\ \forall\xi~{}.$ (4.10)

This condition says that the problem is “easy”, in the sense that all the
functions in the expectation share the same minimizer. This case morally
corresponds to the case in which there is no noise on the stochastic
gradients. However, this condition seems weaker because it says that only in
the optimum the gradient is exact and noisy everywhere else. We will also
assume that each function $f(\boldsymbol{x},\xi)$ is $L$-smooth in the first
argument.

######  Theorem 15.

Assume $f$ is $L$-smooth and $\|\boldsymbol{g}_{t}\|\leq G,G>0$. Then, under
the interpolation assumption in (4.10), Algorithm 3 with
$\boldsymbol{\gamma}_{t}=\frac{\alpha\cdot\mathbf{1}}{\sqrt{G^{2}+\sum_{i=1}^{t}\alpha_{i}^{2}\|\boldsymbol{g}_{i}\|^{2}}}$
guarantees

$\displaystyle\mathbb{E}F(\boldsymbol{x}_{T})-F(\boldsymbol{x}^{\star})\leq\frac{2C}{T}\sqrt{16L^{2}C^{2}\ln^{2}T+8LC\ln
T+G^{2}},$

where
$C\triangleq\left(\frac{\|\boldsymbol{x}_{1}-\boldsymbol{x}^{\star}\|^{2}}{\alpha}+\alpha\right)$.

To the best of our knowledge, this is the first rate for the last iterate of
momentum methods in the interpolation setting.

####  4.5.3 Proofs

Before presenting the proofs of our convergence rates, we revisit the Online-
to-Batch algorithm (Algorithm 5) by Cutkosky (2019), which introduce a
modification to any online learning algorithm to obtain a guarantee on the
last iterate in the stochastic convex setting.

######  Lemma 27.

(Cutkosky, 2019, Theorem 1) Assume $\mathbb{E}\|\boldsymbol{g}_{t}-\nabla
f(\boldsymbol{x}_{t})\|\leq\sigma^{2},\sigma>0$. Then, for all
$\boldsymbol{x}^{\star}\in D$, Algorithm 5 guarantees

$\mathbb{E}[f(\boldsymbol{x}_{T})]-f^{\star}\leq\mathbb{E}\left[\frac{R_{T}(\boldsymbol{x}^{\star})}{\sum_{t=1}^{T}\alpha_{t}}\right]~{}.$
(4.11)

Algorithm 5 Anytime Online-to-Batch (Cutkosky, 2019)

1: Input: Online learning algorithm $\mathcal{A}$ with convex domain D,
$\alpha_{1},...,\alpha_{T}$, with $\alpha_{1}>0$.

2: Get Initial point $\boldsymbol{w}_{1}$ from $\mathcal{A}$

3: for $t=1,\dots,T$ do

4:
$\boldsymbol{x}_{t}=\frac{\sum_{i=1}^{t}\alpha_{i}\boldsymbol{w}_{i}}{\sum_{i=1}^{t}\alpha_{i}}$

5: Play $\boldsymbol{x}_{t}$, receive subgradient $\boldsymbol{g}_{t}$

6: Send
$\ell_{t}(\boldsymbol{x})=\langle\alpha_{t}\boldsymbol{g}_{t},\boldsymbol{x}\rangle$
to $\mathcal{A}$ as the $t$th loss

7: Get $\boldsymbol{w}_{t+1}$ from $\mathcal{A}$

8: end for

Algorithm 6 Anytime Online-to-Batch with FTRL

1: Input: $\alpha_{1},...,\alpha_{T}$, with $\alpha_{t}>0$.
$0<\gamma_{t+1}\leq\gamma_{t}$.

2: Initialize $\boldsymbol{w}_{1}$

3: for $t=1,\dots,T$ do

4:
$\boldsymbol{x}_{t}=\frac{\sum_{i=1}^{t}\alpha_{i}\boldsymbol{w}_{i}}{\sum_{i=1}^{t}\alpha_{i}}$

5: Play $\boldsymbol{x}_{t}$, receive subgradient $\boldsymbol{g}_{t}$

6:
$\boldsymbol{w}_{t+1}=\boldsymbol{w}_{1}-\boldsymbol{\gamma}_{t}\sum_{i=1}^{t}\alpha_{i}\boldsymbol{g}_{i}$

7: end for

Set
$\psi_{t}({\boldsymbol{x}})=\|\frac{\boldsymbol{x}_{1}-\boldsymbol{x}}{\sqrt{\boldsymbol{\gamma}_{t-1}}}\|^{2},1\leq
t\leq T$ as the regularizers of FTRL, where
$\boldsymbol{\gamma}_{t+1}\leq\boldsymbol{\gamma}_{t}$ and
$\boldsymbol{\gamma}_{0}>0$. Then, we write FTRL with loss
$\ell_{t}(\boldsymbol{w})=\langle\alpha_{t}\boldsymbol{g}_{t},\boldsymbol{w}\rangle$
as

$\boldsymbol{w}_{t}\in\mathop{\text{argmin}}_{\boldsymbol{w}\in\mathbb{R}^{d}}\
\psi_{t}(\boldsymbol{w})+\sum_{i=1}^{t-1}\langle\alpha_{i}\boldsymbol{g}_{i},\boldsymbol{w}\rangle=\boldsymbol{w}_{1}-\boldsymbol{\gamma}_{t-1}\sum_{i=1}^{t-1}\alpha_{i}\boldsymbol{g}_{i}~{}.$

We then plug FTRL into Algorithm 5 and it gives Algorithm 6. Hence, using the
well-known regret upper bound of FTRL (Lemma 25), we get the following Lemma.

######  Lemma 28.

Under the same setting with Lemma 27, Algorithm 6 guarantees

$\displaystyle\mathbb{E}$
$\displaystyle\left[f(\boldsymbol{x}_{T})\right]-f^{\star}\leq\frac{1}{\sum_{t=1}^{T}\alpha_{t}}\mathbb{E}\left[\left\|\frac{\boldsymbol{u}-\boldsymbol{x}_{1}}{\sqrt{\boldsymbol{\gamma}_{T-1}}}\right\|^{2}+\sum_{t=1}^{T}\langle\boldsymbol{\gamma}_{t-1},\alpha_{t}^{2}\boldsymbol{g}_{t}^{2}\rangle\right]~{}.$

Now we prove the connection between the FTRL-based SGDM and Algorithm 6.

###### Proof of Theorem 14.

We prove that the updates of $\boldsymbol{x}_{t}$ in Algorithm 3 can be one-
to-one mapped to the updates of $\boldsymbol{x}_{t}$ Algorithm 6 when
$\boldsymbol{w}_{1}=\boldsymbol{x}_{1}$.

The update of $\boldsymbol{x}_{t}$ in Algorithm 6 can be written as following:

$\displaystyle\boldsymbol{x}_{t+1}=\frac{\sum_{i=1}^{t}\alpha_{i}}{\sum_{i=1}^{t+1}\alpha_{i}}\boldsymbol{x}_{t}+\frac{\alpha_{t+1}}{\sum_{i=1}^{t+1}\alpha_{i}}\boldsymbol{w}_{t+1}=\frac{\sum_{i=1}^{t}\alpha_{i}}{\sum_{i=1}^{t+1}\alpha_{i}}\boldsymbol{x}_{t}+\frac{\alpha_{t+1}}{\sum_{i=1}^{t+1}\alpha_{i}}\left(\boldsymbol{w}_{1}-\boldsymbol{\gamma}_{t}\sum_{i=1}^{t}\alpha_{i}\boldsymbol{g}_{i}\right)~{}.$

It is enough to prove that for any $t$,
$\boldsymbol{\eta}_{t}\boldsymbol{m}_{t}=\frac{\alpha_{t+1}}{\sum_{i=1}^{t+1}\alpha_{i}}\left(\boldsymbol{\gamma}_{t}\sum_{i=1}^{t}\alpha_{i}\boldsymbol{g}_{i}\right)$.
We claim it is true and prove it by induction.

When $t=1$, it holds that
$\boldsymbol{\eta}_{1}\boldsymbol{m}_{1}=\frac{\alpha_{2}\alpha_{1}}{\alpha_{1}+\alpha_{2}}\boldsymbol{\gamma}_{1}\boldsymbol{g}_{1}$.
Suppose it holds for $t=k-1,k\geq 2$. Then in the case of $t=k$, we have

$\displaystyle\boldsymbol{\eta}_{k}\boldsymbol{m}_{k}$
$\displaystyle=\left(\frac{\sum_{i=1}^{k-1}\alpha_{i}}{\sum_{i=1}^{k}\alpha_{i}}\boldsymbol{m}_{k-1}+\frac{\alpha_{k}}{\sum_{i=1}^{k}\alpha_{i}}\boldsymbol{g}_{k}\right)\cdot\frac{\alpha_{k+1}\sum_{i=1}^{k}\alpha_{i}}{\sum_{i=1}^{k+1}\alpha_{i}}\boldsymbol{\gamma}_{k}$
$\displaystyle=\left(\frac{\sum_{i=1}^{k-1}\alpha_{i}}{\sum_{i=1}^{k}\alpha_{i}}\left(\frac{1}{\eta_{k-1}}\frac{\alpha_{k}}{\sum_{i=1}^{k}\alpha_{i}}\boldsymbol{\gamma}_{k-1}\sum_{i=1}^{k-1}\alpha_{i}\boldsymbol{g}_{i}\right)+\frac{\alpha_{k}}{\sum_{i=1}^{k}\alpha_{i}}\boldsymbol{g}_{k}\right)\cdot\frac{\alpha_{k+1}\sum_{i=1}^{k}\alpha_{i}}{\sum_{i=1}^{k+1}\alpha_{i}}\boldsymbol{\gamma}_{k}$
$\displaystyle=\frac{\alpha_{k+1}\sum_{i=1}^{k}\alpha_{i}}{\sum_{i=1}^{k+1}\alpha_{i}}\boldsymbol{\gamma}_{k}\cdot\left(\frac{\sum_{i=1}^{k-1}\alpha_{i}}{\sum_{i=1}^{k}\alpha_{i}}\left(\frac{\sum_{i=1}^{k-1}\alpha_{i}\boldsymbol{g}_{i}}{\sum_{i=1}^{k-1}\alpha_{i}}\right)+\frac{\alpha_{k}}{\sum_{i=1}^{k}\alpha_{i}}\boldsymbol{g}_{k}\right)$
$\displaystyle=\frac{\alpha_{k+1}}{\sum_{i=1}^{k+1}\alpha_{i}}\boldsymbol{\gamma}_{k}\sum_{i=1}^{k}\alpha_{i}\boldsymbol{g}_{i}~{}.$

where in the first equation we used the definitions of $\eta_{k}$ and
$\boldsymbol{m}_{k}$ and in the second equality we used the induction step. So
we proved the above claim. Thus, we can directly use Lemma 28. ∎

Here we show the proof of Theorem 15.

###### Proof of Theorem 15.

By Theorem 14, we have

$\displaystyle\mathbb{E}\left[F(\boldsymbol{x}_{T})\right]-F(\boldsymbol{x}^{\star})\leq\frac{2}{T}\left(\frac{\|\boldsymbol{x}_{1}-\boldsymbol{x}^{\star}\|^{2}}{\alpha}+2\alpha\right)\sqrt{\mathbb{E}\sum_{t=1}^{T}\|\nabla
f(\boldsymbol{x}_{t},\xi_{t})\|^{2}+\epsilon}+\frac{\alpha
G^{2}}{\sqrt{\epsilon}}~{}.$ (4.12)

Under the interpolation condition and $L$-smoothness of the functions $f$, it
satisfies that

$\displaystyle\mathbb{E}\sum_{t=1}^{T}\|\nabla
f(\boldsymbol{x}_{t},\xi_{t})\|^{2}$ $\displaystyle\leq
2L\mathbb{E}\left[\sum_{t=1}^{T}\left(f(\boldsymbol{x}_{t},\xi_{t})-f(\boldsymbol{x}^{\star},\xi_{t})\right)\right]$
$\displaystyle\leq
2L\sum_{t=1}^{T}\mathbb{E}\left[F(\boldsymbol{x}_{t})\right]-F(\boldsymbol{x}^{\star})~{}.$

Use (4.12) on each $t$ to get

$\displaystyle\sum_{t=1}^{T}\mathbb{E}\left[F(\boldsymbol{x}_{t})\right]-F(\boldsymbol{x}^{\star})$
$\displaystyle\leq\sum_{t=1}^{T}\frac{1}{t}\left[\left(\frac{\|\boldsymbol{x}_{1}-\boldsymbol{x}^{\star}\|^{2}}{\alpha}+2\alpha\right)\sqrt{\mathbb{E}\sum_{i=1}^{t}\|\nabla
f(\boldsymbol{x}_{i},\xi_{i})\|^{2}+\epsilon}+\frac{\alpha
G^{2}}{\sqrt{\epsilon}}\right]$
$\displaystyle\leq\left(\frac{\|\boldsymbol{x}_{1}-\boldsymbol{x}^{\star}\|^{2}}{\alpha}+2\alpha\right)\cdot\left(\sqrt{\mathbb{E}\sum_{t=1}^{T}\|\nabla
f(\boldsymbol{x}_{t},\xi_{t})\|^{2}+\epsilon}+\frac{\alpha
G^{2}}{\sqrt{\epsilon}}\right)\ln T~{}.$

Then, we solve for $\mathbb{E}\sum_{t=1}^{T}\|\nabla
f(\boldsymbol{x}_{t},\xi_{t})\|^{2}$ and get

$\displaystyle\mathbb{E}\sum_{t=1}^{T}\|\nabla
f(\boldsymbol{x}_{t},\xi_{t})\|^{2}$ $\displaystyle\leq
4L^{2}\left(\frac{\|\boldsymbol{x}_{1}-\boldsymbol{x}^{\star}\|^{2}}{\alpha}+2\alpha\right)^{2}\ln^{2}T+4L\sqrt{\epsilon}\left(\frac{\|\boldsymbol{x}_{1}-\boldsymbol{x}^{\star}\|^{2}}{\alpha}+2\alpha\right)\ln
T+\frac{2\alpha G^{2}}{\sqrt{\epsilon}}~{}.$

Using this expression in (4.12), we have the stated bound. ∎

###  4.6 Conclusion

We have presented an analysis of the convergence of the last iterate of SGDM
in the convex setting. We prove for the first time through a lower bound the
suboptimal convergence rate for the last iterate of SGDM with constant
momentum after T iterations. Moreover, we study a class of FTRL-based SGDM
algorithms with increasing momentum and shrinking updates, of which the last
iterate has optimal convergence rate without projections onto bounded domain
nor knowledge of T.

##  Chapter 5 Conclusions

In this dissertation, we studied the convergence of a series of heuristic
variants of SGD, including the strategies for choosing stepsizes: Delayed
AdaGrad, exponential and cosine stepsize, and the use of momentum. We moved
along the way of closing the gap between the theory and practice by presenting
formal guarantees to these heuristic optimization methods, providing possible
explanations for good empirical performance from a theoretical perspective,
and proposing improved algorithms when the theoretical results are suboptimal.

For future work, on the high probability analysis of SGD with adaptive
stepsizes, an interesting direction is to extend the current analysis of
Delayed AdaGrad with momentum to Adam, the popularly employed algorithm in
machine learning applications. The updates of Adam are composed of a weighted
sum of past gradients, each one multiplied by the current learning rate. The
dependency between the past and the future makes the analysis challenging, as
discussed in Section 2.6.1.

Moreover, most of the time we focus on smooth functions, yet some machine
learning objective functions are non-smooth, such as for ReLU neural network.
Zhang et al. (2019a, 2020) analyzed clipped SGD on a class of non-smooth
functions. An open problem is to study SGD with adaptive stepsizes and
momentum on such non-smooth functions.

## References

  * Abadi et al. [2015] M. Abadi, A. Agarwal, P. Barham, E. Brevdo, Z. Chen, C. Citro, G. S. Corrado, A. Davis, J. Dean, M. Devin, S. Ghemawat, I. Goodfellow, A. Harp, G. Irving, M. Isard, Y. Jia, R. Jozefowicz, L. Kaiser, M. Kudlur, J. Levenberg, D. Mané, R. Monga, S. Moore, D. Murray, C. Olah, M. Schuster, J. Shlens, B. Steiner, I. Sutskever, K. Talwar, P. Tucker, V. Vanhoucke, V. Vasudevan, F. Viégas, O. Vinyals, P. Warden, M. Wattenberg, M. Wicke, Y. Yu, and X. Zheng.  TensorFlow: Large-scale machine learning on heterogeneous systems, 2015\.  URL https://arxiv.org/abs/1603.04467.
  * Abernethy et al. [2008] J. D. Abernethy, E. Hazan, and A. Rakhlin.  Competing in the dark: An efficient algorithm for bandit linear optimization.  In Rocco A. Servedio and Tong Zhang, editors, _Proceedings of Conference on Learning Theory (COLT)_ , pages 263–274. Omnipress, 2008.  URL http://colt2008.cs.helsinki.fi/papers/123-Abernethy.pdf.
  * Alacaoglu et al. [2020] A. Alacaoglu, Y. Malitsky, P. Mertikopoulos, and V. Cevher.  A new regret analysis for Adam-type algorithms.  In _International Conference on Machine Learning_ , pages 202–210. PMLR, 2020.
  * Alber et al. [1998] Ya. I. Alber, A. N. Iusem, and M. V Solodov.  On the projected subgradient method for nonsmooth convex optimization in a Hilbert space.  _Mathematical Programming_ , 81(1):23–35, 1998\.  URL https://link.springer.com/article/10.1007/BF01584842.
  * Allen-Zhu et al. [2019] Z. Allen-Zhu, Y. Li, and Z. Song.  A convergence theory for deep learning via over-parameterization.  In _International Conference on Machine Learning_ , pages 242–252. PMLR, 2019.
  * Arjevani et al. [2019] Y. Arjevani, Y. Carmon, J. C. Duchi, D. J. Foster, N. Srebro, and B. Woodworth.  Lower bounds for non-convex stochastic optimization.  _arXiv preprint arXiv:1912.02365_ , 2019.
  * Arora et al. [2015] S. Arora, R. Ge, T. Ma, and A. Moitra.  Simple, efficient, and neural algorithms for sparse coding.  In Grünwald P, E. Hazan, and S. Kale, editors, _Proceedings of The 28th Conference on Learning Theory_ , volume 40 of _Proceedings of Machine Learning Research_ , pages 113–149, Paris, France, 03–06 Jul 2015. PMLR.
  * Auer et al. [2002] P. Auer, N. Cesa-Bianchi, and C. Gentile.  Adaptive and self-confident on-line learning algorithms.  _Journal of Computer and System Sciences_ , 64(1):48–75, 2002.  URL http://homes.dsi.unimi.it/~cesabian/Pubblicazioni/jcss-02.pdf.
  * Aybat et al. [2019] N. S. Aybat, A. Fallah, M. Gurbuzbalaban, and A. Ozdaglar.  A universally optimal multistage accelerated stochastic gradient method.  In _Advances in Neural Information Processing Systems_ , pages 8523–8534, 2019.
  * Bach and Moulines [2011] F. Bach and E. Moulines.  Non-asymptotic analysis of stochastic approximation algorithms for machine learning.  In J. Shawe-Taylor, R. S. Zemel, P. L. Bartlett, F. Pereira, and K. Q. Weinberger, editors, _Advances in Neural Information Processing Systems 24_ , pages 451–459. Curran Associates, Inc., 2011.
  * Bertsekas and Tsitsiklis [1996] D. P. Bertsekas and J. N. Tsitsiklis.  _Neuro-Dynamic Programming_.  Athena Scientific, 1996.
  * Bertsekas and Tsitsiklis [2000] D. P. Bertsekas and J. N. Tsitsiklis.  Gradient convergence in gradient methods with errors.  _SIAM Journal on Optimization_ , 10(3):627–642, 2000.  URL https://epubs.siam.org/doi/pdf/10.1137/S1052623497331063.
  * Beygelzimer et al. [2011] A. Beygelzimer, J. Langford, L. Li, L. Reyzin, and R. Schapire.  Contextual bandit algorithms with supervised learning guarantees.  In _Proceedings of the International Conference on Artificial Intelligence and Statistics_ , pages 19–26, 2011.
  * Bottou [1991] L. Bottou.  _Une Approche théorique de l’Apprentissage Connexioniste; Applications à la reconnaissance de la Parole_.  PhD thesis, Universite de Paris Sud, Centre d’Orsay, 1991.
  * Bottou [1998] L. Bottou.  Online algorithms and stochastic approximations.  In D. Saad, editor, _Online Learning and Neural Networks_. Cambridge University Press, Cambridge, UK, 1998.  URL http://leon.bottou.org/papers/bottou-98x.  revised, May 2018.
  * Bottou et al. [2018] L. Bottou, F. E. Curtis, and J. Nocedal.  Optimization methods for large-scale machine learning.  _SIAM Review_ , 60(2):223–311, 2018.
  * Chen et al. [2020] T. Chen, S. Kornblith, M. Norouzi, and G. Hinton.  A simple framework for contrastive learning of visual representations.  In Hal Daumé, III and Aarti Singh, editors, _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 1597–1607. PMLR, 13–18 Jul 2020.
  * Chen et al. [2019] X. Chen, S. Liu, R. Sun, and M. Hong.  On the convergence of a class of Adam-type algorithms for non-convex optimization.  In _7th International Conference on Learning Representations, ICLR 2019_ , 2019.
  * Chen and Candes [2015] Y. Chen and E. Candes.  Solving random quadratic systems of equations is nearly as easy as solving linear systems.  In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, _Advances in Neural Information Processing Systems 28_ , pages 739–747. Curran Associates, Inc., 2015.
  * Cubuk et al. [2019] E. D Cubuk, B. Zoph, D. Mane, V. Vasudevan, and Q. V Le.  Autoaugment: Learning augmentation strategies from data.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 113–123, 2019.
  * Cutkosky [2019] A. Cutkosky.  Anytime online-to-batch, optimism and acceleration.  In K. Chaudhuri and R. Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 1446–1454, Long Beach, California, USA, 09–15 Jun 2019. PMLR.  URL http://proceedings.mlr.press/v97/cutkosky19a/cutkosky19a.pdf.
  * Cutkosky and Orabona [2018] A. Cutkosky and F. Orabona.  Black-box reductions for parameter-free online learning in Banach spaces.  In _Proceedings of the Conference on Learning Theory (COLT)_ , 2018\.  URL https://arxiv.org/abs/1802.06293.
  * Davis et al. [2019] D. Davis, D. Drusvyatskiy, and V. Charisopoulos.  Stochastic algorithms with geometric step decay converge linearly on sharp functions.  _arXiv preprint arXiv:1907.09547_ , 2019.
  * Davis et al. [2021] D. Davis, D. Drusvyatskiy, L. Xiao, and J. Zhang.  From low probability to high confidence in stochastic convex optimization.  _Journal of Machine Learning Research_ , 22(49):1–38, 2021.
  * Defazio [2020] A. Defazio.  Understanding the role of momentum in non-convex optimization: Practical insights from a lyapunov analysis.  _arXiv preprint arXiv:2010.00406_ , 2020.
  * Dekel et al. [2012] O. Dekel, R. Gilad-Bachrach, O. Shamir, and L. Xiao.  Optimal distributed online prediction using mini-batches.  _Journal of Machine Learning Research_ , 13(Jan):165–202, 2012.
  * Dieuleveut et al. [2017] A. Dieuleveut, N. Flammarion, and F. Bach.  Harder, better, faster, stronger convergence rates for least-squares regression.  _Journal of Machine Learning Research_ , 18(1):3520–3570, January 2017.
  * Duchi et al. [2011] J. C. Duchi, E. Hazan, and Y. Singer.  Adaptive subgradient methods for online learning and stochastic optimization.  _Journal of Machine Learning Research_ , 12:2121–2159, 2011\.
  * Gaillard et al. [2014] Pierre Gaillard, Gilles Stoltz, and Tim Van Erven.  A second-order bound with excess losses.  In _Conference on Learning Theory_ , pages 176–196. PMLR, 2014.
  * Gastaldi [2017] X. Gastaldi.  Shake-shake regularization of 3-branch residual networks.  In _Proceedings of the International Conference on Learning Representations_ , 2017.  URL https://openreview.net/pdf?id=HkO-PCmYl.
  * Ge et al. [2019] R. Ge, S. M. Kakade, R. Kidambi, and P. Netrapalli.  The step decay schedule: A near optimal, geometrically decaying learning rate procedure for least squares.  In _Advances in Neural Information Processing Systems_ , pages 14951–14962, 2019.
  * Ghadimi and Lan [2012] S. Ghadimi and G. Lan.  Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework.  _SIAM Journal on Optimization_ , 22(4):1469–1492, 2012.
  * Ghadimi and Lan [2013] S. Ghadimi and G. Lan.  Stochastic first- and zeroth-order methods for nonconvex stochastic programming.  _SIAM Journal on Optimization_ , 23(4):2341–2368, 2013.  URL https://arxiv.org/abs/1309.5549.
  * Ginsburg et al. [2019] B. Ginsburg, P. Castonguay, O. Hrinchuk, O. Kuchaiev, V. Lavrukhin, R. Leary, J Li, H. Nguyen, Y. Zhang, and J. M Cohen.  Stochastic gradient methods with layer-wise adaptive moments for training of deep networks.  _arXiv preprint arXiv:1905.11286_ , 2019.
  * Goffin [1977] J.-L. Goffin.  On convergence rates of subgradient optimization methods.  _Mathematical programming_ , 13(1):329–347, 1977\.
  * Grill et al. [2020] J. Grill, F. Strub, F. Altché, C. Tallec, P. Richemond, E. Buchatskaya, C. Doersch, Bernardo Avila P., Z. Guo, M. Gheshlaghi Azar, B. Piot, K. kavukcuoglu, R. Munos, and M. Valko.  Bootstrap your own latent - a new approach to self-supervised learning.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 21271–21284. Curran Associates, Inc., 2020.
  * Harvey et al. [2019a] N. J. Harvey, C. Liaw, Y. Plan, and S. Randhawa.  Tight analyses for non-smooth stochastic gradient descent.  In _Conference on Learning Theory_ , pages 1579–1613, 2019a.
  * Harvey et al. [2019b] N. J. Harvey, C. Liaw, and S. Randhawa.  Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent.  _arXiv preprint arXiv:1909.00843_ , 2019b.
  * Hazan and Kale [2011] E. Hazan and S. Kale.  Beyond the regret minimization barrier: an optimal algorithm for stochastic strongly-convex optimization.  In S. M. Kakade and U. von Luxburg, editors, _Proceedings of the 24th Annual Conference on Learning Theory_ , volume 19 of _Proceedings of Machine Learning Research_ , pages 421–436, Budapest, Hungary, 09–11 Jun 2011\. PMLR.
  * He et al. [2019] T. He, Z. Zhang, H. Zhang, Z. Zhang, J. Xie, and M. Li.  Bag of tricks for image classification with convolutional neural networks.  In _The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2019.  URL https://openaccess.thecvf.com/content_CVPR_2019/papers/He_Bag_of_Tricks_for_Image_Classification_with_Convolutional_Neural_Networks_CVPR_2019_paper.pdf.
  * Jain et al. [2018] P. Jain, S. M. Kakade, R. Kidambi, P. Netrapalli, and A. Sidford.  Accelerating stochastic gradient descent for least squares regression.  In S. Bubeck, V. Perchet, and P. Rigollet, editors, _Proceedings of the 31st Conference On Learning Theory_ , volume 75 of _Proceedings of Machine Learning Research_ , pages 545–604. PMLR, 06–09 Jul 2018.
  * Jain et al. [2021] P. Jain, D. M. Nagaraj, and P. Netrapalli.  Making the last iterate of sgd information theoretically optimal.  _SIAM Journal on Optimization_ , 31(2):1108–1130, 2021.  doi: 10.1137/19M128908X.
  * Jelassi and Defazio [2020] S. Jelassi and A. Defazio.  Dual averaging is surprisingly effective for deep learning optimization.  _arXiv preprint arXiv:2010.10502_ , 2020.
  * Jin et al. [2017] C. Jin, R. Ge, P. Netrapalli, S.M. Kakade, and M. I. Jordan.  How to escape saddle points efficiently.  In _Proceedings of the 34th International Conference on Machine Learning_ , volume 70, pages 1724–1732. PMLR, 2017.
  * Jin et al. [2019] C. Jin, P. Netrapalli, R. Ge, S. M. Kakade, and M. I. Jordan.  A short note on concentration inequalities for random vectors with subgaussian norm.  _arXiv preprint arXiv:1902.03736_ , 2019.
  * Kakade and Tewari [2009] S. M Kakade and A. Tewari.  On the generalization ability of online strongly convex programming algorithms.  In _Advances in Neural Information Processing Systems_ , pages 801–808, 2009.
  * Karimi et al. [2016] H. Karimi, J. Nutini, and M. Schmidt.  Linear convergence of gradient and proximal-gradient methods under the Polyak-Łojasiewicz condition.  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , pages 795–811. Springer, 2016.
  * Khaled and Richtárik [2020] A. Khaled and P. Richtárik.  Better theory for SGD in the nonconvex world.  _arXiv preprint arXiv:2002.03329_ , 2020.
  * Kidambi et al. [2018] R. Kidambi, P. Netrapalli, P. Jain, and S. Kakade.  On the insufficiency of existing momentum schemes for stochastic optimization.  In _2018 Information Theory and Applications Workshop (ITA)_ , pages 1–9. IEEE, 2018.
  * Kingma and Ba [2015] D. P. Kingma and J. Ba.  Adam: A method for stochastic optimization.  In _International Conference on Learning Representations (ICLR)_ , 2015.  URL https://arxiv.org/abs/1412.6980.
  * Kleinberg et al. [2018] B. Kleinberg, Y. Li, and Y. Yuan.  An alternative view: When does SGD escape local minima?  In J. Dy and A. Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 2698–2707, Stockholmsmässan, Stockholm Sweden, 10–15 Jul 2018. PMLR.
  * Kresoja et al. [2017] M. Kresoja, Z. Lužanin, and I. Stojkovska.  Adaptive stochastic approximation algorithm.  _Numerical Algorithms_ , 76(4):917–937, Dec 2017\.
  * Kulunchakov and Mairal [2019] A. Kulunchakov and J. Mairal.  A generic acceleration framework for stochastic composite optimization.  In _Advances in Neural Information Processing Systems_ , pages 12556–12567, 2019.
  * Lan [2012] G. Lan.  An optimal method for stochastic composite optimization.  _Mathematical Programming_ , 133(1):365–397, 2012\.
  * Lan et al. [2012] G. Lan, A. Nemirovski, and A. Shapiro.  Validation analysis of mirror descent stochastic approximation method.  _Mathematical programming_ , 134(2):425–458, 2012\.
  * Lawen et al. [2019] H. Lawen, A. Ben-Cohen, M. Protter, I. Friedman, and L. Zelnik-Manor.  Attention network robustification for person ReID.  _arXiv preprint arXiv:1910.07038_ , 2019.
  * Lei et al. [2017] L. Lei, C. Ju, J. Chen, and M. I. Jordan.  Non-convex finite-sum optimization via SCSG methods.  In _Advances in Neural Information Processing Systems 30_ , pages 2348–2358. Curran Associates, Inc., 2017.
  * Levy et al. [2018] K. Y. Levy, A. Yurtsever, and V. Cevher.  Online adaptive methods, universality and acceleration.  In _Advances in Neural Information Processing Systems_ , pages 6500–6509, 2018.
  * Li and Orabona [2019] X. Li and F. Orabona.  On the convergence of stochastic gradient descent with adaptive stepsizes.  In _Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, AISTATS_ , 2019.  URL http://proceedings.mlr.press/v89/li19c/li19c.pdf.
  * Li and Orabona [2020] X. Li and F. Orabona.  A high probability analysis of adaptive SGD with momentum.  In _ICML 2020 Workshop on Beyond First Order Methods in ML Systems_ , 2020.
  * Li et al. [2020] Z. Li, H. Bao, X. Zhang, and P. Richtárik.  Page: A simple and optimal probabilistic gradient estimator for nonconvex optimization.  _arXiv preprint arXiv:2008.10898_ , 2020.
  * Liu and Belkin [2019] Chaoyue Liu and Mikhail Belkin.  Accelerating sgd with momentum for over-parameterized learning.  In _International Conference on Learning Representations_ , 2019.  URL https://openreview.net/attachment?id=r1gixp4FPH&name=original_pdf.
  * Liu et al. [2018] H. Liu, K. Simonyan, and Y. Yang.  Darts: Differentiable architecture search.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/pdf?id=S1eYHoC5FX.
  * Liu et al. [2020] Y. Liu, Y. Gao, and W. Yin.  An improved analysis of stochastic gradient descent with momentum.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Łojasiewicz [1963] S. Łojasiewicz.  A topological property of real analytic subsets (in french).  _Coll. du CNRS, Les équations aux dérivées partielles_ , pages 87–89, 1963.
  * Loshchilov and Hutter [2017] I. Loshchilov and F. Hutter.  SGDR: Stochastic gradient descent with warm restarts.  In _International Conference on Learning Representations_ , 2017.  URL https://openreview.net/pdf?id=Skq89Scxx.
  * Ma et al. [2018] S. Ma, R. Bassily, and M. Belkin.  The power of interpolation: Understanding the effectiveness of SGD in modern over-parametrized learning.  In _International Conference on Machine Learning_ , pages 3325–3334. PMLR, 2018.
  * Mairal [2013] J. Mairal.  Stochastic majorization-minimization algorithms for large-scale optimization.  In _Advances in Neural Information Processing Systems_ , pages 2283–2291, 2013.  URL https://arxiv.org/abs/1306.4650.
  * McMahan and Streeter [2010] H. B. McMahan and M. J. Streeter.  Adaptive bound optimization for online convex optimization.  In _23rd Conference on Learning Theory,_ , 2010.  URL http://www.learningtheory.org/colt2010/conference-website/papers/104mcmahan.pdf.
  * Needell et al. [2015] D. Needell, N. Srebro, and R. Ward.  Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm.  _Mathematical Programming_ , 155:549–573, 2015.
  * Nemirovski et al. [2009] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro.  Robust stochastic approximation approach to stochastic programming.  _SIAM Journal on optimization_ , 19(4):1574–1609, 2009.
  * Nemirovsky and Yudin [1983] A. S. Nemirovsky and D. Yudin.  _Problem complexity and method efficiency in optimization_.  Wiley, New York, NY, USA, 1983.  URL https://books.google.com/books/about/Problem_Complexity_and_Method_Efficiency.html?id=6ULvAAAAMAAJ.
  * Nesterov [1983] Y. Nesterov.  A method for unconstrained convex minimization problem with the rate of convergence $O(1/k^{2})$.  In _Doklady AN SSSR (translated as Soviet. Math. Docl.)_ , volume 269, pages 543–547, 1983.
  * Nesterov [2004] Y. Nesterov.  _Introductory lectures on convex optimization: A basic course_ , volume 87.  Springer, 2004.
  * Nesterov [2009] Y. Nesterov.  Primal-dual subgradient methods for convex problems.  _Mathematical programming_ , 120(1):221–259, 2009\.  URL https://link.springer.com/content/pdf/10.1007/s10107-007-0149-x.pdf.
  * Nesterov [2015] Y. Nesterov.  Universal gradient methods for convex optimization problems.  _Mathematical Programming_ , 152(1-2):381–404, 2015.
  * Nesterov and Shikhman [2015] Y. Nesterov and V. Shikhman.  Quasi-monotone subgradient methods for nonsmooth convex minimization.  _Journal of Optimization Theory and Applications_ , 165(3):917–940, 2015.
  * Orabona [2019] F. Orabona.  A modern introduction to online learning.  _arXiv preprint arXiv:1912.13213_ , 2019.
  * Orabona and Pál [2015] F. Orabona and D. Pál.  Scale-free algorithms for online linear optimization.  In _International Conference on Algorithmic Learning Theory_ , pages 287–301. Springer, 2015.  URL https://arxiv.org/abs/1502.05744.
  * Paszke et al. [2019] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala.  Pytorch: An imperative style, high-performance deep learning library.  In _Advances in Neural Information Processing Systems 32_ , pages 8024–8035. Curran Associates, Inc., 2019.
  * Polyak [1963] B. T. Polyak.  Gradient methods for minimizing functionals.  _Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki_ , 3(4):643–653, 1963.
  * Polyak [1964] B. T Polyak.  Some methods of speeding up the convergence of iteration methods.  _USSR Computational Mathematics and Mathematical Physics_ , 4(5):1–17, 1964.
  * Qian [1999] N. Qian.  On the momentum term in gradient descent learning algorithms.  _Neural networks_ , 12(1):145–151, 1999.
  * Rakhlin and Sridharan [2013] A. Rakhlin and K. Sridharan.  Optimization, learning, and games with predictable sequences.  In _Advances in Neural Information Processing Systems_ , pages 3066–3074, 2013.  URL https://arxiv.org/abs/1311.1869.
  * Reddi et al. [2016] S. J. Reddi, A. Hefny, S. Sra, B. Poczos, and A. Smola.  Stochastic variance reduction for nonconvex optimization.  In _International conference on machine learning_ , pages 314–323, 2016.
  * Reddi et al. [2018] S. J. Reddi, S. Kale, and S. Kumar.  On the convergence of Adam and beyond.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/pdf?id=ryQu7f-RZ.
  * Robbins and Monro [1951] H. Robbins and S. Monro.  A stochastic approximation method.  _Annals of Mathematical Statistics_ , 22:400–407, 1951\.  URL https://projecteuclid.org/euclid.aoms/1177729586.
  * Savarese et al. [2019] P. Savarese, D. McAllester, S. Babu, and M. Maire.  Domain-independent dominance of adaptive methods.  _arXiv preprint arXiv:1912.01823_ , 2019.
  * Sebbouh et al. [2021] O. Sebbouh, R. M Gower, and A. Defazio.  Almost sure convergence rates for stochastic gradient descent and stochastic heavy ball.  In _Conference on Learning Theory_ , pages 3935–3971. PMLR, 2021\.
  * Shalev-Shwartz [2007] S. Shalev-Shwartz.  _Online Learning: Theory, Algorithms, and Applications_.  PhD thesis, The Hebrew University, 2007.  URL https://www.cs.huji.ac.il/~shais/papers/ShalevThesis07.pdf.
  * Streeter and McMahan [2010] M. Streeter and H. B. McMahan.  Less regret via online conditioning, 2010.  URL https://arxiv.org/abs/1002.4862.  arXiv:1002.4862.
  * Sun and Luo [2016] R. Sun and Z. Luo.  Guaranteed matrix completion via non-convex factorization.  _IEEE Transactions on Information Theory_ , 62(11):6535–6579, 2016.
  * Sutskever et al. [2013] I. Sutskever, J. Martens, G. Dahl, and G. Hinton.  On the importance of initialization and momentum in deep learning.  In _International conference on machine learning_ , pages 1139–1147, 2013.
  * Tao et al. [2018] W. Tao, Z. Pan, G. Wu, and Q. Tao.  Primal averaging: A new gradient evaluation step to attain the optimal individual convergence.  _IEEE transactions on cybernetics_ , 50(2):835–845, 2018.
  * Tao et al. [2021] W. Tao, S. Long, G. Wu, and Q. Tao.  The role of momentum parameters in the optimal convergence of adaptive Polyak’s heavy-ball methods.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=L7WD8ZdscQ5.
  * Tieleman and Hinton [2012] T. Tieleman and G. Hinton.  Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude.  _COURSERA: Neural networks for machine learning_ , 4(2):26–31, 2012.
  * Vaswani et al. [2019] S. Vaswani, F. Bach, and M. Schmidt.  Fast and faster convergence of SGD for over-parameterized models and an accelerated Perceptron.  In K. Chaudhuri and M. Sugiyama, editors, _Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics_ , volume 89 of _Proceedings of Machine Learning Research_ , pages 1195–1204. PMLR, 16–18 Apr 2019.
  * Ward et al. [2019] R. Ward, X. Wu, and L. Bottou.  AdaGrad stepsizes: Sharp convergence over nonconvex landscapes.  In _International Conference on Machine Learning_ , pages 6677–6686. PMLR, 2019.
  * Warmuth and Jagota [1997] M. K. Warmuth and A. K. Jagota.  Continuous and discrete-time nonlinear gradient descent: Relative loss bounds and convergence.  In _Electronic proceedings of the 5th International Symposium on Artificial Intelligence and Mathematics_ , volume 326, 1997.  URL https://users.soe.ucsc.edu/~manfred/pubs/C45.pdf.
  * Wu et al. [2018] X. Wu, R. Ward, and L. Bottou.  WNGrad: Learn the learning rate in gradient descent.  _arXiv preprint arXiv:1803.02865_ , 2018.
  * You et al. [2020] J. You, J. Leskovec, K. He, and S. Xie.  Graph structure of neural networks.  In _International Conference on Machine Learning_ , pages 10881–10891. PMLR, 2020.
  * Yousefian et al. [2012] F. Yousefian, A. Nedić, and U. V. Shanbhag.  On stochastic gradient and subgradient methods with adaptive steplength sequences.  _Automatica_ , 48(1):56–67, 2012.
  * Yuan et al. [2019] Z. Yuan, Y. Yan, R. Jin, and T. Yang.  Stagewise training accelerates convergence of testing error over sgd.  In _Advances in Neural Information Processing Systems_ , pages 2604–2614, 2019.
  * Zeiler [2012] M. D. Zeiler.  ADADELTA: an adaptive learning rate method.  _arXiv preprint arXiv:1212.5701_ , 2012.
  * Zhang et al. [2020] B. Zhang, J. Jin, C. Fang, and L. Wang.  Improved analysis of clipping algorithms for non-convex optimization.  _Advances in Neural Information Processing Systems_ , 33:15511–15521, 2020.
  * Zhang et al. [2019a] J. Zhang, T. He, S. Sra, and A. Jadbabaie.  Why gradient clipping accelerates training: A theoretical justification for adaptivity.  In _International Conference on Learning Representations_ , 2019a.  URL https://openreview.net/pdf?id=BJgnXpVYwS.
  * Zhang et al. [2019b] X. Zhang, Q. Wang, J. Zhang, and Z. Zhong.  Adversarial autoaugment.  In _International Conference on Learning Representations_ , 2019b.  URL https://openreview.net/pdf?id=ByxdUySKvS.
  * Zhang et al. [2019c] Z. Zhang, T. He, H. Zhang, Z. Zhang, J. Xie, and M. Li.  Bag of freebies for training object detection neural networks.  _arXiv preprint arXiv:1902.04103_ , 2019c.
  * Zhao et al. [2020] H. Zhao, J. Jia, and V. Koltun.  Exploring self-attention for image recognition.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2020.
  * Zhou et al. [2018] D. Zhou, Y. Tang, Z. Yang, Y. Cao, and Q. Gu.  On the convergence of adaptive gradient methods for nonconvex optimization, 2018.  arXiv:1808.05671.
  * Zhou et al. [2017] Z. Zhou, P. Mertikopoulos, N. Bambos, S. Boyd, and P. W. Glynn.  Stochastic mirror descent in variationally coherent optimization problems.  In _Advances in Neural Information Processing Systems_ , pages 7043–7052, 2017.
  * Zhu [2018] Z. Zhu.  Natasha 2: Faster non-convex optimization than SGD.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems 31_ , pages 2675–2686. Curran Associates, Inc., 2018.
  * Zoph et al. [2018] B. Zoph, V. Vasudevan, J. Shlens, and Q. V. Le.  Learning transferable architectures for scalable image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 8697–8710, 2018.
  * Zou et al. [2018] F. Zou, L. Shen, Z. Jie, J. Sun, and W. Liu.  Weighted AdaGrad with unified momentum.  _arXiv preprint arXiv:1808.03408_ , 2018.