# SGEM: stochastic gradient with energy and momentum

Hailiang Liu and Xuping Tian  Iowa State University, Mathematics Department,
Ames, IA 50011<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

In this paper, we propose SGEM, Stochastic Gradient with Energy and Momentum,
to solve a large class of general non-convex stochastic optimization problems,
based on the AEGD method that originated in the work [AEGD: Adaptive Gradient
Descent with Energy. arXiv: 2010.05109]. SGEM incorporates both energy and
momentum at the same time so as to inherit their dual advantages. We show that
SGEM features an unconditional energy stability property, and derive energy-
dependent convergence rates in the general nonconvex stochastic setting, as
well as a regret bound in the online convex setting. A lower threshold for the
energy variable is also provided. Our experimental results show that SGEM
converges faster than AEGD and generalizes better or at least as well as SGDM
in training some deep neural networks.

###### Key words and phrases:

gradient descent, stochastic optimization, energy stability, momentum

###### 1991 Mathematics Subject Classification:

90C15, 65K10, 68Q25

##  1\. Introduction

In this paper, we propose SGEM: Stochastic Gradient with Energy and Momentum,
to solve the following general non-convex stochastic optimization problem

(1.1)
$\min_{\theta\in\mathbb{R}^{d}}f(\theta):=\mathbb{E}_{\xi}[f(\theta;\xi)],$

where $\mathbb{E}_{\xi}[\cdot]$ denotes the expectation with respect to the
random variable $\xi$. We assume that $f$ is differentiable and bounded from
below, i.e., $f^{*}=\inf_{\theta\in\mathbb{R}^{d}}f(\theta)>-c$ for some
$c>0$.

Problem (1.1) arises in many statistical learning and deep learning models
[15, 7, 3]. For such large scale problems, it would be too expensive to
compute the full gradient $\nabla f(\theta)$. One approach to handle this
difficulty is to use an unbiased estimator of $\nabla f(\theta)$. Denote the
stochastic gradient at the $t$-th iteration as $g_{t}$, the iteration of
Stochastic Gradient Descent (SGD) [26] can be described as:

$\theta_{t+1}=\theta_{t}-\eta_{t}g_{t},$

where $\eta_{t}$ is called the learning rate. Its convergence is known to be
ensured if $\eta_{t}$ meets the sufficient condition:

(1.2)
$\sum_{t=1}^{\infty}\eta_{t}=\infty,\quad\sum_{t=1}^{\infty}\eta_{t}^{2}<\infty.$

However, vanilla SGD suffers from slow convergence due to the variance of the
stochastic gradient, which is one of the major bottlenecks for practical use
of SGD [2, 28]. Its performance is also sensitive to the learning rate, which
is tricky to tune via (1.2). Different techniques have been introduced to
improve the convergence and robustness of SGD, such as variance reduction [5,
16, 12, 22], momentum acceleration [1, 30], and adaptive learning rate [6, 31,
13]. Among these, momentum and adaptive learning rate techniques are most
economic since they require slightly more computation in each iteration.
However, training with adaptive algorithms such as Adam or its variants
typically generalizes worse than SGD with momentum (SGDM), even when the
training performance is better [32].

The most popular momentum technique, Heavy Ball (HB) [23] has been extensively
studied for stochastic optimization problems [20, 11, 24]. SGDM, also called
SHB, as a combination of SGD and momentum takes the following form

(1.3) $m_{t}=\mu m_{t-1}+g_{t},\;\theta_{t+1}=\theta_{t}-\eta_{t}m_{t},$

where $m_{0}=0$ and $\mu\in(0,1)$ is the momentum factor. This helps to reduce
the variance in stochastic gradients thus speeds up the convergence, and has
been found to be successful in practice [30].

AEGD originated in the work [18] is a gradient-based optimization algorithm
that adjusts the learning rate by a transformed gradient $v$ and an energy
variable $r$. The method includes two ingredients: the base update rule:

(1.4) $\theta_{t+1}=\theta_{t}+2\eta r_{t+1}v_{t},\quad
r_{t+1}=\frac{r_{t}}{1+2\eta v^{2}_{t}},$

and the stochastic evaluation of the transformed gradient $v_{t}$ as

(1.5) $v_{t}=\frac{g_{t}}{2\sqrt{f(\theta_{t};\xi_{t})+c}}.$

AEGD is unconditionally energy stable with guaranteed convergence in energy
regardless of the size of the base learning rate $\eta>0$ and how $v_{t}$ is
evaluated. This explains why the method can have a rapid initial training
process as well as good generalization performance [18].

In addition, the stochastic AEGD has also shown distinct improvement in
performance as observed in experiments in [18], where the convergence analysis
is mostly restricted to the deterministic setting. Questions we want to answer
here are: (i) does Stochastic AEGD converge for non-convex optimization
problems as in the deterministic setting? (ii) whether adding momentum can
help accelerate convergence? In this paper, we propose and analyze a unified
framework by incorporating both energy and momentum so as to inherit their
dual advantages. We do so by keeping the base AEGD update rule (1.4), but
taking

(1.6) $\displaystyle
v_{t}=\frac{m_{t}}{2(1-\beta^{t})\sqrt{f(\theta_{t};\xi_{t})+c}},$
$\displaystyle m_{t}=\beta m_{t-1}+(1-\beta)g_{t},$

where $\beta\in(0,1)$. We call this novel method SGEM. It reduces to AEGD when
$\beta=0$. An immediate advantage is that with such $v_{t}$ one can
significantly reduce the oscillations observed in the AEGD in stochastic
cases. Regarding the theoretical results, we attempt to develop a convergence
theory for SGEM, in both stochastic nonconvex setting and online convex
setting.

We highlight the main contributions of our work as follows:

  * •

We propose a novel and simple gradient-based method SGEM which integrates both
energy and momentum. The only hyperparameter requires tuning is the base
learning rate.

  * •

We show the unconditional energy stability of SGEM, and provide energy-
dependent convergence rates in the general stochastic nonconvex setting, and a
regret bound for the online convex framework. We also obtain a lower threshold
for the energy variable. Our assumptions are natural and mild.

  * •

We empirically validate the good performance of SGEM on several deep learning
benchmarks. Our results show that

    * –

The base learning rate requires little tuning on complex deep learning tasks.

    * –

Overall, SGEM is able to achieve both fast convergence and good generalization
performance. Specifically, SGEM converges faster than AEGD and generalizes
better or at least as well as SGDM.

Related works. The essential idea behind AEGD is the so called Invariant
Energy Quadratizaton (IEQ) strategy, originally introduced for developing
linear and unconditionally energy stable schemes for gradient flows in the
form of partial differential equations [34, 37]. As for gradient-based
methods, there has appeared numerous works on the analysis of convergence
rates. In online convex setting, a regret bound for SGD is derived in [39];
the classical convergence results of SGD in stochastic nonconvex setting can
be found in [3]; For SGDM, we refer the readers to [35, 33, 20] for
convergence rates on smooth nonconvex objectives. For adaptive gradient
methods, most convergence analyses are restricted to online convex setting [6,
25, 21], while recent attempts, such as [4, 40], have been made to analyze the
convergence in stochastic nonconvex setting.

This paper is organized as follows. We first review AEGD in Section 2, then
introduce the proposed algorithm in Section 3. Theoretical analysis including
unconditional energy stability, convergence rates in both stochastic nonconvex
setting and online convex setting are presented in Section 4. In Section 5, we
report some experimental results on deep learning tasks.

Notation For a vector $\theta\in\mathbb{R}^{n}$, we denote $\theta_{t,i}$ as
the $i$-th element of $\theta$ at the $t$-th iteration. For vector norm, we
use $\|\cdot\|$ to denote $l_{2}$ norm and use $\|\cdot\|_{\infty}$ to denote
$l_{\infty}$ norm. We also use $[m]$ to represent the list $\\{1,...,m\\}$ for
any positive integer $m$.

##  2\. Review of AEGD

Recall that for the objective function $f$, we assume that $f$ is
differentiable and bounded from below, i.e., $f(\theta)>-c$ for some $c>0$.
The key idea of AEGD introduced in [18] is the use of an auxiliary energy
variable $r$ such that

(2.1) $\nabla f(\theta)=2rv,\quad v:=\nabla\sqrt{f(\theta)+c},$

where $r$, taking as $\sqrt{f(\theta)+c}$ initially, will be updated together
with $\theta$, and $v$ is dubbed as the transformed gradient. The gradient
flow $\dot{\theta}=-\nabla f(\theta)$ is then replaced by

$\dot{\theta}=-2rv,\quad\dot{r}=v\cdot\dot{\theta}.$

A simple implicit-explicit discretization gives the following AEGD update
rule:

(2.2a) $\displaystyle v_{t}=\frac{\nabla
f(\theta_{t})}{2\sqrt{f(\theta_{t})+c}}.$ (2.2b)
$\displaystyle\theta_{t+1}=\theta_{t}-2\eta r_{t+1}v_{t},$ (2.2c)
$\displaystyle r_{t+1}-r_{t}=v_{t}\cdot(\theta_{t+1}-\theta_{t}).$

This yields a decoupled update for $r$ as
$r_{t+1}=r_{t}/(1+2\eta|v_{t}|^{2})$, which serves to adapt the learning rate.
For large-scale problems, stochastic sampling approach is preferred. Let
$f(\theta_{t};\xi_{t})$ be a stochastic estimator of the function value
$f(\theta_{t})$ at the $t$-th iteration, $g_{t}$ be a stochastic estimator of
the gradient $\nabla f(\theta_{t})$, then the stochastic version of AEGD is
still (2.2) but with $v_{t}$ replaced by

$v_{t}=\frac{g_{t}}{2\sqrt{f(\theta_{t};\xi_{t})+c}}.$

Usually, $g_{t}$ should be required to satisfy $\mathbb{E}[g_{t}]=\nabla
f(\theta_{t})$ and $\mathbb{E}[\|g_{t}\|^{2}]$ bounded. Correspondingly, an
element-wise version of AEGD for stochastic training reads as

(2.3a) $\displaystyle
v_{t,i}=\frac{g_{t,i}}{2\sqrt{f(\theta_{t};\xi_{t})+c}},\quad i\in[n],$ (2.3b)
$\displaystyle r_{t+1,i}=\frac{r_{t,i}}{1+2\eta v_{t,i}^{2}},\quad
r_{1,i}=\sqrt{f(\theta_{1};\xi_{1})+c},$ (2.3c)
$\displaystyle\theta_{t+1,i}=\theta_{t,i}-2\eta r_{t+1,i}v_{t,i}.$

The element-wise AEGD allows for different effective learning rates for
different coordinates, which has been empirically verified to be more
effective than the global AEGD (2.2). For further details, we refer to [18].
We will focus only on the element-wise version of SGEM in what follows.

##  3\. AEGD with momentum

In this section, we present a novel algorithm to improve AEGD with added
momentum in the following manner:

(3.1a) $\displaystyle m_{t}$ $\displaystyle=\beta m_{t-1}+(1-\beta)g_{t},\quad
m_{0}=\bf{0},$ (3.1b) $\displaystyle v_{t}$
$\displaystyle=\frac{m_{t}}{2(1-\beta^{t})\sqrt{f(\theta_{t};\xi_{t})+c}},$

where $\beta\in(0,1)$ controls the weight for gradient at each step. With
$v_{t}$ so defined, the update rule for $r$ and $\theta$ are kept the same as
given in (2.3b, c). The relation between the energy and the momentum in the
algorithm is realized through relating $m_{t}$ ( as an approximation to
$\nabla f$) to $v_{t}$ (as an approximation of $\nabla F=\frac{\nabla
f}{2\sqrt{f+c}}$), where $v_{t}$ is used to update the energy $r_{t+1}$. In
machine learning tasks, $f$ as a loss function is often in the form of
$f(\theta)=\frac{1}{m}\sum_{i=1}^{m}l_{i}(\theta)$, where $l_{i}$, measuring
the distance between the model output and target label at the $i$-th data
point, is typically bounded from below, that is, $l_{i}(\theta)>-c,\forall
i\in[m]$, for some $c>0$. Hence $c$ in (3.1b) can be easily chosen in advance
so that $f(\theta_{t};\xi_{t})$ as a random sample from
$\\{l_{i}(\theta_{t})\\}_{i=1}^{m}$ is bounded below by $-c$ for all
$t\in[T]$. We summarize this in Algorithm 1 (called SGEM, for short).

A key feature of SGEM is that it incorporates momentum into AEGD without
changing the overall structure of the AEGD algorithm (the update of $r$ and
$\theta$ remain the same) so that it is shown (in Section 4) to still enjoy
the unconditional energy stability property as AEGD does. In addition, by
using $m_{t}$ instead of $g_{t}$, the variance can be significantly reduced.
In fact, as proved in [20], under the assumption
$\mathbb{E}_{\xi_{t}}[\|g_{t}-\nabla
f(\theta_{t})\|^{2}]=\sigma^{2}_{g}<\infty$, $m_{t}$, which can be expressed
as a linear combination of the gradients at all previous steps,

(3.2) $m_{t}=(1-\beta)\sum_{j=1}^{t}\beta^{t-j}g_{j},$

enjoys a reduced “variance” in the sense that

$\mathbb{E}_{\xi_{t}}\Bigg{[}\bigg{\|}m_{t}-(1-\beta)\sum_{j=1}^{t}\beta^{t-j}\nabla
f(\theta_{j})\bigg{\|}^{2}\Bigg{]}\leq(1-\beta)\sigma^{2}_{g}.$

Hence compared with AEGD, we expect SGEM to achieve faster convergence due to
the reduced variance. This is also the main advantage of SGEM over AEGD that
we observed in experiments (See Figure 1).

Figure 1. The training loss of a Logistic regression model for the multiclass
classification problem on MNIST dataset. Unlike the common setting where the
batch size is set as 128 or 64, we take the batch size as 1 so that the
problem of the variance of the stochastic gradient is more severe. Algorithm 1
SGEM. Good default setting for parameters are $\eta=0.2$, $\beta=0.9$

1:Require: the base learning rate $\eta$; a constant $c$ such that
$f(\theta_{t};\xi_{t})+c>0$ for all $t\in[T]$; a momentum factor
$\beta\in(0,1)$.

2:Initialization: $\theta_{1}$; $m_{0}=\bf{0}$;
$r_{1}=\sqrt{f(\theta_{1};\xi_{1})+c}\,\bf{1}$

3:for $t=1$ to $T-1$ do

4: Compute gradient: $g_{t}=\nabla f(\theta_{t};\xi_{t})$

5: $m_{t}=\beta m_{t-1}+(1-\beta)g_{t}$ (momentum update)

6: $v_{t}=m_{t}/(2(1-\beta^{t})\sqrt{f(\theta_{t};\xi_{t})+c})$ (transformed
momentum)

7: $r_{t+1}=r_{t}/(1+2\eta v_{t}\odot v_{t})$ (energy update)

8: $\theta_{t+1}=\theta_{t}-2\eta r_{t+1}\odot v_{t}$ (state update)

9:return ${\theta}_{T}$

######  Remark 1.

(i) In Algorithm 1, we use $x\odot y$ to denote element-wise product, $x/y$ to
denote element-wise division of two vectors $x,y\in\mathbb{R}^{n}$.
(ii) It is clear that $m_{t}$ defined in (3.2) is not a convex combination of
$g_{j}$, this is why there is a factor $1-\beta^{t}$ in (3.1b); such treatment
is dubbed as bias correction in [13] for Adam.
(iii) In most machine learning problems, we have $f(\theta)\geq 0$, for which
a good default value for $c$ in Algorithm 1 is $1$.

##  4\. Theoretical results

In this section, we present our theoretical results, including the
unconditional energy stability of SGEM, the convergence of SGEM for the
general stochastic nonconvex optimization, a lower bound for energy $r_{T}$,
and a regret bound in the online convex setting.

###  4.1. Unconditional energy stability

######  Theorem 1.

(Unconditional energy stability) SGEM in Algorithm 1 is unconditionally energy
stable in the sense that for any step size $\eta>0,i\in[n]$,

(4.1) $\displaystyle\mathbb{E}[r^{2}_{t+1,i}]=\mathbb{E}[r^{2}_{t,i}]$
$\displaystyle-\mathbb{E}[(r_{t+1,i}-r_{t,i})^{2}]$
$\displaystyle-\eta^{-1}\mathbb{E}[(\theta_{t+1,i}-\theta_{t,i})^{2}],$

that is $\mathbb{E}[r_{t,i}]$ is strictly decreasing and convergent with
$\mathbb{E}[r_{t,i}]\to\mathbb{E}[r_{i}^{*}]$ as $t\to\infty$, and also

(4.2)
$\displaystyle\lim_{t\to\infty}\mathbb{E}[(\theta_{t+1,i}-\theta_{t,i})^{2}]=0,$
$\displaystyle\sum_{t=1}^{\infty}\mathbb{E}[(\theta_{t+1,i}-\theta_{t,i})^{2}]\leq\eta(f(\theta_{1})+c).$

######  Remark 2.

(i) The unconditional energy stability only depends on (2.3b, c), irrespective
of the choice for $v_{t}$. This property essentially means that the energy
variable $r_{t}$, which serves to approximate $\sqrt{f(\theta_{t})+c}$, is
strictly decreasing for any $\eta>0$. (ii) (4.2) indicates that the sequence
$\|\theta_{t+1}-\theta_{t}\|$ converges to zero at a rate of at least
$1/\sqrt{t}$. We note that this does not guarantee the convergence of
$\\{\theta_{t}\\}$ unless additional information on the geometry of $f$ is
available.

###### Proof.

From (2.3b, c) we have

$\displaystyle(\theta_{t+1,i}-\theta_{t,i})^{2}$
$\displaystyle=4\eta^{2}r^{2}_{t+1,i}v^{2}_{t,i}\quad\text{(By \ref{aegd}c)}$
$\displaystyle=(2\eta r_{t+1,i})(r_{t,i}-r_{t+1,i})\quad\text{(By
\ref{aegd}b)}$
$\displaystyle=\eta((r^{2}_{t,i}-r^{2}_{t+1,i})-(r_{t,i}-r_{t+1,i})^{2}).$

This upon taking expectation ensures the asserted properties. Such proof with
no use of the special form of $v_{t}$, is the same as that for AEGD (see
[18]). ∎

###  4.2. Convergence analysis

Below, we state the necessary assumptions that are commonly used for analyzing
the convergence of a stochastic algorithm for nonconvex problems, and
notations that will be used in our analysis.

######  Assumption 1.

  1. (1)

(Smoothness) The objective function in (1.1) is $L$-smooth: for any
$x,y\in\mathbb{R}^{n}$,

$f(y)\leq f(x)+\nabla f(x)^{\top}(y-x)+\frac{L}{2}\|y-x\|^{2}.$

  2. (2)

(Independent samples) The random samples $\\{\xi_{t}\\}_{t=1}^{\infty}$ are
independent.

  3. (3)

(Unbiasedness) The estimator of the gradient and function value are unbiased:

$\mathbb{E}_{\xi_{t}}[g_{t}]=\nabla
f(\theta_{t}),\quad\mathbb{E}_{\xi_{t}}[f(\theta_{t};\xi_{t})]=f(\theta_{t}).$

Denote the variance of the stochastic gradient and function value by
$\sigma_{g}$ and $\sigma_{f}$, respectively:

$\mathbb{E}_{\xi_{t}}[\|g_{t}-\nabla
f(\theta_{t})\|^{2}]=\sigma^{2}_{g},\quad\mathbb{E}_{\xi_{t}}[\lvert
f(\theta_{t};\xi_{t})-f(\theta_{t})\rvert^{2}]=\sigma^{2}_{f}.$

Before presenting our energy-dependent convergence rates, we first state a
result on the lower bound of $r_{T}$.

######  Theorem 2 (Lower bound of $r_{T}$).

Under Assumption 1 and assume that the stochastic gradient and function value
are bounded such that $\|g_{t}\|_{\infty}\leq G_{\infty}$ and $0<a\leq
f(\theta_{t};\xi_{t})+c\leq B$, in the absence of noise, we have

(4.3) $\min_{i}r_{T,i}\geq\max\\{F(\theta^{*})-\eta D_{1}-\beta D_{2},0\\},$

where $L_{F}$ is given in (4.6) and

$\displaystyle D_{1}=\frac{L_{F}nF^{2}(\theta_{1})}{2},\quad
D_{2}=\frac{\sqrt{B}nF(\theta_{1})}{(1-\beta)\sqrt{a}}.$

This implies

(4.4) $\min_{i}r_{T,i}>\min_{i}r^{*}_{i}>0\quad\text{if}\quad\eta D_{1}+\beta
D_{2}<F(\theta^{*}).$

######  Remark 3.

(i) (4.4) is only a sufficient condition, not intended as a guide for choosing
$\eta$. We observe from our experimental results that the upper bound for
$\eta$ to guarantee the positiveness of $r^{*}_{i}$ can be much larger (See
Figure 2).
(ii) In Theorem 2, we measure how far $r^{*}$ can deviate from $F(\theta^{*})$
in the worst scenario using simple error split, where $\eta D_{1}$ is the
error brought by the step size $\eta$, and $\beta D_{2}$ is due to the use of
momentum.

We only present a sketch of proofs for Theorem 2 and 3 here, using notation
$\tilde{F}_{t}=\sqrt{f(\theta_{t};\xi_{t})+c}$, $\eta_{t}=\eta/\tilde{F}_{t}$
and viewing $r_{t+1}$ as a $n\times n$ diagonal matrix that is made up of
$[r_{t+1,1},...,r_{t+1,i},...,r_{t+1,n}]$. Detailed proofs, including two
crucial lemmas and the full proof for Theorem 4, are deferred to the appendix.

###### Proof.

Using the $L_{F}$-smoothness of $F(\theta)$, we have

(4.5) $F(\theta_{t+1})-F(\theta_{t})\leq\nabla
F(\theta_{t})^{\top}(\theta_{t+1}-\theta_{t})+\frac{L_{F}}{2}\|\theta_{t+1}-\theta_{t}\|^{2},$

in which the key term $\nabla F(\theta_{t})^{\top}(\theta_{t+1}-\theta_{t})$
can be decomposed into three terms:

$\displaystyle(\nabla
F(\theta_{t})-\frac{g_{t}}{2\tilde{F}_{t}})^{\top}(\theta_{t+1}-\theta_{t}),$
$\displaystyle(\frac{g_{t}}{2\tilde{F}_{t}}-\frac{v_{t}}{1-\beta})^{\top}(\theta_{t+1}-\theta_{t}),\quad(\frac{v_{t}}{1-\beta})^{\top}(\theta_{t+1}-\theta_{t}).$

The first two terms are bounded by using the bounded variance assumption and
(4.2), respectively. We convert the last term, using (recall 2.2c)

$r_{t+1,i}-r_{t,i}=v_{t,i}(\theta_{t+1,i}-\theta_{t,i}),$

into expressions in terms of $r_{t+1,i}-r_{t,i}$, which upon summation is
bounded by $r_{T,i}$. The last term in (4.5) is bounded again by using (4.2).
∎

We proceed to discuss the convergence results. First note that the
$L$-smoothness of $f(\theta)$ implies the $L_{F}$-smoothness of
$F(\theta)=\sqrt{f(\theta)+c}$ with

(4.6)
$L_{F}=\frac{1}{2F(\theta^{*})}\left(L+\frac{G^{2}_{\infty}}{2F^{2}(\theta^{*})}\right).$

This will be used in the following result and its proof.

######  Theorem 3.

Let $\\{\theta_{t}\\}$ be the solution sequence generated by Algorithm 1 with
a fixed $\eta>0$. Under the same assumptions as in Theorem 2, we have
$\sigma_{g}\leq G_{\infty}$ and for all $T\geq 1$ and $\epsilon\in(0,1)$,

$\displaystyle\quad\;\mathbb{E}\Bigg{[}\min_{1\leq t\leq T}\|\nabla
f(\theta_{t})\|^{2-2\epsilon}\Bigg{]}$
$\displaystyle\leq\left(\frac{C_{1}+C_{2}n+C_{3}\sigma_{g}\sqrt{nT}}{\eta
T}\right)^{1-\epsilon}\cdot\mathbb{E}\Big{[}(\min_{i}r_{T,i})^{1-1/\epsilon}\Big{]}^{\epsilon},$

where $C_{1},C_{2},C_{3}$ are constants depending on
$\beta,\eta,L,G_{\infty},a,B,n$ and $f(\theta_{1})+c$.

######  Remark 4.

(i) The stated bound is a hybrid estimate depending on both $T$ and $r_{T}$,
which can be helpful in adjusting the base step size depending on the
asymptotic behavior of $r_{T}$. (ii) In Theorem 2 below, we identify a
sufficient condition for ensuring a lower threshold for $r_{T,i}$.
Numerically, we observe that for reasonable choice of $\eta$, $r_{T,i}$ either
stays above a positive threshold or decays but much slower than $1/\sqrt{T}$
(See Figures 2); in either case the result in Theorem 3 ensures the
convergence.

Figure 2. $\min_{i}r_{t,i}$ of SGEM with default base learning rate $0.2$ in
training DL tasks.

(iii) The assumption that the magnitude of the stochastic gradient is bounded
is standard in nonconvex stochastic analysis [3]. The upper bound on the
stochastic function value is technically needed to bound $m_{t}$ since
$m_{t}=2(1-\beta^{t})\sqrt{f+c}v_{t}$. To bound $v_{t}$, we don’t need an
upper bound on $f$.

###### Proof.

Using the $L$-smoothness of $f$, we have

(4.7) $f(\theta_{t+1})-f(\theta_{t})\leq\nabla
f(\theta_{t})^{\top}(\theta_{t+1}-\theta_{t})+\frac{L}{2}\|\theta_{t+1}-\theta_{t}\|^{2}.$

The first term on the RHS is carefully regrouped as

$\displaystyle-\frac{1-\beta}{1-\beta^{t}}\nabla
f(\theta_{t})^{\top}\eta_{t-1}r_{t}g_{t}+\frac{1-\beta}{1-\beta^{t}}\nabla
f(\theta_{t})^{\top}(\eta_{t-1}r_{t}-\eta_{t}r_{t+1})g_{t}-\frac{\beta}{1-\beta^{t}}\nabla
f(\theta_{t})^{\top}\eta_{t}r_{t+1}m_{t-1}.$

Taking a conditional expectation on the first term gives

$\displaystyle\quad\frac{1-\beta}{1-\beta^{t}}\eta_{t-1}\nabla
f(\theta_{t})^{T}r_{t}\nabla
f(\theta_{t})\geq(1-\beta)\frac{\eta}{\sqrt{B}}\min_{i}r_{t,i}\|\nabla
f(\theta_{t})\|^{2}.$

We manage to bound the other two terms in terms of

$\sum_{i=1}^{n}\sum_{t=1}^{T}r_{t+1,i}g^{2}_{t,i}\quad\text{and}\quad\sum_{i=1}^{n}\sum_{t=1}^{T}r_{t+1,i}m^{2}_{t,i}.$

Their bounds are presented in Lemma 2. The asserted bound then follows by
further summation in $t$ with telescope cancellation for
$f(\theta_{t+1})-f(\theta_{t})$ and bounding the last term in (4.7) using
(4.2). ∎

###  4.3. Regret bound for Online convex optimization

Our algorithm is also applicable to the online optimization that deals with
the optimization problems having no or incomplete knowledge of the future
(online). In the framework proposed in [39], at each step $t$, the goal is to
predict the parameter $\theta_{t}\in\mathcal{F}$, where
$\mathcal{F}\subset\mathbb{R}^{n}$ is a feasible set, and evaluate it on a
previously unknown loss function $f_{t}$. The nature of the sequence is
unknown in advance, the SGEM algorithm needs to be modified. This can be done
by replacing $f(\theta_{t},\xi_{t})$ by $f_{t}(\theta_{t})$ and taking
$g_{t}=\nabla f_{t}(\theta_{t})$ in $v_{t}$ defined in (3.1), i.e.,

(4.8a) $\displaystyle m_{t}=\beta m_{t-1}+(1-\beta)\nabla f_{t}(\theta_{t}),$
(4.8b) $\displaystyle
v_{t}=\frac{m_{t}}{2(1-\beta^{t})\sqrt{f_{t}(\theta_{t})+c}}.$

This algorithm is also unconditionally energy stable as pointed out in Remark
2. For convergence, we evaluate our algorithm using the regret, that is the
sum of all the previous difference between the online prediction
$f_{t}(\theta_{t})$ and the best fixed point parameter $f_{t}(\theta^{*})$
from a feasible set $\mathcal{F}$:

$R(T)=\sum_{t=1}^{T}[f_{t}(\theta_{t})-f_{t}(\theta^{*})],$

where $\theta^{*}={\rm
argmin}_{\theta\in\mathcal{F}}\sum_{t=1}^{T}f_{t}(\theta)$. For convex
objectives we have the following regret bound.

######  Theorem 4.

Let $\\{\theta_{t}\\}$ be the solution sequence generated by SGEM with a fixed
$\eta>0$. Assume that $\|x-y\|_{\infty}\leq D_{\infty}$ for all
$x,y\in\mathcal{F}$, $0<a\leq f_{t}(\theta_{t})+c\leq B$, and
$\theta_{t}\in\mathcal{F}$ for all $t\in[T]$. When $\mathcal{F}$ and $f_{t}$
are convex, SGEM achieves the following bound on the regret, for all $T\geq
1$,

(4.9) $R(T)\leq
C\sqrt{nT/\eta}\left(\sum_{i=1}^{n}\frac{1}{r_{T,i}}\right)^{1/2},$

where $C$ is a constant depending on $\beta,B,D_{\infty}$ and
$f_{1}(\theta_{1})+c$.

######  Remark 5.

(i) If $r_{T,i}>r^{*}_{i}>0$ as in (4.4), then $R(T)$ is of order
$O(\sqrt{T})$, which is known the best possible bound for online convex
optimization [See Section 3.2 in [8]], hence the convergence holds true in the
sense that

$\lim_{T\to\infty}\frac{R(T)}{T}=0.$

(ii) The bound on $\theta_{t}$ is typically enforced by projection onto
$\mathcal{F}$ [39], with which the regret bound (4.9) can still be proven
since projection is a contraction operator [8, Chapter 3]. As for the upper
bound on the function value, just like we remarked for Theorem 3, it is
technically needed to bound $m_{t}$.

##  5\. Numerical experiments

In this section, we compare the performance of the proposed SGEM and AEGD with
several other methods, including SGDM, AdaBelief [38], AdaBound [21], RAdam
[19], Yogi [36], and Adam [13], when applied to training deep neural networks.
***Code is available at https://github.com/txping/SGEM. We consider three
convolutional neural network (CNN) architectures: VGG-16 [29], ResNet-34 [9],
DenseNet-121 [10] on the CIFAR-100 dataset [14]; we also conduct experiments
on ImageNet dataset [27] with the ResNet-18 architecture [9].

For experiments on CIFAR-100, we employ the fixed budget of 200 epochs and
reduce the learning rates by 10 after 150 epochs. The weight decay and
minibatch size are set as $5\times 10^{-4}$ and $128$ respectively. For the
ImageNet tasks, we run 90 epochs and use similar learning rate decaying
strategy at the 30th and 60th epoch. The weight decay and minibatch size are
set as $1\times 10^{-4}$ and $256$ respectively.

In each task, we only tune the base learning rate and report the one that
achieves the best final generalization performance for each method:

  * •

SGEM: For CIFAR-100 tasks, we use the default parameter $\eta=0.2$; for the
ImageNet task, the learning rate is set as $\eta=0.3$.

  * •

SGDM, AEGD: We search learning rate among $\\{0.05,0.1,0.2\\}$.

  * •

AdaBelief, AdaBound, Yogi, RAdam, Adam: We search learning rate among
$\\{0.0005,0.001,0.01\\}$, other hyperparameters such as
$\beta_{1},\beta_{2},\epsilon$ are set as the default values in their
literature.

(a) VGG-16 training

(b) ResNet-34 training

(c) DenseNet-121 training

(d) VGG-16 test

(e) ResNet-34 test

(f) DenseNet-121 test

Figure 3. Training Loss and test accuracy for VGG-16, ResNet-34 and
DenseNet-121 on CIFAR-100

Figure 4. Training loss and test accuracy for ResNet-18 on ImageNet

From the experimental results of CIFAR-100, we see that in all tasks, SGEM and
AEGD achieve higher test accuracy than the other methods while the oscillation
of AEGD in test accuracy is significantly reduced by SGEM as expected. To
highlight the advantage of SGEM over AEGD, we also present the training loss
of the two methods in each experiment, which shows SGEM indeed displays faster
convergence than AEGD in most cases.

For the ImageNet task, all existing experiments show that SGDM gives the
highest test accuracy, we therefore focus only on the comparison between SGDM
and SGEM, and run Adam only as a representative of other adaptive methods. The
results are presented in Figure 4. We see that SGEM still shows faster
convergence and is able to achieve comparable test accuracy as SGDM in the end
of training. Here the highest test accuracy achieved by SGDM and SGEM are
$69.89$ and $69.92$, respectively.

##  6\. Conclusion

In this paper, we propose and analyze SGEM, which integrates AEGD with
momentum. We show that SGEM still enjoys the unconditional energy stability
property as AEGD, while the use of momentum helps to reduce the variance of
the stochastic gradient significantly, as verified in our experiments. We also
provide convergence analysis in both online convex setting and the general
stochastic nonconvex setting. Since our convergence results depend on the
energy variable, a lower bound on the energy is also presented. Finally, we
empirically show that SGEM converges faster than AEGD and generalizes better
or at least as well as SGDM on several deep learning benchmarks.

We believe these results are important. First, we go in the direction of
establishing a theory beyond the empirical results for this new class of
optimization algorithms. Second, our convergence rates can indeed provide an
explanation for the good performance of AEGD algorithms.

One of the limitations of the current analysis is the fact that the obtained
bound depends on $r_{T}$. It would be better to derive an asymptotic bound for
$r_{T}$ as in [17] for estimating the adaptive learning rate $\eta_{T}$.
However, the technique used in [17] relies on the specific form of $\eta_{T}$,
while analysis for $r_{T}$ with SGEM is far from straightforward. This issue
will be addressed in our future work.

Momentum is known to help accelerate gradient vectors in right directions and
reduce oscillations, thus leading to faster convergence. It is desirable to
quantify such effects also in the theoretical convergence bounds.
Unfortunately, this has not been well understood in the literature even for
SGDM. For example, SGDM (1.3) with constant step size is shown in [33, 35] to
have convergence bound:

$\min_{1\leq t\leq T}\mathbb{E}[\|\nabla f(\theta_{t})\|^{2}]=O\left(1/\eta
T+\eta\sigma^{2}/(1-\beta)\right),$

for general smooth nonconvex objectives. An improved bound in [20] is

$O\left(1/\eta T+\eta\sigma^{2}\right),$

since common choices for $\beta$ are close to 1. In contrast, when $r_{T}$
admits a positive lower bound, our result in Theorem 3 indeed ensures
convergence.

Based on our observations in this paper, we list some problems for future
work. First, we believe there is a threshold for $\eta^{*}$, such that $r_{T}$
either tends to a positive number or decays slower than $1/\sqrt{T}$ if
$\eta<\eta^{*}$. This issue merits a further theoretical investigation.
Second, since $r_{t}$ is strictly decreasing, there is a room to limit $r_{t}$
for controlling its decay whenever necessary. A proper energy limiter can be
of help.

##  Appendix A Proof of Theorem 2

For the proofs of Theorem 2 and Theorem 3, we introduce notation

(1.1) $\tilde{F}_{t}:=\sqrt{f(\theta_{t};\xi_{t})+c}.$

The initial data for $r_{i}$ is taken as $r_{1,i}=\tilde{F}_{1}$. We also
denote the update rule presented in Algorithm 1 as

(1.2) $\theta_{t+1}=\theta_{t}-2\eta r_{t+1}v_{t},$

where $r_{t+1}$ is viewed as a $n\times n$ diagonal matrix that is made up of
$[r_{t+1,1},...,r_{t+1,i},...,r_{t+1,n}]$.

######  Lemma 1.

Under the assumptions in Theorem 2, we have for all $t\in[T]$,

  1. (i)

$\|\nabla f(\theta_{t})\|_{\infty}\leq G_{\infty}$.

  2. (ii)

$\mathbb{E}[(\tilde{F}_{t})^{2}]=F^{2}(\theta_{t})=f(\theta_{t})+c$.

  3. (iii)

$\mathbb{E}[\tilde{F}_{t}]\leq F(\theta_{t})$. In particular,
$\mathbb{E}[r_{1,i}]=\mathbb{E}[\tilde{F}_{1}]\leq F(\theta_{1})$ for all
$i\in[n]$.

  4. (iv)

$\sigma^{2}_{g}=\mathbb{E}[\|g_{t}-\nabla f(\theta_{t})\|^{2}]\leq
G^{2}_{\infty}$ and $\sigma^{2}_{f}=\mathbb{E}[\lvert
f(\theta_{t};\xi_{t})-f(\theta_{t})\rvert^{2}]\leq B^{2}.$

  5. (v)

$\mathbb{E}[\lvert
F(\theta_{t})-\tilde{F}_{t}\rvert]\leq\frac{1}{2\sqrt{a}}\sigma_{f}$.

  6. (vi)

$\mathbb{E}[\|\nabla
F(\theta_{t})-\frac{g_{t}}{2\tilde{F}_{t}}\|^{2}]\leq\frac{G^{2}_{\infty}}{8a^{3}}\sigma^{2}_{f}+\frac{1}{2a}\sigma^{2}_{g}.$

###### Proof.

(i) By assumption $\|g_{t}\|_{\infty}\leq G_{\infty}$, we have

$\|\nabla
f(\theta_{t})\|_{\infty}=\|\mathbb{E}[g_{t}]\|_{\infty}\leq\mathbb{E}[\|g_{t}\|_{\infty}]\leq
G_{\infty}.$

(ii) This follows from the unbiased sampling of

$f(\theta_{t})=\mathbb{E}_{\xi_{t}}[f(\theta_{t};\xi_{t})].$

(iii) By Jensen’s inequality, we have

$\mathbb{E}[\tilde{F}_{t}]\leq\sqrt{\mathbb{E}[\tilde{F}_{t}^{2}]}=\sqrt{F(\theta_{t})^{2}}=F(\theta_{t}).$

(iv) By assumptions $\|g_{t}\|_{\infty}\leq G_{\infty}$ and
$f(\theta_{t};\xi_{t})+c<B$, we have

$\sigma^{2}_{g}=\mathbb{E}[\|g_{t}-\nabla
f(\theta_{t})\|^{2}]=\mathbb{E}[\|g_{t}\|^{2}]-\|\nabla
f(\theta_{t})\|^{2}\leq G^{2}_{\infty},$
$\sigma^{2}_{f}=\mathbb{E}[\|f(\theta_{t};\xi_{t})-f(\theta_{t})\|^{2}]=\mathbb{E}[\|f(\theta_{t};\xi_{t})\|^{2}]-\|f(\theta_{t})\|^{2}\leq
B^{2}.$

(v) By the assumption $0<a\leq f(\theta_{t};\xi_{t})+c=\tilde{F}_{t}^{2}$, we
have

$\displaystyle\quad\mathbb{E}[\lvert
F(\theta_{t})-\tilde{F}_{t}\rvert]\leq\mathbb{E}\Bigg{[}\bigg{\lvert}\frac{f(\theta_{t})-f(\theta_{t};\xi_{t})}{F(\theta_{t})+\tilde{F}_{t}}\bigg{\rvert}\Bigg{]}\leq\frac{1}{2\sqrt{a}}\mathbb{E}[\lvert
f(\theta_{t})-f(\theta_{t};\xi_{t})\rvert]\leq\frac{1}{2\sqrt{a}}\sigma_{f}.$

(vi) By the definition of $F(\theta)$, we have

$\displaystyle\|\nabla F(\theta_{t})-\frac{g_{t}}{2\tilde{F}_{t}}\|^{2}$
$\displaystyle=\bigg{\|}\frac{\nabla
f(\theta_{t})}{2F(\theta_{t})}-\frac{g_{t}}{2\tilde{F}_{t}}\bigg{\|}^{2}$
$\displaystyle=\frac{1}{4}\bigg{\|}\frac{\nabla
f(\theta_{t})(\tilde{F}_{t}-F(\theta_{t}))}{F(\theta_{t})\tilde{F}_{t}}+\frac{\nabla
f(\theta_{t})-g_{t}}{\tilde{F}_{t}}\bigg{\|}^{2}$
$\displaystyle\leq\frac{1}{2}\bigg{\|}\frac{\nabla
f(\theta_{t})(\tilde{F}_{t}-F(\theta_{t}))}{F(\theta_{t})\tilde{F}_{t}}\bigg{\|}^{2}+\frac{1}{2}\bigg{\|}\frac{\nabla
f(\theta_{t})-g_{t}}{\tilde{F}_{t}}\bigg{\|}^{2}$
$\displaystyle\leq\frac{G^{2}_{\infty}}{2a^{2}}\lvert\tilde{F}_{t}-F(\theta_{t})\rvert^{2}+\frac{1}{2a}\|\nabla
f(\theta_{t})-g_{t}\|^{2},$

where both the gradient bound and the assumption that $0<a\leq
f(\theta_{t};\xi_{t})+c=\tilde{F}^{2}_{t}$ are essentially used. Take an
expectation to get

$\displaystyle\mathbb{E}[\|\nabla
F(\theta_{t})-\frac{g_{t}}{2\tilde{F}_{t}}\|^{2}]\leq\frac{G^{2}_{\infty}}{2a^{2}}\mathbb{E}[\lvert\tilde{F}_{t}-F(\theta_{t})\rvert^{2}]+\frac{1}{2a}\mathbb{E}[\|\nabla
f(\theta_{t})-g_{t}\|^{2}].$

Similar to the proof for ($iv$), we have

$\mathbb{E}[\lvert\tilde{F}_{t}-F(\theta_{t})\rvert^{2}]\leq\frac{1}{4a}\sigma^{2}_{f}.$

This together with the variance assumption for $g_{t}$ gives

$\mathbb{E}[\|\nabla
F(\theta_{t})-\frac{g_{t}}{2\tilde{F}_{t}}\|^{2}]\leq\frac{G^{2}_{\infty}}{8a^{3}}\sigma^{2}_{f}+\frac{1}{2a}\sigma^{2}_{g}.$

∎

######  Lemma 2.

For any $T\geq 1$, we have

  1. (i)

$\mathbb{E}\Big{[}\sum_{t=1}^{T}v_{t}^{\top}r_{t+1}v_{t}\Big{]}\leq\frac{nF(\theta_{1})}{2\eta}$.

  2. (ii)

$\mathbb{E}\Big{[}\sum_{t=1}^{T}m_{t-1}^{\top}r_{t+1}m_{t-1}\Big{]}\leq\mathbb{E}\Big{[}\sum_{t=1}^{T}m_{t}^{\top}r_{t+1}m_{t}\Big{]}\leq\frac{2BnF(\theta_{1})}{\eta}$.

  3. (iii)

$\mathbb{E}\Big{[}\sum_{t=1}^{T}\|r_{t+1}m_{t}\|^{2}\Big{]}\leq\frac{2BnF^{2}(\theta_{1})}{\eta}$.

  4. (iv)

$\mathbb{E}\Big{[}\sum_{t=1}^{T}g_{t}^{\top}r_{t+1}g_{t}\Big{]}\leq\frac{8BnF(\theta_{1})}{(1-\beta)^{2}\eta}$.

  5. (v)

$\mathbb{E}\Big{[}\sum_{t=1}^{T}\|r_{t+1}g_{t}\|^{2}\Big{]}\leq\frac{8BnF^{2}(\theta_{1})}{(1-\beta)^{2}\eta}$.

###### Proof.

From Algorithm 1 line 5, we have

$r_{t,i}-r_{t+1,i}=2\eta r_{t+1,i}v^{2}_{t,i}.$

Taking summation over $t$ from $1$ to $T$ gives

$r_{1,i}-r_{T+1,i}=2\eta\sum_{t=1}^{T}r_{t+1,i}v^{2}_{t,i}\quad\Rightarrow\quad\sum_{t=1}^{T}r_{t+1,i}v^{2}_{t,i}\leq\frac{r_{1,i}}{2\eta}.$

From which we get

$\sum_{t=1}^{T}v_{t}^{\top}r_{t+1}v_{t}=\sum_{i=1}^{n}\sum_{t=1}^{T}r_{t+1,i}v^{2}_{t,i}\leq\frac{n\tilde{F}_{1}}{2\eta}.$

Taking expectation and using (iii) in Lemma 1 gives (i).

Recall that $m_{t}=2(1-\beta^{t})\tilde{F}_{t}v_{t}$ and
$\tilde{F}_{t}\leq\sqrt{B}$, we further get

$\sum_{t=1}^{T}m_{t}^{\top}r_{t+1}m_{t}\leq
4B\sum_{t=1}^{T}v_{t}^{\top}r_{t+1}v_{t}=\frac{2Bn\tilde{F}_{1}}{\eta}.$

Using $r_{t+1,i}\leq r_{t,i}$ and $m_{0,i}=0$, we also have

(1.3)
$\sum_{i=1}^{n}\sum_{t=1}^{T}r_{t+1,i}m^{2}_{t-1,i}\leq\sum_{i=1}^{n}\sum_{t=1}^{T}r_{t,i}m^{2}_{t-1,i}=\sum_{i=1}^{n}\sum_{t=1}^{T-1}r_{t+1,i}m^{2}_{t,i}\leq\sum_{i=1}^{n}\sum_{t=1}^{T}r_{t+1,i}m^{2}_{t,i}.$

Connecting the above two inequalities and taking expectation gives (ii).

Using $r_{t+1,i}\leq r_{1,i}$, the above inequality further implies

$\displaystyle\sum_{t=1}^{T}\|r_{t+1}m_{t}\|^{2}$
$\displaystyle=\sum_{i=1}^{n}\sum_{t=1}^{T}r^{2}_{t+1,i}m_{t,i}^{2}\leq\sum_{i=1}^{n}\sum_{t=1}^{T}r_{1,i}r_{t+1,i}m_{t,i}^{2}$
$\displaystyle=\bigg{(}\sum_{i=1}^{n}\sum_{t=1}^{T}r_{t,i}m_{t,i}^{2}\bigg{)}\tilde{F}_{1}\leq
2Bn\tilde{F}^{2}_{1}/\eta.$

Taking expectation and using (ii) in Lemma 1 gives (iii).

By $m_{t}=\beta m_{t-1}+(1-\beta)g_{t}$, we have

$\displaystyle\sum_{t=1}^{T}g_{t}^{\top}r_{t+1}g_{t}$
$\displaystyle=\sum_{i=1}^{n}\sum_{t=1}^{T}r_{t+1,i}g^{2}_{t,i}=\sum_{i=1}^{n}\sum_{t=1}^{T}r_{t+1,i}\bigg{(}\frac{1}{1-\beta}m_{t,i}-\frac{\beta}{1-\beta}m_{t-1,i}\bigg{)}^{2}$
$\displaystyle\leq\frac{2}{(1-\beta)^{2}}\sum_{i=1}^{n}\sum_{t=1}^{T}r_{t+1,i}m^{2}_{t,i}+\frac{2\beta^{2}}{(1-\beta)^{2}}\sum_{i=1}^{n}\sum_{t=1}^{T}r_{t+1,i}m^{2}_{t-1,i}$
$\displaystyle\leq\frac{2(1+\beta^{2})}{(1-\beta)^{2}}\sum_{t=1}^{T}m_{t}^{\top}r_{t+1}m_{t}\leq\frac{8Bn\tilde{F}_{1}}{(1-\beta)^{2}\eta}.$

Here the third inequality is by $(a+b)^{2}\leq 2a^{2}+2b^{2}$; (1.3) and
$0<\beta<1$ are used in the fourth inequality. Taking expectation and using
(iii) in Lemma 1 gives (iv).

Similar as the derivation for (ii), we have

$\displaystyle\sum_{t=1}^{T}\|r_{t+1}g_{t}\|^{2}\leq\bigg{(}\sum_{i=1}^{n}\sum_{t=1}^{T}r_{t,i}g_{t,i}^{2}\bigg{)}\tilde{F}_{1}$
$\displaystyle\leq\frac{8Bn\tilde{F}^{2}_{1}}{(1-\beta)^{2}\eta}.$

Taking expectation and using (ii) in Lemma 1 gives (v). ∎

First note that by (iv) in Lemma 1,
$\max\\{\sigma_{g},\sigma_{f}\\}\leq\max\\{G_{\infty},B\\}$.
Recall that $F(\theta)=\sqrt{f(\theta)+c}$, then for any
$x,y\in\\{\theta_{t}\\}_{t=0}^{T}$ we have

$\displaystyle\|\nabla F(x)-\nabla F(y)\|$
$\displaystyle=\bigg{\|}\frac{\nabla f(x)}{2F(x)}-\frac{\nabla
f(y)}{2F(y)}\bigg{\|}$ $\displaystyle=\frac{1}{2}\bigg{\|}\frac{\nabla
f(x)(F(y)-F(x))}{F(x)F(y)}+\frac{\nabla f(x)-\nabla f(y)}{F(y)}\bigg{\|}$
$\displaystyle\leq\frac{G_{\infty}}{2(F(\theta^{*}))^{2}}|F(y)-F(x)|+\frac{1}{2F(\theta^{*})}\|\nabla
f(x)-\nabla f(y)\|.$

One may check that

$\lvert F(y)-F(x)\rvert\leq\frac{G_{\infty}}{2F(\theta^{*})}\|x-y\|.$

These together with the $L$-smoothness of $f$ lead to

$\|\nabla F(x)-\nabla F(y)\|\leq L_{F}\|x-y\|,$

where

$L_{F}=\frac{1}{2\sqrt{f(\theta^{*})+c}}\left(L+\frac{G^{2}_{\infty}}{2(f(\theta^{*})+c)}\right).$

This confirms the $L_{F}$-smoothness of $F$, which yields

$\displaystyle F(\theta_{t+1})-F(\theta_{t})$ $\displaystyle\leq\nabla
F(\theta_{t})^{\top}(\theta_{t+1}-\theta_{t})+\frac{L_{F}}{2}\|\theta_{t+1}-\theta_{t}\|^{2}$
$\displaystyle=(\nabla
F(\theta_{t})-\frac{g_{t}}{2\tilde{F}_{t}})^{\top}(\theta_{t+1}-\theta_{t})+(\frac{g_{t}}{2\tilde{F}_{t}}-\frac{1-\beta^{t}}{1-\beta}v_{t})^{\top}(\theta_{t+1}-\theta_{t})$
$\displaystyle\quad+(\frac{1-\beta^{t}}{1-\beta}v_{t})^{\top}(\theta_{t+1}-\theta_{t})+\frac{L_{F}}{2}\|\theta_{t+1}-\theta_{t}\|^{2}.$

Summation of the above over $t$ from $1$ to $T$ and taken with the expectation
gives

(1.4) $\mathbb{E}[F(\theta_{T+1})-F(\theta_{1})]\leq\sum_{i=1}^{4}S_{i},$

where

$\displaystyle
S_{1}=\mathbb{E}\Bigg{[}\sum_{t=1}^{T}\frac{1-\beta^{t}}{1-\beta}v_{t}^{\top}(\theta_{t+1}-\theta_{t})\Bigg{]},$
$\displaystyle
S_{2}=\mathbb{E}\Bigg{[}\sum_{t=1}^{T}(\frac{g_{t}}{2\tilde{F}_{t}}-\frac{1-\beta^{t}}{1-\beta}v_{t})^{\top}(\theta_{t+1}-\theta_{t})\Bigg{]},$
$\displaystyle S_{3}=\mathbb{E}\Bigg{[}\sum_{t=1}^{T}(\nabla
F(\theta_{t})-\frac{g_{t}}{2\tilde{F}_{t}})^{\top}(\theta_{t+1}-\theta_{t})\Bigg{]},$
$\displaystyle
S_{4}=\mathbb{E}\Bigg{[}\sum_{t=1}^{T}\frac{L_{F}}{2}\|\theta_{t+1}-\theta_{t}\|^{2}\Bigg{]}.$

Below we bound $S_{1},S_{2},S_{3},S_{4}$ separately. To bound $S_{1}$, we
first note that

$\displaystyle r_{t+1,i}-r_{t,i}$ $\displaystyle=-2\eta
r_{t+1,i}v^{2}_{t,i}=v_{t,i}(-2\eta
r_{t+1,i}v_{t,i})=v_{t,i}(\theta_{t+1,i}-\theta_{i})$

from which we get

$\displaystyle S_{1}$
$\displaystyle=\mathbb{E}\Bigg{[}\sum_{t=1}^{T}\frac{1-\beta^{t}}{1-\beta}v_{t}^{\top}(\theta_{t+1}-\theta_{t})\Bigg{]}$
$\displaystyle=\mathbb{E}\Bigg{[}\sum_{i=1}^{n}\sum_{t=1}^{T}\frac{1-\beta^{t}}{1-\beta}(r_{t+1,i}-r_{t,i})\Bigg{]}$
$\displaystyle\leq\mathbb{E}\Bigg{[}\sum_{i=1}^{n}\sum_{t=1}^{T}r_{t+1,i}-r_{t,i}\Bigg{]}\quad\text{(Since
$r_{t+1,i}\leq r_{t,i}$)}$
$\displaystyle=\sum_{i=1}^{n}\mathbb{E}[r_{T+1,i}]-n\mathbb{E}[\tilde{F}_{1}].$

For $S_{2}$, we have

$\displaystyle S_{2}$
$\displaystyle=\mathbb{E}\Bigg{[}\sum_{t=1}^{T}(\frac{g_{t}}{2\tilde{F}_{t}}-\frac{1-\beta^{t}}{1-\beta}v_{t})^{\top}(\theta_{t+1}-\theta_{t})\Bigg{]}$
$\displaystyle=\mathbb{E}\Bigg{[}\sum_{i=1}^{n}\sum_{t=1}^{T}(-\frac{1}{2\tilde{F}_{t}}\frac{\beta}{1-\beta}m_{t-1,i})^{\top}(-2\eta
r_{t+1,i}v_{t,i})\Bigg{]}$
$\displaystyle\leq\frac{\beta\eta}{(1-\beta)\sqrt{a}}\mathbb{E}\Bigg{[}\left\lvert\sum_{i=1}^{n}\sum_{t=1}^{T}r_{t+1,i}m_{t-1,i}v_{t,i}\right\rvert\Bigg{]}$
$\displaystyle\leq\frac{\beta\eta}{(1-\beta)\sqrt{a}}\mathbb{E}\Bigg{[}\bigg{(}\sum_{i=1}^{n}\sum_{t=1}^{T}r_{t+1,i}m^{2}_{t-1,i}\bigg{)}^{1/2}\bigg{(}\sum_{i=1}^{n}\sum_{t=1}^{T}r_{t+1,i}v^{2}_{t,i}\bigg{)}^{1/2}\Bigg{]}$
$\displaystyle\leq\frac{\beta\sqrt{B}nF(\theta_{1})}{(1-\beta)\sqrt{a}},$

where the fourth inequality is by the Cauchy-Schwarz inequality, the last
inequality is by Lemma 1 (i) (ii).

For $S_{3}$, by the Cauchy-Schwarz inequality, we have

$\displaystyle S_{3}$ $\displaystyle=\mathbb{E}\Bigg{[}\sum_{t=1}^{T}(\nabla
F(\theta_{t})-\frac{g_{t}}{2\tilde{F}_{t}})^{\top}(\theta_{t+1}-\theta_{t})\Bigg{]}$
$\displaystyle\leq\mathbb{E}\Bigg{[}\sum_{t=1}^{T}\|\nabla
F(\theta_{t})-\frac{g_{t}}{2\tilde{F}_{t}})\|\|\theta_{t+1}-\theta_{t})\|\Bigg{]}$
$\displaystyle\leq\mathbb{E}\Bigg{[}\bigg{(}\sum_{t=1}^{T}\|\nabla
F(\theta_{t})-\frac{g_{t}}{2\tilde{F}_{t}})\|^{2}\bigg{)}^{1/2}\bigg{(}\sum_{t=1}^{T}\|\theta_{t+1}-\theta_{t}\|^{2}\bigg{)}^{1/2}\Bigg{]}$
$\displaystyle\leq\Bigg{(}\mathbb{E}\Bigg{[}\sum_{t=1}^{T}\|\nabla
F(\theta_{t})-\frac{g_{t}}{2\tilde{F}_{t}})\|^{2}\Bigg{]}\Bigg{)}^{1/2}\Bigg{(}\mathbb{E}\Bigg{[}\sum_{t=1}^{T}\|\theta_{t+1}-\theta_{t}\|^{2}\Bigg{]}\Bigg{)}^{1/2}$
$\displaystyle\leq F(\theta_{1})\sqrt{\eta
nT}\sqrt{\frac{G^{2}_{\infty}}{8a^{3}}\sigma^{2}_{f}+\frac{1}{2a}\sigma^{2}_{g}},$

where the last inequality is by (vi) in Lemma 1 and (4.2) in Theorem 1.

For $S_{4}$, also by (4.2) in Theorem 1, we have

$\displaystyle
S_{4}=\frac{L_{F}}{2}\mathbb{E}\Bigg{[}\sum_{t=1}^{T}\|\theta_{t+1}-\theta_{t}\|^{2}\Bigg{]}\leq\frac{L_{F}\eta
nF^{2}(\theta_{1})}{2}.$

With the above bounds on $S_{1},S_{2},S_{3},S_{4}$, (1.4) can be rearranged as

$\displaystyle\quad
F(\theta^{*})-\frac{\beta\sqrt{B}nF(\theta_{1})}{(1-\beta)\sqrt{a}}-F(\theta_{1})\sqrt{\eta
nT}\sqrt{\frac{G^{2}_{\infty}}{4a^{3}}\sigma^{2}_{f}+\frac{1}{a}\sigma^{2}_{g}}-\frac{L_{F}\eta
nF^{2}(\theta_{1})}{2}$
$\displaystyle\leq\sum_{i=1}^{n}\mathbb{E}[r_{T+1,i}]-n\mathbb{E}[\tilde{F}_{1}]+F(\theta_{1})$
$\displaystyle\leq\Big{(}\min_{i}\mathbb{E}[r_{T+1,i}]+(n-1)\mathbb{E}[\tilde{F}_{1}]\Big{)}-(n-1)\mathbb{E}[\tilde{F}_{1}]+\Big{(}F(\theta_{1})-\mathbb{E}[\tilde{F}_{1}]\Big{)}$
$\displaystyle\leq\min_{i}\mathbb{E}[r_{T+1,i}]+\mathbb{E}[\lvert
F(\theta_{1})-\tilde{F}_{1}\rvert]$
$\displaystyle\leq\min_{i}\mathbb{E}[r_{T+1,i}]+\frac{1}{2\sqrt{a}}\sigma_{f},$

where (iii) in Lemma 1 was used. Hence,

$\min_{i}\mathbb{E}[r_{T,i}]\geq\max\\{F(\theta^{*})-\eta D_{1}-\beta
D_{2}-\sigma D_{3},0\\},$

where $\sigma=\max\\{\sigma_{f},\sigma_{g}\\}$ and

$\displaystyle D_{1}=\frac{L_{F}nF^{2}(\theta_{1})}{2},\quad
D_{2}=\frac{\sqrt{B}nF(\theta_{1})}{(1-\beta)\sqrt{a}},$ $\displaystyle
D_{3}=\frac{1}{2\sqrt{a}}+F(\theta_{1})\sqrt{\eta
nT}\sqrt{\frac{G^{2}_{\infty}}{4a^{3}}+\frac{1}{a}}.$

In the case $\sigma=0$, we obtain the stated estimate in Theorem 2.

##  Appendix B Proof of Theorem 3

The upper bound on $\sigma_{g}$ is given by (iv) in Lemma 1. Since $f$ is
$L$-smooth, we have

(2.1) $\displaystyle f(\theta_{t+1})\leq f(\theta_{t})+\nabla
f(\theta_{t})^{\top}(\theta_{t+1}-\theta_{t})+\frac{L}{2}\|\theta_{t+1}-\theta_{t}\|^{2}.$

Denoting $\eta_{t}=\eta/\tilde{F}_{t}$, the second term in the RHS of (2.1)
can be expressed as

$\displaystyle\quad\nabla f(\theta_{t})^{\top}(\theta_{t+1}-\theta_{t})$
$\displaystyle=\nabla f(\theta_{t})^{\top}(-2\eta r_{t+1}v_{t})$
$\displaystyle=-\frac{1}{1-\beta^{t}}\nabla
f(\theta_{t})^{\top}\eta_{t}r_{t+1}m_{t}\quad\text{(since$\;m_{t}=2(1-\beta^{t})\tilde{F}_{t}v_{t}$)}$
(2.2) $\displaystyle=-\frac{1}{1-\beta^{t}}\nabla
f(\theta_{t})^{\top}\eta_{t}r_{t+1}(\beta m_{t-1}+(1-\beta)g_{t})$
$\displaystyle=-\frac{1-\beta}{1-\beta^{t}}\nabla
f(\theta_{t})^{\top}\eta_{t}r_{t+1}g_{t}-\frac{\beta}{1-\beta^{t}}\nabla
f(\theta_{t})^{\top}\eta_{t}r_{t+1}m_{t-1}$
$\displaystyle=-\frac{1-\beta}{1-\beta^{t}}\nabla
f(\theta_{t})^{\top}\eta_{t-1}r_{t}g_{t}+\frac{1-\beta}{1-\beta^{t}}\nabla
f(\theta_{t})^{\top}(\eta_{t-1}r_{t}-\eta_{t}r_{t+1})g_{t}$
$\displaystyle\quad-\frac{\beta}{1-\beta^{t}}\nabla
f(\theta_{t})^{\top}\eta_{t}r_{t+1}m_{t-1}.$

We further bound the second term and third term in the RHS of (2.2),
respectively. For the second term, we note that
$\lvert\frac{1-\beta}{1-\beta^{t}}\rvert\leq 1$ and

$\displaystyle\quad\lvert\nabla
f(\theta_{t})^{\top}(\eta_{t-1}r_{t}-\eta_{t}r_{t+1})g_{t}\rvert$
$\displaystyle=\lvert\nabla
f(\theta_{t})^{\top}\eta_{t-1}(r_{t}-r_{t+1})g_{t}+\nabla
f(\theta_{t})^{\top}(\eta_{t-1}-\eta_{t})r_{t+1}g_{t}\rvert$
$\displaystyle=\lvert\nabla
f(\theta_{t})^{\top}\eta_{t-1}(r_{t}-r_{t+1})g_{t}+(\eta_{t-1}-\eta_{t})g_{t}^{\top}r_{t+1}g_{t}$
$\displaystyle\quad+(\eta_{t-1}-\eta_{t})(\nabla
f(\theta_{t})-g_{t})^{\top}r_{t+1}g_{t}\rvert$ $\displaystyle\leq\|\nabla
f(\theta_{t})\|_{\infty}\lvert\eta_{t-1}\rvert\|r_{t}-r_{t+1}\|_{1,1}\|g_{t}\|_{\infty}+\lvert\eta_{t-1}-\eta_{t}\rvert
g_{t}^{\top}r_{t+1}g_{t}$
$\displaystyle\quad+\lvert\eta_{t-1}-\eta_{t}\rvert\lvert(\nabla
f(\theta_{t})-g_{t})^{\top}r_{t+1}g_{t}\rvert$ $\displaystyle\leq(\eta
G^{2}_{\infty}/\sqrt{a})(\|r_{t}\|_{1,1}-\|r_{t+1}\|_{1,1})+(2\eta/\sqrt{a})g_{t}^{\top}r_{t+1}g_{t}$
(2.3) $\displaystyle\quad+(2\eta/\sqrt{a})\lvert(\nabla
f(\theta_{t})-g_{t})^{\top}r_{t+1}g_{t}\rvert.$

The third inequality holds because for a positive diagonal matrix $A$,
$x^{\top}Ay\leq\|x\|_{\infty}\|A\|_{1,1}\|y\|_{\infty}$, where
$\|A\|_{1,1}=\sum_{i}a_{ii}$. The last inequality follows from the result
$r_{t+1,i}\leq r_{t,i}$ for $i\in[n]$, the assumption $\|g_{t}\|_{\infty}\leq
G_{\infty}$, $\tilde{F}_{t}\geq\sqrt{a}$, and (i) in Lemma (1).

For the third term in the RHS of (2.2), we note that

$-\frac{\beta}{1-\beta^{t}}\nabla
f(\theta_{t})^{\top}\eta_{t}r_{t+1}m_{t-1}\leq\frac{\beta\eta}{(1-\beta)\sqrt{a}}\lvert\nabla
f(\theta_{t})^{\top}\eta_{t}r_{t+1}m_{t-1}\rvert,$

in which

$\displaystyle\quad\lvert\nabla f(\theta_{t})^{\top}r_{t+1}m_{t-1}\rvert$
$\displaystyle=\lvert g_{t}^{\top}r_{t+1}m_{t-1}+(\nabla
f(\theta_{t})-g_{t})^{\top}r_{t+1}m_{t-1}\rvert$ (2.4)
$\displaystyle\leq\frac{1}{2}g_{t}^{\top}r_{t+1}g_{t}+\frac{1}{2}m_{t-1}^{\top}r_{t+1}m_{t-1}+\lvert(\nabla
f(\theta_{t})-g_{t})^{\top}r_{t+1}m_{t-1}\rvert,$

where the last inequality is because for a positive diagonal matrix $A$,
$x^{\top}Ay\leq\frac{1}{2}x^{\top}Ax+\frac{1}{2}y^{\top}Ay$. Substituting
(2.3) and (2.4) into (2.2), we get

(2.5) $\displaystyle\nabla f(\theta_{t})^{\top}$
$\displaystyle(\theta_{t+1}-\theta_{t})\leq-\frac{1-\beta}{1-\beta^{t}}\nabla
f(\theta_{t})^{\top}\eta_{t-1}r_{t}g_{t}+\frac{\eta
G^{2}_{\infty}}{\sqrt{a}}(\|r_{t}\|_{1,1}-\|r_{t+1}\|_{1,1})$
$\displaystyle+\bigg{(}\frac{2\eta}{\sqrt{a}}+\frac{\beta\eta}{2(1-\beta)\sqrt{a}}\bigg{)}g_{t}^{\top}r_{t+1}g_{t}+\frac{\beta\eta}{2(1-\beta)\sqrt{a}}m_{t-1}^{\top}r_{t+1}m_{t-1}$
$\displaystyle+\frac{2\eta}{\sqrt{a}}\lvert(\nabla
f(\theta_{t})-g_{t})^{\top}r_{t+1}g_{t}\rvert+\frac{\beta\eta}{(1-\beta)\sqrt{a}}\lvert(\nabla
f(\theta_{t})-g_{t})^{\top}r_{t+1}m_{t-1}\rvert.$

With (2.5), we take an conditional expectation on (2.1) with respect to
$(\theta)$ and rearrange to get

(2.6) $\displaystyle\quad\frac{1-\beta}{1-\beta^{t}}\nabla
f(\theta_{t})^{\top}\eta_{t-1}r_{t}\nabla
f(\theta_{t})=\mathbb{E}_{\xi_{t}}\bigg{[}\frac{1-\beta}{1-\beta^{t}}\nabla
f(\theta_{t})^{\top}\eta_{t-1}r_{t}g_{t}\bigg{]}$
$\displaystyle\leq\mathbb{E}_{\xi_{t}}\Bigg{[}f(\theta_{t})-f(\theta_{t+1})+\frac{\eta
G^{2}_{\infty}}{\sqrt{a}}(\|r_{t}\|_{1,1}-\|r_{t+1}\|_{1,1})$
$\displaystyle\quad\quad+\bigg{(}\frac{2\eta}{\sqrt{a}}+\frac{\beta\eta}{2(1-\beta)\sqrt{a}}\bigg{)}g_{t}^{\top}r_{t+1}g_{t}+\frac{\beta\eta}{2(1-\beta)\sqrt{a}}m_{t-1}^{\top}r_{t+1}m_{t-1}$
$\displaystyle\quad\quad+\frac{2\eta}{\sqrt{a}}\lvert(\nabla
f(\theta_{t})-g_{t})^{\top}r_{t+1}g_{t}\rvert$
$\displaystyle\quad\quad+\frac{\beta\eta}{(1-\beta)\sqrt{a}}\lvert(\nabla
f(\theta_{t})-g_{t})^{\top}r_{t+1}m_{t-1}\rvert+\frac{L}{2}\|\theta_{t+1}-\theta_{t}\|^{2}\Bigg{]},$

where the assumption $\mathbb{E}_{\xi_{t}}[g_{t}]=\nabla f(\theta_{t})$ is
used in the first equality. Since $\xi_{1},...,\xi_{t}$ are independent random
variables, we set
$\mathbb{E}=\mathbb{E}_{\xi_{1}}\mathbb{E}_{\xi_{2}}...\mathbb{E}_{\xi_{T}}$
and take a summation on (2.6) over $t$ from 1 to $T$ to get

(2.7)
$\displaystyle\quad\mathbb{E}\Bigg{[}\sum_{t=1}^{T}\frac{1-\beta}{1-\beta^{t}}\nabla
f(\theta_{t})^{\top}\eta_{t-1}r_{t}\nabla f(\theta_{t})\Bigg{]}$
$\displaystyle\leq\mathbb{E}\Big{[}f(\theta_{1})-f(\theta_{T+1})\Big{]}+\frac{\eta
G^{2}_{\infty}}{\sqrt{a}}\mathbb{E}\Big{[}\|r_{1}\|_{1,1}-\|r_{T+1}\|_{1,1}\Big{]}$
$\displaystyle\quad+\bigg{(}\frac{2\eta}{\sqrt{a}}+\frac{\beta\eta}{2(1-\beta)\sqrt{a}}\bigg{)}\mathbb{E}\Bigg{[}\sum_{t=1}^{T}g_{t}^{\top}r_{t+1}g_{t}\Bigg{]}+\frac{\beta\eta}{2(1-\beta)\sqrt{a}}\mathbb{E}\Bigg{[}\sum_{t=1}^{T}m_{t-1}^{\top}r_{t}m_{t-1}\Bigg{]}$
$\displaystyle\quad+\frac{2\eta}{\sqrt{a}}\mathbb{E}\Bigg{[}\sum_{t=1}^{T}\lvert(\nabla
f(\theta_{t})-g_{t})^{\top}r_{t+1}g_{t}\rvert\Bigg{]}$
$\displaystyle\quad+\frac{\beta\eta}{(1-\beta)\sqrt{a}}\mathbb{E}\Bigg{[}\sum_{t=1}^{T}\lvert(\nabla
f(\theta_{t})-g_{t})^{\top}r_{t+1}m_{t-1}\rvert\Bigg{]}+\frac{L}{2}\mathbb{E}\Bigg{[}\sum_{t=1}^{T}\|\theta_{t+1}-\theta_{t}\|^{2}\Bigg{]}.$

Below we bound each term in (2.7) separately. By the Cauchy-Schwarz
inequality, we get

$\displaystyle\quad\mathbb{E}\Bigg{[}\sum_{t=1}^{T}\lvert(\nabla
f(\theta_{t})-g_{t})^{\top}r_{t+1}m_{t-1}\rvert\Bigg{]}$
$\displaystyle\leq\mathbb{E}\Bigg{[}\sum_{t=1}^{T}\|\nabla
f(\theta_{t})-g_{t}\|\|r_{t+1}m_{t-1}\|\Bigg{]}$
$\displaystyle\leq\mathbb{E}\Bigg{[}\bigg{(}\sum_{t=1}^{T}\|\nabla
f(\theta_{t})-g_{t}\|^{2}\bigg{)}^{1/2}\bigg{(}\sum_{t=1}^{T}\|r_{t+1}m_{t-1}\|^{2}\bigg{)}^{1/2}\Bigg{]}$
$\displaystyle\leq\Bigg{(}\mathbb{E}\Bigg{[}\sum_{t=1}^{T}\|\nabla
f(\theta_{t})-g_{t}\|^{2}\Bigg{]}\Bigg{)}^{1/2}\Bigg{(}\mathbb{E}\Bigg{[}\sum_{t=1}^{T}\|r_{t+1}m_{t-1}\|^{2}\Bigg{]}\Bigg{)}^{1/2}$
(2.8) $\displaystyle\leq\sqrt{2BnT/\eta}F(\theta_{1})\sigma_{g},$

where Lemma 1 (ii) and the bounded variance assumption were used. We replace
$m_{t-1}$ in (2.8) by $g_{t}$ and use Lemma 1 (v) to get

$\displaystyle\quad\mathbb{E}\Bigg{[}\sum_{t=1}^{T}\lvert(\nabla
f(\theta_{t})-g_{t})^{\top}r_{t+1}g_{t}\rvert\Bigg{]}$
$\displaystyle\leq\Bigg{(}\mathbb{E}\Bigg{[}\sum_{t=1}^{T}\|\nabla
f(\theta_{t})-g_{t}\|^{2}\Bigg{]}\Bigg{)}^{1/2}\Bigg{(}\mathbb{E}\Bigg{[}\sum_{t=1}^{T}\|r_{t+1}g_{t}\|^{2}\Bigg{]}\Bigg{)}^{1/2}$
(2.9)
$\displaystyle\leq\frac{2\sqrt{2BnT/\eta}F(\theta_{1})\sigma_{g}}{1-\beta}.$

By (4.2), the last term in (2.7) is bounded above by

(2.10)
$\frac{L}{2}\mathbb{E}\left[\sum_{t=0}^{\infty}\|\theta_{t+1}-\theta_{t}\|^{2}\right]\leq\frac{L\eta
n}{2}F^{2}(\theta_{1}).$

Substituting Lemma 1 (i) (iii), (2.10), (2.9), (2.8) into (2.7) to get

(2.11)
$\displaystyle\mathbb{E}\Bigg{[}\sum_{t=1}^{T}\frac{1-\beta}{1-\beta^{t}}$
$\displaystyle\nabla f(\theta_{t})^{\top}\eta_{t-1}r_{t}\nabla
f(\theta_{t})\Bigg{]}\leq(f(\theta_{1})-f^{*})+\frac{\eta
G^{2}_{\infty}}{\sqrt{a}}nF(\theta_{1})$
$\displaystyle+\bigg{(}\frac{2}{\sqrt{a}}+\frac{\beta}{2(1-\beta)\sqrt{a}}\bigg{)}\frac{8BnF(\theta_{1})}{(1-\beta)^{2}}+\frac{\beta
BnF(\theta_{1})}{(1-\beta)\sqrt{a}}$
$\displaystyle+\frac{(4+\beta)\sqrt{2B\eta}}{(1-\beta)\sqrt{a}}F(\theta_{1})\sqrt{nT}\sigma_{g}+\frac{L\eta
n}{2}F^{2}(\theta_{1}).$

Note that the left hand side is bounded from below by

$(1-\beta)\frac{\eta}{\sqrt{B}}\mathbb{E}\Bigg{[}\min_{i}r_{T,i}\sum_{t=1}^{T}\|\nabla
f(\theta_{t})\|^{2}\Bigg{]},$

where we used $\lvert\frac{1-\beta}{1-\beta^{t}}\rvert\geq 1-\beta$ and
$\eta_{t}\geq\eta/\sqrt{B}$. Thus we have

(2.12) $\displaystyle\mathbb{E}\Bigg{[}\min_{i}r_{T,i}\sum_{t=1}^{T}\|\nabla
f(\theta_{t})\|^{2}\Bigg{]}\leq\frac{C_{1}+C_{2}n+C_{3}\sigma_{g}\sqrt{nT}}{\eta},$

where

$\displaystyle C_{1}$
$\displaystyle=\frac{(f(\theta_{1})-f^{*})\sqrt{B}}{1-\beta},$ $\displaystyle
C_{2}$ $\displaystyle=\frac{\sqrt{B}\eta
G^{2}_{\infty}F(\theta_{1})}{(1-\beta)\sqrt{a}}+\bigg{(}\frac{2}{\sqrt{a}}+\frac{\beta}{2(1-\beta)\sqrt{a}}\bigg{)}\frac{8B^{3/2}F(\theta_{1})}{(1-\beta)^{3}}$
$\displaystyle\quad+\frac{\beta
B^{3/2}F(\theta_{1})}{(1-\beta)^{2}\sqrt{a}}+\frac{\sqrt{B}L\eta}{2(1-\beta)^{2}}F^{2}(\theta_{1}),$
$\displaystyle C_{3}$
$\displaystyle=\frac{(4+\beta)B\sqrt{2\eta}}{(1-\beta)\sqrt{a}}F(\theta_{1}).$

By the Hölder inequality, we have for any $\alpha\in(0,1)$,

$\mathbb{E}[X^{\alpha}]\leq\mathbb{E}[XY]^{\alpha}\mathbb{E}[Y^{-\alpha/(1-\alpha)}]^{1-\alpha}.$

Take $X=\Delta:=\sum_{t=1}^{T}\|\nabla f(\theta_{t})\|^{2},Y=\min_{i}r_{T,i}$,
we obtain

$\mathbb{E}[\Delta^{\alpha}]\leq\mathbb{E}[\min_{i}r_{T,i}\Delta]^{\alpha}\mathbb{E}[(\min_{i}r_{T,i})^{-\alpha/(1-\alpha)}]^{1-\alpha}.$

Using (2.12), and lower bounding $\mathbb{E}[\Delta^{\alpha}]$ by
$T^{\alpha}\mathbb{E}[\min_{1\leq t\leq T}\|\nabla
f(\theta_{t})\|^{2\alpha}]$, we obtain

$\mathbb{E}\Bigg{[}\min_{1\leq t\leq T}\|\nabla
f(\theta_{t})\|^{2\alpha}\Bigg{]}\leq\left(\frac{C_{1}+C_{2}n+C_{3}\sigma_{g}\sqrt{nT}}{\eta
T}\right)^{\alpha}\mathbb{E}[(\min_{i}r_{T,i})^{-\alpha/(1-\alpha)}]^{1-\alpha}.$

This by taking $\alpha=1-\epsilon$ yields the stated bound.

##  Appendix C Proof of Theorem 4

Using the same argument as for (iv) in Lemma 2, we have

$\sum_{i=1}^{n}\sum_{t=1}^{T}r_{t+1,i}g^{2}_{t,i}\leq\frac{8Bn\sqrt{f_{1}(\theta_{1})+c}}{(1-\beta)^{2}\eta}.$

With this estimate and the convexity of $f_{t}$, the regret can be bounded by

$\displaystyle R(T)$
$\displaystyle=\sum_{t=1}^{T}f_{t}(\theta_{t})-f_{t}(\theta^{*})\leq\sum_{t=1}^{T}g_{t}^{\top}(\theta_{t}-\theta^{*})$
$\displaystyle\leq\sum_{i=1}^{n}\sum_{t=1}^{T}\lvert
g_{t,i}\rvert\sqrt{r_{t+1,i}}\frac{\lvert\theta_{t,i}-\theta^{*}_{i}\rvert}{\sqrt{r_{t+1,i}}}$
$\displaystyle\leq\left(\sum_{i=1}^{n}\sum_{t=1}^{T}r_{t+1,i}g_{t,i}^{2}\right)^{1/2}\left(\sum_{i=1}^{n}\sum_{t=1}^{T}\frac{\lvert\theta_{t,i}-\theta^{*}_{i}\rvert^{2}}{r_{t+1,i}}\right)^{1/2}$
$\displaystyle\leq\frac{2D_{\infty}\sqrt{2B}}{1-\beta}(f_{1}(\theta_{1})+c)^{1/4}\sqrt{nT/\eta}\left(\sum_{i=1}^{n}\frac{1}{r_{T+1,i}}\right)^{1/2},$

where the fourth inequality is by the Cauchy-Schwarz inequality, and the
assumption $\|x-y\|_{\infty}\leq D_{\infty}$ for all $x,y\in\mathcal{F}$ is
used in the last inequality.

## References

  * [1] Zeyuan Allen-Zhu, _Katyusha: The first direct acceleration of stochastic gradient methods_ , Journal of Machine Learning Research 18 (2018), no. 221, 1–51.
  * [2] Leon Bottou, _Stochastic gradient descent tricks_ , neural networks, tricks of the trade, reloaded ed., Lecture Notes in Computer Science (LNCS), vol. 7700, Springer, January 2012.
  * [3] Léon Bottou, Frank E. Curtis, and Jorge Nocedal, _Optimization methods for large-scale machine learning_ , SIAM Rev. 60 (2018), no. 2, 223–311.
  * [4] Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong, _On the convergence of a class of Adam-type algorithms for non-convex optimization_ , International Conference on Learning Representations, 2019.
  * [5] Aaron Defazio, Francis Bach, and Simon Lacoste-Julien, _SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives_ , Advances in Neural Information Processing Systems, vol. 27, 2014\.
  * [6] John Duchi, Elad Hazan, and Yoram Singer, _Adaptive subgradient methods for online learning and stochastic optimization_ , Journal of Machine Learning Research 12 (2011), 2121–2159.
  * [7] Ian Goodfellow, Yoshua Bengio, and Aaron Courville, _Deep learning_ , MIT Press, 2016.
  * [8] Elad Hazan, _Introduction to online convex optimization_ , arXiv abs/1909.05207 (2019).
  * [9] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun, _Deep residual learning for image recognition_ , 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016, pp. 770–778.
  * [10] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q. Weinberger, _Densely connected convolutional networks_ , 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017, pp. 2261–2269.
  * [11] Chi Jin, Praneeth Netrapalli, and Michael I. Jordan, _Accelerated gradient descent escapes saddle points faster than gradient descent_ , Proceedings of the 31st Conference On Learning Theory, vol. 75, 2018, pp. 1042–1085.
  * [12] Rie Johnson and Tong Zhang, _Accelerating stochastic gradient descent using predictive variance reduction_ , Advances in Neural Information Processing Systems, vol. 26, 2013.
  * [13] Diederik P. Kingma and Jimmy Ba, _Adam: A method for stochastic optimization_ , arXiv abs/1412.6980 (2017).
  * [14] Alex Krizhevsky and Geoffrey Hinton, _Learning multiple layers of features from tiny images_ , University of Toronto (2009).
  * [15] Yann LeCun, Y. Bengio, and Geoffrey Hinton, _Deep learning_ , Nature 521 (2015), 436–44.
  * [16] Lihua Lei, Cheng Ju, Jianbo Chen, and Michael I Jordan, _Non-convex finite-sum optimization via SCSG methods_ , Advances in Neural Information Processing Systems, vol. 30, 2017.
  * [17] Xiaoyu Li and Francesco Orabona, _On the convergence of stochastic gradient descent with adaptive stepsizes_ , Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, vol. 89, 2019, pp. 983–992.
  * [18] Hailiang Liu and Xuping Tian, _AEGD: Adaptive gradient decent with energy_ , arXiv abs/2010.05109 (2020).
  * [19] Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han, _On the variance of the adaptive learning rate and beyond_ , International Conference on Learning Representations, 2020.
  * [20] Yanli Liu, Yuan Gao, and Wotao Yin, _An improved analysis of stochastic gradient descent with momentum_ , NeurIPS, 2020.
  * [21] Liangchen Luo, Yuanhao Xiong, and Yan Liu, _Adaptive gradient methods with dynamic bound of learning rate_ , International Conference on Learning Representations, 2019.
  * [22] Stanley Osher, Bao Wang, Penghang Yin, Xiyang Luo, Farzin Barekat, Minh Pham, and Alex Lin, _Laplacian smoothing gradient descent_ , arXiv abs/1806.06317 (2019).
  * [23] B. T. Polyak, _Some methods of speeding up the convergence of iterative methods_ , Ž. Vyčisl. Mat i Mat. Fiz. 4 (1964), 791–803.
  * [24] Ning Qian, _On the momentum term in gradient descent learning algorithms_ , Neural Networks 12 (1999), no. 1, 145–151.
  * [25] Sashank Reddi, Satyen Kale, and Sanjiv Kumar, _On the convergence of Adam and beyond_ , International Conference on Learning Representations, 2018\.
  * [26] Herbert Robbins and Sutton Monro, _A stochastic approximation method_ , Ann. Math. Statistics 22 (1951), 400–407.
  * [27] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei, _ImageNet Large Scale Visual Recognition Challenge_ , International Journal of Computer Vision (IJCV) 115 (2015), no. 3, 211–252.
  * [28] A. Shapiro and Y. Wardi, _Convergence analysis of gradient descent stochastic algorithms_ , J. Optim. Theory Appl. 91 (1996), no. 2, 439–454.
  * [29] K. Simonyan and Andrew Zisserman, _Very deep convolutional networks for large-scale image recognition_ , arXiv abs/1409.1556 (2015).
  * [30] Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton, _On the importance of initialization and momentum in deep learning_ , Proceedings of the 30th International Conference on Machine Learning, vol. 28, 2013, pp. 1139–1147.
  * [31] Tijmen Tieleman and Geoffrey Hinton, _RMSprop: Divide the gradient by a running average of its recent magnitude_ , COURSERA: Neural networks for machine learning 4(2) (2012), 26–31.
  * [32] Ashia C. Wilson, Rebecca Roelofs, Mitchell Stern, Nathan Srebro, and Benjamin Recht, _The marginal value of adaptive gradient methods in machine learning_ , arXiv abs/1705.08292 (2018).
  * [33] Yan Yan, Tianbao Yang, Zhe Li, Qihang Lin, and Yi Yang, _A unified analysis of stochastic momentum methods for deep learning_ , Proceedings of the 27th International Joint Conference on Artificial Intelligence, 2018, p. 2955–2961.
  * [34] Xiaofeng Yang, _Linear, first and second-order, unconditionally energy stable numerical schemes for the phase field model of homopolymer blends_ , Journal of Computational Physics 327 (2016), 294–316.
  * [35] Hao Yu, Rong Jin, and Sen Yang, _On the linear speedup analysis of communication efficient momentum SGD for distributed non-convex optimization_ , Proceedings of the 36th International Conference on Machine Learning, vol. 97, 2019, pp. 7184–7193.
  * [36] Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar, _Adaptive methods for nonconvex optimization_ , Advances in Neural Information Processing Systems (S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, eds.), vol. 31, Curran Associates, Inc., 2018.
  * [37] Jia Zhao, Qi Wang, and Xiaofeng Yang, _Numerical approximations for a phase field dendritic crystal growth model based on the invariant energy quadratization approach_ , International Journal for Numerical Methods in Engineering 110 (2017), 279–300.
  * [38] Juntang Zhuang, Tommy Tang, Yifan Ding, Sekhar C Tatikonda, Nicha Dvornek, Xenophon Papademetris, and James Duncan, _Adabelief optimizer: Adapting stepsizes by the belief in observed gradients_ , Advances in Neural Information Processing Systems, vol. 33, 2020, pp. 18795–18806.
  * [39] Martin Zinkevich, _Online convex programming and generalized infinitesimal gradient ascent_ , Proceedings of the Twentieth International Conference on International Conference on Machine Learning, ICML, 2003, p. 928–935.
  * [40] Fangyu Zou, Li Shen, Zequn Jie, Weizhong Zhang, and Wei Liu, _A sufficient condition for convergences of adam and rmsprop_ , 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) (2019), 11119–11127.