# Understanding Accelerated Stochastic Gradient Descent via the Growth
Condition

You-Lin Chen
Department of Statistics
University of Chicago
Chicago, IL 60615
<EMAIL_ADDRESS>
&Mladen Kolar
Booth School of Business
University of Chicago
Chicago, IL 60615
<EMAIL_ADDRESS>

###### Abstract

We study accelerated stochastic gradient descent through the lens of the
growth condition. Stochastic gradient methods (SGD) with momentum, such as
heavy ball (HB) and Nesterov’s accelerated methods (NAM), are widely used in
practice, especially for training neural networks. However, numerical
experiments and theoretical results have shown that there are simple problem
instances where SGD with momentum cannot outperform vanilla SGD. Furthermore,
most of the research on accelerated SGD consider restricted settings with
quadratic functions or assumption of additive noise with bounded variance. In
this work, we assume a growth condition that states the stochastic gradients
can be dominated by a multiplicative part and an additive part, where the
multiplicative part shrinks relative to the full gradient, while the additive
part is bounded. We provide insight into the behavior of acceleration in
stochastic settings under the growth condition by showing robustness, with
respect to a perturbation on gradients, of accelerated methods. Several
accelerated methods, including accelerated dual averaging methods and robust
momentum methods, are examined for the robust property. We illustrate how the
multiplicative noise affects the convergence rate of accelerated methods and
may cause convergence to fail. We establish a trade-off between robustness and
convergence rate, which shows that even though simple accelerated methods like
HB and NAM are optimal in the deterministic case, more sophisticated design of
algorithms leads to robustness in stochastic settings and achieves a better
convergence rate than vanilla SGD. Moreover, we provide unified optimal
schemes of averaging and diminishing momentum and stepsize, which achieves the
theoretical lower bound up to some constants.

##  1 Introduction

First-order stochastic methods are prominently used for optimization in
machine learning and for solving stochastic approximation problems due to
their scalability and extreme success in training neural networks. In a non-
stochastic setting, where gradient without noise can be accessed, the gradient
descent is suboptimal for the class of convex functions [48], and accelerated
methods, such as heavy ball (HB) [52] and Nesterov’s accelerated methods (NAM)
[49], are commonly applied as they achieve the optimal convergence rate.
Although the accelerated first-order methods are well-studied in past decades,
theoretical understanding of accelerated methods remains limited when used
with stochastic gradients.

Consider an unconstrained optimization problem in a stochastic setting:

$\min_{x\in\mathbb{R}^{d}}f(x),$ (1)

where $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is $L$-smooth and $m$-strongly
convex (see Section 1.2). Instead of having a direct access to the full
gradient $\nabla f(x)$, we query a noisy oracle that returns
$\widehat{\nabla}f(x)=\nabla f(x)+\varepsilon(x)$, where $x\in\mathbb{R}^{d}$
and $\varepsilon(x)$ is a perturbation that depends on the current iterate
$x$. Most existing works of vanilla SGD [53, 39, 58] and accelerated SGD [9,
8] are restricted to additive noise with a uniformly bounded variance,
$\mathbb{E}\|\varepsilon(x)\|^{2}\leq\sigma^{2}$ for some constant
$\sigma^{2}$. However, such an assumption is restrictive even in the least
squares regression problem

$\min_{x\in\mathbb{R}^{d}}f(x)=\frac{1}{2}\mathbb{E}_{a,b\sim\mathcal{D}}\left[(a^{\top}x-b)^{2}\right],$
(2)

where $a,b$ are sampled from a distribution $\mathcal{D}$. Let $x_{\star}$
denote the optimum, $\mathbb{E}aa^{\top}=\Sigma$. Then the noise
$\varepsilon(x)$ of a stochastic first-order oracle $\widehat{\nabla}f(x)$
with sample $a,b\sim\mathcal{D}$ is:

$\widehat{\nabla}f(x)-\nabla
f(x)=(aa^{\top}-\Sigma)(x-x_{\star})+a^{\top}(x_{\star}-a^{\top}b)-\mathbb{E}[a^{\top}(x_{\star}-a^{\top}b)].$
(3)

Therefore the uniform bound assumption is not satisfied in this example unless
$x$ is in a compact domain. A more general assumption on the noise
$\varepsilon$, which is satisfied by the least squares regression example, is
a growth condition [61, 55, 12, 65, 51, 59], which assumes that the stochastic
gradient can be dominated by a multiplicative part and an additive part, where
the multiplicative part shrinks relative to the full gradient, while the
additive part is bounded. The growth condition is the necessary and sufficient
condition for linear convergence of the stochastic gradient method for the
class of strongly convex functions with Lipschitz gradient [14].

We study the following fundamental questions: Can one obtain a similar
accelerated convergence rate as in a deterministic case and achieve the
minimax optimal statistical risk faster than vanilla SGD? To understand this
question, for the least square regression with additive noise that has
variance bounded by $\sigma^{2}$, [62] showed the minimax rate of convergence
is $\mathcal{O}(d\sigma^{2}/n)$, where $n$ is the sample size. This risk is
obtained by the empirical risk minimizer. Tail-averaged SGD [33] satisfies the
risk bound
$f(x_{n}^{\text{SGD}})-f(x_{\star})=\mathcal{O}\left(\exp(-nm/L)+\sigma^{2}d/n\right)$.
Thus, the question is if we can accelerate SGD and achieve

$f(x_{n})-f(x_{\star})=\mathcal{O}\left(\exp(-n\sqrt{m/L})+d\sigma^{2}/n\right).$
(4)

Unfortunately there is a negative example for the least square regression (See
Section 3.1) where SGD with the heavy ball cannot outperform vanilla SGD [37].
On the other hand, $\mathcal{O}\left(\exp(-n\sqrt{m/L})+\sigma^{2}d/n\right)$
can be achieved under some cases. For example, with extra moment conditions,
[34] introduces a stochastic algorithm and obtains the bound (4). [13, 8]
further established faster convergence rate for SGD with momentum under
bounded variance assumption, while [26] achieved accelerated rate of
convergence in the setting of constrained (bounded-diameter) minimization. In
this work, we unify these theoretical and empirical observations on
acceleration in SGD. A short answer to the fundamental question is that
acceleration in the stochastic setting is possible under the growth condition
introduced Section 3. However, not all methods can be accelerated. For
example, HB is not robust to the multiplicative noise, which is the key to
getting faster convergence rate.

Our contribution is threefold. First, we prove that several accelerated first-
order methods are robust to the multiplicative noise in Section 2. Second, we
discuss convergence bounds under the growth condition in Section 3. We show
that the multiplicative part affects the convergence rate and is one reason
why SGD cannot be accelerated. Finally, in Section 4, we provide optimal
schemes of averaging and diminishing momentum and stepsize, which achieve the
faster convergence bound (4) under the growth condition.

###  1.1 Additional Related Work

There is a large body of literature on accelerated gradient methods. [63] is
the work closest to ours, where convergence rate of accelerated SGD with
constant stepsize and diminishing momentum was studied. However, they do not
discuss how to eliminate the variance term and achieve optimal convergence
rate. Recently,[70] proposed a gradient averaging strategy with decreasing
stepsize, which can improve the convergence rate in probability. [35]
presented accelerated stochastic approximation methods using mini-batch with
multiplicative noise.

In least squares regression, [23, 18, 10] studied SGD with constant-step size,
and [20] extended the analysis to more general functions. [68, 38, 19] model
the trajectory of accelerated gradient methods using differential equations.
[41] used a control-theoretic stability framework to cast momentum schemes as
linear dynamical systems with feedback and characterize their convergence
rate. [32] extend the control-theoretic stability framework. [27] characterize
convergence properties of the quasi-hyperbolic momentum method [44] around the
minimizer for strongly-convex quadratic functions with bounded gradients and
bounded gradient noise variance.

###  1.2 Notation

We use $\|\cdot\|$ to denote the $\ell_{2}$ norm and $I_{d}$ and $0_{d}$ to
denote the $d\times d$ identity and zero matrices, respectively. We write
$A\otimes B$ for the Kronecker product of two matrices. Matrix inequalities
hold in the semidefinite sense. Throughout the paper we assume that $f$ in (1)
is twice differentiable, $L$-smooth, and $m$-strongly convex with respect to
$\|\cdot\|$, i.e. it holds that for all $x,y$

$\displaystyle f(y)\leq f(x)+\nabla f(x)^{T}(y-x)+\frac{L}{2}\|y-x\|^{2},\ \
f(y)\geq f(x)+\nabla f(x)^{T}(y-x)+\frac{m}{2}\|y-x\|^{2}.$

We will frequently use the several well known properties of convexity and
smoothness. See appendix A and [73, 48]. Let $\mathcal{F}(m,L)$ denote a class
of functions that are $m$-strongly convex and $L$-smooth and
$x_{\star}=\arg\min_{x}f(x)$ denote the unique optimum of (1). Given a convex
function $\phi(x)$, we define Bregman divergence
$\Delta_{\psi}(x,y)=\psi(x)-\psi(y)-\langle\nabla\psi(y),x-y\rangle$ and
convex conjugate $\psi^{\star}(z)=\max_{x}\left\\{z^{\top}x-\psi(x)\right\\}$.
See Appendix A for more useful properties. For two sequences of numbers
$\\{a_{n}\\}_{n=1}^{\infty}$ and $\\{b_{n}\\}_{n=1}^{\infty}$, we use
$a_{n}=\mathcal{O}(b_{n})$ to denote that $a_{n}\leq Cb_{n}$ and
$a_{n}=\Omega(b_{n})$ to denote that $a_{n}\geq Cb_{n}$ for some finite
positive constant $C$. $\widetilde{\mathcal{O}}(b_{n})$ is the same as
$\mathcal{O}(b_{n})$ but hides log factors.

##  2 Robustness to Multiplicative Noises

Given a filtration $\mathcal{G}_{k}$ containing all the past information up to
time $k$ and $\zeta\in\mathbb{R}^{d}$, the perturbation
$\varepsilon_{k+1}(\zeta)$ is a $\mathcal{G}_{k+1}$-measurable random field
with $\mathbb{E}[\varepsilon_{k+1}(\zeta)\mid\mathcal{G}_{k}]=0$. Moreover,
$\\{\varepsilon_{k}(\zeta)\\}_{k>0}$ are independent and identically
distributed. We will omit $\zeta$ and write
$\varepsilon_{k}(\zeta)=\varepsilon_{k}$ when it is clear from the context.
Consider an initial point $\xi_{0}\in\mathcal{G}_{0}$ and a linear dynamical
system for a first order method

$\xi_{k+1}=A\xi_{k}+B\omega_{k}(\zeta_{k}),\quad\zeta_{k}=C\xi_{k},$ (5)

where $\omega_{k}(\zeta_{k})=\nabla
f(\zeta_{k})+\varepsilon_{k+1}(\zeta_{k})$. The following example shows why
SGD converges under the growth condition and motivate us to define the general
concept.

######  Example 1.

Suppose that $f\in\mathcal{F}(m,L)$. The iterates of SGD are given as
$x_{k+1}=x_{k}-\eta_{k}\omega_{k}$, where $\omega_{k}=\nabla
f(x)+\varepsilon_{k+1}(x)$. Then by strong convexity, we have

$\displaystyle\mathbb{E}$
$\displaystyle\left[\|x_{k+1}-x_{\star}\|^{2}\mid\mathcal{G}_{k}\right]=\|x_{k}-x_{\star}\|^{2}-2\eta_{k}\nabla
f(x_{k})^{\top}(x_{k}-x_{\star})+\eta_{k}^{2}\mathbb{E}\left[\|\omega_{k}\|^{2}\mid\mathcal{G}_{k}\right]$
$\displaystyle\leq(1-m\eta_{k})\|x_{k}-x_{\star}\|^{2}-\frac{\eta_{k}}{m}\|\nabla
f(x_{k})\|^{2}+\eta_{k}^{2}\mathbb{E}\left[\|\nabla
f(x_{k})\|^{2}+\|\varepsilon_{k+1}\|^{2}\mid\mathcal{G}_{k}\right]$
$\displaystyle\leq(1-m\eta_{k})\|x_{k}-x_{\star}\|^{2}-\left(\frac{\eta_{k}}{m}-\eta_{k}^{2}\right)\|\nabla
f(x_{k})\|^{2}+\eta_{k}^{2}\mathbb{E}\left[\|\varepsilon_{k}\|^{2}\mid\mathcal{G}_{k}\right].$

By taking expectation on both sides and denoting
$\mathcal{E}_{k}=\|x_{k}-x_{\star}\|^{2}$ and
$(r_{k},m_{k},n_{k})=(m\eta_{k},\eta_{k}/m-\eta_{k}^{2},\eta_{k}^{2})$, we get

$\mathbb{E}\left[\mathcal{E}_{k+1}\right]\leq(1-r_{k})\mathbb{E}\left[\mathcal{E}_{k}\right]-m_{k}\mathbb{E}\|\nabla
f(x_{k})\|^{2}+n_{k}\mathbb{E}\|\varepsilon_{k+1}(x_{k})\|^{2}$ (6)

and $\eta_{k}/m-\eta_{k}^{2}>0,1-m\eta_{k}>0$ as long as $\eta_{k}<1/m$. If
$\mathbb{E}\|\varepsilon_{k+1}(\zeta_{k})\|^{2}\leq\mathbb{E}\|\nabla
f(x)\|^{2}$, it is clear now that the extra margin $m_{k}\mathbb{E}\|\nabla
f(\zeta_{k})\|^{2}$ cancels out the noise term
$n_{k}\mathbb{E}\|\varepsilon_{k+1}(\zeta_{k})\|^{2}$ by choosing a small
$\eta$, which leads to
$\mathbb{E}\left[\mathcal{E}_{k+1}\right]\leq(1-r_{k})\mathbb{E}\left[\mathcal{E}_{k}\right]$.

We will show that this recursion (6) can also be shown for some accelerated
methods. In fact, lacking a robust margin may be the reason causing
accelerated methods such as NAM and HB to fail. Moreover, (6) allows us to
study schemes of averaging and diminishing momentum and stepsize in a uniform
manner and showing optimal convergence rate. See Section 4. Motivated by
Example 1, we define the property of robustness of an algorithm, which is the
key concept throughout this paper.

######  Definition 1 (Property of Robustness).

We say an algorithm $\mathcal{A}$ following the dynamics (5) have a property
of robustness if there exist $\mathcal{G}_{k}$-measurable random variables
$\mathcal{E}_{k}$ and sequences $\\{r_{k},m_{k},n_{k}\\}_{k>0}$ such that
$0<r_{k}<1$, $m_{k},n_{k}>0$, $\mathbb{E}[\mathcal{E}_{k}]\geq 0$ and

$\mathbb{E}\left[\mathcal{E}_{k+1}\right]\leq(1-r_{k})\mathbb{E}\left[\mathcal{E}_{k}\right]-m_{k}\mathbb{E}\|\nabla
f(\zeta_{k})\|^{2}+n_{k}\mathbb{E}\|\varepsilon_{k+1}(\zeta_{k})\|^{2}.$ (7)

Here $\mathbb{E}\left[\mathcal{E}_{k+1}\right]$ measures progress of the
algorithm and can be interpreted as a general definition of the Lyapunov
function. The term $m_{k}\mathbb{E}\|\nabla f(\zeta_{k})\|^{2}$ can be
interpreted as an additional robustness margin, while ensuring the inequality
(7) holds. There is a trade off between robustness $m_{k}$ and convergence
rate $(1-r_{t})$: with a small $r_{k}$, the convergence rate $(1-r_{t})$ is
slower, but the robustness margin $m_{k}$ increases. We start by providing
concrete examples in the following sections.

###  2.1 Accelerated Dual Averaging Method

The iterates of accelerated dual averaging (ADA) method [19] are defined as
follows:

$\begin{split}x_{k}=\frac{A_{k-1}}{A_{k}}y_{k-1}+\frac{a_{k}}{A_{k}}\nabla\phi_{k}^{\star}(z_{k-1}),\
y_{k}=x_{k}-\eta_{k}\omega_{k},\ z_{k}=z_{k-1}-a_{k}\omega_{k},\end{split}$
(8)

where $\omega_{k}=\nabla f(x_{k})+\varepsilon_{k+1}(x_{k})$,
$\phi_{k}(x)=\sum_{i=1}^{k}(a_{i}m/2)\|x-x_{i}\|^{2}+(m_{0}/2)\|x-x_{0}\|^{2}$,
and $A_{k}=\sum_{i=1}^{k}a_{i}$ for a non-negative constant $m_{0}$ and non-
negative sequence $a_{k}$.

Dual averaging method [69] tackles the dual problem by constructing lower
bounds to the optimum. Since $f\in\mathcal{F}(m,L)$, we have

$\begin{split}f(x_{\star})&\geq\frac{1}{A_{k}}\sum_{i=1}^{k}a_{i}[f(x_{i})+\nabla
f(x_{k})^{\top}(x_{\star}-x_{k})+\frac{m}{2}\|x_{k}\|^{2}]\\\
&\geq\frac{1}{A_{k}}\sum_{i=1}^{k}a_{i}[f(x_{i})-\varepsilon_{i}^{\top}(x_{\star}-x_{i})]+\frac{m_{0}}{2}\|x_{\star}-x_{0}\|\\\
&\quad+\frac{1}{A_{k}}\min_{x}\left\\{\sum_{i=1}^{k}a_{i}\left[\omega_{i}^{\top}(x-x_{i})+\frac{m}{2}\|x-x_{i}\|^{2}\right]+\frac{m_{0}}{2}\|x-x_{0}\|^{2}\right\\}\stackrel{{\scriptstyle\rm
def}}{{=}}L_{k},\end{split}$ (9)

and the dual averaging method aims to minimize the upper bound
$f(x_{k})-f(x_{\star})$. We can accelerate dual averaging method by adding
gradient descent steps with a new upper bound $U_{k}=f(y_{k})$ and linearly
coupling two approaches [6, 19].

For a Euclidean norm, we have $\nabla\phi_{k}^{\star}(z)$ in a closed form

$\nabla\phi_{k}^{\star}(z)=\frac{z+m\sum_{i=1}^{k}a_{i}x_{i}+m_{0}x_{0}}{A_{k}m+m_{0}},$
(10)

which shows that ADA fits the framework (5). Note that by replacing
$\nabla\phi_{k}^{\star}(z_{k-1})$ with $\nabla\phi_{k-1}^{\star}(z_{k-1})$ in
(8), the ADA recovers Nesterov acceleration [47, 34, 64]. The following result
shows ADA has the property of robustness (7), whose proof is deferred to
Appendix C.

######  Theorem 2.

ADA have the property of robustness (7) with
$\mathcal{E}_{k}=G_{k}=U_{k}-L_{k}$ and

$(r_{k},m_{k},n_{k})=\left(\frac{a_{k}}{A_{k}},\eta_{k}-\frac{L\eta_{k}^{2}}{2}-\frac{a_{k}^{2}}{2A_{k}^{2}m},\frac{L\eta_{k}^{2}}{2}+\frac{a_{k}^{2}}{2A_{k}^{2}m}\right).$
(11)

Note that $f(y_{k})-f(x_{\star})\leq G_{k}$. When $\varepsilon_{k}=0$, then
choosing $\eta_{k}=1/L$ and $a_{k}/A_{k}=\sqrt{m/L}$ recovers accelerated
convergence rate $1-\sqrt{m/L}$.

###  2.2 Implicit Accelerated Dual Averaging Method

The iterates of Implicit Accelerated Dual Averaging Method (iADA or $\mu$AGD+
in [15]) are

$\begin{split}x_{k}=\frac{A_{k-1}}{A_{k}}y_{k-1}+\frac{a_{k}}{A_{k}}\nabla\phi_{k}^{\star}(z_{k-1}),\
z_{k}=z_{k-1}-a_{k}\omega_{k},\
y_{k}=\frac{A_{k-1}}{A_{k}}y_{k-1}+\frac{a_{k}}{A_{k}}\nabla\phi_{k}^{\star}(z_{k}),\end{split}$
(12)

where $\omega_{k}=\nabla f(x_{k})+\varepsilon_{k+1}(x_{k})$. Consider the
continuous time dynamics of accelerated dual averaging method under the
setting of strong convexity (See Section 3 in [19] for derivation):

$\frac{dz_{t}}{dt}=\frac{dA_{t}}{dt}\nabla
f(y_{t}),\quad\frac{dy_{t}}{dt}=\frac{dA_{t}}{dt}\frac{\nabla\phi_{t}^{\star}(z_{t})-y_{t}}{A_{t}}.$
(13)

Then ADA can be interpreted as an explicit (forward) Euler discretization of
(13) with additional gradient steps aiming to reduce discretization errors. On
the other hand, iADA can be derived by implicit (backward) Euler
discretization:

$z_{k}=z_{k-1}-a_{k}\nabla f(y_{k}),\quad
y_{k}=\frac{A_{k-1}}{A_{k}}y_{k-1}+\frac{a_{k}}{A_{k}}\phi_{k}^{\star}(z_{k})$
(14)

Since both sides of (14) involve $y_{k}$ and $z_{k}$, we need to solve this
fixed-point equation, and $x_{k}$ in (12) is obtained from one step of fixed-
point iteration to approximate of $y_{k}$:

$x_{k}\stackrel{{\scriptstyle
def}}{{=}}\frac{A_{k-1}}{A_{k}}y_{k-1}+\frac{a_{k}}{A_{k}}\phi_{k-1}^{\star}(z_{k-1})\approx
y_{k}.$ (15)

We then replace $\phi_{k-1}^{\star}(z_{k-1})$ by $\phi_{k}^{\star}(z_{k-1})$,
since this is a better approximation for $y_{k}$ from one step of fixed-point
iteration. This minor difference actually improves convergence bound. The
following result shows robustness for iADA and is proven in Appendix C.

######  Theorem 3.

Setting $m_{0}=0$, iADA converges robustly with the
$\mathcal{E}_{k}=G_{k}=U_{k}-L_{k}$ and

$(r_{t},m_{t},n_{t})=\left(\frac{a_{k}}{A_{k}},\left(\frac{m}{2}-\frac{a_{k}^{2}L}{2A_{k}^{2}}\right)\frac{a_{k}^{2}}{A_{k}^{2}},\frac{a_{k}^{2}}{A_{k}^{2}}-\left(\frac{m}{2}-\frac{a_{k}^{2}L}{2A_{k}^{2}}\right)\frac{a_{k}^{2}}{A_{k}^{2}}\right).$
(16)

If $\varepsilon_{k}=0$, then choosing $a_{k}/A_{k}=\sqrt{m/L}$ achieves
accelerated convergence rate $1-\sqrt{m/L}$.

###  2.3 Robust Momentum Method

A “synthesized Nesterov variant” (SNV) algorithm [41, 63, 16] is governed by
the following recursion:

$\begin{split}x_{k+1}=x_{k}+\beta_{1}(x_{k}-x_{k-1})-\eta_{1}\nabla
f(y_{k})),\quad y_{k}=x_{k}+\beta_{2}(x_{k}-x_{k-1}).\end{split}$ (17)

The above recursion can be reparametrized using $z_{k}=x_{k}-x_{k-1}$,
$\eta_{1}=\eta/L$, $\beta_{1}=\beta$ and $\beta_{2}=\beta/\eta$ as:

$\begin{split}z_{k+1}=\beta z_{k}-\frac{\eta}{L}\omega_{k},\quad
x_{k+1}=x_{k}+z_{k+1},\quad y_{k}=x_{k}+\frac{\beta}{\eta}z_{k},\end{split}$
(18)

where $\omega_{k}=\nabla f(y_{k})+\varepsilon_{k+1}(y_{k})$. We call this
Robust Momentum Method (RMM). This reparametrization shows that (18) is
similar to (8) and (12) with different parameters restrictions.

######  Theorem 4.

Define $\widetilde{\kappa}=L/(\theta m)$,
$\eta_{k}=\widetilde{\kappa}(1-\rho)(1-\rho^{2})$,
$\beta_{k}=\widetilde{\kappa}\rho^{3}/(\widetilde{\kappa}-1)$ and set

$\lambda=\frac{\theta^{2}m^{2}(\widetilde{\kappa}-\widetilde{\kappa}\rho^{2}-1)}{2\rho(1-\rho)(1-\rho^{2})^{2}},\nu=\frac{(1+\rho)(1-\widetilde{\kappa}+2\widetilde{\kappa}\rho-\widetilde{\kappa}\rho^{2})}{2\rho}.$
(19)

Then RMM converges robustly with
$\mathcal{E}_{k}=V(\xi_{k})=\lambda\xi_{k}^{\top}P\xi_{k}+q_{\theta}(y_{k})$
and

$(r_{k},m_{k},n_{k})=\left(1-\rho,\nu(1-2\theta
m^{2}/L^{2}+\theta^{2}),1-\nu\right),$ (20)

where $\xi_{k}=(x_{k}^{\top},z_{k}^{\top})^{\top}$,
$g_{\theta}(x)=f(x)-f(x_{\star})-\theta m/2\|x-x_{\star}\|^{2}$,
$q_{\theta}(y_{k})=(L-\theta m)g(y_{k})-\|\nabla f(y_{k})\|/2$, and

$P=\begin{bmatrix}1&\rho^{2}/(1-\rho^{2})\\\
\rho^{2}/(1-\rho^{2})&\rho^{4}/(1-\rho^{2})^{2}\end{bmatrix}\otimes I_{d}.$
(21)

The proof and the discussion of $V(\xi_{k})$ is deferred to Appendix C and is
based on dissipativity theory, which is briefly introduced in Appendix B. When
$\varepsilon_{k}=0$, setting $\theta=1$, we recover accelerated convergence
rate by noting that $0\leq\nu\leq 1-1/\kappa$, if
$1-1/\sqrt{\kappa}\leq\rho\leq 1-1/\kappa$.

##  3 Convergence Analysis under the Growth Condition

We discuss how to show the accelerated convergence result under the growth
condition. The growth condition states that the stochastic gradients can be
dominated by a multiplicative part and an additive part, where the
multiplicative part shrinks relative to the full gradient, while the additive
part is bounded. Formally, for a point $\zeta$ and all $k$, the error
$\varepsilon_{k}(\zeta)$ satisfies the growth condition with constants
$\delta$, $\sigma^{2}$, if

$\mathbb{E}\|\varepsilon_{k+1}(\zeta)\|^{2}\leq\delta\|\nabla
f(\zeta)\|^{2}+\sigma^{2}.$ (22)

######  Example 2.

Several easy examples are provided for illustrating the growth condition.

  1. 1.

There is an upper bound $\sigma^{2}$ such that
$\|\varepsilon\|^{2}\leq\sigma^{2}$ almost surely, which is a typical
assumption for SGD. In this case, heavy-ball method [24] and Nesterov’s
accelerated method [31] can achieve acceleration [13].

  2. 2.

For the randomized coordinate descent [36], we have

$\mathbb{E}|\nabla_{i_{k}}f(\zeta)|^{2}\leq\frac{1}{d}\sum_{i=1}^{d}|\nabla_{i}f(\zeta)|^{2}=\frac{1}{d}\|\nabla
f(\zeta)\|^{2},$ (23)

where $\nabla_{i}$ is the $i$-th partial derivative and $i_{k}$ is uniformly
distributed.

  3. 3.

If $f$ is $L$-smooth and has a minima at $x_{\star}$, then $\varepsilon$
satisfies the weak growth condition with constant $\tau\geq 0$ if

$\mathbb{E}\|\varepsilon(\zeta)\|^{2}\leq 2\tau L[f(\zeta)-f(x_{\star})].$
(24)

SGD meets weak growth condition if the function $f$ is convex and has a finite
sum structure for a model that interpolates the data. See Proposition 2 and
more discussions in [64].

The following convergence theorem follows from the growth condition and
robustness.

######  Theorem 5.

Suppose that an algorithm $\mathcal{A}$ has property of robustness (7) with
$\mathcal{E}_{k}$ and $(r_{k},m_{k},n_{k})$ and $\varepsilon_{k}$ satisfies
the growth condition (22) with $\delta,\sigma^{2}$. If $\delta n_{k}-m_{k}\leq
0$, then

$\mathbb{E}\mathcal{G}_{k+1}\leq(1-r_{k})\mathbb{E}\mathcal{G}_{k}+n_{k}\sigma^{2}.$
(25)

We can apply this theorem to ADA, iADA and RMM.

######  Corollary 6.

Choosing $a_{k}^{2}/A_{k}^{2}=mL\eta^{2}$ and $\eta=1/(L(1+\delta))$ for ADA
and $a_{k}^{2}/A_{k}^{2}=(m(1-\delta))/(L(1+\delta))$ and $m_{0}=0$ for iADA,
we have convergence rate of ADA $r_{\text{ADA}}$ and iADA $r_{\text{iADA}}$

$r_{\text{ADA}}=\sqrt{\frac{m}{L(1+\delta)^{2}}},\quad
r_{\text{iADA}}=\sqrt{\frac{m(1-\delta)}{L(1+\delta)}}.$ (26)

For RMM, if $1-2(m^{2}/L^{2})(1-\delta)+(1-\delta)^{2}-\delta>0$, then we get
the convergence rate $r_{\text{RMM}}$ of RMM as

$r_{\text{RMM}}=\sqrt{\frac{m(1-\delta)}{L}\left(1-\frac{\delta}{1-2(m^{2}/L^{2})(1-\delta)+(1-\delta)^{2}}\right)},$
(27)

by choosing $\theta=(1-\delta)$ and parameters in Theorem 4.

The proof is in Appendix D. Compared with the bound $\sqrt{m/(L\delta^{2})}$in
[64], (26) is slightly worse. However, our convergence bounds of all methods
achieve original accelerated convergence bound when $\delta=0$, which is more
intuitive. For comparison, ADA can handle arbitrarily large noise levels, but
iADA and RMM can only deal with small noise level $0\leq\delta<1$. iADA has
similar robustness compared to ADA, while the convergence bound of RMM is
worse than ADA and iADA.

###  3.1 Stochastic Gradient Descent for Least Squares Regression

We discuss how to accelerate SGD for least squares regression. Though
accelerating SGD is impossible in general, [34] showed an acceleration result
in least squares regression. Consider the least square regression problem in
(2). SGD uses the first-order oracle that can be decomposed as the
multiplicative part and the additive part:

$\widehat{\nabla}f(x)=a(a^{\top}x-b)=aa^{\top}(x-x_{\star})+a(a^{\top}x_{\star}-b).$
(28)

Since we know the additive part would not affect acceleration, for simplicity,
we assume $b=a^{\top}x_{\star}$. If
$\mathbb{E}[a^{\top}aaa^{\top}]\leq\delta(\mathbb{E}[aa^{\top}])^{2}$, then
the growth condition holds. Given the canonical basis $\\{e_{i}\\}_{i=1}^{d}$
and random variables $\\{c_{i}\\}_{i=1}^{d}$ that are distributed as Normal
with zero mean and variance $s_{i}^{2}$, we set $a=c_{i}e_{i}$ where $i$ is
chosen uniformly at random from $\\{1,\ldots,d\\}$. Since
$\mathbb{E}c_{i}^{4}=3s_{i}^{2}$, we have
$\mathbb{E}[a^{\top}aaa^{\top}]=3(\mathbb{E}[aa^{\top}])^{2}$. While this
example seems simple, [37, Proposition 3] showed that the heavy ball method
cannot improve convergence rate in this case.

We also derive the growth condition using mini-batch samples for empirical
risk minimization.

######  Proposition 7.

For $f(x)=\sum_{i=1}^{n}f_{i}(x)$ such that $\mathbb{E}f_{i}=f$ and
$f_{i}\in\mathcal{F}(0,L_{i})$, we have

$\mathbb{E}\|\widehat{\nabla}f(x)-\nabla
f(x)\|^{2}=\left(\frac{4}{b}\frac{L_{\max}}{m}-1\right)\|\nabla
f(x)\|^{2}+\frac{2}{b}\frac{1}{n}\sum_{i=1}^{n}\|f_{i}(x_{\star})\|^{2},$ (29)

where $\widehat{\nabla}f(x)=\frac{1}{b}\sum_{i=1}^{b}\nabla f_{k_{i}}(x)$ and
a subset $\\{k_{i}\\}_{i=1}^{b}$ is sampled uniformly from $\\{1,\dots,n\\}$
and $L_{\max}=\max_{i}L_{i}$.

From this result we have that if $b=\Omega(L_{\max}/m)$,
$\delta=\left(4L_{\max}/(mb)-1\right)=\mathcal{O}(1)$, then SGD can be
accelerated by ADA, iADA and RMM. A similar result can be found in [35, 42].
We have more discussion on least squares regression in Appendix G and variance
reduction methods in Appendix F.

##  4 Optimal Averaging Schemes and Decreasing Stepsizes

We discuss general averaging schemes and achieve the optimal convergence rate
in the stochastic setting. Suppose that $(m_{k}-\delta n_{k})$ < 0 and
$r_{k}=r<1$. Defining $e_{k}=\mathbb{E}\mathcal{E}_{k}$, we have the following
bound:

$e_{k+1}\leq(1-r)^{-k}e_{1}+\frac{n_{k}\sigma^{2}}{r}.$ (30)

By Corollary 6, we know ADA, iADA, and RMM converge to a neighborhood of
optimum exponentially with the rate $\Omega(1-\sqrt{m/L})$. To eliminate the
variance term $n_{k}\sigma^{2}/r$, we could use a decreasing sequence $n_{k}$
or averaging schemes. First, we introduce a useful lemma for a recursion which
from Example 1.

######  Lemma 8 (Lemma 2 and 3 in [59]).

Consider a recursion relationship

$e_{k+1}\leq(1-ar_{k})e_{k}-br_{k}s_{k}+cr_{k}^{2}$ (31)

for non-negative sequences $\\{e_{k}\\}_{k>0}$, $\\{s_{k}\\}_{k>0}$ and non-
negative constants $a,b,c,d,r$ such that $d\geq a$.

  1. 1.

Constant Stepsizes (with Log Terms). Let $w_{k}=(1-ar)^{-(k+1)}$ and
$W_{K}=\sum_{k=1}^{K}w_{k}$. There exists a constant $r=r_{k}\leq 1/d$ such
that

$\frac{b}{W_{K}}\sum_{k=1}^{K}w_{k}s_{k}+ae_{K+1}=\widetilde{\mathcal{O}}\left(de_{1}\exp\left[-\frac{aK}{d}\right]+\frac{c}{aK}\right).$
(32)

  2. 2.

Decreasing Stepsizes (Avoiding Log Terms). There exists weights $w_{k}$ and
$W_{K}=\sum_{k=1}^{K}w_{k}$ and $r_{k}=r\leq 1/d$ such that

$\frac{b}{W_{K}}\sum_{k=1}^{K}w_{k}s_{k}+ae_{K+1}=32de_{1}\exp\left[-\frac{aK}{d}\right]+36\frac{c}{aK}.$
(33)

The key observation is that ADA and iADA have a similar recursion as SGD in
Example 1. Applying Lemma 8, ADA can achieve faster convergence rate.

######  Theorem 9.

Let $\bar{x}_{K}=\frac{1}{W_{K}}\sum_{k=1}^{K}w_{k}x_{k}$ and
$a_{k}^{2}/A_{k}^{2}=mL\eta^{2}$. For weights $w_{k}$ and
$W_{K}=\sum_{k=1}^{K}w_{k}$ described in the first part of Lemma 8, there
exists a constant $\eta=\eta_{k}$ such that $(1-(1+\delta)L\eta)>0$ and
iterates obtain by ADA satisfy:

$\mathbb{E}[f(\bar{x}_{K})-f(x_{\star})]=\widetilde{\mathcal{O}}\left(\frac{(1+\delta)L}{m}\mathbb{E}G_{1}\exp\left[-\frac{K}{2(1+\delta)}\sqrt{\frac{m}{L}}\right]+\frac{\sigma^{2}}{\sqrt{mL}K}\right).$
(34)

Moreover, if we choose the weights $w_{k}$ and decreasing $\eta_{k}$ described
in the second part of Lemma 8, we can remove the log terms in (34), i.e.,
replace $\widetilde{\mathcal{O}}$ with $\mathcal{O}$.

Appendix H obtains a similar convergence rate for iADA. [15] shows that iADA
has the convergence rate
$\mathcal{O}\left(\frac{\log(k)}{k^{\log(k)}}\cdot\frac{(L-\mu)\left\|x_{\star}-x_{0}\right\|^{2}}{2}+\frac{\log(k)}{k}\cdot\frac{\sigma^{2}}{m}\right)$.
On the other hand, we apply averaging schemes to achieve the optimal
convergence rate $\mathcal{O}((1-\sqrt{m/L})^{k}+\sigma^{2}/k)$, which is also
a lower bound [11].

Though Lemma 8 gives an optimal convergence rate, weights decrease
exponentially and depend on the convergence rate. In the following section we
provide a simpler scheme.

###  4.1 $\alpha$-Suffix Averaging

In this section, we seek a scheme with constant weights, but decreasing
$r_{k}$. In particular, we use the following $r_{k}$ and $\alpha$-suffix
averaging [54] as follows:

$r_{k}=\begin{cases}d^{-1}&\text{if }t<(1-\alpha)K+1\\\
(a(k_{0}+k-(1-\alpha)K))^{-1}&\text{otherwise}\end{cases},\
w_{k}=\begin{cases}0&\text{if }t<(1-\alpha)K+1\\\
1&\text{otherwise}\end{cases},$ (35)

for some constant $0<\alpha<1$ such that $\alpha T$ is an integer. We can
derive a similar result as Lemma 8 for (35) .

######  Proposition 10.

Consider the following recursive relationship

$e_{k+1}\leq(1-ar_{k})e_{k}-br_{k}s_{k}+cr_{k}^{2}.$ (36)

For $r_{k}$ and weights $w_{k}$ defined in (35) with $k_{0}=d/a$, and
$W_{K}=\sum_{k=1}^{K}w_{k}$, we have

$\frac{b}{W_{K}}\sum_{t=1}^{K}w_{k}s_{k}\leq\frac{d}{\alpha}e_{0}\exp\left[-\frac{a(1-\alpha)K}{d}\right]+\frac{c}{Ka\alpha}\left(1+\log\left(\frac{1}{1-\alpha}\right)\right).$
(37)

Applying Proposition 10, we show the optimal convergence bound.

######  Theorem 11.

Let $\bar{x}_{K}=\frac{1}{W_{K}}\sum_{k=1}^{K}w_{k}x_{k}$,
$a_{k}^{2}/A_{k}^{2}=mL\eta^{2}$, $\eta_{k}=r_{k}$. For $r_{k}$ and a weights
$w_{k}$, $W_{K}=\sum_{k=1}^{K}w_{k}$ defined in (35), ADA achieves the
following bound:

$\mathbb{E}[f(\bar{x}_{K})-f(x_{\star})]=\frac{2(1+\delta)L}{\alpha
m}e_{0}\exp\left[-\frac{(1-\alpha)}{2(1+\delta)}\sqrt{\frac{m}{L}}K\right]+\frac{\sigma^{2}\left(1+\log\left(\frac{1}{1-\alpha}\right)\right)}{Km^{1.5}L^{0.5}\alpha}.$
(38)

Compared to Lemma 8, here we discard the first $(1-\alpha)K$ iterates to avoid
the $\log$ term. Equation (35) consists of two phases. In the first phase, we
use a constant step size to reduces the bias term exponentially and approach a
neighborhood of the optimum. In the second phase, we average up last iterates
and reduce the variance term. The scheme in (35) uses the constant weights
that do not depend on the convergence rate and only requires the polynomial
decay of step size, which is commonly used in SGD and much easy to tune in
practice.

##  5 Discussion and Conclusion

This paper contributes to a broader understanding of the accelerated SGD. We
discuss the definition of the property of robustness and study accelerated
convergence rate with a growth condition. Our results build intuitions of
acceleration phenomena in the stochastic setting for convergence analysis and
proof techniques in the literature. Three algorithms in Section 2 involve
averaging of past gradients. The use of momentum can be treated as a variance
reducer [7]. It may be a critical observation to derive deep understanding and
design a more robust algorithm. We also provide optimal averaging and
decreasing schemes to achieve faster convergence rate up to some constants
under the growth condition. It remains open and is worth studying the minimax
optimality depending on the noise level $\delta$ of multiplicative noise under
the growth condition (22). It is also interesting to consider composite
optimization, constrained optimization.

Non-strongly convex and non-convex functions. Even though we only discuss the
setting where $f$ is smooth and strongly convex, we can extend our results to
the class of non-strongly convex or non-convex functions. Incorporating the
growth condition and some locally convex conditions, such as Polyak-
Lojasiewicz condition [36] or error bound [43], it has been shown that SGD
converges in [64, Theorem 4]. It remains open for accelerated SGD as our
future work. For objectives $f(x)$that are non-strongly convex and $L$-smooth,
we can use AdaptReg in [5], which optimizes regularized objective
$f(x)+(m/2)\left\|x-x_{0}\right\|^{2}$ and exponentially decreases value $m$.
[5] showed that this reduction is optimal for algorithms that satisfy the
homogenous objective decrease property (HOOD), and it is not hard to see ADA,
iADA, and RMM satisfy HOOD.

## Broader Impact

Momentum-based acceleration of stochastic gradient descent is incredibly
successful in training neural networks. Typically training deep learning
models requires thousands of epochs and SGD iterations. A slight improvement
of optimizer can save tremendous consumption of time and energy. Moreover,
lacking theoretical understanding for acceleration, trial and error is the
only way for choosing optimizer and tuning parameters, which is ad-hoc and
inefficient. This work serves as a step towards providing the intuition and
insight of acceleration of SGD. The theorems provided in this paper could have
a profound impact on optimizing state-of-the-art machine learning models by
leading to a better design for robust accelerated algorithms.

## References

  * Allen-Zhu [2017a] Z. Allen-Zhu.  Katyusha: The first direct acceleration of stochastic gradient methods.  _The Journal of Machine Learning Research_ , 18(1):8194–8244, 2017a.
  * Allen-Zhu [2017b] Z. Allen-Zhu.  Natasha: Faster non-convex stochastic optimization via strongly non-convex parameter.  In _Proceedings of the 34th International Conference on Machine Learning-Volume 70_ , pages 89–97. JMLR. org, 2017b.
  * Allen-Zhu [2018a] Z. Allen-Zhu.  Katyusha x: Practical momentum method for stochastic sum-of-nonconvex optimization.  _arXiv preprint arXiv:1802.03866_ , 2018a.
  * Allen-Zhu [2018b] Z. Allen-Zhu.  Natasha 2: Faster non-convex optimization than sgd.  In _Advances in neural information processing systems_ , pages 2675–2686, 2018b.
  * Allen-Zhu and Hazan [2016] Z. Allen-Zhu and E. Hazan.  Optimal black-box reductions between optimization objectives.  In _Advances in Neural Information Processing Systems_ , pages 1614–1622, 2016.
  * Allen-Zhu and Orecchia [2014] Z. Allen-Zhu and L. Orecchia.  Linear coupling: An ultimate unification of gradient and mirror descent.  _arXiv preprint arXiv:1407.1537_ , 2014.
  * Arnold et al. [2019] S. Arnold, P.-A. Manzagol, R. B. Harikandeh, I. Mitliagkas, and N. Le Roux.  Reducing the variance in online optimization by transporting past gradients.  In _Advances in Neural Information Processing Systems_ , pages 5392–5403, 2019.
  * Assran and Rabbat [2020] M. Assran and M. Rabbat.  On the convergence of nesterov’s accelerated gradient method in stochastic settings.  _arXiv preprint arXiv:2002.12414_ , 2020.
  * Aybat et al. [2020] N. S. Aybat, A. Fallah, M. Gurbuzbalaban, and A. Ozdaglar.  Robust accelerated gradient methods for smooth strongly convex functions.  _SIAM Journal on Optimization_ , 30(1):717–751, 2020.
  * Bach and Moulines [2013] F. Bach and E. Moulines.  Non-strongly-convex smooth stochastic approximation with convergence rate o (1/n).  In _Advances in neural information processing systems_ , pages 773–781, 2013.
  * Blair [1985] C. Blair.  Problem complexity and method efficiency in optimization (as nemirovsky and db yudin).  _SIAM Review_ , 27(2):264, 1985.
  * 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.
  * Can et al. [2019] B. Can, M. Gurbuzbalaban, and L. Zhu.  Accelerated linear convergence of stochastic momentum methods in wasserstein distances.  _Proceedings of Machine Learning Research_ , 97, 2019.
  * Cevher and Vũ [2019] V. Cevher and B. C. Vũ.  On the linear convergence of the stochastic gradient method with constant step-size.  _Optimization Letters_ , 13(5):1177–1187, 2019\.
  * Cohen et al. [2018] M. Cohen, J. Diakonikolas, and L. Orecchia.  On acceleration with noise-corrupted gradients.  In _International Conference on Machine Learning_ , pages 1019–1028, 2018.
  * Cyrus et al. [2018] S. Cyrus, B. Hu, B. Van Scoy, and L. Lessard.  A robust accelerated optimization algorithm for strongly convex functions.  In _2018 Annual American Control Conference (ACC)_ , pages 1376–1381. IEEE, 2018.
  * Defazio et al. [2014] A. Defazio, J. Domke, et al.  Finito: A faster, permutable incremental gradient method for big data problems.  In _International Conference on Machine Learning_ , pages 1125–1133, 2014.
  * Défossez and Bach [2015] A. Défossez and F. Bach.  Averaged least-mean-squares: Bias-variance trade-offs and optimal sampling distributions.  In _Artificial Intelligence and Statistics_ , pages 205–213, 2015\.
  * Diakonikolas and Orecchia [2019] J. Diakonikolas and L. Orecchia.  The approximate duality gap technique: A unified theory of first-order methods.  _SIAM Journal on Optimization_ , 29(1):660–689, 2019.
  * Dieuleveut et al. [2017] A. Dieuleveut, A. Durmus, and F. Bach.  Bridging the gap between constant step size stochastic gradient descent and markov chains.  _arXiv preprint arXiv:1707.06386_ , 2017.
  * Driggs et al. [2019] D. Driggs, M. J. Ehrhardt, and C.-B. Schönlieb.  Accelerating variance-reduced stochastic gradient methods.  _arXiv preprint arXiv:1910.09494_ , 2019.
  * Fang et al. [2018] C. Fang, C. J. Li, Z. Lin, and T. Zhang.  Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator.  In _Advances in Neural Information Processing Systems_ , pages 689–699, 2018.
  * Flammarion and Bach [2017] N. Flammarion and F. Bach.  Stochastic composite least-squares regression with convergence rate $o(1/n)$.  In _Conference on Learning Theory_ , pages 831–875, 2017.
  * Gadat et al. [2018] S. Gadat, F. Panloup, S. Saadane, et al.  Stochastic heavy ball.  _Electronic Journal of Statistics_ , 12(1):461–529, 2018.
  * Gannot [2019] O. Gannot.  A frequency-domain analysis of inexact gradient descent.  _arXiv preprint arXiv:1912.13494_ , 2019.
  * Ghadimi and Lan [2013] S. Ghadimi and G. Lan.  Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, ii: shrinking procedures and optimal algorithms.  _SIAM Journal on Optimization_ , 23(4):2061–2089, 2013.
  * Gitman et al. [2019] I. Gitman, H. Lang, P. Zhang, and L. Xiao.  Understanding the role of momentum in stochastic gradient methods.  In _Advances in Neural Information Processing Systems_ , pages 9630–9640, 2019.
  * Gower et al. [2018] R. M. Gower, P. Richtárik, and F. Bach.  Stochastic quasi-gradient methods: Variance reduction via jacobian sketching.  _arXiv preprint arXiv:1805.02632_ , 2018.
  * Hanzely et al. [2018] F. Hanzely, K. Mishchenko, and P. Richtárik.  Sega: Variance reduction via gradient sketching.  In _Advances in Neural Information Processing Systems_ , pages 2082–2093, 2018.
  * Hsu et al. [2014] D. Hsu, S. Kakade, and T. Zhang.  Random design analysis of ridge regression.  _Foundations of Computational Mathematics_ , 14(3), 2014\.
  * Hu and Lessard [2017] B. Hu and L. Lessard.  Dissipativity theory for nesterov’s accelerated method.  In _Proceedings of the 34th International Conference on Machine Learning-Volume 70_ , pages 1549–1557. JMLR. org, 2017.
  * Hu et al. [2018] B. Hu, S. Wright, and L. Lessard.  Dissipativity theory for accelerating stochastic variance reduction: A unified analysis of svrg and katyusha using semidefinite programs.  _Proceedings of Machine Learning Research_ , 80, 2018.
  * Jain et al. [2017] P. Jain, P. Netrapalli, S. M. Kakade, R. Kidambi, and A. Sidford.  Parallelizing stochastic gradient descent for least squares regression: mini-batching, averaging, and model misspecification.  _The Journal of Machine Learning Research_ , 18(1):8258–8299, 2017.
  * Jain et al. [2018] P. Jain, P. Netrapalli, S. M. Kakade, R. Kidambi, and A. Sidford.  Accelerating stochastic gradient descent for least squares regression.  _Proceedings of Machine Learning Research vol_ , 75:1–60, 2018.
  * Jofré and Thompson [2019] A. Jofré and P. Thompson.  On variance reduction for stochastic smooth convex optimization with multiplicative noise.  _Mathematical Programming_ , 174(1-2):253–292, 2019.
  * 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.
  * 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.
  * Laborde and Oberman [2019] M. Laborde and A. M. Oberman.  A lyapunov analysis for accelerated gradient methods: From deterministic to stochastic case.  _arXiv preprint arXiv:1908.07861_ , 2019.
  * Lacoste-Julien et al. [2012] S. Lacoste-Julien, M. Schmidt, and F. Bach.  A simpler approach to obtaining an o (1/t) convergence rate for the projected stochastic subgradient method.  _arXiv preprint arXiv:1212.2002_ , 2012.
  * Lan et al. [2019] G. Lan, Z. Li, and Y. Zhou.  A unified variance-reduced accelerated gradient method for convex optimization.  In _Advances in Neural Information Processing Systems_ , pages 10462–10472, 2019.
  * Lessard et al. [2016] L. Lessard, B. Recht, and A. Packard.  Analysis and design of optimization algorithms via integral quadratic constraints.  _SIAM Journal on Optimization_ , 26(1):57–95, 2016.
  * Lin et al. [2020] Z. Lin, H. Li, and C. Fang.  _Accelerated Stochastic Algorithms_ , pages 137–207.  Springer Singapore, Singapore, 2020.  ISBN 978-981-15-2910-8.  doi: 10.1007/978-981-15-2910-8_5.  URL https://doi.org/10.1007/978-981-15-2910-8_5.
  * Luo and Tseng [1992] Z.-Q. Luo and P. Tseng.  Error bound and convergence analysis of matrix splitting algorithms for the affine variational inequality problem.  _SIAM Journal on Optimization_ , 2(1):43–54, 1992\.
  * Ma and Yarats [2018] J. Ma and D. Yarats.  Quasi-hyperbolic momentum and adam for deep learning.  _arXiv preprint arXiv:1810.06801_ , 2018.
  * Mairal [2015] J. Mairal.  Incremental majorization-minimization optimization with application to large-scale machine learning.  _SIAM Journal on Optimization_ , 25(2):829–855, 2015.
  * Murata and Suzuki [2017] T. Murata and T. Suzuki.  Doubly accelerated stochastic variance reduced dual averaging method for regularized empirical risk minimization.  In _Advances in Neural Information Processing Systems_ , pages 608–617, 2017.
  * Nesterov [2012] Y. Nesterov.  Efficiency of coordinate descent methods on huge-scale optimization problems.  _SIAM Journal on Optimization_ , 22(2):341–362, 2012.
  * Nesterov [2013] Y. Nesterov.  _Introductory lectures on convex optimization: A basic course_ , volume 87.  Springer Science & Business Media, 2013.
  * Nesterov [1983] Y. E. Nesterov.  A method for solving the convex programming problem with convergence rate $o(1/k^{2})$.  In _Dokl. akad. nauk Sssr_ , volume 269, pages 543–547, 1983.
  * Nguyen et al. [2017] L. M. Nguyen, J. Liu, K. Scheinberg, and M. Takáč.  Sarah: A novel method for machine learning problems using stochastic recursive gradient.  In _Proceedings of the 34th International Conference on Machine Learning-Volume 70_ , pages 2613–2621. JMLR. org, 2017.
  * Nguyen et al. [2019] L. M. Nguyen, P. H. Nguyen, P. Richtárik, K. Scheinberg, M. Takáč, and M. van Dijk.  New convergence aspects of stochastic gradient algorithms.  _Journal of Machine Learning Research_ , 20(176):1–49, 2019.
  * 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.
  * Polyak [1990] B. T. Polyak.  New method of stochastic approximation type.  _Automation and remote control_ , 51(7 pt 2):937–946, 1990.
  * Rakhlin et al. [2012] A. Rakhlin, O. Shamir, and K. Sridharan.  Making gradient descent optimal for strongly convex stochastic optimization.  In _Proceedings of the 29th International Coference on International Conference on Machine Learning_ , pages 1571–1578, 2012.
  * Schmidt and Roux [2013] M. Schmidt and N. L. Roux.  Fast convergence of stochastic gradient descent under a strong growth condition.  _arXiv preprint arXiv:1308.6370_ , 2013.
  * Schmidt et al. [2017] M. Schmidt, N. Le Roux, and F. Bach.  Minimizing finite sums with the stochastic average gradient.  _Mathematical Programming_ , 162(1-2):83–112, 2017.
  * Shalev-Shwartz and Zhang [2013] S. Shalev-Shwartz and T. Zhang.  Stochastic dual coordinate ascent methods for regularized loss minimization.  _Journal of Machine Learning Research_ , 14(Feb):567–599, 2013.
  * Shamir and Zhang [2013] O. Shamir and T. Zhang.  Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes.  In _International conference on machine learning_ , pages 71–79, 2013\.
  * Stich [2019] S. U. Stich.  Unified optimal analysis of the (stochastic) gradient method.  _arXiv preprint arXiv:1907.04232_ , 2019.
  * Tracy and Sultan [1993] D. S. Tracy and S. A. Sultan.  Higher order moments of multivariate normal distribution using matrix derivatives.  _Stochastic Analysis and Applications_ , 11(3):337–348, 1993.
  * Tseng [1998] P. Tseng.  An incremental gradient (-projection) method with momentum term and adaptive stepsize rule.  _SIAM Journal on Optimization_ , 8(2):506–531, 1998.
  * Van der Vaart [2000] A. W. Van der Vaart.  _Asymptotic statistics_ , volume 3.  Cambridge university press, 2000.
  * Van Scoy et al. [2017] B. Van Scoy, R. A. Freeman, and K. M. Lynch.  The fastest known globally convergent first-order method for minimizing strongly convex functions.  _IEEE Control Systems Letters_ , 2(1):49–54, 2017\.
  * Vaswani et al. [2019a] S. Vaswani, F. Bach, and M. Schmidt.  Fast and faster convergence of sgd for over-parameterized models and an accelerated perceptron.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pages 1195–1204, 2019a.
  * Vaswani et al. [2019b] S. Vaswani, A. Mishkin, I. Laradji, M. Schmidt, G. Gidel, and S. Lacoste-Julien.  Painless stochastic gradient: Interpolation, line-search, and convergence rates.  In _Advances in Neural Information Processing Systems_ , pages 3727–3740, 2019b.
  * Willems [1972a] J. C. Willems.  Dissipative dynamical systems part i: General theory.  _Archive for rational mechanics and analysis_ , 45(5):321–351, 1972a.
  * Willems [1972b] J. C. Willems.  Dissipative dynamical systems part ii: Linear systems with quadratic supply rates.  _Archive for rational mechanics and analysis_ , 45(5):352–393, 1972b.
  * Wilson et al. [2016] A. C. Wilson, B. Recht, and M. I. Jordan.  A lyapunov analysis of momentum methods in optimization.  _arXiv preprint arXiv:1611.02635_ , 2016.
  * Xiao [2010] L. Xiao.  Dual averaging methods for regularized stochastic learning and online optimization.  _Journal of Machine Learning Research_ , 11(Oct):2543–2596, 2010.
  * Xu and Luo [2020] X. Xu and X. Luo.  Can speed up the convergence rate of stochastic gradient methods to $\mathcal{O}(1/k^{2})$ by a gradient averaging strategy?  _arXiv preprint arXiv:2002.10769_ , 2020.
  * Zhou [2018a] K. Zhou.  Direct acceleration of saga using sampled negative momentum.  _arXiv preprint arXiv:1806.11048_ , 2018a.
  * Zhou et al. [2018] K. Zhou, F. Shang, and J. Cheng.  A simple stochastic variance reduced algorithm with fast convergence rates.  In _International Conference on Machine Learning_ , pages 5980–5989, 2018.
  * Zhou [2018b] X. Zhou.  On the fenchel duality between strong convexity and lipschitz continuous gradient.  _arXiv preprint arXiv:1803.06573_ , 2018b.

##  Appendix A Strong Convexity, Lipschitz Continuous Gradient and Bregman
Divergence

We present some useful results on strongly convex and smooth functions. See
Zhou [2018b] for details.

######  Lemma 12.

For $f\in\mathcal{F}(m,0)$, we have

$f(y)\geq f(x)+\nabla f(x)^{T}(y-x)+\frac{m}{2}\|y-x\|^{2},\ \forall x,y,$

which implies the following:

  1. 1.

$\|\nabla f(x)-\nabla f(y)\|\geq m\|x-y\|,\ \forall x,y$;

  2. 2.

$f(y)\leq f(x)+\nabla f(x)^{T}(y-x)+\frac{1}{2m}\|\nabla f(y)-\nabla
f(x)\|^{2},\ \forall x,y$.

######  Lemma 13.

For $f\in\mathcal{F}(0,L)$, the following conditions are equivalent:

  1. 1.

$\|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|,\ \forall x,y$.

  2. 2.

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

  3. 3.

$f(y)\geq f(x)+\nabla f(x)^{T}(y-x)+\frac{1}{2L}\|\nabla f(y)-\nabla
f(x)\|^{2},\ \forall x,y$.

We give the definition of a Bregman divergence, which is the difference
between the value of $\psi$ at $x$ and the first order Taylor expansion of
$\psi$ around $y$ evaluated at point $x$.

######  Definition 14 (Bregman divergence).

Let $\psi:\Omega\rightarrow\mathbb{R}$ be a function that is: a) strictly
convex, b) continuously differentiable, and $c$) defined on a closed convex
set $\Omega$. The Bregman divergence associated with $\psi$ for points
$x,y\in\Omega$ is defined as

$\Delta_{\psi}(x,y)=\psi(x)-\psi(y)-\langle\nabla\psi(y),x-y\rangle.$

Note that $\Omega=\mathbb{R}^{d}$ in our analysis. We have several useful
properties of Bregman divergences:

######  Fact 15 (Nonnegativity).

$\Delta_{\psi}(x,y)\geq 0$ for all $x,y$.

######  Fact 16.

$\Delta_{\psi}(x,y)=0$ if and only if $x=y$.

######  Fact 17 (Linearity in $\psi$).

For any $a>0$,
$\Delta_{\psi+a\varphi}(x,y)=\Delta_{\psi}(x,y)+a\Delta_{\varphi}(x,y)$.

We define the dual norm $\|z\|_{\star}=\sup\\{z^{\top}x:\|x\|=1\\}$ and the
convex conjugate.

######  Definition 18 (Convex Conjugate).

A function $\psi^{\star}$ is the convex conjugate of $\psi(x)$ if

$\psi^{\star}(z)=\max_{x}\left\\{z^{\top}x-\psi(x)\right\\}.$ (39)

######  Fact 19.

Let $\psi$ be a differentiable strongly-convex function. Then:

$\nabla\psi^{\star}(z)=\arg\max_{x}\\{z^{\top}x-\psi(x)\\}.$ (40)

######  Fact 20 (Duality).

Suppose $\psi$ is strongly convex. Then

$\left(\nabla\psi^{\star}\right)(\nabla\psi(x))=x,\quad\Delta_{\psi}(x,y)=\Delta_{\psi^{\star}}(\nabla\psi(y),\nabla\psi(x)).$

##  Appendix B Dissipativity Theory

We briefly review dissipativity theory Willems [1972a, b] in this section.
Consider a linear dynamical system:

$\xi_{t+1}=A\xi_{t}+B\omega_{t},$ (41)

where $\xi_{t}\in\mathbb{R}^{d_{\xi}}$ is the state,
$\omega_{k}\in\mathbb{R}^{d_{\omega}}$ is the input,
$A\in\mathbb{R}^{d_{\xi}\times d_{\xi}}$ is the state transition matrix, and
$B\in\mathbb{R}^{d_{\xi}\times d_{\omega}}$ is the input matrix.

The key concepts in dissipativity theory is the supply rate and the storage
function. Supply rate is the energy change in $\xi_{k}$ caused by the driving
force $\omega_{k}$, and the storage function quantifies the energy stored in
the state $\xi$. Formally, the supply rate is a function
$S:\in\mathbb{R}^{d_{\xi}}\times\mathbb{R}^{d_{\xi}}\rightarrow\mathbb{R}$
that maps any state/input pair $(\xi,\omega)$ to the energy delivered from
$\omega$ to state $\xi$. The storage function is a function
$V:\mathbb{R}^{d_{\xi}}\rightarrow\mathbb{R}_{+}$, where $\mathbb{R}_{+}$ is
denoted as the set of nonnegative real numbers. We say the dissipation
inequality holds if for some $0\leq\rho<1$

$V(\xi_{k+1})-\rho V(\xi_{k})\leq S(\xi_{k},w_{k}),$ (42)

which states that the internal energy will dissipate at every step.

Suppose that we know the system satisfies some linear matrix inequalities
(LMI) for any state and input $(\xi,\omega)$ or a set of external system,
which is also called integral quadratic constraint (IQC) [Lessard et al.,
2016, Gannot, 2019] in the control theory literature. For example, given
$f\in\mathcal{F}(m,L)$ and $x$, then by co-coercivity, we have the following
sector IQC [Lessard et al., 2016, Lemma 6]:

$S(x,\nabla f(x))=\begin{bmatrix}x\\\ \nabla
f(x)\end{bmatrix}^{\top}\begin{bmatrix}2mLI_{d}&-(m+L)I_{d}\\\
-(m+L)I_{d}&2I_{d}\end{bmatrix}\begin{bmatrix}x\\\ \nabla
f(x)\end{bmatrix}\leq 0.$ (43)

IQC can be interpreted as the law of energy conservation followed by the
dynamics. Then one can automatically construct the dissipation inequality
using semidefinite programming and the storage function $V$ can serve as a
Lyapunov function. The following key lemma that is a standard result from the
control theory literature.

######  Lemma 21 (Theorem 2 in Hu and Lessard [2017]).

Suppose there exists a matrix $P\in\mathbb{R}^{d_{\xi}\times d_{\omega}}$ with
$P\geq 0$ and
$X\in\mathbb{R}^{(d_{\xi}+d_{\omega})\times(d_{\xi}+d_{\omega})}$ such that

$\begin{bmatrix}A^{\top}PA-\rho^{2}P&A^{\top}PB\\\
B^{\top}PA&B^{\top}PB\end{bmatrix}-X\leq 0.$ (44)

Then the dissipation inequality (42) holds for all trajectories of (41) with
the quadratic supply rate
$S(\xi,\omega)=(\xi^{\top},\omega^{\top})X(\xi^{\top},\omega^{\top})^{\top}$
and the storage function $V(\xi)=\xi^{\top}P\xi$. In particular, if for all
$S(\xi,\omega)\leq 0$, we have $V(\xi_{k+1})\leq\rho^{2}V(\xi_{k})$.

It is trivial to extend to a stochastic input
$\omega_{t}:=\omega_{t}(\varsigma_{t})$ with some randomness $\varsigma_{t}$
and the case involving multiple linear matrix inequalities.

######  Corollary 22.

Suppose there exists a matrix $P\in\mathbb{R}^{d_{\xi}\times d_{\omega}}$ with
$P\geq 0$ such that

$\lambda_{0}\begin{bmatrix}A^{\top}PA-\rho^{2}P&A^{\top}PB\\\
B^{\top}PA&B^{\top}PB\end{bmatrix}-\sum_{j=1}^{J}\lambda_{j}X_{j}\leq 0,$ (45)

where
$(\lambda_{j},X_{j})\in\mathbb{R}\times\mathbb{R}^{(d_{\xi}+d_{\omega})\times(d_{\xi}+d_{\omega})}$
for $j=1\dots,J$. Then

$\lambda_{0}\mathbb{E}V(\xi_{k+1})\leq\rho^{2}\lambda_{0}\mathbb{E}V(\xi_{k})+\sum_{j=1}^{J}\lambda_{j}\mathbb{E}S(\xi_{k},\omega_{k}),$
(46)

where $S=\sum_{j=1}^{J}S_{j}$,
$S_{j}(\xi,\omega)=(\xi^{\top},\omega^{\top})X_{j}(\xi^{\top},\omega^{\top})^{\top}$,
and $V(\xi)=\xi^{\top}P\xi$.

In order to apply dissipativity theory, we are required to have some prior
knowledge for the supply rate $S(\xi,\omega)$. IQCs is used to capture
features of the behavior of partially known components in a dynamical system
and have physical interpretation that dynamical system must satisfy some laws
of energy conservation. They can also be treated as some constraints that all
states $\xi$ and inputs $\omega$ or a set of external systems, i.e. a linear
dynamical system generated by $(\xi_{t},\omega_{t})$, must meet. Next, we
introduce a IQC which is particular useful for robust momentum method.

######  Proposition 23.

Suppose $f\in\mathcal{F}(m,L)$. Let $x_{\star}$ be the unique minimizer of $f$
and $g_{k}=\nabla f(y_{k})$. Given $\rho,\theta$ such that $0<\theta\leq 1$
and $0\leq\rho\leq 1$, and any sequence of points $y_{k}$, define
$\widetilde{y}_{k}=y_{k}-x_{\star}$, $g_{\theta}(x)=f(x)-f(x_{\star})-\theta
m/2\|x-x_{\star}\|^{2}$, and $q_{\theta}(y_{k})=(L-\theta
m)g(y_{k})-\|g_{k}\|/2$. Then, for all $k$,

  1. 1.

$q_{\theta}(y_{k})\geq 0$;

  2. 2.

$(g_{k}-\theta m\widetilde{y}_{k})^{\top}(L\widetilde{y}_{k}-g_{k})\geq
q_{\theta}(y_{k})$;

  3. 3.

$(g_{k}-\theta
m\widetilde{y}_{k})^{\top}(L(\widetilde{y}_{k}-\rho^{2}\widetilde{y}_{k-1})-(g_{k}-\rho^{2}g_{k-1}))\geq
q_{\theta}(y_{k})-\rho^{2}q_{\theta}(y_{k-1})$.

This proposition extends Lemma 3 in Cyrus et al. [2018].

##  Appendix C Proofs in Section 2

We first give a proof of Theorem 2, which is related to the proof in
Diakonikolas and Orecchia [2019]. However, we prove this theorem without the
lemma on discretization error. Moreover, in order to have a meaningful bound,
we need $G_{1}$ to be finite. This follows, for example, from Proposition 6.1
in Cohen et al. [2018].

###### Proof of Theorem 2.

Recall that

$\phi_{k}(x)=\sum_{i=1}^{k}\frac{a_{i}m}{2}\|x-x_{i}\|^{2}+\frac{m_{0}}{2}\|x-x_{0}\|^{2}.$

Then $\phi_{k}$ is $m_{k}$-smooth where $m_{k}=A_{k}m+m_{0}$. By convexity and
(8), we have

$A_{k-1}(f(x_{k})-f(y_{k-1}))\leq A_{k-1}\nabla
f(x_{k})^{\top}(x_{k}-y_{k-1})=a_{k}\nabla
f(x_{k})^{\top}(\nabla\phi_{k}^{\star}(z_{k-1})-x_{k}).$ (47)

Therefore, for the upper bound $U_{k}=f(y_{k})$, we have

$\begin{split}A_{k}U_{k}-A_{k-1}U_{k-1}=&a_{k}f(x_{k})+A_{k}(f(y_{k})-f(x_{k}))+A_{k-1}(f(x_{k})-f(y_{k-1}))\\\
\leq&a_{k}f(x_{k})+A_{k}(f(y_{k})-f(x_{k}))+a_{k}\nabla
f(x_{k})^{\top}(\nabla\phi_{k}^{\star}(z_{k-1})-x_{k}).\end{split}$ (48)

On the other hand, the lower bound can be expressed as

$\begin{split}L_{k}=\frac{1}{A_{k}}\sum_{i=1}^{k}a_{i}[f(x_{i})-\varepsilon_{i+1}^{\top}(x_{\star}-x_{i})]+\frac{m_{0}}{2}\|x_{\star}-x_{0}\|-\frac{1}{A_{k}}\phi_{k}^{\star}(z_{k})-\frac{1}{A_{k}}\sum_{i=1}^{k}a_{i}\omega_{i}^{\top}x_{i},\end{split}$
(49)

which yields

$\begin{split}A_{k}L_{k}-A_{k-1}L_{k-1}=a_{k}f(x_{k})-a_{k}\varepsilon_{k+1}^{\top}x_{\star}-a_{k}\nabla
f(x_{k})^{\top}x_{k}-\phi_{k}^{\star}(z_{k})+\phi_{k-1}^{\star}(z_{k-1}).\end{split}$
(50)

Combining (48) and (50), we get

$\begin{split}&A_{k}G_{k}-A_{k-1}G_{k-1}\\\
=&A_{k}U_{k}-A_{k-1}U_{k-1}-(A_{k}L_{k}-A_{k-1}L_{k-1})\\\
\leq&A_{k}(f(y_{k})-f(x_{k}))+a_{k}\varepsilon_{k+1}^{\top}x_{\star}+a_{k}\nabla
f(x_{k})^{\top}\nabla\phi_{k}^{\star}(z_{k-1})+\phi_{k}^{\star}(z_{k})-\phi_{k-1}^{\star}(z_{k-1})\\\
=&A_{k}(f(y_{k})-f(x_{k}))+a_{k}\varepsilon_{k+1}^{\top}x_{\star}+a_{k}\nabla
f(x_{k})^{\top}\nabla\phi_{k}^{\star}(z_{k-1})+\phi_{k}^{\star}(z_{k})-\phi_{k-1}^{\star}(z_{k-1})\\\
\leq&A_{k}(f(y_{k})-f(x_{k}))+a_{k}\varepsilon_{k+1}^{\top}(x_{\star}-\phi_{k}^{\star}(z_{k-1}))+(z_{k}-z_{k-1})^{\top}\nabla\phi_{k}^{\star}(z_{k-1})\\\
&+\phi_{k}^{\star}(z_{k})-\phi_{k}^{\star}(z_{k-1})\\\
\leq&-A_{k}\eta_{k}\left(1-\frac{L\eta_{k}}{2}\right)\|\omega_{k}\|^{2}+A_{k}\eta_{k}\varepsilon_{k+1}^{\top}\omega_{k}+a_{k}\varepsilon_{k+1}^{\top}(x_{\star}-\phi_{k}^{\star}(z_{k-1}))+\Delta_{\phi_{k}^{\star}}(z_{k},z_{k-1})\\\
=&-A_{k}\eta_{k}\left(1-\frac{L\eta_{k}}{2}\right)\|\omega_{k}\|^{2}+A_{k}\eta_{k}\varepsilon_{k+1}^{\top}\omega_{k}+a_{k}\varepsilon_{k+1}^{\top}(x_{\star}-\phi_{k}^{\star}(z_{k-1}))\\\
&+\Delta_{\phi_{k}}(\nabla\phi_{k}^{\star}(z_{k}),\nabla\phi_{k}^{\star}(z_{k-1}))\\\
\leq&-A_{k}\eta_{k}\left(1-\frac{L\eta_{k}}{2}\right)\|\omega_{k}\|^{2}+A_{k}\eta_{k}\varepsilon_{k+1}^{\top}\omega_{k}+a_{k}\varepsilon_{k+1}^{\top}(x_{\star}-\phi_{k}^{\star}(z_{k-1}))\\\
&+\frac{a_{k}^{2}}{2(A_{k}m+m_{0})}\|\omega_{k}\|^{2},\end{split}$ (51)

where we have used the duality of Bregman divergence (fact 20) and
$\phi_{k-1}^{\star}(z)\geq\phi_{k}^{\star}(z)$, and (10) and the third
inequality follows by

$\begin{split}&\left(\eta_{k}-\frac{L\eta_{k}^{2}}{2}\right)\|\omega_{k}\|^{2}\\\
=&-\left[\frac{L}{2}\|y_{k}-x_{k}\|^{2}+\omega_{k}^{\top}(y_{k}-x_{k})\right]\\\
=&f(x_{k})-\left[\frac{L}{2}\|y_{k}-x_{k}\|^{2}+\nabla
f(x_{k})^{\top}(y_{k}-x_{k})+f(x_{k})\right]-\varepsilon_{k+1}^{\top}(y_{k}-x_{k})\\\
\leq&f(x_{k})-f(y_{k})+\eta_{k}\varepsilon_{k+1}^{\top}\omega_{k}.\end{split}$
(52)

By taking expectation on both sides, we get

$\begin{split}\mathbb{E}\left[G_{k}-\frac{A_{k-1}}{A_{k}}G_{k-1}\right]\leq&-\left(\eta_{k}\left(1-\frac{L\eta_{k}}{2}\right)-\frac{a_{k}^{2}}{2A_{k}^{2}m}\right)\mathbb{E}\|\omega_{k}\|^{2}+\eta_{k}\mathbb{E}\|\varepsilon_{k+1}\|^{2}\\\
=&-\left(\eta_{k}\left(1-\frac{L\eta_{k}}{2}\right)-\frac{a_{k}^{2}}{2A_{k}^{2}m}\right)\mathbb{E}\|\nabla
f(x_{k})\|^{2}\\\
&+\left(\eta_{k}-\eta_{k}\left(1-\frac{L\eta_{k}}{2}\right)+\frac{a_{k}^{2}}{2A_{k}^{2}m}\right))\mathbb{E}\|\varepsilon_{k+1}\|^{2},\end{split}$
(53)

which completes the proof. ∎

Next we show the robustness property of iADA. The technique is similar to the
proof of ADA.

###### Proof of Theorem 3.

Define $v_{k}=\phi_{k}^{\star}(z_{k})$ and

$h_{k}(x)=\sum_{i=1}^{k}a_{i}\left[\omega_{i}^{\top}\left(x-x_{i}\right)+\frac{m}{2}\left\|x-x_{i}\right\|^{2}\right]+\frac{m_{0}}{2}\left\|x-x_{0}\right\|^{2}.$
(54)

Note that $v_{k}=\arg\min_{v}h_{k}(v)$ and

$h_{k}(v_{k})=h_{k-1}(v_{k})+a_{k}\omega_{k}^{\top}(v_{k}-x_{k})+a_{k}m/2\|v_{k}-x_{k}\|^{2}.$
(55)

Since the linear term does not affect the Bregman divergence, we have for all
$u$

$\begin{split}h_{k-1}(v_{k})-h_{k-1}(v_{k-1})&=\nabla
h_{k-1}(v_{k-1})^{\top}(u-v_{k-1})+\Delta_{h_{k-1}}(v_{k},v_{k-1})\\\
&\geq\Delta_{h_{k-1}}(v_{k},v_{k-1})\\\
&=\frac{m_{k-1}}{2}\|v_{k}-v_{k-1}\|^{2},\end{split}$ (56)

where we have used that $\nabla h_{k-1}(v_{k-1})^{\top}(u-v_{k-1})\geq 0$,
since $v_{k}=\arg\min_{v}h_{k}(v)$. Using (10), we have

$\phi_{k}^{\star}(z_{k-1})=\frac{m_{k-1}}{m_{k}}v_{k-1}+\frac{a_{k}}{m_{k}}x_{k}.$
(57)

Then by Jensen’s inequality, (55), (56) and (57) yield

$\begin{split}h_{k}(v_{k})-h_{k-1}(v_{k-1})\geq&\frac{m_{k-1}}{2}\|v_{k}-v_{k-1}\|^{2}+\frac{a_{k}m}{2}\|v_{k}-x_{k}\|^{2}+a_{k}\omega_{k}^{\top}(v_{k}-x_{k})\\\
\geq&\frac{m_{k}}{2}\|\phi_{k}^{\star}(z_{k})-\phi_{k}^{\star}(z_{k-1})\|^{2}+a_{k}\omega_{k}^{\top}(v_{k}-x_{k}).\end{split}$
(58)

Recall
$L_{k}=(1/A_{k})\left\\{\sum_{i=1}^{k}a_{i}\left[f\left(x_{i}\right)-\varepsilon_{i}^{\top}\left(x_{\star}-x_{i}\right)\right]+\frac{m_{0}}{2}\left\|x_{\star}-x_{0}\right\|+h_{k}(v_{k})\right\\}$.
Then we have

$\begin{split}A_{k}L_{k}-A_{k-1}L_{k-1}\geq&a_{k}f(x_{k})+a_{k}\nabla
f(x_{k})^{\top}(v_{k}-x_{k})\\\
&+\frac{m_{k}}{2}\|\phi_{k}^{\star}(z_{k})-\phi_{k}^{\star}(z_{k-1})\|^{2}-a_{k}\varepsilon_{k+1}^{\top}(x_{\star}-v_{k}).\end{split}$
(59)

On the other hand, for the upper bound $U_{k}=f(y_{k}),$ we obtain by
convexity and (12) that

$A_{k-1}(f(x_{k})-f(y_{k-1}))\leq a_{k}\nabla
f(x_{k})^{\top}(\nabla\phi_{k}^{\star}(z_{k-1})-x_{k}),$ (60)

and

$\begin{split}A_{k}U_{k}-A_{k-1}U_{k-1}&=a_{k}f(x_{k})+A_{k}(f(y_{k})-f(x_{k}))+A_{k-1}(f(x_{k})-f(y_{k-1}))\\\
&\leq a_{k}f(x_{k})+A_{k}(f(y_{k})-f(x_{k}))+a_{k}\nabla
f(x_{k})^{\top}(\nabla\phi_{k}^{\star}(z_{k-1})-x_{k}).\end{split}$ (61)

Combining (59) and (61) and (12) yields

$\begin{split}A_{k}G_{k}-A_{k-1}G_{k-1}\leq&A_{k}(f(y_{k})-f(x_{k}))+a_{k}\nabla
f(x_{k})^{\top}(\nabla\phi_{k}^{\star}(z_{k-1})-\nabla\phi_{k}^{\star}(z_{k}))\\\
&-\frac{m_{k}}{2}\|\phi_{k}^{\star}(z_{k})-\phi_{k}^{\star}(z_{k-1})\|^{2}+a_{k}\varepsilon_{k+1}^{\top}(x_{\star}-v_{k})\\\
=&A_{k}(f(y_{k})-f(x_{k}))-A_{k}\nabla f(x_{k})^{\top}(y_{k}-x_{k})\\\
&-\frac{m_{k}}{2}\|\phi_{k}^{\star}(z_{k})-\phi_{k}^{\star}(z_{k-1})\|^{2}+a_{k}\varepsilon_{k+1}^{\top}(x_{\star}-v_{k})\\\
\leq&\frac{A_{k}L}{2}\|y_{k}-x_{k}\|^{2}-\frac{m_{k}}{2}\|\phi_{k}^{\star}(z_{k})-\phi_{k}^{\star}(z_{k-1})\|^{2}+a_{k}\varepsilon_{k}^{\top}(x_{\star}-v_{k})\\\
=&\left(\frac{a_{k}^{2}L}{A_{k}}-\frac{m_{k}}{2}\right)\|\phi_{k}^{\star}(z_{k})-\phi_{k}^{\star}(z_{k-1})\|^{2}+a_{k}\varepsilon_{k+1}^{\top}(x_{\star}-v_{k})\\\
=&\left(\frac{a_{k}^{2}L}{2A_{k}}-\frac{m_{k}}{2}\right)\frac{a_{k}^{2}}{m_{k}^{2}}\|\omega_{k}\|^{2}+a_{k}\varepsilon_{k+1}^{\top}(x_{\star}-v_{k}),\end{split}$
(62)

where we have used the inequality of smoothness from Lemma 13 and (10)

Observe that the strong convexity parameter of $\phi_{k}$ is $mA_{k}+m_{0}$.
Define

$\widehat{v}_{k}=\nabla\phi_{k}^{\star}(z_{k}+a_{k}\varepsilon_{k+1})=\nabla\phi_{k}^{\star}(z_{k-1}-a_{k}\nabla
f(x_{k})).$

Then $\widehat{v}_{k}$ is independent of $\varepsilon_{k+1}$, and, using
strong convexity (Lemma 12), we have

$\begin{split}\mathbb{E}\left[a_{k}\varepsilon_{k+1}^{\top}(x_{\star}-v_{k})\right]=&\mathbb{E}\left[a_{k}\varepsilon_{k+1}^{\top}(x_{\star}-\widehat{v}_{k})\right]+\mathbb{E}\left[a_{k}\varepsilon_{k+1}^{\top}(\widehat{v}_{k}-v_{k})\right]\\\
\leq&\frac{a_{k}^{2}}{m_{k}}\mathbb{E}\|\varepsilon_{k+1}\|^{2}.\end{split}$

Therefore,

$\displaystyle\mathbb{E}\left[G_{k}-\frac{A_{k-1}}{A_{k}}G_{k-1}\right]$
$\displaystyle\leq$
$\displaystyle\left(\frac{a_{k}^{2}L}{2A_{k}^{2}}-\frac{m_{k}}{2A_{k}}\right)\frac{a_{k}^{2}}{m_{k}^{2}}\mathbb{E}\left(\|\nabla
f(x_{k})\|^{2}+\|\varepsilon_{k+1}\|^{2}\right)+\frac{a_{k}^{2}}{A_{k}m_{k}}\mathbb{E}\|\varepsilon_{k+1}\|^{2}$
$\displaystyle=$
$\displaystyle-\left(\frac{m_{k}}{2A_{k}}-\frac{a_{k}^{2}L}{2A_{k}^{2}}\right)\frac{a_{k}^{2}}{m_{k}^{2}}\mathbb{E}\|\nabla
f(x_{k})\|^{2}+\left(\frac{a_{k}^{2}}{A_{k}m_{k}}-\left(\frac{m_{k}}{2A_{k}}-\frac{a_{k}^{2}L}{2A_{k}^{2}}\right)\frac{a_{k}^{2}}{m_{k}^{2}}\right)\mathbb{E}\|\varepsilon_{k+1}\|^{2},$

and the theorem follows by setting $m_{0}=0$. ∎

To prove Theorem 4, we need the following proposition.

######  Proposition 24.

For the system (18), $f\in\mathcal{F}(m,L)$, and $0<\theta\leq 1$, $0<\rho<1$,
define $\widetilde{\kappa}=L/(\theta m)$,

$v_{k}=(1-\rho^{2})^{-1}((1-\rho^{2})x_{k}-\rho^{2}z_{k}),$

and set

$\eta=\widetilde{\kappa}(1-\rho)(1-\rho^{2}),\beta=\frac{\widetilde{\kappa}\rho^{3}}{\widetilde{\kappa}-1}.$

Then

$(g_{k}-\theta
m\widetilde{y}_{k})^{\top}(L(\widetilde{y}_{k}-\rho\widetilde{y}_{k-1})-(g_{k}-\rho^{2}g_{k-1}))\\\
+\lambda(\|v_{k+1}\|^{2}-\rho^{2}\|v_{k}\|^{2})+\nu\|g_{k}-\theta
m\widetilde{y}_{k}\|^{2}=0,$ (63)

where $\widetilde{y}_{k}=y_{k}-x_{\star}$, $g_{k}=\nabla f(y_{k})$,

$\lambda=\frac{(\theta
m)^{2}(\widetilde{\kappa}-\widetilde{\kappa}\rho^{2}-1)}{2\rho(1-\rho)(1-\rho^{2})^{2}},\quad\nu=\frac{(1+\rho)(1-\widetilde{\kappa}+2\widetilde{\kappa}\rho-\widetilde{\kappa}\rho^{2})}{2\rho}.$

###### Proof.

From the dynamic (18), we have

$g_{k-1}=(L/\eta)(\beta z_{k-1}-z_{k}).$

Thus,

$(L(\widetilde{y}_{k}-\widetilde{y}_{k-1})-(g_{k}-g_{k-1}))=L\frac{\eta+\beta-1}{\eta}z_{k}-g_{k}.$
(64)

Now (63) follows from direct calculation and the fact that
$f\in\mathcal{F}(\theta m,L)$. ∎

We are ready to prove Theorem 4.

###### Proof of Theorem 4.

Define $g_{k}=\nabla f(y_{k})$. From the dynamic (18), we know that

$g_{k-1}=(L/\eta)(\beta z_{k-1}-z_{k})-\varepsilon_{k}.$

Thus,

$((\widetilde{y}_{k}-\widetilde{y}_{k-1})-(g_{k}-g_{k-1}))=L\frac{\eta_{k-1}+\beta_{k-1}-1}{\eta}z_{k}-g_{k}+\varepsilon_{k}.$
(65)

Then we get the IQC for the stochastic setting:

$(g_{k}-m\widetilde{y}_{k})^{\top}(L(1+\eta+\beta)/\eta z_{k}-g_{k})\geq
q_{k}-\rho^{2}q_{k-1}-(g_{k}-m\widetilde{y}_{k})^{\top}\varepsilon_{k-1}.$
(66)

Proposition 24 states

$\lambda\begin{bmatrix}A^{\top}PA-\rho^{2}P&A^{\top}P\bar{B}\\\
\bar{B}^{\top}PA&\bar{B}^{\top}P\bar{B}\end{bmatrix}+(-X_{1}+\nu
U^{\top}U)\otimes I_{d}=0,$ (67)

where

$\displaystyle U_{1}=(-\theta m,-\theta
m\beta/\eta,1,0),V_{1}=(L,L\beta/\eta,-1,0),V_{2}=(0,L(\eta+\beta-1)/\eta,0),$

and $Y_{1}=(U^{\top}V_{1}+V_{1}^{\top}U)/2$,
$Y_{2}=(U^{\top}V_{2}+V_{2}^{\top}U)/2$,
$-X_{1}=(1-\rho^{2})Y_{1}+\rho^{2}Y_{2}$ and

$P=\begin{bmatrix}1&\rho^{2}/(1-\rho^{2})\\\
\rho^{2}/(1-\rho^{2})&\rho^{4}/(1-\rho^{2})^{2}\end{bmatrix}\otimes
I_{d},A=\begin{bmatrix}1&\beta\\\ \beta&0\end{bmatrix}\otimes
I_{d},\bar{B}=-\frac{\eta}{L}\begin{bmatrix}1&0\\\ 1&0\end{bmatrix}\otimes
I_{d}.$ (68)

To use the language of dissipativity theory, define

$\displaystyle X_{2}=\frac{\eta}{L}\begin{bmatrix}0&0&0&\beta-(1-\rho^{2})\\\
0&0&0&\beta\\\ 0&0&0&\eta/L\\\
\beta-(1-\rho^{2})&\beta&\eta/L&0\end{bmatrix},$

$\displaystyle X_{3}=\begin{bmatrix}0&0&m/2&0\\\ 0&0&m\beta/(2\eta)&0\\\
m/2&m\beta/(2\eta)&-1&0\\\ 0&0&0&0\end{bmatrix},$

$\displaystyle X_{4}=\begin{bmatrix}-L&-L\beta/\eta&0&0\\\
-L\beta/\eta&-L\beta^{2}/\eta^{2}&0&0\\\ 0&0&1&0\\\ 0&0&0&0\end{bmatrix}.$

Then

$U^{\top}U+2\theta
X_{3}+\frac{\theta^{2}m^{2}}{L}X_{4}=\left(1-2\theta\frac{m^{2}}{L^{2}}+\theta^{2}\right)\begin{bmatrix}0&0&0&0\\\
0&0&0&0\\\ 0&0&1&0\\\ 0&0&0&0\end{bmatrix}.$ (69)

Combining (67) and (69), we know

$\lambda\begin{bmatrix}A^{\top}PA-\rho^{2}P&A^{\top}PB\\\
B^{\top}PA&B^{\top}PB\end{bmatrix}-\left(X_{1}+X_{2}+2\theta
X_{3}+\frac{\theta^{2}m^{2}}{L}X_{4}\right)\otimes I_{d}\\\
=\begin{bmatrix}0&0&0&0\\\ 0&0&0&0\\\
0&0&-\nu\left(1-2\theta\frac{m^{2}}{L^{2}}+\theta^{2}\right)&0\\\
0&0&0&1-\nu\end{bmatrix}\otimes I_{d}\leq 0,$ (70)

where we use $\lambda a^{2}/L=1-\nu$. The theorem follows by Corollary 22 and
the conservation laws:

$\displaystyle\mathbb{E}\begin{bmatrix}x_{k}\\\ z_{k}\\\ g_{k}\\\
\varepsilon_{i}\end{bmatrix}\left(X_{3}\otimes
I_{d}\right)\begin{bmatrix}x_{k}\\\ z_{k}\\\ g_{k}\\\
\varepsilon_{i}\end{bmatrix}\leq 0\text{ (Strong convexity)},$
$\displaystyle\mathbb{E}\begin{bmatrix}x_{k}\\\ z_{k}\\\ g_{k}\\\
\varepsilon_{i}\end{bmatrix}\left(X_{4}\otimes
I_{d}\right)\begin{bmatrix}x_{k}\\\ z_{k}\\\ g_{k}\\\
\varepsilon_{i}\end{bmatrix}\leq 0\text{ (Strong smoothness)},$
$\displaystyle\mathbb{E}\begin{bmatrix}x_{k}\\\ z_{k}\\\ g_{k}\\\
\varepsilon_{i}\end{bmatrix}\left(X_{2}\otimes
I_{d}\right)\begin{bmatrix}x_{k}\\\ z_{k}\\\ g_{k}\\\
\varepsilon_{i}\end{bmatrix}=0\text{ (Unbiasedness)},$
$\displaystyle\mathbb{E}\begin{bmatrix}x_{k}\\\ z_{k}\\\ g_{k}\\\
\varepsilon_{i}\end{bmatrix}\left(-X_{1}\otimes
I_{d}\right)\begin{bmatrix}x_{k}\\\ z_{k}\\\ g_{k}\\\
\varepsilon_{i}\end{bmatrix}\leq-
q_{\theta}(y_{k})+\rho^{2}q_{\theta}(y_{k-1})\text{ (Momentum)},$

where $g_{\theta}(x)=f(x)-f(x_{\star})-\theta m/2\|x-x_{\star}\|^{2}$ and
$q_{\theta}(y_{k})=(L-\theta m)g(y_{k})-\|g_{k}\|/2$. ∎

We can relate the Lyapunov function of RMM to
$\mathbb{E}\|x_{k}-x_{\star}\|^{2}$ as follows. Suppose that

$\lambda
V(\xi_{k+1})+q_{\theta}(y_{k})\leq\rho^{2k}(V(\xi_{1})+q_{\theta}(y_{0}))+\frac{1-\nu}{1-\rho^{2}}\sigma^{2}.$
(71)

Letting $\widetilde{x}_{k}=x_{k}-x_{\star}$,
$(1-\rho^{2})v_{k}=\widetilde{x}_{k}-\rho^{2}\widetilde{x}_{k}$, we know
$\|v_{k}\|^{2}=V(\xi_{k})$ and

$\widetilde{x}_{k}=\rho^{2(k-1)}\widetilde{x}_{0}+(1-\rho^{2})\sum_{t=0}^{k-1}\rho^{2(k-t)}v_{t}.$
(72)

This gives us

$\begin{split}\|\widetilde{x}_{k}\|^{2}\leq&2\rho^{4(k-1)}\|\widetilde{x}_{0}\|^{2}+2(1-\rho^{2})^{2}k\sum_{t=0}^{k-1}\rho^{4(k-t)}\|w_{t}\|^{2}\\\
\leq&2\rho^{4(k-1)}\|\widetilde{x}_{0}\|^{2}+\rho^{2k}2(1-\rho^{2})^{2}k\sum_{t=0}^{k-1}\rho^{t}\left((V(\xi_{1})+q_{\theta}(y_{0}))+\frac{1-\nu}{1-\rho^{2}}\sigma^{2}\right)\\\
\leq&O(\rho^{k}+\sigma^{2}),\end{split}$ (73)

which implies $\mathbb{E}\|x_{k}-x_{\star}\|\leq O(\rho^{k}+\sigma^{2})$.

##  Appendix D Proofs in Section 3

We combine the property of robustness (defnition 1) with the growth condition
(22). We also show the growth condition for the case of finite sum, which is
common in the literature of SGD.

###### Proof of Corollary 6.

For ADA, $\delta n_{k}-m_{k}\leq 0$ becomes

$(1+\delta)\left(\frac{L\eta^{2}}{2}+\frac{a_{k}^{2}}{2A_{k}^{2}m}\right)\leq\eta.$

Letting

$\frac{a_{k}^{2}}{A_{k}^{2}}=mL\eta^{2},$

we have $(1+\delta)L\eta^{2}\leq\eta$, which yields

$\eta\leq\frac{1}{(1+\delta)L}.$

The first part that $r_{\text{ADA}}=1-\sqrt{\frac{m}{L(1+\delta)^{2}}}$
follows by choosing $\eta=\frac{1}{(1+\delta)L}$.

Let $\gamma_{k}=\frac{a_{k}}{A_{k}}$. Then, for iADA, $\delta n_{k}-m_{k}\leq
0$ becomes

$-(1+\delta)\left(\frac{m}{2}-\frac{\gamma_{k}^{2}L}{2}\right)\frac{\gamma_{k}^{2}}{m^{2}}+\delta\frac{\gamma_{k}^{2}}{m}\leq
0.$

Choosing $\gamma_{k}^{2}=\frac{m}{L}\frac{1-\delta}{1+\delta}$ to satisfy the
inequality, gives us

$r_{\text{iADA}}=\sqrt{\frac{m(1-\delta)}{L(1+\delta)}}.$ (74)

For RMM, $\delta n_{k}-m_{k}\leq 0$ is

$\delta\leq\frac{\nu}{(1-\nu)}\left(1-2\theta\frac{m^{2}}{L^{2}}+\theta^{2}\right),$
(75)

and the right hand side is form 0 to 1 when $0<\theta<1$. To characterize the
robustness, we use the sufficient condition of $\delta n_{k}-m_{k}\leq 0$,
since $(1+\rho)/(\rho(1-\nu))>1$. Letting $\theta=1-\delta$, we have

$\frac{\delta(1-\delta)}{1-2(m^{2}/L^{2})(1-\delta)+(1-\delta)^{2}}\leq(1-\delta)-\kappa+2\kappa\rho-\kappa\rho^{2}.$
(76)

Solving this for $\rho$ and $\rho=1-r$ implies

$r_{\text{RMM}}=\sqrt{\frac{m(1-\delta)}{L}\left(1-\frac{\delta}{1-2(m^{2}/L^{2})(1-\delta)+(1-\delta)^{2}}\right)},$
(77)

provided that

$1-\frac{\delta}{1-2(m^{2}/L^{2})(1-\delta)+(1-\delta)^{2}}>0.$ (78)

∎

###### Proof of Proposition 7.

From the smoothness and $L_{\max}=\max_{i}L_{i}$, we have

$\begin{split}&\mathbb{E}\|\widehat{\nabla}f(x)-\nabla
f(x)\|^{2}=\mathbb{E}\|\widehat{\nabla}f(x)\|^{2}-\|\nabla f(x)\|^{2}\\\
\leq&\frac{1}{b^{2}}\sum_{i=1}^{b}\left[2\mathbb{E}\|\nabla f_{i}(x)-\nabla
f_{i}(x_{\star})\|^{2}+2\mathbb{E}\|\nabla
f_{i}(x_{\star})\|^{2}\right]-\|\nabla f(x)\|^{2}\\\
\leq&\frac{4}{b}L_{\max}\|f(x)-f(x_{\star})\|^{2}+\frac{2}{b}\mathbb{E}\|f_{i}(x_{\star})\|^{2}-\|\nabla
f(x)\|^{2}\\\ \leq&\left(\frac{4}{b}\frac{L_{\max}}{m}-1\right)\|\nabla
f(x)\|^{2}+\frac{2}{b}\frac{1}{n}\sum_{i=1}^{n}\|f_{i}(x_{\star})\|^{2}.\end{split}$
(79)

∎

##  Appendix E Proofs in Section 4

We prove a faster convergence rate for ADA from Lemma 8 and establish a new
result for recursion.

###### Proof of Theorem 9.

For ADA, by Theorem 2, choosing $a_{k}^{2}/A_{k}^{2}=mL\eta^{2}$, we have

$\mathbb{E}G_{k+1}\leq(1-\sqrt{mL}\eta_{k})\mathbb{E}G_{k}-\eta_{k}(1-(1+\delta)L\eta_{k})\mathbb{E}\|\nabla
f(x_{k})\|^{2}+L\eta_{k}^{2}\sigma^{2}.$ (80)

Setting $e_{k}=\mathbb{E}G_{k}$, $s_{k}=\mathbb{E}\|\nabla f(x_{k})\|^{2}$,
$d=2(1+\delta)L\geq\sqrt{mL}=a$, $b=(1-(1+\delta)L\eta)$, $c=\sigma^{2}$,
$\eta_{k}=\eta$ and applying lemma 8, we get that there exist a $\eta<1/d$
such that $b>(1-(1+\delta)L/d)=0.5>0$ and

$\frac{b}{W_{K}}\sum_{k=1}^{K}w_{k}s_{k}+ae_{K+1}=\widetilde{\mathcal{O}}\left(de_{1}\exp\left[-\frac{aK}{d}\right]+\frac{c}{aK}\right).$
(81)

Moreover, it follows from Jensen’s inequality and convexity that

$\begin{split}\mathbb{E}[f(\bar{x}_{K})-f(x_{\star})]\leq&\frac{1}{W_{K}}\sum_{k=1}^{K}w_{k}\mathbb{E}\left[f(x_{k})-f(x_{\star})\right]\\\
\leq&\frac{1}{2mb}\frac{b}{W_{K}}\sum_{k=1}^{K}w_{k}\mathbb{E}\|\nabla
f(x_{k})\|^{2}\\\
=&\widetilde{\mathcal{O}}\left(\frac{d}{m}e_{1}\exp\left[-\frac{aK}{d}\right]+\frac{c}{aK}\right),\end{split}$
(82)

where $\bar{x}_{K}=\frac{1}{W_{K}}\sum_{k=1}^{K}w_{k}x_{k}$. The second
statement follows using a similar argument. ∎

###### Proof of Proposition 10.

Using (36) and (35) gives for $k\geq(1-\alpha K)+1$

$\begin{split}bs_{k}w_{k}&\leq\frac{w_{k}\left(1-ar_{k}\right)e_{t}}{r_{k}}-\frac{w_{k}e_{k+1}}{r_{k}}+cr_{k}w_{k}\\\
&=a(k_{0}+k-1-(1-\alpha)K)e_{t}-a(k_{0}+k-(1-\alpha)K)e_{t+1}+\frac{c}{ak}.\end{split}$
(83)

Then we have a telescoping sum

$\begin{split}\frac{b}{W_{K}}\sum_{t=1}^{K}w_{k}s_{k}+\frac{a(k_{0}+\alpha
K)}{W_{T}}e_{K+1}\leq&\frac{ak_{0}e_{(1-\alpha)K+1}}{W_{K}}+\frac{c}{aW_{K}}\sum_{k=(1-\alpha)K+1}^{K}\frac{1}{k}\\\
\leq&\frac{ak_{0}}{\alpha K}e_{(1-\alpha)}+\frac{c}{a\alpha
K}\log\left(\frac{1}{1-\alpha}\right),\end{split}$ (84)

where we have used that
$\sum_{k=(1-\alpha)K}^{K}\frac{1}{k}\leq\log\left(\frac{1}{1-\alpha}\right)$
and $W_{K}=\alpha K$. Moreover, for the first $(1-\alpha)K$ of the iterates,
we have

$e_{(1-\alpha)}\leq
e_{0}\exp\left[-\frac{a(1-\alpha)K}{d}\right]+\frac{c}{ad}.$ (85)

The proposition follows by combining (84) and (85) and

$\begin{split}&\frac{b}{W_{K}}\sum_{t=1}^{K}w_{k}s_{k}+\frac{a(k_{0}+\alpha
K)}{\alpha K}e_{K+1}\\\ \leq&\frac{ak_{0}}{\alpha
K}\left(e_{0}\exp\left[-\frac{a(1-\alpha)K}{d}\right]+\frac{c}{ad}\right)+\frac{c}{a\alpha
K}\log\left(\frac{1}{1-\alpha}\right)\\\
\leq&\frac{d}{\alpha}e_{0}\exp\left[-\frac{a(1-\alpha)K}{d}\right]+\frac{c}{Ka\alpha}\left(1+\log\left(\frac{1}{1-\alpha}\right)\right).\end{split}$
(86)

∎

###### The proof of Theorem 11.

For ADA, by theorem 2, choosing $a_{k}^{2}/A_{k}^{2}=mL\eta^{2}$, we have

$\mathbb{E}G_{k+1}\leq(1-\sqrt{mL}\eta_{k})\mathbb{E}G_{k}-\eta_{k}(1-(1+\delta)L\eta_{k})\mathbb{E}\|\nabla
f(x_{k})\|^{2}+L\eta_{k}^{2}\sigma^{2}.$ (87)

Setting $e_{k}=\mathbb{E}G_{k}$, $s_{k}=\mathbb{E}\|\nabla f(x_{k})\|^{2}$,
$d=2(1+\delta)L\geq\sqrt{mL}=a$, $b=(1-(1+\delta)L\eta)$,
$c=\sigma^{2}$,$\eta_{k}=\eta$ and applying Proposition 10, we get
$b\geq(1-(1+\delta)L/d)>0.5>0$ and

$\frac{b}{\alpha
T}\sum_{k=1}^{K}w_{k}s_{k}\leq\frac{2(1+\delta)L}{\alpha}e_{0}\exp\left[-\frac{(1-\alpha)}{2(1+\delta)}\sqrt{\frac{m}{L}}K\right]+\frac{\sigma^{2}}{K\sqrt{mL}\alpha}\left(1+\log\left(\frac{1}{1-\alpha}\right)\right).$
(88)

This theorem follows from Jensen’s inequality and convexity that

$\begin{split}\mathbb{E}[f(\bar{x}_{K})-f(x_{\star})]\leq&\frac{1}{W_{K}}\sum_{k=1}^{K}w_{k}\mathbb{E}\left[f(x_{k})-f(x_{\star})\right]\\\
\leq&\frac{1}{2mb}\frac{b}{W_{K}}\sum_{k=1}^{K}w_{k}\mathbb{E}\|\nabla
f(x_{k})\|^{2}.\end{split}$ (89)

∎

##  Appendix F Variance-Reduced Stochastic Gradient Methods

We discuss how variance-reduced stochastic gradient methods satisfy the growth
condition. Starting with Katyusha [Allen-Zhu, 2017a, 2018a] and followed by
many others [Allen-Zhu, 2017b, 2018b, Zhou et al., 2018, Lan et al., 2019], a
family of variance reduced stochastic gradient algorithms have recently
emerged that achieve the optimal convergence rates using negative momentum.
Murata and Suzuki [2017] developed a method incorporating the “double
acceleration” technique to accelerate SVRG, achieving an optimal convergence
rate for non-strongly convex and strongly convex objectives in non-mini-batch
settings. Zhou [2018a] proposed a directly accelerated variant of SAGA using a
novel Sampled Negative Momentum, which achieves the best-known oracle
complexity for strongly convex problems. However, numerical experiments and
theoretical results in Driggs et al. [2019] shown that negative momentum is
unnecessary to achieve acceleration and established a universal acceleration
framework that allows all popular variance-reduced methods to achieve
accelerated convergence rates, which is closely related to our general growth
condition.

Consider the convex minimization problem in finite-sum setting,

$\min f(x):=\frac{1}{n}\sum_{i=1}^{n}f_{i}(x),$ (90)

where $f_{i}$ is $L_{i}$-smooth. An estimator of gradient
$\widehat{\nabla}f(y_{k})$ satisfies General Growth Condition (GGC) if it is
unbiased and there exist $c_{1},c_{2},r$ and a sequence $\mathcal{V}_{k}$,
such that $0\leq r<1$,

$\mathbb{E}\|\widehat{\nabla}f(y_{k+1})-\nabla
f(y_{k+1})\|^{2}\leq\frac{c_{1}}{n}\sum_{i=i}^{n}\mathbb{E}\|\nabla
f_{i}(y_{k+1})-\nabla f_{i}(x_{\star})\|^{2}+\mathcal{V}_{k},$ (91)
$\mathcal{V}_{k}\leq\frac{c_{2}}{n}\sum_{i=i}^{n}\mathbb{E}\|\nabla
f_{i}(y_{y+1})-\nabla f_{i}(x_{\star})\|^{2}+(1-r)\mathcal{V}_{k-1}.$ (92)

This definition and proofs is similar to Driggs et al. [2019], but our
definition is closely related to the growth condition. We are ready to prove
the convergence theorem for accelerating variance-reduced stochastic gradient
methods.

######  Proposition 25.

Suppose GGC holds for $\widehat{\nabla}f(y_{k})$. For a sequence $s_{k}>0$
such that $s_{t}(1-r)\leq s_{t-1}(1-r/2)$, we have

$\sum_{t=1}^{k}s_{t}\mathbb{E}\|\widehat{\nabla}f(x_{t})-\nabla
f(x_{t})\|^{2}\leq\sum_{t=1}^{k}\left(c_{1}+\frac{2c_{2}}{r}\right)s_{t}\sum_{i=1}^{n}\mathbb{E}\|\nabla
f_{i}(x_{t})-\nabla f_{i}(x_{\star})\|^{2}.$ (93)

###### Proof of Proposition 25.

The recursive expression of (92) yields

$\begin{split}\sum_{t=1}^{k}s_{t}\mathcal{V}_{t}\leq&c_{2}\sum_{t=1}^{k}\sum_{j=1}^{t}s_{t}(1-r)^{t-j}\sum_{i=1}^{n}\mathbb{E}\|\nabla
f_{i}(x_{j})-\nabla f_{i}(x_{\star})\|\\\
=&c_{2}\sum_{j=1}^{k}\sum_{t=j}^{k}s_{t}(1-r)^{t-j}\sum_{i=1}^{n}\mathbb{E}\|\nabla
f_{i}(x_{j})-\nabla f_{i}(x_{\star})\|\\\
\leq&c_{2}\sum_{j=1}^{k}\sum_{t=j}^{k}s_{j}\left(1-\frac{r}{2}\right)^{t-j}\sum_{i=1}^{n}\mathbb{E}\|\nabla
f_{i}(x_{j})-\nabla f_{i}(x_{\star})\|\\\
\leq&c_{2}\sum_{j=1}^{k}\frac{2s_{j}}{r}\sum_{i=1}^{n}\mathbb{E}\|\nabla
f_{i}(x_{j})-\nabla f_{i}(x_{\star})\|,\end{split}$ (94)

by exchanging the summation and the assumption $s_{t}(1-r)\leq s_{t-1}(1-r/2)$
and $\sum_{t=j}^{k}(1-r/2)^{t-j}<2/r$. This implies the proposition. ∎

Our main theorem for variance reduced methods is as follows.

######  Theorem 26.

Suppose that an algorithm $\mathcal{A}$ converges robustly with constants
$(\rho,R,N)$ and a Lyapunov function $V$, the general growth condition (91)
and (92) holds for constants $(c_{1},c_{2},r)$ such that

$L_{\text{max}}N\left(c_{1}+\frac{2c_{2}}{r}\right)-mR<0.$ (95)

Assume that

$\quad 1-r\leq\rho(1-r/2).$ (96)

Then

$\mathbb{E}V(\xi_{k+1})\leq\rho^{k}\mathbb{E}V(\xi_{1}).$ (97)

###### The proof of Theorem 26.

The smoothness and convexity of $f_{i}$ imply

$\frac{1}{n}\sum_{i=1}^{n}\frac{1}{2L_{i}}\|\nabla f_{i}(\zeta_{k})-\nabla
f_{i}(x_{\star})\|^{2}\leq\frac{1}{n}\sum_{i=1}^{n}\left[f_{i}(\zeta_{k})-f_{i}(x_{\star})\right]=f(\zeta_{k})-f(x_{\star}).$
(98)

The strong convexity of $f$ yields

$\|\nabla f(\zeta_{k})\|^{2}\geq 2m(f(\zeta_{k})-f(x_{\star})).$ (99)

By the definition of robust convergence, we have

$\begin{split}\mathbb{E}V(\xi_{k+1})\leq&\rho\mathbb{E}V(\xi_{k})-R\mathbb{E}\|\nabla
f(\zeta_{k})\|^{2}+N\mathbb{E}\|\varepsilon_{k}\|^{2}\\\
\leq&\rho^{k}\mathbb{E}V(\xi_{1})-R\sum_{t=1}^{k}\rho^{k-t}\mathbb{E}\|\nabla
f(\zeta_{t})\|^{2}+N\rho^{k}\sum_{t=1}^{k}\rho^{-t}\mathbb{E}\|\widehat{\nabla}f(\zeta_{t})-\nabla
f(\zeta_{t})\|^{2}\\\
\leq&\rho^{k}\mathbb{E}V(\xi_{1})-2mR\sum_{t=1}^{k}\rho^{k-t}\mathbb{E}\left[f(\zeta_{t})-f(x_{\star})\right]\\\
&+N\rho^{k}\sum_{t=1}^{k}\left(c_{1}+\frac{2c_{2}}{r}\right)\rho^{-t}\mathbb{E}\left[\frac{1}{n}\sum_{i=1}^{n}\|\nabla
f_{i}(\zeta_{t})-\nabla f_{i}(x_{\star})\|^{2}\right]\\\
\leq&\rho^{k}\mathbb{E}V(\xi_{1})-\sum_{t=1}^{k}2mR\rho^{k-t}\mathbb{E}\left[f(\zeta_{t})-f(x_{\star})\right]\\\
&+\sum_{t=1}^{k}2L_{\text{max}}N\left(c_{1}+\frac{2c_{2}}{r}\right)\rho^{k-t}\mathbb{E}\left[f(\zeta_{t})-f(x_{\star})\right],\end{split}$
(100)

where we have used Proposition 25 and (99) and (98), and
$L_{\text{max}}=\max_{i}{L_{i}}$. This theorem follows by the assumption that

$L_{\text{max}}N\left(c_{1}+\frac{2c_{2}}{r}\right)-mR<0.$ (101)

∎

Two population variance reduction methods, SAGA and SVRG, satisfy GGC.

######  Proposition 27.

Consider SAGA:

$\widehat{\nabla}^{\text{SAGA}}f(y_{k+1})=\frac{1}{b}\left(\sum_{j\in
J_{k}}\nabla f_{j}(y_{k+1})-\nabla
f_{j}(\phi_{k}^{j})\right)+\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(\phi_{k}^{i}),$ (102)

and $\phi_{k+1}^{j}=y_{k+1}\text{ for }j\in J_{k}$ where $J_{k}$ is sampled
uniformly in $\\{1,\dots,n\\}$ with size $b$ and replacement. Then SAGA
satisfies GGC (91) and (92) with

$c_{1}=\frac{2}{b},c_{2}=\frac{2}{n},r=\frac{b}{n},\mathcal{V}=\frac{2}{bn}\sum_{i=1}^{n}\mathbb{E}\left\|\nabla
f_{i}(\phi_{k}^{i})-\nabla f_{i}(x_{\star})\right\|^{2}.$ (103)

###### Proof of Proposition 27.

Note that

$\begin{split}&\mathbb{E}_{J_{k}}\|\widehat{\nabla}f(y_{k+1})-\nabla
f(y_{k+1})\|^{2}\\\ \leq&\mathbb{E}_{J_{k}}\left\|\frac{1}{b}\left(\sum_{j\in
J_{k}}\nabla f_{j}(y_{k+1})-\nabla f_{j}(\phi_{k}^{j})\right)-\left[\nabla
f(y_{k+1})-\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(\phi_{k}^{i})\right]\right\|^{2}\\\
\leq&\frac{1}{bn}\sum_{i=1}^{n}\mathbb{E}_{J_{k}}\left\|\nabla
f_{i}(y_{k+1})-\nabla f_{i}(x_{\star})+\nabla f_{i}(x_{\star})-\nabla
f_{i}(\phi_{k}^{i})\right\|^{2}\\\
\leq&\frac{2}{bn}\sum_{i=1}^{n}\mathbb{E}_{J_{k}}\left\|\nabla
f_{i}(y_{k+1})-\nabla
f_{i}(x_{\star})\right\|^{2}+\frac{2}{bn}\sum_{i=1}^{n}\mathbb{E}_{J_{k}}\left\|\nabla
f_{i}(\phi_{k}^{i})-\nabla f_{i}(x_{\star})\right\|^{2},\end{split}$ (104)

where $\mathbb{E}_{J_{k}}[\cdot]=\mathbb{E}[\cdot|\mathcal{G}_{k}]$ and we use
the equality $\mathbb{E}\|X-\mathbb{E}X\|^{2}\leq\mathbb{E}\|X\|^{2}$. We also
have

$\begin{split}&\mathbb{E}_{J_{k}}\sum_{i=1}^{n}\|\nabla
f_{i}(\phi_{k}^{i})-\nabla f_{i}(x_{\star})\|^{2}\\\
=&\mathbb{E}_{J_{k}}\sum_{i\in J_{k}}\|\nabla f_{i}(\phi_{k}^{i})-\nabla
f_{i}(x_{\star})\|^{2}+\mathbb{E}_{J_{k}}\sum_{i\notin J_{k}}\|\nabla
f_{i}(\phi_{k}^{i})-\nabla f_{i}(x_{\star})\|^{2}\\\
=&\frac{b}{n}\sum_{i=1}^{n}\|\nabla f_{i}(y_{k+1})-\nabla
f_{i}(x_{\star})\|^{2}+\left(1-\frac{b}{n}\right)\sum_{i=1}^{n}\|\nabla
f_{i}(\phi_{k-1}^{i})-\nabla f_{i}(x_{\star})\|^{2}.\end{split}$ (105)

Thus,

$c_{1}=\frac{2}{b},c_{2}=\frac{2}{n},r=\frac{b}{n},\mathcal{V}=\frac{2}{bn}\sum_{i=1}^{n}\mathbb{E}\left\|\nabla
f_{i}(\phi_{k}^{i})-\nabla f_{i}(x_{\star})\right\|^{2}.$ (106)

It is not hard to see the estimations are unbiased. ∎

######  Proposition 28.

Consider a variant of SVRG: A random variable $I_{k}$ is 0 with probability
$1-1/p$ and 1 with probability $1/p$ and define

$\begin{split}\widehat{\nabla}^{\text{SVRG}}f(y_{k+1})=&\begin{cases}\frac{1}{b}\left(\sum_{j\in
J_{k}}\nabla f_{j}(y_{k+1})-\nabla f_{j}(\bar{y}_{k})\right)+\nabla
f(\bar{y}_{k})&\text{ if $I_{k}=0$ }\\\ \nabla f(y_{k+1})&\text{ if $I_{k}=1$
}\end{cases},\\\ \bar{y}_{k+1}=&\begin{cases}\bar{y}_{k}&\text{ if $I_{k}=0$
}\\\ y_{k+1}&\text{ if $I_{k}=1$ }\end{cases},\end{split}$ (107)

where $J_{k}$ is sampled uniformly in $\\{1,\dots,n\\}$ with size $b$ and
replacement. Then SVRG satisfies GGC (91) and (92) with

$c_{1}=\frac{2(1-1/p)}{b},c_{2}=\frac{2}{bp}\left(1-\frac{1}{p}\right),r=\frac{1}{p},$
(108)

and

$\mathcal{V}=\frac{2(1-1/p)}{bn}\sum_{i=1}^{n}\left\|\nabla
f_{i}(\bar{y}_{k})-\nabla f_{i}(x_{\star})\right\|^{2}.$ (109)

###### Proof of Proposition 28.

Following the same argument as in the the proof of Proposition 27, we have

$\begin{split}&\mathbb{E}_{J_{k},I_{k}}\|\widehat{\nabla}f(y_{k+1})-\nabla
f(y_{k+1})\|^{2}\\\
\leq&\frac{1-1/p}{bn}\sum_{i=1}^{n}\mathbb{E}_{J_{k},I_{k}}\left\|\nabla
f_{i}(y_{k+1})-\nabla f_{i}(x_{\star})+\nabla f_{i}(x_{\star})-\nabla
f_{i}(\bar{y}_{k})\right\|^{2}\\\
\leq&\frac{2(1-1/p)}{bn}\sum_{i=1}^{n}\mathbb{E}_{J_{k},I_{k}}\left\|\nabla
f_{i}(y_{k+1})-\nabla f_{i}(x_{\star})\right\|^{2}\\\
&+\frac{2(1-1/p)}{bn}\sum_{i=1}^{n}\mathbb{E}_{J_{k},I_{k}}\left\|\nabla
f_{i}(\bar{y}_{k})-\nabla f_{i}(x_{\star})\right\|^{2},\end{split}$ (110)

where $\mathbb{E}_{J_{k},I_{k}}[\cdot]=\mathbb{E}[\cdot|\mathcal{G}_{k}]$.
Note also that

$\begin{split}&\mathbb{E}_{I_{k-1}}\left\|\nabla f_{i}(\bar{y}_{k})-\nabla
f_{i}(x_{\star})\right\|^{2}\\\ =&\frac{1}{p}\|\nabla f_{i}(y_{k})-\nabla
f_{i}(x_{\star})\|+\left(1-\frac{1}{p}\right)\|\nabla
f_{i}(\bar{y}_{k-1})-\nabla f_{i}(x_{\star})\|.\end{split}$ (111)

Thus,

$c_{1}=\frac{2(1-1/p)}{b},c_{2}=\frac{2}{bp}\left(1-\frac{1}{p}\right),r=\frac{1}{p},$
(112)

and

$\mathcal{V}=\frac{2(1-1/p)}{bn}\sum_{i=1}^{n}\left\|\nabla
f_{i}(\bar{y}_{k})-\nabla f_{i}(x_{\star})\right\|^{2}.$ (113)

It is not hard to see the estimations are unbiased. ∎

If we choose $p=b/n$, then SAGA and SVRG have similar constants for GGC. We
think there are more variance reduction methods such as Finito [Defazio et
al., 2014], MISO [Mairal, 2015], SDCA [Shalev-Shwartz and Zhang, 2013] that
can be applied to this framework. Also, it is possible to extend to other
incremental gradient algorithms [Hanzely et al., 2018, Gower et al., 2018] and
biased methods like SAG [Schmidt et al., 2017] and SARAH [Nguyen et al., 2017,
Fang et al., 2018].

Assume that $\rho\geq(1+r/2)^{-1}$. We get (96) since

$(1+r/2)(1-r)\leq(1+\frac{r}{2})(1-r)\leq 1-\frac{r}{2}.$ (114)

For SAGA,

$c_{1}+\frac{x_{2}}{r}=\frac{4}{b}.$ (115)

Then we apply this to ADA and obtain

$\rho\geq
1-\sqrt{\frac{m}{L}}\frac{b}{b+\kappa}\geq\left(1+\sqrt{\frac{m}{L}}\frac{b}{b+\kappa}\right)^{-1}.$
(116)

Combining two low bounds yield

$\rho\geq\left(1+\min\left\\{1+\sqrt{\frac{m}{L}}\frac{b}{b+\kappa},\frac{b}{2n}\right\\}\right)^{-1}.$
(117)

##  Appendix G More discussions on Accelerated SGD for least square regression

Jain et al. [2018] proposed two moment assumptions that

$\displaystyle\mathbb{E}[a^{\top}aaa^{\top}]<C_{1}\Sigma,\quad\mathbb{E}[a^{\top}\Sigma^{-1}aa^{\top}a]<C_{2}\Sigma,$
(118)

where $\Sigma=\mathbb{E}[aa^{\top}]$. The former states the co-coercivity
(smoothness) that ensures SGD converges and is a the common assumption for SGD
with constant-step size [Flammarion and Bach, 2017, Défossez and Bach, 2015,
Bach and Moulines, 2013, Dieuleveut et al., 2017]. The latter is called
statistical condition and governs how many samples $a_{i}\sim\mathcal{D}$ are
required such that the empirical covariance is spectrally close, i.e.
$\Sigma/c<\frac{1}{n}a_{i}a_{i}^{\top}<c\Sigma$. See Hsu et al. [2014] for
derivation of matrix concentration inequalities. Here we use a different
prospective to understand the moment condition and accelerated SGD which is
close related to growth condition.

If we assume $a$ is normal distributed, $a\sim\mathcal{N}(0,\Sigma)$, it is
well-known [Tracy and Sultan, 1993] that

$\mathbb{E}(a^{\top}Aa)(a^{\top}Ba)=\mathop{\mathrm{tr}}(A\Sigma)\mathop{\mathrm{tr}}(B\Sigma)+2\mathop{\mathrm{tr}}(A\Sigma
B\Sigma),$ (119)

for all symmetric $A,B$, yielding

$\begin{split}\mathbb{E}\|\widehat{\nabla}f(x)-\nabla
f(x)\|^{2}=&\mathop{\mathrm{tr}}((x-x_{\star})(x-x_{\star})^{\top}\Sigma)\mathop{\mathrm{tr}}(\Sigma)\\\
&+2\mathop{\mathrm{tr}}((x-x_{\star})(x-x_{\star})^{\top}\Sigma^{2})-\|\nabla
f(x)\|^{2}\\\ \leq&\left(\frac{dL}{m}+1\right)\|\nabla f(x)\|^{2}.\end{split}$
(120)

This does not implies acceleration and variance reduction or mini-batch are
needed for acceleration. However, if we use different norm, then

$\|\widehat{\nabla}f(x)\|_{\Sigma^{-1}}\leq(2+d)\|\nabla
f(x)\|_{\Sigma^{-1}}.$ (121)

This can incorporate with the potential function
$\|y_{k}-x_{\star}\|^{2}+\|\phi_{k}^{\star}(z_{k})-x_{\star}\|^{2}/m$ for ADA
to prove an accelerated convergence bound. See Lemma 4 and Appendix D in Jain
et al. [2018].

Note that the assumption of the normal distribution is not too restricted
since (118) means the fourth moment is dominated by the second moment.

##  Appendix H Optimal Averaging Schemes and Decreasing Stepsizes for iADA

By the proof of Theorem 3, letting $a_{k}^{2}/A_{k}^{2}=\gamma_{k}^{2}$,
$g_{k}=\mathbb{E}\|\nabla f(x_{k})\|^{2}$, we have

$\begin{split}\mathbb{E}G_{k+1}\leq&(1-\gamma_{k})\mathbb{E}G_{k}-\frac{\gamma_{k}^{2}}{m^{2}}\left(\frac{m}{2}-\frac{\gamma_{k}^{2}L}{2}\right)\mathbb{E}\|\nabla
f(x_{k})\|^{2}\\\
&+\left[\frac{\gamma_{k}^{2}}{m}-\left(\frac{m}{2}-\frac{\gamma_{k}^{2}L}{2}\right)\frac{\gamma^{2}}{m^{2}}\right](\delta
g_{k}+\sigma^{2})\\\
\leq&(1-\gamma_{k})\mathbb{E}G_{k}+\left[-(1+\delta)\left(\frac{m}{2}-\frac{\gamma_{k}^{2}L}{2}\right)\frac{\gamma_{k}^{2}}{m^{2}}+\delta\frac{\gamma_{k}^{2}}{m}\right]g_{k}\\\
&+\left[\frac{\gamma_{k}^{2}}{m}-\left(\frac{m}{2}-\frac{\gamma_{k}^{2}L}{2}\right)\frac{\gamma_{k}^{2}}{m^{2}}\right]\sigma^{2}.\end{split}$
(122)

If $\gamma_{k}^{2}\leq\frac{m}{L}\frac{1-\delta}{1+\delta}$, we have

$-(1+\delta)\left(\frac{m}{2}-\frac{\gamma_{k}^{2}L}{2}\right)\frac{\gamma_{k}^{2}}{m^{2}}+\delta\frac{\gamma_{k}^{2}}{m}\leq
0.$

Hence, we can rewrite (122) as

$\mathbb{E}G_{k+1}\leq\left(1-\frac{\gamma_{k}}{2}\right)\mathbb{E}G_{k}-\frac{\gamma_{k}}{2}\mathbb{E}G_{k}+\frac{\gamma_{k}^{2}\sigma^{2}}{m},$
(123)

which is the form of (36). Then we can apply same technique in proof of
Theorem 9 and Theorem 11.