# On uniform boundedness properties of SGD
and its momentum variants

Xiaoyu Wang
KTH - Royal Institute of Technology
Stockholm, Sweden
<EMAIL_ADDRESS>
&Mikael Johansson
KTH - Royal Institute of Technology
Stockholm, Sweden
<EMAIL_ADDRESS>

###### Abstract

A theoretical, and potentially also practical, problem with stochastic
gradient descent is that trajectories may escape to infinity. In this note, we
investigate uniform boundedness properties of iterates and function values
along the trajectories of the stochastic gradient descent algorithm and its
important momentum variant. Under smoothness and $R$-dissipativity of the loss
function, we show that broad families of step-sizes, including the widely used
step-decay and cosine with (or without) restart step-sizes, result in
uniformly bounded iterates and function values. Several important applications
that satisfy these assumptions, including phase retrieval problems, Gaussian
mixture models and some neural network classifiers, are discussed in detail.
We further extend the uniform boundedness of SGD and its momentum variant
under the generalized dissipativity for the functions whose tails grow slower
than quadratic functions. This includes some interesting applications, for
example, Bayesian logistic regression and logistic regression with $\ell_{1}$
regularization.

_K_ eywords Stochastic gradient descent $\cdot$ Dissipativity $\cdot$ Uniform
boundedness

##  1 Introduction

We consider the stochastic optimization problem of minimizing a (possibly non-
convex) function $f$

$\displaystyle\underset{x}{\min}\;f(x)=\mathbb{E}_{\xi\approx\Xi}[f(x;\xi)].$
(1)

Here, $\xi$ is a random variable drawn from the unknown probability
distribution $\Xi$ and $f(x;\xi)$ is the instantaneous loss function over the
variable $x$. We assume that we may query the gradient of $f$ by randomly
sampling mini-batches of size $b$. Stochastic gradient descent (SGD (Robbins
and Monro, 1951)) and its momentum (or accelerated) variants (Polyak, 1964;
Sutskever et al., 2013) have been the subject of intense research, both in
terms of theoretical developments and applications, particularly to training
of deep neural networks and other machine learning models.

The standard SGD algorithm (Robbins and Monro, 1951) is

$\displaystyle x_{k+1}=x_{k}-\eta_{k}g_{k}\qquad\mbox{ for }k\in{\mathbb{N}}$
(2)

where $\eta_{k}>0$ is the step-size and $g_{k}$ is a noisy but unbiased
estimator of $\nabla f(x_{k})$. In the noise-less setting (_i.e.,_ when
$g_{k}=\nabla f(x_{k})$), the function value $f(x_{k})$ is decreasing with $k$
as long as $\nabla f$ is $L$-Lipschitz continuous and $\eta_{k}\leq 1/L$. In
fact, neither $f(x_{k})$ nor the distance between $x_{k}$ and the optimal set
will expand. However, the behaviour is very different in the presence of
noise. It may happen that $x_{k}$ tends to infinity if the correction
$\eta_{k}g_{k}$ is always large even though the step-size $\eta_{k}$ tends to
zero; or if the variance $\mathbb{E}[\left\|g_{k}-\nabla
f(x_{k})\right\|^{2}]$ increases rapidly with $\left\|x\right\|$. In this
note, we are interested in finding simple and verifiable conditions under
which $\left\|x_{k}-x^{\ast}\right\|$ and $f(x_{k})-f^{\ast}$ remain bounded
along every possible trajectory of the system.

Of course, $f(x_{k})$ will remain bounded if $f$ itself is bounded on
$\mathbb{R}^{d}$; this is the case for some truncated loss functions that have
been used in the robust machine-learning literature (Park and Liu, 2011; Xu et
al., 2020). Another trivial case is when the variable $x$ is kept in the
bounded region, for example by running a projected SGD. But these are not the
cases that we are interested in addressing int his paper. The main focus of
this work is on loss functions $f$ that may go to infinity when
$\left\|x\right\|$ tends to infinity. The most common loss functions in
machine learning, such as the least-squares and the logistic loss, are
unbounded on $\mathbb{R}^{d}$, and it very common to add a weight-decay
regularization $\lambda\left\|x\right\|^{2}$ ($\lambda>0$) to the original
loss function to help to avoid overfitting (Krogh and Hertz, 1992). Hence, the
resulting objective function is typically unbounded.

Motivation. Many theoretical analyses of SGD or its variants simply assume
that $\left\|x_{k}-x^{\ast}\right\|$ or $f(x_{k})-f^{\ast}$ are uniformly
bounded (in expectation or almost sure) (Ljung, 1977; Hazan and Kale, 2014; Xu
et al., 2019a; Davis et al., 2020; Wang et al., 2021; Wang and Johansson,
2021), even that $f$ itself is bounded (Xu et al., 2019b, 2020; Yuan et al.,
2019). However, in the noise regime, this uniform boundedness assumption may
be not always correct. One intuitive guess is that such a character may be
very relevant to the landscape of the target function $f$ especially the point
is far from its global minimizer (or local minimizers). As we know, there is
very little work that directly state that the uniform boundedness hypothesis
is true or can be guaranteed under the proper conditions.

Related work. A few recent contributions have been able to establish
convergence rates or almost sure convergence (which also implies the stability
$\left\|x_{k}-x^{\ast}\right\|<+\infty$) of SGD (Mertikopoulos et al., 2020;
Wojtowytsch, 2021; Patel and Zhang, 2021) and its momentum (heavy ball)
variant (Sebbouh et al., 2021) if the step-size $\eta_{k}$ is diminishing and
satisfies the Robbins-Monro condition: $\sum_{k=1}^{\infty}\eta_{k}=+\infty$
and $\sum_{k=1}^{\infty}\eta_{k}^{2}<+\infty$. However, such step-sizes (e.g.,
$\eta_{k}=\eta_{1}/t^{p}$ for $p\in(1/2,1]$) which decay very rapidly are not
so attractive in the non-convex setting and often performs poorly in practice
(Ge et al., 2019; Wang et al., 2021). Stepsizes that are more popular in
practice, such as step-decay (Ge et al., 2019; Wang et al., 2021), exponential
decay (Li et al., 2021) and cosine decay step-sizes (Loshchilov and Hutter,
2017) may not satisfy the Robbins-Monro condition. However, these step-sizes
are covered by the analysis in this paper.

For constant step-sizes, Yu et al. (2021) established an asymptotic normality
result for the SGD algorithm for a non-convex and non-smooth objective
function satisfying a dissipativity property. The paper (Chen et al., 2021)
analyzed the asymptotic stationary behavior of SGD for constant step-size on
smooth and strongly convex function, while Shi et al. (2020) revealed the
dependence of the linear convergence on the constant step-size for continuous-
time formulation of SGD. In the discrete-time case, the authors of (Shi et
al., 2020) also provided an upper bound but do not state how this bound
depends on the total number of iteration, which opens up the possibility that
the bounds are loose.

Contributions. In this work, we study uniform boundedness properties of SGD
and its momentum variant (SGD with momentum) with the help of a regularity
assumption which we call “$R$-dissipativity": $\left\langle x-x^{\ast},\nabla
f(x)\right\rangle\geq\theta_{1}\left\|x-x^{\ast}\right\|^{2}-\theta_{2}$ for
all $x$ with $\left\|x-x^{\ast}\right\|\geq R$ where $\theta_{1}>0$,
$\theta_{2}\geq 0$ and $R\geq 0$. This concept is a slight variation of the
“localized dissipativity” property introduced in (Yu et al., 2021) but we do
not concerns the local properties of the function for $x$ with
$\left\|x-x^{\ast}\right\|\leq R$. The term of “dissipativity" is originated
from dynamic systems (Hale, 1988) and used in a number of papers in
optimization, learning and Bayesian analysis (Mattingly et al., 2002; Raginsky
et al., 2017; Erdogdu et al., 2018; Mou et al., 2019). As we will see in
Section 3.1, many important application in machine learning, including shallow
neural networks and the sum of a weight-decay regularization and the function
whose gradient is bounded result in $R$-dissipative objective functions. We
make the following contributions:

  * •

Uniform boundedness properties of SGD and its momentum variant (SGD with
momentum) are established for $L$-smooth and $R$-dissipative loss functions.

  * •

We consider a broad class of step-sizes that are only required to be smaller
than a constant $\mathcal{O}(1/L)$. Our results cover many of the most popular
step-size policies, including the classical constant and polynomial decay
step-sizes, as well as more recently proposed time-dependent step-sizes such
as stage-wise decay (Li et al., 2021; Wang et al., 2021), cosine with or
without restart (Loshchilov and Hutter, 2017), and bandwidth-based step-sizes
(Wang and Yuan, 2021; Wang and Johansson, 2021).

In addition, we generalize the $R$-dissipativity to cover a class of function
of slower asymptotic growth, for example, the $\ell_{1}$ regularized logistic
regression and Bayesian logistic regression. We also make the contributions:

  * •

The uniform boundedness properties of SGD can also be guaranteed for a broad
of class of step-sizes that is only required to be upper bounded.

  * •

For the important variant momentum, the uniform boundedness can be established
for constant step-size, polynomial decaying, exponential decaying step-size
and also stage-wise step-sizes which decay like constant, polynomial, and
exponential at each stage.

##  2 Preliminaries

Throughout the paper, we make the following assumption on the stochastic
gradient oracle $\mathcal{O}$ which samples the stochastic gradient as an
unbiased estimator of the true gradient given any input variable $x$.

######  Assumption 1.

For any input vector $x$, the stochastic gradient oracle $\mathcal{O}$ returns
a vector $g$ such that (a) $\mathbb{E}[g_{k}]=\nabla f(x_{k})$; (b)
$\mathbb{E}[\left\|g_{k}-\nabla f(x_{k})\right\|^{2}]\leq\rho\left\|\nabla
f(x_{k})\right\|^{2}+\sigma^{2}$ where $\rho\geq 0$.

######  Definition 1.

($L$-smooth) A function $f$ is $L$-smooth if $\|\nabla f(x)-\nabla f(y)\|\leq
L\|x-y\|$ for every $x,y\in\mbox{dom}\,(f)$. The smoothness property also
implies that $|f(x)-f(y)-\left\langle\nabla
f(y),x-y\right\rangle|\leq\frac{L}{2}\left\|x-y\right\|^{2}.$

Notations. We use $x^{\ast}$ to denote the minimizer of function $f$ and
$f^{\ast}=f(x^{\ast})$. Let $\left\|\cdot\right\|:=\left\|\cdot\right\|_{2}$
without specific mention. We use $[n]$ denote the set of
$\left\\{1,2,\cdots,n\right\\}$. The subgradient of the function $f$ on $x$ is
denoted by $\partial f(x):=\left\\{v:f(y)\geq f(x)+\left\langle
v,y-x\right\rangle\text{for any }\,y\right\\}$. For simplicity of the
notations, we use $N,T,S$ are all integers. We use $\mathcal{F}_{k}$ to denote
$\sigma$-algebra generated by all the random information at the current
iterate $x_{k}$ and $x_{k}\in\mathcal{F}_{k}$.

##  3 Non-convex Function with its Tail Growing Quadratically

In this section, we establish uniform boundedness of SGD and its momentum
variant when the objective function is potentially nonconvex and satisfies the
following regularity assumption.

######  Definition 2.

($R$-dissipativity) A function is $R$-dissipative that there exist
$\theta_{1}>0$, $\theta_{2}\geq 0$, and $R\geq 0$ such that, for all $x$ with
$\left\|x-x^{\ast}\right\|\geq R$, the function $f$ satisfies

$\displaystyle\left\langle x-x^{\ast},\nabla
f(x)\right\rangle\geq\theta_{1}\left\|x-x^{\ast}\right\|^{2}-\theta_{2}.$ (3)

When $R=0$, this assumption reduces the standard dissipativity assumption
(Raginsky et al., 2017; Yu et al., 2021)(see (A.3) in (Raginsky et al.,
2017)). Dissipativity can be seen as a relaxation of strong convexity, since
every $\mu$-strongly convex function is also dissipative. In particular, it
satisfies Definition 2 with $\theta_{1}=\mu$, $\theta_{2}=0$ and $R=0$.

The term “dissipative" comes from the theory of dynamical systems (Hale, 1988)
but the concept has found many uses in the analysis of optimization and
learning algorithms (Mattingly et al., 2002; Raginsky et al., 2017; Erdogdu et
al., 2018), and in Bayesian analysis (Mou et al., 2019). $R$-dissipativity is
a natural property of many non-convex optimization problems, such as neural
network training with weight-decay regularization (Krogh and Hertz, 1992); see
§ 3.1 for more details.

######  Remark 1.

For $L$-smooth functions, an alternative way of verifying $R$-dissipativity is
to find $\theta_{1}^{\prime}$ and $\theta_{2}^{\prime}$ such that

$\displaystyle\left\langle x,\nabla
f(x)\right\rangle\geq\theta_{1}^{\prime}\left\|x\right\|^{2}-\theta_{2}^{\prime}$
(4)

for $\left\|x-x^{\ast}\right\|\geq R$. As shown in Appendix A, this implies
that $f$ is $R$-dissipative with parameters

$\displaystyle\theta_{1}$
$\displaystyle=\frac{\theta_{1}^{\prime}}{2},\qquad\theta_{2}=\left(\theta_{1}^{\prime}+2L+\frac{L^{2}}{2\theta_{1}^{\prime}}\right)\left\|x^{\ast}\right\|^{2}+\theta_{2}^{\prime}.$

######  Remark 2.

Although the definition of $R$-dissipativity in Definition 2 considers
differentiable functions, smoothness is not an essential property of our
analysis. If $f$is non-differentiable, the gradient $\nabla f(x)$ in
Definition 2 can be replaced by the sub-gradient $\partial f(x)$ and the
subsequent analysis for SGD and SGD with momentum still holds true.

###  3.1 Applications

We now show that several important applications in machine learning, robust
statistic learning, and Bayesian models are $R$-dissipative. Some of these are
also dissipative, while others are localized dissipative, but it is only the
$R$-dissipative concept that captures all examples.

Least squares problems where $f(x)=\frac{1}{2}\left\|Px-b\right\|^{2}$ and $P$
has full rank are $R$-dissipative with $\theta_{1}=\lambda_{\min}(P^{T}P)$
(the smallest eigenvalues of $P^{T}P$), $\theta_{2}=0$, and $R=0$. They are
therefore also dissipative.

$\ell_{2}$-regularized problems, where $f+\lambda\left\|x\right\|^{2}$ with
$\lambda>0$ and $f$ is a possibly non-convex whose gradient norm is bounded by
$G$ also satisfy Assumption 2. For example, most of the activation functions
in machine learning including the sigmoid, hyperbolic tangent, rectified
linear unit (ReLU) and variants such as Leaky ReLU and ELU can be applied. In
this case, we have $\theta_{1}=\lambda/2$, $\theta_{2}=G/(2\lambda)$, and
$R=0$.

Shallow neural networks A subset of neural network training objectives with
weight-decay regularization can also be shown to satisfy Assumption 2 (or the
alternative condition (4)). For example, consider the training a fully
connected 2-layer neural network (with $m$ hidden nodes) for binary
classification with a weight decay ($\lambda\left\|\cdot\right\|^{2}/2$). Let
$\sigma_{1}$ and $\sigma_{2}(\cdot)$ denote the inner and output layer
activation functions, respectively and use cross-entropy to measure the output
with its true label. If we use $\sigma_{2}(y)=1/(1+\exp(-y))$ and
$\sigma_{1}(x)=\max(0,x)$ (the ReLU loss function), then the resulting
training objective satisfies

$\displaystyle\left\langle x,\nabla
f(x)\right\rangle\geq\lambda\left\|x\right\|^{2}-2.$ (5)

On the other hand, if $\sigma_{1}(x)=1/(1+\exp(-x))$, we find

$\displaystyle\left\langle x,\nabla f(x)\right\rangle$
$\displaystyle\geq\frac{\lambda}{2}\left\|x\right\|^{2}-\left(1+\frac{m}{2\lambda}\right).$
(6)

Similarly, a $S$-layer fully connected neural network with ReLU as the
activation function of the inner-layers satisfies

$\displaystyle\left\langle x,\nabla
f(x)\right\rangle\geq\lambda\left\|x\right\|^{2}-S.$ (7)

These three examples are all dissipative and $R$-dissipative, but not
localized dissipative; see Appendix D for details.

Phase retrieval problems (Tan and Vershynin, 2019), where
$f(x)=1/(2n)\sum_{i=1}^{n}(|\left\langle a_{i},x\right\rangle|-b_{i})^{2}$
also satisfy this condition with $\theta_{1}=\lambda_{\min}(P^{T}P)/(2n)$
($P=[a_{1}^{T},\cdots,a_{n}^{T}]^{T}\in\mathbb{R}^{n\times d}$),
$\theta_{2}=\sum_{i=1}^{n}b_{i}^{2}/(2n)$, and $R=0$.

Regularized MLE Another important example that satisfies the $R$-dissipativity
assumption is the regularized MLE for heavy tailed linear regression (Yu et
al., 2021) arising in robust statistics. Here,
$f(x)=\frac{1}{2n}\sum_{i=1}^{n}\log(1+(b_{i}-\left\langle
a_{i},x\right\rangle)^{2})+\frac{\lambda}{2}\left\|x\right\|^{2}$ with
$\theta_{1}=\lambda$, $\theta_{2}=\frac{1}{n}\sum_{i=1}^{n}|b_{i}|$ and $R=0$.

Blake & Zisserman MLE As shown in (Yu et al., 2021), the objective function of
regularized Blake-Zisserman maximum-likelihood estimation, where
$f(x)=-\frac{1}{2n}\sum_{i=1}^{n}\log(\nu+\exp(-(b_{i}-\left\langle
a_{i},x\right\rangle)^{2}))+\frac{\lambda}{2}\left\|x\right\|^{2}$ for some
$\nu>0$ satisfies Assumption 2 with $\theta_{1}=\lambda$,
$\theta_{2}=1/(2n)\sum_{i=1}^{n}|b_{i}|/\sqrt{\nu(\nu+1)}$, and $R=0$.

Gaussian mixture model As a final example, we note that over-specified
Bayesian Gaussian mixture models, which have been widely used to study
datasets with heterogeneity (Mou et al., 2019), can be verified to satisfy
Assumption 2 with $\theta_{1}=4c_{1}$, $\theta_{2}=4c_{1}$, and $R=\sqrt{2}$
where $c_{1}>0$ is a universal constant (see Section 4.3 in (Mou et al.,
2019)). Gaussian mixture models are $R$-dissipative and localized dissipative,
but not dissipative.

######  Remark 3.

If the original objective function does not satisfy $R$-dissipativity, it can
always be rendered $R$-dissipative by adding a smooth regularizer
$\max\left\\{\left\|x\right\|^{2}-R^{2},0\right\\}$ with $R>0$. By properly
choosing $R$, we do not have to change the structure of the function around
global optimizer but still force the iterations in a bounded region. A similar
technique has been used in matrix completion problems in (Sun and Luo, 2016).

###  3.2 Uniform Boundedness Properties of SGD

In the remaining pages of this note, we use the concept of $R$-dissipativity
to establish boundedness properties of SGD and SGD with momentum. Our first
result, proven in Appendix A is the following:

######  Theorem 3.1.

Let $f$ be $L$-smooth and $R$-dissipative. If the stochastic gradient oracle
that satisfies Assumption 1, then the iterates of SGD with step-size
$\eta_{k}\leq\frac{\theta_{1}}{(\rho+1)L^{2}}$ satisfy

$\displaystyle\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]\leq\max\left\\{\left\|x_{1}-x^{\ast}\right\|^{2},\frac{2(\sigma^{2}+L^{2}r^{2})\theta_{1}^{2}}{(1+\rho)^{2}L^{4}}+2r^{2}\right\\}.$
(8)

where
$r^{2}=\max\left\\{R^{2},\frac{2\theta_{2}}{\theta_{1}}+\frac{\sigma^{2}}{(1+\rho)L^{2}}\right\\}$.

Theorem 3.1 shows that the iterations of SGD can be guaranteed to be in a
bounded region under mild conditions. The uniform bound is directly related to
the initial state, the noise $\sigma^{2}$, and the properties of the function
itself.

Although the result is valid for all values of $R$ (and therefore holds for
both dissipative and localized dissipative functions), the right-hand side of
(8) is not tight when $R=0$. We analyze dissipative functions in Appendix E
and derive tighter results, recovering the well-known bounds for
$\mu$-strongly convex functions as a special case.

######  Remark 4.

Theorem 3.1 guarantees uniform boundedness of the SGD iterates for any
(possibly non-monotonic) step-size upper bounded by
$\frac{\theta_{1}}{(\rho+1)L^{2}}$. This includes common step-size policies
such as constant, polynomial decay (Moulines and Bach, 2011) step-decay (Wang
et al., 2021), and exponential decay (Li et al., 2021), as well as more
recently proposed non-monotonic step-sizes such as the bandwidth-based (Wang
and Yuan, 2021; Wang and Johansson, 2021) and cosine (Loshchilov and Hutter,
2017) step-sizes.

The last comment we make for SGD is to relax the $L$-smoothness and try to
include more classes of examples.

######  Remark 5.

(Relaxation of $L$-smooth) The $L$-smooth assumption in Theorem 3.1 can be
replaced by $\left\|\nabla f(x)\right\|\leq L\left(1+\left\|x\right\|\right)$
as (Yu et al., 2021) (or there exists a vector $g\in\partial f(x)$ such that
$\left\|g\right\|\leq L(1+\left\|x\right\|)$). As a consequence, this also
ensures that uniform boundedness of the SGD algorithm. This condition allows
some functions that are non-smooth and is an extension of the $L$-smoothness.

###  3.3 Uniform Boundedness of SGD with Momentum

We now extend the results to also cover the following momentum variant of SGD

$\displaystyle v_{k+1}$ $\displaystyle=\beta v_{k}+(1-\beta)g_{k}$ (9a)
$\displaystyle x_{k+1}$ $\displaystyle=x_{k}-\eta_{k}v_{k+1}$ (9b)

where $\beta\in(0,1)$ and $x_{0}=x_{1}$. We analyze the three common step-size
policies: constant step-size, decaying step-sizes, and bandwidth step-sizes,
respectively. Our first result is the following:

######  Theorem 3.2.

(Constant step-size) Let $f$ be $L$-smooth and $R$-dissipative with a
stochastic oracle satisfying Assumption 1. Consider SGD with momentum defined
by (9a) and (9b) with $\beta\in(0,1)$, for any constant step-size

$\displaystyle\eta_{k}=\eta\leq\min\left\\{\frac{(1-\beta^{2})}{\beta
L\left(1-\beta+(1-\beta)^{-1}\right)},\,\,\frac{\theta_{1}}{2((1-\beta)^{2}+1)(\rho+1)L^{2}}\right\\},$

The, the quantities $\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]$ and
$\mathbb{E}[f(x_{k})-f^{\ast}]$ are uniformly bounded for all $k\in[1,T+1]$.

Theorem 3.2 establishes uniform boundedness properties of SGD with momentum
for any constant step-size under mild conditions. The most challenging part in
establishing Theorem 3.2 is how to construct a Lyapunov function that is
decreasing when $\|x_{k}-x^{\star}\|_{2}^{2}\geq R^{2}$. The details of the
proofs are given in Appendix B.

For the time dependent step-size, the analysis is more complicated than the
constant step-size (see Theorem 3.2). But our next theorem shows that the
uniform boundedness can also be guaranteed.

######  Theorem 3.3.

(Decaying step-sizes) Suppose that the objective function is $L$-smooth and
$R$-dissipative, and that the stochastic gradient oracle satisfies Assumption
1. Consider SGD with momentum defined by (9a) and (9b) with a time-varying
step-size
$\eta_{k}\leq\min\left\\{\frac{\theta_{1}}{2(\rho+1)(1+(1-\beta)^{2})L^{2}},\frac{1-\beta^{2}}{\beta
L(1-\beta+(1-\beta)^{-1}))}\right\\}$. Then both
$\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]$ and
$\mathbb{E}[f(x_{k})-f^{\ast}]$ are uniformly bounded for all $k\in[1,T+1]$,
under the following step-size policies:

  * (1)

polynomial decaying $\eta_{k}=\eta_{1}/k^{r}$ for $r\in(0,1]$ and
$\eta_{1}\geq\frac{2}{\theta_{1}}$, for any $k\geq 3$

  * (2)

linearly decaying $\eta_{k}=A-Bk$ where $\eta_{1}=\eta_{\max}$ and
$\eta_{T}=c/\sqrt{T}$ for
$c\geq\left(\frac{2\eta_{\max}^{2}}{\theta_{1}}\right)^{1/2}$

  * (3)

cosine decaying $\eta_{k}=A+B\cos\left(\frac{k\pi}{T}\right)$ where
$\eta_{1}=\eta_{\max}$ and $\eta_{T}=c/\sqrt{T}$ with
$c\geq\max\left\\{\left(\frac{\eta_{\max}^{2}\pi^{2}}{2\theta_{1}}\right)^{1/2},\frac{\eta_{\max}\pi^{2}}{4T^{3/2}}\right\\}$

  * (4)

exponentially decaying $\eta_{k}=\eta_{1}/\alpha^{k-1}$ where
$\alpha=(\nu/T)^{-1/T}>1$, $\nu\geq 1$, and
$\eta_{1}\geq\frac{2\ln(T/\nu)}{\theta_{1}\nu}$.

In the above theorem, we analyze four important families of decaying step-
sizes that have excellent practical performance, see _e.g._ (Loshchilov and
Hutter, 2017) for the cosine step-size and Li et al. (2021) for the
exponential step-size. Our results demonstrate that the uniform boundedness of
SGD with momentum can also be verified under these step-size policies.

Finally, we show that the uniform boundedness properties of SGD with momentum
can be guaranteed also by stage-wise bandwidth step-sizes (Wang and Yuan,
2021; Wang and Johansson, 2021), a class of step-size policies that allow for
non-monotonic behaviour (bot within and between stages). The bandwidth
framework not only covers the most popular stage-wise step-size (sometimes
referred to as the step-decay step-size) (Ge et al., 2019; Yuan et al., 2019;
Wang et al., 2021), but it also includes the popular cosine with restart step-
size (Loshchilov and Hutter, 2017).

######  Theorem 3.4.

(Stage-wise bandwidth-based step-size) Given the total number of iterations
$T$, we consider the bandwidth step-size with the form
$\eta_{\min}^{t}\leq\eta_{k}\leq\eta_{\max}^{t}$ and its upper and lower
bounds $\eta_{\min}^{t}$ and $\eta_{\max}^{t}$ are decreasing with $t$ where
$t\in[N]$, $k\in[\sum_{i=1}^{t-1}S_{i}+1,\sum_{i=1}^{t}S_{i}]$, and
$\sum_{t=1}^{N}S_{t}=T$. We assume that the bandwidth
$s=\eta_{\max}^{t}/\eta_{\min}^{t}$ is bounded and the step-size is decreasing
at each stage $t$. Under the same setting as Theorem 3.3, we consider the
constant and decaying modes discussed in Theorems 3.2 and 3.3, then the
quantities $\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]$ and
$\mathbb{E}[f(x_{k})-f^{\ast}]$ for all $k\in[1,T+1]$ are uniformly bounded.

Theorem 3.4 gives us a lot of freedom to choose the lower and upper bounds
$\eta_{\min}^{t},\eta_{\max}^{t}$ and stage length $S_{t}$. For example
$\eta_{\min}^{t}$ and $\eta_{\max}^{t}$ can be selected as
$\mathcal{O}\left(1/t^{p}\right)$ with $p\in(0,1]$ or
$\mathcal{O}\left(1/\alpha^{t}\right)$ with $\alpha>1$. Although we restrict
$s=\eta_{\max}^{t}/\eta_{\min}^{t}$ is bounded, the lower bound
$\eta_{\min}^{t}$ and upper bound $\eta_{\max}^{t}$ may be of different
orders. The stage length $S_{t}$ can be a constant ($S_{t}=S\geq 1$) or time
dependent with $t$.

##  4 Non-convex Function with its Tails Growing Slower than Quadratic

In this part, we extend the $R$-dissipativity of Section 3 to include the non-
convex function with its tail growing slower than quadratic, for example,
logistic regression with $\ell_{1}$ regularizer. When the point is far from
the global minimizer $x^{\ast}$ (i.e. $\left\|x-x^{\ast}\right\|\geq R$), we
consider the landscape of the objective function $f$ has the following
properties:

######  Definition 3.

(Generalized $R$-dissipativity) Suppose that there exist constants
$\theta_{1}>0$, $\theta_{2}\geq 0$, and $R>0$ such that for all
$\left\|x-x^{\ast}\right\|\geq R$, the objective function satisfies that

$\displaystyle\left\langle\nabla
f(x),x-x^{\ast}\right\rangle\geq\theta_{1}\left\|x-x^{\ast}\right\|^{p}-\theta_{2}$
(10)

with $p\in[0,2)$.

Definition 3 generalized the $R$-dissipativity property in Section 3 which
extends to the problems whose tails grow slower than quadratic (e.g.,
superlinear or sublinear $\left\|x\right\|^{p}$ for $p\in[0,2)$). As we can
see $p=2$ can be included Definition 3. However, to distinguish with
$R$-dissipativity in Section 3, here we do not include $p=2$.

######  Definition 4.

($\tau$-growth gradient) The gradient of the objective function $f$ is
$\tau$-growth if $\left\|\nabla
f(x)\right\|^{2}\leq\theta_{3}(1+\left\|x-x^{\ast}\right\|^{2\tau})$ where
$\tau\geq 0$ and $x\in\mathbb{R}^{d}$.

The $\tau$-growth gradient condition is regarded as the extension of
$L$-smoothness in Section 3 and is coupled with generalized $R$-dissipativity
in the following analysis. The generalized $R$-dissipativity where $p\in[1,2]$
together with $\tau$-growth gradient ($\tau\leq p/2$) has been introduced to
develop the convergence rates for Langevin Monte Carlo algorithm (Erdogdu and
Hosseinzadeh, 2021, Assumption 2). In our definition, we allow $p\in(0,2)$.
This includes the potential function may behave like $c\ln(x)$.

Some potential functions for example
$f(x)=c\log(1+\frac{1}{2}\left\|x\right\|^{2})$ for $\left\|x\right\|\geq R$,
which is sub-linear growth in $\left\|x\right\|$ satisfies generalized
$R$-dissipativity with $\theta_{1}=2c,\theta_{2}=4c/3$, $R=1$, and $p=0$, and
its gradient is $\tau$-growth with $\tau=0$ and $\theta_{3}=2c^{2}/3$ for
$\left\|x\right\|\geq 1$. Also, for any function $f$ whose tails grow like
$cx^{\alpha}$ for $\alpha\in(0,2]$ for some $c>0$, we have that the
generalized $R$-dissipativity holds with $\theta_{1}=c\alpha,\theta_{2}=0$,
and $p=\alpha$, and the gradient is $\tau$-growth with
$\tau=\alpha-1<\alpha/2$.

######  Remark 6.

(How to check generalized $R$-dissipativity) Suppose that there exist two
positive constants $\theta_{1}^{{}^{\prime}}$ and $\theta_{2}^{{}^{\prime}}$
such that

$\displaystyle\left\langle\nabla
f(x),x\right\rangle\geq\theta_{1}^{{}^{\prime}}\left\|x\right\|^{p}-\theta_{2}^{{}^{\prime}}$
(11)

If $x^{\ast}\neq 0$, let
$R\geq\max\left\\{2\left\|x^{\ast}\right\|,1\right\\}$ and assume that
gradient is $\tau$-growth with $\tau\leq p/2$, there exist two constant
$\theta_{1},\theta_{2}\geq 0$ such that

$\displaystyle\left\langle\nabla
f(x),x-x^{\ast}\right\rangle\geq\theta_{1}\left\|x-x^{\ast}\right\|^{p}-\theta_{2}$
(12)

where $\theta_{1}=\frac{\theta_{1}^{{}^{\prime}}}{2^{p+1}}$ and
$\theta_{2}=\theta_{2}^{{}^{\prime}}+\frac{\left\|x^{\ast}\right\|^{\alpha_{2}}}{s^{\alpha_{2}}\alpha_{2}}$
with $\alpha_{2}=\frac{p}{p-\tau}$ and
$s=\left(\frac{\theta_{1}^{{}^{\prime}}p}{\tau
2^{p+1}}\right)^{\tau/p}/\sqrt{2\theta_{3}}$.

###  4.1 Applications of Generalized $R$-dissipativity

Next we present some interesting applications in machine learning regime that
satisfy the generalized $R$-dissipativity.

Bayesian logistic regression (Mou et al., 2019):
$f(x)=\frac{1}{n}\sum_{i=1}^{n}b_{i}\log\left(1+\exp(-a_{i}^{T}{x})\right)+(1-b_{i})\log(1+\exp(a_{i}^{T}x))$
where $a_{i}$ is generated from the Gaussian distribution
$N(0,\mathbb{I}_{d})$ and $b_{i}|a_{i}$ is drawn according to the conditional
probability from logistic regression models. This function satisfies
generalized $R$-dissipativity with $\theta_{1}=c_{1}$, $\theta_{2}=0$, $R=1$,
and $p=1$ for the universal constant $c_{1}>0$.

Logistic regression with a $\ell_{1}$ regularizer where
$f(x)=\frac{1}{n}\sum_{i=1}^{n}\log(1+\exp(-b_{i}a_{i}^{T}x))+\lambda\left\|x\right\|_{1}$
satisfies generalized $R$-dissipativity with
$\theta_{1}=\lambda,\theta_{2}=\frac{1}{2}$, $R=0$, and $p=1$. The gradient of
$f$ is $\tau$-growth with
$\theta=\frac{2}{n}(\sum_{i=1}^{n}\left\|a_{i}\right\|^{2}+\lambda^{2}d)$ and
$\tau=0$.

Shallow neural networks with $\ell_{1}$ regularizer A subset of deep neural
networks with $\ell_{1}$ regularization can be proved to satisfy generalized
$R$-dissipativity. For instance, we consider a fully connected $S$-layer
($S-1$ hidden) neural network to train a binary classification dataset with
$\lambda\left\|\right\|_{1}$. We use $\sigma_{i}(x)=\max(0,x)$ for
$i=1,\cdots,S-1$ be the activation function of the inner layers,
$\sigma_{S}(y)=1/(1+\exp(-y))$ be the activation function of the output layer,
and use cross-entropy to measure the output with its true label. This results
the objective function satisfies that

$\displaystyle\left\langle\nabla
f(x),x\right\rangle\geq\lambda\left\|x\right\|-S$ (13)

which implies that the generalized $R$-dissipativity holds with
$\theta_{1}=\lambda$, $\theta_{2}=S$,$R=0$ and $p=1$.

###  4.2 Uniform boundedness of SGD Under Generalized Dissipativity

In the remaining of this section, we first show how the uniformly boundedness
of SGD can be guaranteed under the generalized $R$-dissipativity.

######  Theorem 4.1.

Suppose that the objective function $f$ is generalized $R$-dissipativity with
$p\in[0,2)$ and the gradient $\tau$-growth with $\tau\leq p/2$ for
$\left\|x-x^{\ast}\right\|\geq R$. Consider the SGD algorithm with the
stochastic gradient oracle satisfies Assumption 1. For any step-size
$\eta_{k}\leq\eta_{\max}$ where $\eta_{\max}$ is a positive constant, we have

$\displaystyle\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]\leq\min\left\\{\left\|x_{1}-x^{\ast}\right\|^{2},2(1+\eta_{\max}^{2}(\rho+1)\theta_{3})r^{2}+2\eta_{\max}^{2}\left(\sigma^{2}+(\rho+1)\theta_{3}\right)\right\\}$
(14)

with
$r^{2}=\max\left\\{R^{2},\left(8\eta_{\max}(\rho+1)\frac{\theta_{3}}{\theta_{1}}\right)^{1/(p-2\tau)},\left(\frac{2\theta_{2}}{\theta_{1}}+\frac{\left(\sigma^{2}+(\rho+1)\theta_{3}\right)\eta_{\max}}{\theta_{1}}\right)^{2/p}\right\\}.$

The theorem shows that for the functions whose tails grow slower than
quadratic, the uniform boundedness property of SGD can also be guaranteed for
any bounded step-sizes. In Definitions 3 and 4, we assume that the objective
function is differentiable. However, the above results also hold if the
gradient in Definitions 3 and 4 is replaced by a vector $g$ which belongs to
its subgradient $\partial f(x)$ ($g\in\partial f(x)$).

###  4.3 Uniform Boundedness of SGD with Momentum Under Generalized
Dissipativity

We then provide the analysis to cover the momentum variant of SGD under
generalized $R$-dissipativity.

######  Theorem 4.2.

(Constant step-size) Let the objective function $f$ be $L$-smooth. We further
assume that $f$ is generalized $R$-dissipativity with $p\in(0,2)$ and its
gradient is $\tau$-growth with $\tau\leq p/2$ for
$\left\|x-x^{\ast}\right\|\geq R\geq 1$. Consider the SGD with momentum method
defined in (9a) and (9b) with $\beta\in(0,1)$ and stochastic gradient oracle
satisfies Assumption 1, then for any constant step-size that

$\displaystyle\eta_{k}\leq\frac{1-\beta^{2}}{\beta L(1-\beta+(1-\beta)^{-1})}$
(15)

the quantities $\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]$,
$\mathbb{E}[f(x_{k})-f^{\ast}]$ are uniformly bounded for all $k\geq 1$.

Theorem 4.2 establishes the uniform boundedness of the SGD algorithm with
momentum under the constant step-size. Compared to the analysis of SGD in
Section 4.2, here we also require that the objective function $f$ is
$L$-smooth in $\mathbb{R}^{d}$. This is not contradictory with $\tau$-growth
gradient for $\left\|x-x^{\ast}\right\|\geq R\geq 1$ because if the gradient
is $\tau$-growth, of course, it also implies that $\left\|\nabla
f(x)\right\|^{2}\leq\theta_{3}(1+\left\|x-x^{\ast}\right\|^{2\tau})\leq\theta_{3}(1+\left\|x-x^{\ast}\right\|^{2})$
for $\left\|x-x^{\ast}\right\|\geq R\geq 1$.

We then analyze the two popular time-varying step-sizes: polynomial decaying
and exponential decaying step-size. The results below show the uniformly
boundedness of SGD with momentum is also guaranteed.

######  Theorem 4.3.

(Time-decaying step-size) Let the objective function $f$ be $L$-smooth. We
further assume that $f$ satisfies Assumption 3 and stochastic gradient oracle
satisfies Assumption 1. Consider the SGD with momentum method defined in (9a)
and (9b) with $\beta\in(0,1)$, then
$\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]$ and
$\mathbb{E}[f(x_{k})-f^{\ast}]$ are uniformly bounded for all $k\geq 1$, under
the following step-sizes:

  * •

Polynomial decaying step-size $\eta_{k}=\eta_{1}/k^{p}$ for $p\in(0,1]$ where
$\eta_{k}\leq\frac{1-\beta^{2}}{2\beta L(1-\beta+(1-\beta)^{-1})}$;

  * •

Exponential decaying step-size $\eta_{k}=\eta_{1}/\alpha^{k}$ with
$\alpha=(\nu/T)^{-1/T}$ where $\eta_{k}\leq\frac{1-\beta^{2}}{\beta
L(1-\beta+2(1-\beta)^{-1})}$.

Finally, based on the results of Theorems 4.2 and 4.3, the uniform boundedness
property also holds for three special stage-wise bandwidth step-sizes. The
proof of the below theorem is very similar to that of Theorem 3.4, therefore
we omit it in this note.

######  Theorem 4.4.

(bandwidth-based stage-wise step-size) Given the total number of iteration
$T$, we consider the bandwidth step-size with the form
$\eta_{\min}^{t}\leq\eta_{k}\leq\eta_{\max}^{t}$ and the upper and lower
bounds are decreasing with $t\in[N]$ where
$k\in[\sum_{i=1}^{t-1}S_{i}+1,\sum_{i=1}^{t}S_{i}]$ and
$\sum_{i=1}^{N}S_{i}=T$. We assume the bandwidth
$s=\eta_{\max}^{t}/\eta_{\min}^{t}$ is bounded and step-size is decreasing at
each stage $t$. Under the same setting as Theorem 4.3, we consider the
constant and decaying modes discussed in Theorem 4.3, then
$\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]$ and
$\mathbb{E}[f(x_{k})-f^{\ast}]$ are uniformly bounded for all $k\geq 1$.

##  5 Conclusion

We have provided uniform boundedness guarantees for SGD and SGD with momentum
under the $L$-smoothness and $R$-dissipativity conditions. Our results allow
for broad families of step-sizes that are only upper bounded by a constant
$\mathcal{O}(1/L)$. We have demonstrated that,
$\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]$ and
$\mathbb{E}[f(x_{k})-f^{\ast}]$ stay bounded along every possible trajectory,
even under step-sizes that do not satisfy the Robbins-Monro conditions (square
summable but not summable). The uniform bounds that we have derived depend on
loss function properties, noise parameters $\sigma^{2}$ and $\rho$ of the
stochastic oracle, and the initial state of the algorithm.

$R$-dissipativity captures non-convex functions that grow quadratically when
we move (possibly far) away from the global minimizer. As shown in Section
3.1, several interesting applications in machine learning satisfy this
regularity condition. Furthermore, uniform boundedness properties can be
guaranteed also for loss functions with slower asymptotic growth, such as
Bayesian logistic regression. For the SGD algorithm, we have proved that,
$\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]$ and
$\mathbb{E}[f(x_{k})-f^{\ast}]$ stay bounded under a broad class of step-size
that is only required to be upper bounded. The uniformly boundedness
properties of SGD with momentum can be guaranteed for several popular step-
sizes including constant step-size, polynomial decaying and exponential
decaying step-size, and also the stage-wise bandwidth step-sizes which locally
decay like constant, polynomial and exponential functions.

## References

  * Chen et al. (2021) Z. Chen, S. Mou, and S. T. Maguluri.  Stationary behavior of constant stepsize sgd type algorithms: An asymptotic characterization.  _arXiv preprint arXiv:2111.06328_ , 2021.
  * Davis et al. (2020) D. Davis, D. Drusvyatskiy, S. Kakade, and J. D. Lee.  Stochastic subgradient method converges on tame functions.  _Foundations of computational mathematics_ , 20(1):119–154, 2020.
  * Erdogdu and Hosseinzadeh (2021) M. A. Erdogdu and R. Hosseinzadeh.  On the convergence of langevin monte carlo: The interplay between tail growth and smoothness.  In M. Belkin and S. Kpotufe, editors, _Proceedings of Thirty Fourth Conference on Learning Theory_ , volume 134 of _Proceedings of Machine Learning Research_ , pages 1776–1822. PMLR, 15–19 Aug 2021.
  * Erdogdu et al. (2018) M. A. Erdogdu, L. Mackey, and O. Shamir.  Global non-convex optimization with discretized diffusions.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31, 2018.
  * Ge et al. (2019) R. Ge, S. M. Kakade, R. Kidambi, and P. Netrapalli.  The step decay schedule: A near optimal, geometrically decaying learning rate procedure for least squares.  In _Advances in Neural Information Processing Systems_ , pages 14977–14988, 2019.
  * Hale (1988) J. K. Hale.  Asymptotic behavior of dissipative systems.  In _AMS_ , 1988.
  * Hazan and Kale (2014) E. Hazan and S. Kale.  Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization.  _Journal of Machine Learning Research_ , 15(1):2489–2512, 2014.
  * Krogh and Hertz (1992) A. Krogh and J. A. Hertz.  A simple weight decay can improve generalization.  In _Advances in neural information processing systems_ , pages 950–957, 1992.
  * Li et al. (2021) X. Li, Z. Zhuang, and F. Orabona.  A second look at exponential and cosine step sizes: Simplicity, adaptivity, and performance.  In _International Conference on Machine Learning_ , pages 6553–6564. PMLR, 2021.
  * Ljung (1977) L. Ljung.  Analysis of recursive stochastic algorithms.  _IEEE transactions on automatic control_ , 22(4):551–575, 1977.
  * Loshchilov and Hutter (2017) I. Loshchilov and F. Hutter.  SGDR: Stochastic gradient descent with warm restarts.  In _5th International Conference on Learning Representations, ICLR 2017, Toulon, France_ , 2017.
  * Mattingly et al. (2002) J. C. Mattingly, A. M. Stuart, and D. J. Higham.  Ergodicity for sdes and approximations: locally lipschitz vector fields and degenerate noise.  _Stochastic processes and their applications_ , 101(2):185–232, 2002.
  * Mertikopoulos et al. (2020) P. Mertikopoulos, N. Hallak, A. Kavis, and V. Cevher.  On the almost sure convergence of stochastic gradient descent in non-convex problems.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Mou et al. (2019) W. Mou, N. Ho, M. J. Wainwright, P. Bartlett, and M. I. Jordan.  A diffusion process perspective on posterior contraction rates for parameters.  _arXiv preprint arXiv:1909.00966_ , 2019.
  * Moulines and Bach (2011) E. Moulines and F. R. Bach.  Non-asymptotic analysis of stochastic approximation algorithms for machine learning.  In _Advances in Neural Information Processing Systems_ , pages 451–459, 2011.
  * Park and Liu (2011) S. Y. Park and Y. Liu.  Robust penalized logistic regression with truncated loss functions.  _Canadian Journal of Statistics_ , 39(2):300–323, 2011.
  * Patel and Zhang (2021) V. Patel and S. Zhang.  Stochastic gradient descent on nonconvex functions with general noise models.  _arXiv preprint arXiv:2104.00423_ , 2021.
  * 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.
  * Raginsky et al. (2017) M. Raginsky, A. Rakhlin, and M. Telgarsky.  Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis.  In _Conference on Learning Theory_ , pages 1674–1703. PMLR, 2017\.
  * Robbins and Monro (1951) H. Robbins and S. Monro.  A stochastic approximation method.  _The Annals of Mathematical Statistics_ , pages 400–407, 1951.
  * Sebbouh et al. (2021) O. Sebbouh, R. M. Gower, and A. Defazio.  Almost sure convergence rates for stochastic gradient descent and stochastic heavy ball.  In _Conference on Learning Theory_ , pages 3935–3971. PMLR, 2021\.
  * Shi et al. (2020) B. Shi, W. J. Su, and M. I. Jordan.  On learning rates and schr$\backslash$" odinger operators.  _arXiv preprint arXiv:2004.06977_ , 2020.
  * Sun and Luo (2016) R. Sun and Z.-Q. Luo.  Guaranteed matrix completion via non-convex factorization.  _IEEE Transactions on Information Theory_ , 62(11):6535–6579, 2016.
  * Sutskever et al. (2013) I. Sutskever, J. Martens, G. Dahl, and G. Hinton.  On the importance of initialization and momentum in deep learning.  In _International Conference on Machine Learning_ , pages 1139–1147. PMLR, 2013.
  * Tan and Vershynin (2019) Y. S. Tan and R. Vershynin.  Online stochastic gradient descent with arbitrary initialization solves non-smooth, non-convex phase retrieval.  _arXiv preprint arXiv:1910.12837_ , 2019.
  * Wang and Johansson (2021) X. Wang and M. Johansson.  Bandwidth-based step-sizes for non-convex stochastic optimization.  _arXiv preprint arXiv:2106.02888_ , 2021.
  * Wang and Yuan (2021) X. Wang and Y.-x. Yuan.  On the convergence of stochastic gradient descent with bandwidth-based step size.  _arXiv preprint arXiv:2102.09031_ , 2021.
  * Wang et al. (2021) X. Wang, S. Magnússon, and M. Johansson.  On the convergence of step decay step-size for stochastic optimization.  In _Advances in Neural Information Processing Systems_ , 2021.
  * Wojtowytsch (2021) S. Wojtowytsch.  Stochastic gradient descent with noise of machine learning type. part i: Discrete time analysis.  _arXiv preprint arXiv:2105.01650_ , 2021.
  * Xu et al. (2019a) Y. Xu, Q. Qi, Q. Lin, R. Jin, and T. Yang.  Stochastic optimization for dc functions and non-smooth non-convex regularizers with non-asymptotic convergence.  In _International Conference on Machine Learning_ , pages 6942–6951. PMLR, 2019a.
  * Xu et al. (2019b) Y. Xu, Z. Yuan, S. Yang, R. Jin, and T. Yang.  On the convergence of (stochastic) gradient descent with extrapolation for non-convex minimization.  In _Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)_ , 2019b.
  * Xu et al. (2020) Y. Xu, S. Zhu, S. Yang, C. Zhang, R. Jin, and T. Yang.  Learning with non-convex truncated losses by sgd.  In _Proceedings of The 35th Uncertainty in Artificial Intelligence Conference_ , volume 115, pages 701–711. PMLR, 22–25 Jul 2020.
  * Yu et al. (2021) L. Yu, K. Balasubramanian, S. Volgushev, and M. A. Erdogdu.  An analysis of constant step size sgd in the non-convex regime: Asymptotic normality and bias.  In _Advances in Neural Information Processing Systems_ , 2021.
  * Yuan et al. (2019) Z. Yuan, Y. Yan, R. Jin, and T. Yang.  Stagewise training accelerates convergence of testing error over sgd.  In _Proceedings of the 33rd International Conference on Neural Information Processing Systems_ , pages 2608–2618, 2019.

##  Appendix A Supplementary Theoretical Results for SGD

######  Lemma A.1.

We consider the SGD algorithm and assume that the noise of the stochastic
gradient satisfies Assumption 1. Then

$\displaystyle\mathbb{E}[\left\|x_{k+1}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k}]\leq\left\|x_{k}-x^{\ast}\right\|^{2}-2\eta_{k}\left\langle\nabla
f(x_{k}),x_{k}-x^{\ast}\right\rangle+\eta_{k}^{2}\left((1+\rho)\left\|\nabla
f(x_{k})\right\|^{2}+\sigma^{2}\right)$

###### Proof.

Applying the iteration of the SGD algorithm, we have

$\displaystyle\left\|x_{k+1}-x^{\ast}\right\|^{2}$
$\displaystyle=\left\|x_{k}-\eta_{k}g_{k}-x^{\ast}\right\|^{2}=\left\|x_{k}-x^{\ast}\right\|^{2}-2\eta_{k}\left\langle
g_{k},x_{k}-x^{\ast}\right\rangle+\eta_{k}^{2}\left\|g_{k}\right\|^{2}.$ (16)

By Assumption 1, we can estimate the expectation of $\left\|g_{k}\right\|^{2}$
as below

$\displaystyle\mathbb{E}[\left\|g_{k}\right\|^{2}\mid\mathcal{F}_{k}]=\mathbb{E}[\left\|g_{k}-\nabla
f(x_{k})+\nabla f(x_{k})\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle=\mathbb{E}[\left\|g_{k}-\nabla
f(x_{k})\right\|^{2}\mid\mathcal{F}_{k}]+\left\|\nabla f(x_{k})\right\|^{2}$
$\displaystyle\leq\sigma^{2}+(\rho+1)\left\|\nabla f(x_{k})\right\|^{2}.$ (17)

Taking conditional expectation with respect to $\mathcal{F}_{k}$ on the both
sides of (16) and applying (A.1) gives

$\displaystyle\mathbb{E}\left[\left\|x_{k+1}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k}\right]$
$\displaystyle=\left\|x_{k}-x^{\ast}\right\|^{2}-2\eta_{k}\left\langle\nabla
f(x_{k}),x_{k}-x^{\ast}\right\rangle+\eta_{k}^{2}\left(\mathbb{E}\left[\left\|g_{k}-\nabla
f(x_{k})+\nabla f(x_{k})\right\|^{2}\right]\right)$
$\displaystyle=\left\|x_{k}-x^{\ast}\right\|^{2}-2\eta_{k}\left\langle\nabla
f(x_{k}),x_{k}-x^{\ast}\right\rangle+\eta_{k}^{2}\left(\mathbb{E}[\left\|g_{k}-\nabla
f(x_{k})\right\|^{2}]+\left\|\nabla f(x_{k})\right\|^{2}\right)$
$\displaystyle\leq\left\|x_{k}-x^{\ast}\right\|^{2}-2\eta_{k}\left\langle\nabla
f(x_{k}),x_{k}-x^{\ast}\right\rangle+\eta_{k}^{2}\left((1+\rho)\left\|\nabla
f(x_{k})\right\|^{2}+\sigma^{2}\right).$

∎

###### Proof.

(of Theorem 3.1) Let
$r^{2}=\max\left\\{R^{2},\frac{2\theta_{2}}{\theta_{1}}+\frac{\sigma^{2}}{(1+\rho)L^{2}}\right\\}$.
In this theorem, we consider two different cases based on the distance of the
initial point $x_{1}$ with the global minimizer $x^{\ast}$. First, we consider
the initial point $\left\|x_{1}-x^{\ast}\right\|\leq r$. Suppose that at time
$k$,
$\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k-1}]>r^{2}$ but
$\mathbb{E}[\left\|x_{k-1}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k-2}]\leq
r^{2}$. We can see that

$\displaystyle\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k-1}]$
$\displaystyle=\mathbb{E}[\left\|x_{k}-x_{k-1}+x_{k-1}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k-1}]\leq
2\mathbb{E}[\left\|x_{k}-x_{k-1}\right\|^{2}\mid\mathcal{F}_{k-1}]+2\left\|x_{k-1}-x^{\ast}\right\|^{2}$
$\displaystyle\leq
2\eta_{k-2}^{2}\mathbb{E}[\left\|g_{k-1}\right\|^{2}\mid\mathcal{F}_{k-1}]+2\left\|x_{k-1}-x^{\ast}\right\|^{2}\leq
2\eta_{k-1}^{2}\left(\sigma^{2}+L^{2}\left\|x_{k-1}-x^{\ast}\right\|^{2}\right)+2\left\|x_{k-1}-x^{\ast}\right\|^{2}$
$\displaystyle=2\eta_{k-1}^{2}\sigma^{2}+2(\eta_{k-1}^{2}L^{2}+1)\left\|x_{k-1}-x^{\ast}\right\|^{2}$
$\displaystyle<2\eta_{k-1}^{2}\sigma^{2}+2(\eta_{k-1}^{2}L^{2}+1)r^{2}\leq\frac{2(\sigma^{2}+L^{2}r^{2})\theta_{1}^{2}}{(1+\rho)^{2}L^{4}}+2r^{2}.$
(18)

This means that when $\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]>r^{2}$,
then $R$-dissipativity holds. By Lemma A.1, we have

$\displaystyle\mathbb{E}[\left\|x_{k+1}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle=\left\|x_{k}-x^{\ast}\right\|^{2}-2\eta_{k}\left\langle\nabla
f(x_{k}),x_{k}-x^{\ast}\right\rangle+\eta_{k}^{2}\left((1+\rho)\left\|\nabla
f(x_{k})\right\|^{2}+\sigma^{2}\right)$
$\displaystyle\leq\left\|x_{k}-x^{\ast}\right\|^{2}+(-2\theta_{1}\eta_{k}+(1+\rho)L^{2}\eta_{k}^{2})\left\|x_{k}-x^{\ast}\right\|^{2}+2\theta_{2}\eta_{k}+\eta_{k}^{2}\sigma^{2}.$
(19)

By $\eta_{k}\leq\frac{\theta_{1}}{(\rho+1)L^{2}}$, we have
$-2\theta_{1}\eta_{k}+(1+\rho)L^{2}\eta_{k}^{2}\leq-\theta_{1}\eta_{k}$. Then

$\displaystyle\mathbb{E}[\left\|x_{k+1}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle\leq\left\|x_{k}-x^{\ast}\right\|^{2}-\theta_{1}\eta_{k}\left\|x_{k}-x^{\ast}\right\|^{2}+2\theta_{2}\eta_{k}+\eta_{k}^{2}\sigma^{2}.$
(20)

Once $\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]>r^{2}$, for any kinds of
step-sizes as long as $\eta_{k}\leq\frac{\theta_{1}}{(\rho+1)L^{2}}$, if $r$
is large enough for example

$\displaystyle
r^{2}=\max\left\\{R^{2},\frac{2\theta_{2}}{\theta_{1}}+\frac{\sigma^{2}}{(1+\rho)L^{2}}\right\\}$

to make sure that

$\displaystyle-\theta_{1}\eta_{k}\left\|x_{k}-x^{\ast}\right\|^{2}+2\theta_{2}\eta_{k}+\eta_{k}^{2}\sigma^{2}<0$

Then

$\displaystyle\mathbb{E}[\left\|x_{k+1}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k}]<\left\|x_{k}-x^{\ast}\right\|^{2}.$

That is to say, once there exist an iterate $k$ such that
$\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]>r^{2}$, for any step-size
$\eta_{k}\leq\frac{\theta_{1}}{(\rho+1)L^{2}}$, then the follow-up
$\mathbb{E}[\left\|x_{k+1}-x^{\ast}\right\|^{2}]$ is decreasing.

If the initial point $x_{1}$ is far from the optimal point $x^{\ast}$, that is
$\left\|x_{1}-x^{\ast}\right\|^{2}>r^{2}$ but $\left\|x_{1}-x^{\ast}\right\|$
is bounded, by applying the above statements, we can see that the follow-up
$\mathbb{E}[\left\|x_{k+1}-x^{\ast}\right\|^{2}]$ is decreasing until
$\mathbb{E}[\left\|x_{k+1}-x^{\ast}\right\|^{2}]\leq r^{2}$.

∎

###### Proof.

(of Remark 1) In this proof, we show that $R$-dissipativity condition can be
derived from

$\displaystyle\left\langle x,\nabla
f(x)\right\rangle\geq\theta_{1}^{{}^{\prime}}\left\|x\right\|^{2}-\theta_{2}^{{}^{\prime}}$
(21)

for all $\left\|x-x^{\ast}\right\|\geq R$. When $x^{\ast}=0$, the two
conditions are the same. Suppose that $\left\|x^{\ast}\right\|>0$, then

$\displaystyle\left\langle x,\nabla
f(x)\right\rangle\geq\theta_{1}^{{}^{\prime}}\left\|x\right\|^{2}-\theta_{2}^{{}^{\prime}}\geq\theta_{1}^{{}^{\prime}}\left(\left\|x-x^{\ast}\right\|^{2}+\left\|x^{\ast}\right\|^{2}-2\left\|x^{\ast}\right\|\left\|x-x^{\ast}\right\|\right)-\theta_{2}^{{}^{\prime}}$
(22)

and

$\displaystyle\left\langle\nabla
f(x),x^{\ast}\right\rangle\mathop{\leq}^{(a)}\left\|\nabla
f(x)\right\|\left\|x^{\ast}\right\|\leq
L\left\|x-x^{\ast}\right\|\left\|x^{\ast}\right\|$ (23)

where $(a)$ follows from the fact that $\left\|\nabla f(x)\right\|\leq
L\left\|x-x^{\ast}\right\|$ (due to $L$-smoothness). Incorporating the above
results gives that

$\displaystyle\left\langle x-x^{\ast},\nabla f(x)\right\rangle$
$\displaystyle\geq\theta_{1}^{{}^{\prime}}\left\|x-x^{\ast}\right\|^{2}-\left(2\theta_{1}^{{}^{\prime}}+L\right)\left\|x^{\ast}\right\|\left\|x-x^{\ast}\right\|-\theta_{2}^{{}^{\prime}}+\theta_{1}^{{}^{\prime}}\left\|x^{\ast}\right\|^{2}$
$\displaystyle\geq\frac{\theta_{1}^{{}^{\prime}}}{2}\left\|x-x^{\ast}\right\|^{2}-\left(\frac{(2\theta_{1}^{{}^{\prime}}+L)^{2}}{2\theta_{1}^{{}^{\prime}}}-\theta_{1}^{{}^{\prime}}\right)\left\|x^{\ast}\right\|^{2}-\theta_{2}^{{}^{\prime}}.$
(24)

Thus the $R$-dissipativity condition holds with
$\theta_{1}=\frac{\theta_{1}^{{}^{\prime}}}{2}$ and
$\theta_{2}=\left(\theta_{1}^{{}^{\prime}}+2L+\frac{L^{2}}{2\theta_{1}^{{}^{\prime}}}\right)\left\|x^{\ast}\right\|^{2}+\theta_{2}^{{}^{\prime}}$.

∎

##  Appendix B Supplementary Material for SGD with Momentum

In this part, we provide supplementary proofs for theorems in Section 3.3.
Before given the main proofs, we first show some extra and useful lemmas.

######  Lemma B.1.

Suppose that the objective function $f$ is $L$-smooth and the stochastic
gradient satisfies Assumption 1. Consider SGD with momentum with the momentum
parameter $\beta\in(0,1)$, for any step-size $\eta_{k}>0$, we have

$\displaystyle\mathbb{E}[\left\|x_{k+1}-x_{k}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle=\frac{\eta_{k}^{2}\beta^{2}}{\eta_{k-1}^{2}}\left\|x_{k}-x_{k-1}\right\|^{2}+\eta_{k}^{2}(1-\beta)^{2}\mathbb{E}[\left\|g_{k}\right\|^{2}\mid\mathcal{F}_{k}]+\frac{\eta_{k}^{2}\beta(1-\beta)}{\eta_{k-1}}\left(f(x_{k-1})-f(x_{k})+\frac{L}{2}\left\|x_{k}-x_{k-1}\right\|^{2}\right).$

###### Proof.

(of Lemma B.1) Applying the update recursion of the SGD with momentum
algorithm in (9a) and (9b) gives

$\displaystyle\mathbb{E}[\left\|x_{k+1}-x_{k}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle=\mathbb{E}[\left\|\eta_{k}v_{k+1}\right\|^{2}\mid\mathcal{F}_{k}]=\eta_{k}^{2}\,\mathbb{E}[\left\|\beta
v_{k}+(1-\beta)g_{k}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle=\eta_{k}^{2}\mathbb{E}\left[\left\|\beta\eta_{k-1}^{-1}(x_{k-1}-x_{k})+(1-\beta)g_{k}\right\|^{2}\mid\mathcal{F}_{k}\right]$
$\displaystyle=\frac{\eta_{k}^{2}\beta^{2}}{\eta_{k-1}^{2}}\left\|x_{k}-x_{k-1}\right\|^{2}+\eta_{k}^{2}(1-\beta)^{2}\mathbb{E}[\left\|g_{k}\right\|^{2}\mid\mathcal{F}_{k}]+\frac{2\eta_{k}^{2}\beta(1-\beta)}{\eta_{k-1}}\left\langle
x_{k-1}-x_{k},\nabla f(x_{k})\right\rangle$ (25)

where $\mathbb{E}[g_{k}\mid\mathcal{F}_{k}]=\nabla f(x_{k})$. Using the
$L$-smooth assumption, for any $x,y\in\mathbb{R}^{d}$, we have

$\displaystyle\left\|\nabla f(x)-\nabla f(y)\right\|\leq L\left\|x-y\right\|.$

Let $x=x_{k-1}$ and $y=x_{k}$, the $L$-smoothness also implies that

$\displaystyle f(x_{k-1})\geq f(x_{k})+\left\langle x_{k-1}-x_{k},\nabla
f(x_{k})\right\rangle-\frac{L}{2}\left\|x_{k}-x_{k-1}\right\|^{2}.$ (26)

Applying the above inequality into (B), we have

$\displaystyle\mathbb{E}[\left\|x_{k+1}-x_{k}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle\leq\frac{\eta_{k}^{2}}{\eta_{k-1}^{2}}\beta^{2}\left\|x_{k}-x_{k-1}\right\|^{2}+\eta_{k}^{2}(1-\beta)^{2}\mathbb{E}[\left\|g_{k}\right\|^{2}\mid\mathcal{F}_{k}]+\frac{2\eta_{k}^{2}\beta(1-\beta)}{\eta_{k-1}}\left(f(x_{k-1})-f(x_{k})+\frac{L}{2}\left\|x_{k}-x_{k-1}\right\|^{2}\right).$

Then the proof is complete. ∎

######  Lemma B.2.

We define $\tilde{x}_{k+1}:=\frac{x_{k+1}-\beta x_{k}}{1-\beta}$. Suppose that
Assumption 1 and (2 ) hold at current iterations $x_{k}$ and
$\tau_{k}=\eta_{k}/\eta_{k-1}\in(0,1]$, then

  * (i)

If $\tau_{k}=1$, _i.e._ , $\eta_{k}=\eta$ for all $k\geq 1$, we have

$\displaystyle\mathbb{E}[\left\|\tilde{x}_{k+1}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle\leq\left\|\tilde{x}_{k}-x^{\ast}\right\|^{2}-2\theta_{1}\eta_{k}\left\|x_{k}-x^{\ast}\right\|^{2}+2\theta_{2}\eta_{k}+\eta_{k}^{2}\mathbb{E}[\left\|g_{k}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle\quad+\frac{2\beta\eta_{k}}{1-\beta}\left(f(x_{k-1})-f(x_{k})+\frac{L}{2}\left\|x_{k}-x_{k-1}\right\|^{2}\right).$

  * (ii)

else if $\tau_{k}\in(0,1)$, we have

$\displaystyle\mathbb{E}[\left\|\tilde{x}_{k+1}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle\leq\tau_{k}\left\|\tilde{x}_{k}-x^{\ast}\right\|^{2}-\left(2\eta_{k}\theta_{1}-\left(1-\tau_{k}\right)\right)\left\|x_{k}-x^{\ast}\right\|^{2}+2\eta_{k}\theta_{2}+\eta_{k}^{2}\mathbb{E}[\left\|g_{k}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle\quad+\frac{2\beta
L}{1-\beta}\cdot\eta_{k}\tau_{k}\left\|x_{k-1}-x_{k}\right\|^{2}+\frac{2\beta\tau_{k}\eta_{k}}{1-\beta}\left(f(x_{k-1})-f(x_{k})\right).$

###### Proof.

(of Lemma B.2) Recalling the definition of $\tilde{x}_{k+1}$ and applying the
recursion of SGD with momentum, we have

$\displaystyle\left\|\tilde{x}_{k+1}-x^{\ast}\right\|^{2}$
$\displaystyle=\left\|(1-\beta)^{-1}\left(x_{k+1}-\beta
x_{k}\right)-x^{\ast}\right\|^{2}=\left\|(1-\beta)^{-1}\left(x_{k}-\eta_{k}(\beta
v_{k}+(1-\beta)g_{k})-\beta x_{k}\right)-x^{\ast}\right\|^{2}$
$\displaystyle=\left\|x_{k}-\frac{\eta_{k}}{1-\beta}\left(\beta\left(\frac{x_{k-1}-x_{k}}{\eta_{k-1}}\right)+(1-\beta)g_{k}\right)-x^{\ast}\right\|^{2}$
$\displaystyle=\left\|\frac{\eta_{k}}{(1-\beta)\eta_{k-1}}\left(x_{k}-\beta
x_{k-1}\right)+\left(1-\frac{\eta_{k}}{\eta_{k-1}}\right)x_{k}-\eta_{k}g_{k}-x^{\ast}\right\|^{2}$
$\displaystyle=\left\|\frac{\eta_{k}}{\eta_{k-1}}\left(\tilde{x}_{k}-x^{\ast}\right)+\left(1-\frac{\eta_{k}}{\eta_{k-1}}\right)(x_{k}-x^{\ast})-\eta_{k}g_{k}\right\|^{2}$
$\displaystyle=\tau_{k}\left\|\tilde{x}_{k}-x^{\ast}\right\|^{2}+\left(1-\tau_{k}\right)\left\|x_{k}-x^{\ast}\right\|^{2}-2\tau_{k}\eta_{k}\left\langle\tilde{x}_{k}-x^{\ast},g_{k}\right\rangle-2(1-\tau_{k})\eta_{k}\left\langle{x}_{k}-x^{\ast},g_{k}\right\rangle$
$\displaystyle\quad+\eta_{k}^{2}\left\|g_{k}\right\|^{2}$ (27)

Taking conditional expectation on both sides, we then estimate the first inner
product:

$\displaystyle-\mathbb{E}[\left\langle\tilde{x}_{k}-x^{\ast},g_{k}\right\rangle]$
$\displaystyle=-\left\langle\tilde{x}_{k}-x^{\ast},\nabla
f(x_{k})\right\rangle=-\left\langle(1-\beta)^{-1}\left(x_{k}-\beta
x_{k-1}\right)-x^{\ast},\nabla f(x_{k})\right\rangle$
$\displaystyle=-\frac{\left\langle x_{k}-x^{\ast},\nabla
f(x_{k})\right\rangle}{1-\beta}+\frac{\beta}{1-\beta}\left\langle
x_{k-1}-x_{k}+x_{k}-x^{\ast},\nabla f(x_{k})\right\rangle$
$\displaystyle\mathop{\leq}^{(a)}-\left(\theta_{1}\left\|x_{k}-x^{\ast}\right\|^{2}-\theta_{2}\right)+\frac{\beta}{1-\beta}\left(f(x_{k-1})-f(x_{k})+\frac{L}{2}\left\|x_{k}-x_{k-1}\right\|^{2}\right)$
(28)

where $(a)$ follows from the $R$-dissipativity condition and $L$-smoothness
which implies that (26).

Next, we consider two situations: (1) if $\tau_{k}=1$, that is
$\eta_{k}=\eta_{k-1}$. Incorporating the inequality (B) into (B), we have

$\displaystyle\mathbb{E}[\left\|\tilde{x}_{k+1}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle\leq\left\|\tilde{x}_{k}-x^{\ast}\right\|^{2}-2\theta_{1}\eta_{k}\left\|x_{k}-x^{\ast}\right\|^{2}+2\theta_{2}\eta_{k}+\eta_{k}^{2}\mathbb{E}[\left\|g_{k}\right\|^{2}\mid\mathcal{F}_{k}]+\frac{2\beta\eta_{k}}{1-\beta}\left(f(x_{k-1})-f(x_{k})+\frac{L}{2}\left\|x_{k}-x_{k-1}\right\|^{2}\right)$

(2) If $\tau_{k}\in(0,1)$, we then estimate

$\displaystyle-\mathbb{E}[\left\langle{x}_{k}-x^{\ast},g_{k}\right\rangle\mid\mathcal{F}_{k}]=-\left\langle{x}_{k}-x^{\ast},\nabla
f(x_{k})\right\rangle\leq-\theta_{1}\left\|x_{k}-x^{\ast}\right\|^{2}+\theta_{2}.$
(30)

Finally, incorporating the above results (B) and (30) into (B), we can achieve
that

$\displaystyle\mathbb{E}[\left\|\tilde{x}_{k+1}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle\leq\tau_{k}\left\|\tilde{x}_{k}-x^{\ast}\right\|^{2}+\left(1-\tau_{k}\right)\left\|x_{k}-x^{\ast}\right\|^{2}-2\tau_{k}\eta_{k}\left(\theta_{1}\left\|x_{k}-x^{\ast}\right\|^{2}-\theta_{2}\right)+\eta_{k}^{2}\mathbb{E}[\left\|g_{k}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle\quad+\frac{2\beta\tau_{k}\eta_{k}}{1-\beta}\left(f(x_{k-1})-f(x_{k})+\frac{L}{2}\left\|x_{k}-x_{k-1}\right\|^{2}\right)+2(1-\tau_{k})\eta_{k}\left(-\theta_{1}\left\|x_{k}-x^{\ast}\right\|^{2}+\theta_{2}\right)$
$\displaystyle=\tau_{k}\left\|\tilde{x}_{k}-x^{\ast}\right\|^{2}-\left(2\eta_{k}\theta_{1}-\left(1-\tau_{k}\right)\right)\left\|x_{k}-x^{\ast}\right\|^{2}+2\eta_{k}\theta_{2}+\eta_{k}^{2}\mathbb{E}[\left\|g_{k}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle\quad+\frac{2\beta
L}{1-\beta}\cdot\eta_{k}\tau_{k}\left\|x_{k-1}-x_{k}\right\|^{2}+\frac{2\beta\tau_{k}\eta_{k}}{1-\beta}\left(f(x_{k-1})-f(x_{k})\right).$

We now complete the proof. ∎

###### Proof.

(of Theorem 3.2) In this case, we consider $\eta_{k}=\eta$ is a constant step-
size. From Lemma B.1, we have

$\displaystyle\mathbb{E}[\left\|x_{k+1}-x_{k}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle\leq\beta^{2}\left\|x_{k}-x_{k-1}\right\|^{2}+\eta^{2}(1-\beta)^{2}\mathbb{E}[\left\|g_{k}\right\|^{2}]+2\eta\beta(1-\beta)\left(f(x_{k-1})-f(x_{k})+\frac{L}{2}\left\|x_{k}-x_{k-1}\right\|^{2}\right)$
$\displaystyle=\left(\beta^{2}+\eta\beta(1-\beta)L\right)\left\|x_{k}-x_{k-1}\right\|^{2}+\eta^{2}(1-\beta)^{2}\mathbb{E}[\left\|g_{k}\right\|^{2}]+2\eta\beta(1-\beta)\left(f(x_{k-1})-f(x_{k})\right).$
(31)

Then we turn to estimate $\left\|\tilde{x}_{k+1}-x^{\ast}\right\|^{2}$. For
the constant step-size $\eta_{k}=\eta$, we have
$\tau_{k}=\eta_{k}/\eta_{k-1}=1$. By Lemma B.2(i), we can achieve that

$\displaystyle\mathbb{E}[\left\|\tilde{x}_{k+1}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle\leq\left\|\tilde{x}_{k}-x^{\ast}\right\|^{2}-2\theta_{1}\eta\left\|x_{k}-x^{\ast}\right\|^{2}+2\theta_{2}\eta_{k}+\eta^{2}\mathbb{E}[\left\|g_{k}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle\quad+\frac{2\beta\eta}{1-\beta}\left(f(x_{k-1})-f(x_{k})+\frac{L}{2}\left\|x_{k}-x_{k-1}\right\|^{2}\right).$

Next we define a function $W_{k}$:

$\displaystyle
W_{k+1}=\left\|\tilde{x}_{k+1}-x^{\ast}\right\|^{2}+\left\|x_{k+1}-x_{k}\right\|^{2}+2\eta\beta\left((1-\beta)+(1-\beta)^{-1}\right)\left(f(x_{k})-f^{\ast}\right).$

Then applying the results derived from Lemmas B.1 and B.2, we have

$\displaystyle\mathbb{E}[W_{k+1}\mid\mathcal{F}_{k}]=\mathbb{E}[\left\|\tilde{x}_{k+1}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k}]+\mathbb{E}[\left\|x_{k+1}-x_{k}\right\|^{2}\mid\mathcal{F}_{k}]+2\eta\beta(1-\beta)\left(f(x_{k})-f^{\ast}\right)$
$\displaystyle\leq\left\|\tilde{x}_{k}-x^{\ast}\right\|^{2}+\left(\beta^{2}+\eta\beta(1-\beta)L+\eta\frac{\beta
L}{(1-\beta)}\right)\left\|x_{k-1}-x_{k}\right\|^{2}-2\theta_{1}\eta\left\|x_{k}-x^{\ast}\right\|^{2}+2\eta\theta_{2}$
$\displaystyle\quad+\eta^{2}\left((1-\beta)^{2}+1\right)\left(\sigma^{2}+(\rho+1)L^{2}\left\|x_{k}-x^{\ast}\right\|^{2}\right)+2\eta\beta\left((1-\beta)+(1-\beta)^{-1}\right)\left(f(x_{k-1})-f^{\ast}\right).$
(32)

where the above inequality uses the fact that

$\displaystyle\mathbb{E}[\left\|g_{k}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle=\mathbb{E}[\left\|g_{k}-\nabla f(x_{k})+\nabla
f(x_{k})\right\|^{2}\mid\mathcal{F}_{k}]=\mathbb{E}[\left\|g_{k}-\nabla
f(x_{k})\right\|^{2}\mid\mathcal{F}_{k}]+\left\|\nabla f(x_{k})\right\|^{2}$
$\displaystyle\leq(\rho+1)\left\|\nabla
f(x_{k})\right\|^{2}+\sigma^{2}\leq(\rho+1)L^{2}\left\|x_{k}-x^{\ast}\right\|^{2}+\sigma^{2}.$

Suppose that

$\displaystyle\eta\leq\frac{(1-\beta^{2})}{\beta
L\left(1-\beta+(1-\beta)^{-1}\right)},$ (33)

we have

$\displaystyle\beta^{2}+\eta\beta(1-\beta)L+\eta\frac{\beta L}{(1-\beta)}\leq
1.$

Then (B) can be estimated as

$\displaystyle\mathbb{E}[W_{k+1}\mid\mathcal{F}_{k}]$ $\displaystyle\leq
W_{k}-2\eta\theta_{1}\left\|x_{k}-x^{\ast}\right\|^{2}+\eta^{2}\left((1-\beta)^{2}+1\right)\left(\sigma^{2}+(\rho+1)L^{2}\left\|x_{k}-x^{\ast}\right\|^{2}\right)+2\eta\theta_{2}$
$\displaystyle=W_{k}-\eta\left(2\theta_{1}-\eta((1-\beta)^{2}+1)(\rho+1)L^{2}\right)\left\|x_{k}-x^{\ast}\right\|^{2}+2\eta\theta_{2}+\eta^{2}\left((1-\beta)^{2}+1\right)\sigma^{2}.$

Furthermore, assume that
$\eta\leq\frac{\theta_{1}}{((1-\beta)^{2}+1)(\rho+1)L^{2}}$, then
$2\theta_{1}-\eta((1-\beta)^{2}+1)(\rho+1)L^{2}\geq\theta_{1}$, we have

$\displaystyle\mathbb{E}[W_{k+1}\mid\mathcal{F}_{k}]$ $\displaystyle\leq
W_{k}-\eta\theta_{1}\left\|x_{k}-x^{\ast}\right\|^{2}+2\eta\theta_{2}+\eta^{2}\left((1-\beta)^{2}+1\right)\sigma^{2}.$

If we further let

$\displaystyle
r^{2}=\max\left\\{R^{2},\frac{2\theta_{2}}{\theta_{1}}+\frac{2\eta\left((1-\beta)^{2}+1\right)\sigma^{2}}{\theta_{1}}\right\\},$

once $\left\|x_{k}-x^{\ast}\right\|^{2}\geq r^{2}$, we have

$\displaystyle-\eta\theta_{1}\left\|x_{k}-x^{\ast}\right\|^{2}+2\eta\theta_{2}+\eta^{2}\left((1-\beta)^{2}+1\right)\sigma^{2}\leq
0.$

Then $\mathbb{E}[W_{k+1}\mid\mathcal{F}_{k}]\leq W_{k}$.

If $\left\|x_{1}-x^{\ast}\right\|^{2}\leq r^{2}$, let $x_{k^{{}^{\prime}}}$ be
the first iteration that makes
$\left\|x_{k^{{}^{\prime}}}-x^{\ast}\right\|^{2}\geq r^{2}$ and
$\left\|x_{k^{{}^{\prime}}-2}-x^{\ast}\right\|^{2},\left\|x_{k^{{}^{\prime}}-1}-x^{\ast}\right\|^{2}\leq
r^{2}$. First, we show that $\left\|x_{k^{{}^{\prime}}}-x^{\ast}\right\|^{2}$
will not be far larger than $r^{2}$.

If $\left\|x_{k^{{}^{\prime}}-1}-x^{\ast}\right\|^{2}\leq r^{2}$ and
$\left\|x_{k^{{}^{\prime}}-2}-x^{\ast}\right\|^{2}\leq r^{2}$, then applying
the recursion of SGD with momentum, we have

$\displaystyle\mathbb{E}[\left\|x_{k^{{}^{\prime}}}-x^{\ast}\right\|^{2}]$
$\displaystyle=\mathbb{E}[\left\|x_{k^{{}^{\prime}}-1}-\eta
v_{k^{{}^{\prime}}}-x^{\ast}\right\|^{2}]=\mathbb{E}\left[\left\|x_{k^{{}^{\prime}}-1}-\eta\left(\beta\eta^{-1}\left(x_{k^{{}^{\prime}}-2}-x_{k^{{}^{\prime}}-1}\right)+(1-\beta)g_{k^{{}^{\prime}}-1}\right)-x^{\ast}\right\|^{2}\right]$
$\displaystyle=\mathbb{E}[\left\|(1+\beta)\left(x_{k^{{}^{\prime}}-1}-x^{\ast}\right)-\beta\left(x_{k^{{}^{\prime}}-2}-x^{\ast}\right)-\eta(1-\beta)g_{k^{{}^{\prime}}-1}\right\|^{2}]$
$\displaystyle\mathop{\leq}^{(a)}3(1+\beta)^{2}\left\|x_{k^{{}^{\prime}}-1}-x^{\ast}\right\|^{2}+3\beta^{2}\left\|x_{k^{{}^{\prime}}-2}-x^{\ast}\right\|^{2}+3\eta^{2}(1-\beta)^{2}\mathbb{E}[\left\|g_{k^{{}^{\prime}}-1}\right\|^{2}]$
$\displaystyle\mathop{\leq}^{(b)}3(1+\beta)^{2}\left\|x_{k^{{}^{\prime}}-1}-x^{\ast}\right\|^{2}+3\beta^{2}\left\|x_{k^{{}^{\prime}}-2}-x^{\ast}\right\|^{2}+3\eta^{2}(1-\beta)^{2}(\sigma^{2}+(\rho+1)L\left\|x_{k^{{}^{\prime}}-1}-x^{\ast}\right\|^{2})$
$\displaystyle\leq
3\left((1+\beta)^{2}+\beta^{2}\right)r^{2}+3\eta^{2}(1-\beta)^{2}(\sigma^{2}+(\rho+1)L^{2}r^{2}):=\Delta_{{}^{\prime}}^{2}$
(34)

where $(a)$ follows from the fact that $\left(\frac{x+y+z}{3}\right)^{2}\leq
3(x^{2}+y^{2}+z^{2})$ and $(b)$ applies inequality (A.1) that
$\mathbb{E}[\left\|g_{k}\right\|^{2}\mid\mathcal{F}_{k}]\leq\sigma^{2}+(\rho+1)\left\|\nabla
f(x_{k})\right\|^{2}$. In the case that
$\left\|x_{k^{{}^{\prime}}}-x^{\ast}\right\|^{2}\geq r^{2}$ and
$\left\|x_{k^{{}^{\prime}}-1}-x^{\ast}\right\|^{2}\leq r^{2}$), we can
estimate the Lyapunov function $W_{k}$ at $k^{{}^{\prime}}$-th iteration

$\displaystyle\mathbb{E}[W_{k^{{}^{\prime}}}]$
$\displaystyle=\mathbb{E}[\left\|\tilde{x}_{k^{{}^{\prime}}}-x^{\ast}\right\|^{2}+\left\|x_{k^{{}^{\prime}}}-x_{k^{{}^{\prime}}-1}\right\|^{2}+2\eta\beta\left((1-\beta)+(1-\beta)^{-1}\right)\left(f(x_{k^{{}^{\prime}}-1})-f^{\ast}\right)]$
$\displaystyle\leq\mathbb{E}\left[\left\|(1-\beta)^{-1}\left(x_{k^{{}^{\prime}}}-\beta
x_{k^{{}^{\prime}}-1}\right)-x^{\ast}\right\|^{2}+\left\|x_{k^{{}^{\prime}}}-x^{\ast}-(x_{k^{{}^{\prime}}-1}-x^{\ast})\right\|^{2}\right]$
$\displaystyle\quad+\eta\beta\left((1-\beta)+(1-\beta)^{-1}\right)L\mathbb{E}[\left\|x_{k^{{}^{\prime}}-1}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle\leq\left(\frac{1}{(1-\beta)^{2}}+\frac{\beta^{2}}{(1-\beta)^{2}}\right)\left(\mathbb{E}[\left\|x_{k^{{}^{\prime}}}-x^{\ast}\right\|^{2}]+\mathbb{E}[\left\|x_{k^{{}^{\prime}}-1}-x^{\ast}\right\|^{2}]\right)+2\left(\mathbb{E}[\left\|x_{k^{{}^{\prime}}}-x^{\ast}\right\|^{2}]+\mathbb{E}[\left\|x_{k^{{}^{\prime}}-1}-x^{\ast}\right\|^{2}]\right)$
$\displaystyle\quad+\eta\beta\left((1-\beta)+(1-\beta)^{-1}\right)L\mathbb{E}[\left\|x_{k^{{}^{\prime}}-1}-x^{\ast}\right\|^{2}]$
$\displaystyle\leq\left(\frac{1+\beta^{2}}{(1-\beta)^{2}}+2\right)\left(\Delta_{{}^{\prime}}^{2}+r^{2}\right)+\eta\beta\left((1-\beta)+(1-\beta)^{-1}\right)Lr^{2}.$

As we discussed before, once $\left\|x_{k}-x^{\ast}\right\|^{2}\geq r^{2}$,
then $\mathbb{E}[W_{k}]$ is decreasing. Thus we can conclude that
$\mathbb{E}[W_{k}]$ is uniformly bounded by

$\displaystyle\mathbb{E}[W_{k}]\leq\left(\frac{1+\beta^{2}}{(1-\beta)^{2}}+2\right)\left(\Delta_{{}^{\prime}}^{2}+r^{2}\right)+\eta\beta\left((1-\beta)+(1-\beta)^{-1}\right)Lr^{2}.$

If the initial point $\left\|x_{1}-x^{\ast}\right\|^{2}>r^{2}$ but is finite.
Then we can see that $\mathbb{E}[W_{k}]$ is decreasing until
$\left\|x_{k}-x^{\ast}\right\|^{2}\leq r^{2}$. Thus in this case, we also can
conclude that $\mathbb{E}[W_{k}]$ is uniformly bounded. Due to that the three
quantities
$\mathbb{E}[\left\|\tilde{x}_{k}-x^{\ast}\right\|],\mathbb{E}[\left\|x_{k}-x_{k-1}\right\|^{2}],\eta\mathbb{E}[f(x_{k-1})-f^{\ast}]\geq
0$, so we can conclude that the three quantities are uniformly bounded. By the
$L$-smoothness, we can estimate the function value
$\mathbb{E}[f(x_{k})-f^{\ast}]$ as

$\displaystyle\mathbb{E}[f(x_{k})-f^{\ast}]$
$\displaystyle\leq\frac{L}{2}\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]=\frac{L}{2}\mathbb{E}\left[\left\|\tilde{x}_{k}-\frac{\beta}{1-\beta}(x_{k}-x_{k-1})-x^{\ast}\right\|^{2}\right]$
$\displaystyle\leq
L\mathbb{E}[\left\|\tilde{x}_{k}-x^{\ast}\right\|^{2}]+\frac{L\beta^{2}}{(1-\beta)^{2}}\mathbb{E}[\left\|x_{k}-x_{k-1}\right\|^{2}]\leq
L\left(1+\frac{\beta^{2}}{(1-\beta)^{2}}\right)\mathbb{E}[W_{k}]$

is uniformly bounded. Now we complete the proof. ∎

###### Proof.

(Proofs of Theorem 3.3) In this case, we consider the step-size $\eta_{k}$ is
strictly decaying which implies that $\tau_{k}=\eta_{k}/\eta_{k-1}<1$. By
applying Lemma B.1, we have

$\displaystyle\mathbb{E}[\left\|x_{k+1}-x_{k}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle\leq\tau_{k}^{2}\beta^{2}\left\|x_{k}-x_{k-1}\right\|^{2}+\eta_{k}^{2}(1-\beta)^{2}\mathbb{E}[\left\|g_{k}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle\quad+2\beta(1-\beta)\tau_{k}\eta_{k}\left(f(x_{k-1})-f(x_{k})+\frac{L}{2}\left\|x_{k}-x_{k-1}\right\|^{2}\right).$
(35)

By Lemma B.2(ii), we can achieve that

$\displaystyle\mathbb{E}[\left\|\tilde{x}_{k+1}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle\leq\tau_{k}\left\|\tilde{x}_{k}-x^{\ast}\right\|^{2}-\left(2\eta_{k}\theta_{1}-\left(1-\tau_{k}\right)\right)\left\|x_{k}-x^{\ast}\right\|^{2}+2\eta_{k}\theta_{2}+\eta_{k}^{2}\mathbb{E}[\left\|g_{k}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle\quad+\frac{2\beta
L}{1-\beta}\cdot\eta_{k}\tau_{k}\left\|x_{k-1}-x_{k}\right\|^{2}+\frac{2\beta\tau_{k}\eta_{k}}{1-\beta}\left(f(x_{k-1})-f(x_{k})\right).$
(36)

We now define a Lyapunov function $W_{k}$:

$\displaystyle
W_{k+1}=\left\|\tilde{x}_{k+1}-x^{\ast}\right\|^{2}+\left\|x_{k+1}-x_{k}\right\|^{2}+2\gamma_{\beta}\eta_{k}\tau_{k}\left(f(x_{k})-f^{\ast}\right).$

where $\gamma_{\beta}=\beta(1-\beta+(1-\beta)^{-1})$. Then incorporating the
above inequalities (B) and (B), we have

$\displaystyle\mathbb{E}[W_{k+1}\mid\mathcal{F}_{k}]$
$\displaystyle\leq\left\|\tilde{x}_{k}-x^{\ast}\right\|^{2}+\left(\tau_{k}^{2}\beta^{2}+\beta(1-\beta)L\tau_{k}\eta_{k}+\frac{\beta\tau_{k}}{1-\beta}\left(2L\eta_{k}\right)\right)\left\|x_{k}-x_{k-1}\right\|^{2}$
$\displaystyle\quad+2\gamma_{\beta}\eta_{k-1}\tau_{k-1}\left(f(x_{k-1})-f^{\ast}\right)+2\gamma_{\beta}\left(\eta_{k}\tau_{k}-\eta_{k-1}\tau_{k-1}\right)(f(x_{k-1})-f^{\ast})$
$\displaystyle\quad-\left(2\theta_{1}\eta_{k}-(1-\tau_{k})-(\rho+1)\left((1-\beta)^{2}+1\right)L^{2}\eta_{k}^{2}\right)\left\|x_{k}-x^{\ast}\right\|^{2}$
$\displaystyle\quad+2\theta_{2}\eta_{k}+\left((1-\beta)^{2}+1\right)\sigma^{2}\eta_{k}^{2}.$
(37)

If the step-size $\eta_{k}$ is decreasing, then
$\tau_{k}=\eta_{k}/\eta_{k-1}\leq 1$. We assume

$\displaystyle\eta_{k}\leq\frac{1-\tau_{k}^{2}\beta^{2}}{L\tau_{k}\gamma_{\beta}}$
(38)

to ensure that

$\displaystyle\tau_{k}^{2}\beta^{2}+\beta(1-\beta)\tau_{k}\eta_{k}L+\frac{\beta\tau_{k}}{1-\beta}\cdot
2L\eta_{k}\leq 1$

The right side of (38) is decreasing with $\tau_{k}\in(0,1]$, so we set

$\displaystyle\eta_{k}\leq\frac{1-\beta^{2}}{L\gamma_{\beta}}.$

Furthermore, we choose

$\displaystyle\eta_{k}\leq\frac{\theta_{1}}{2(\rho+1)((1-\beta)^{2}+1)L^{2}},$

such that

$\displaystyle(\rho+1)\left((1-\beta)^{2}+1\right)L^{2}\eta_{k}^{2}\leq\frac{\theta_{1}\eta_{k}}{2}.$

That is to say, if

$\displaystyle\eta_{k}\leq\min\left\\{\frac{\theta_{1}}{2(\rho+1)((1-\beta)^{2}+1)L^{2}},\frac{1-\beta^{2}}{L\beta(1-\beta+(1-\beta)^{-1})}\right\\}$

then (B) can be re-written as

$\displaystyle\mathbb{E}[W_{k+1}\mid\mathcal{F}_{k}]$ $\displaystyle\leq
W_{k}-\left(\frac{3\theta_{1}\eta_{k}}{2}-(1-\tau_{k})\right)\left\|x_{k}-x^{\ast}\right\|^{2}+2\theta_{2}\eta_{k}+\left((1-\beta)^{2}+1\right)\sigma^{2}\eta_{k}^{2}$
$\displaystyle\quad+2\gamma_{\beta}\left(\eta_{k}\tau_{k}-\eta_{k-1}\tau_{k-1}\right)(f(x_{k-1})-f^{\ast}).$

Based on different decaying modes, we can achieve the following results.

  * •

Polynomial decaying step-size: $\eta_{k}=\eta_{1}/k^{r}$ for $r\in(0,1]$. In
this case $\tau_{k}=\eta_{k}/\eta_{k-1}=(k-1)^{r}/k^{r}$, then

$\displaystyle\eta_{k}\tau_{k}-\eta_{k-1}\tau_{k-1}$
$\displaystyle=\eta_{1}\left(\frac{(k-1)^{r}}{k^{2r}}-\frac{(k-2)^{r}}{(k-1)^{2r}}\right)=\eta_{1}\frac{(k-1)^{3r}-(k-2)^{r}k^{2r}}{k^{2r}(k-1)^{2r}}$
$\displaystyle=\eta_{1}\frac{(k-1)^{3r}-\left((k-1)^{3}-(k-1)+(k-1)^{2}-1\right)^{r}}{k^{2r}(k-1)^{2r}}<0$

for all $k\geq 3$. For any $r\in(0,1]$ and $k\geq 1$, we have

$\displaystyle k^{r}\leq(k-1)^{r}+1$

then

$\displaystyle 1-\tau_{k}=1-\frac{(k-1)^{r}}{k^{r}}\leq
1-\frac{k^{r}-1}{k^{r}}=\frac{1}{k^{r}}.$

For $\eta_{1}\geq\frac{2}{\theta_{1}}$, we have
$1-\tau_{k}\leq\frac{\theta_{1}}{2}\eta_{k}$, then

$\displaystyle\mathbb{E}[W_{k+1}\mid\mathcal{F}_{k}]$ $\displaystyle\leq
W_{k}-\theta_{1}\eta_{k}\left\|x_{k}-x^{\ast}\right\|^{2}+2\theta_{2}\eta_{k}+\left((1-\beta)^{2}+1\right)\sigma^{2}\eta_{k}^{2}.$

  * •

Linear decay: $\eta_{k}=A-Bk$ where $\eta_{1}=\eta_{\max}$ and
$\eta_{T}=\eta_{\min}=c/\sqrt{T}$, then we have

$\displaystyle A=\frac{T\eta_{\max}-\eta_{\min}}{T-1},$ $\displaystyle\quad
B=\frac{\eta_{\max}-\eta_{\min}}{T-1}.$

Next we turn to estimate the sign of $\eta_{k}\tau_{k}-\eta_{k-1}\tau_{k-1}$.

$\displaystyle\eta_{k}\tau_{k}-\eta_{k-1}\tau_{k-1}=\frac{\eta_{k}^{2}\eta_{k-2}-\eta_{k-1}^{3}}{\eta_{k-1}\eta_{k-2}}$
$\displaystyle=\frac{(A-Bk)^{2}(A-B(k-2))-(A-B(k-1))^{3}}{(A-B(k-1))(A-B(k-2))}$
$\displaystyle=\frac{(A-B(k-1+1))^{2}(A-B(k-1-1))-(A-B(k-1))^{3}}{(A-B(k-1))(A-B(k-2))}$
$\displaystyle=\frac{-B\left[(A-B(k-1))^{2}+B(A-B(k-1)))-B^{2}\right]}{(A-B(k-1))(A-B(k-2))}$
$\displaystyle=\frac{-B\left[(A-Bk+B)^{2}+B(A-Bk)\right]}{(A-B(k-1))(A-B(k-2))}.$

We know that $B>0$ and $A-Bk>0$, then $(A-Bk+B)^{2}+B(A-Bk)>0$, thus we have
$\eta_{k}\tau_{k}-\eta_{k-1}\tau_{k-1}<0$. Next we estimate $1-\tau_{k}$:

$\displaystyle
1-\tau_{k}=1-\frac{\eta_{k}}{\eta_{k-1}}=1-\frac{A-Bk}{A-B(k-1)}=\frac{B}{A-B(k-1)}.$

We know that $\eta_{\min}=c/\sqrt{T}$, let
$c\geq\left(2\frac{\eta_{\max}}{\theta_{1}}\right)^{1/2}$, we have

$\displaystyle
1-\tau_{k}\leq\frac{B}{\eta_{k-1}}\leq\frac{(\eta_{\max}-\eta_{\min})}{(T-1)\eta_{\min}}\leq\frac{\theta_{1}}{2}\eta_{\min}\leq\frac{\theta_{1}}{2}\eta_{k}.$

Finally, we can achieve that

$\displaystyle\mathbb{E}[W_{k+1}\mid\mathcal{F}_{k}]$ $\displaystyle\leq
W_{k}-\theta_{1}\eta_{k}\left\|x_{k}-x^{\ast}\right\|^{2}+2\theta_{2}\eta_{k}+\eta_{k}^{2}\left((1-\beta)^{2}+1\right)\sigma^{2}.$

  * •

Cosine decay step-size: $\eta_{k}=A+B\cos(k\pi/T)$ where
$A=\frac{\eta_{\min}+\eta_{\max}}{2}$ and
$B=\frac{\eta_{\max}-\eta_{\min}}{2}$. We first estimate
$\tau_{k}\eta_{k}-\eta_{k-1}\eta_{k-1}$:

$\displaystyle\eta_{k}\tau_{k}-\eta_{k-1}\tau_{k-1}$
$\displaystyle=\frac{\eta_{k}^{2}}{\eta_{k-1}}-\frac{\eta_{k-1}^{2}}{\eta_{k-2}}=\eta_{k-1}\left(\left(\frac{\eta_{k}}{\eta_{k-1}}\right)^{2}-\frac{\eta_{k-1}}{\eta_{k-2}}\right)$

In order to estimate the sign of $\eta_{k}\tau_{k}-\eta_{k-1}\tau_{k-1}$, we
try to estimate
$\left(\frac{\eta_{k}}{\eta_{k-1}}\right)^{2}-\frac{\eta_{k-1}}{\eta_{k-2}}$.
Then

$\displaystyle\psi_{k}:=\frac{\left(1-\frac{\eta_{k-1}}{\eta_{k-2}}\right)}{1-\left(\frac{\eta_{k}}{\eta_{k-1}}\right)^{2}}=\frac{\frac{\eta_{k-1}}{\eta_{k-2}}}{\frac{\eta_{k}}{\eta_{k-1}}+1}\cdot\frac{\eta_{k-2}-\eta_{k-1}}{\eta_{k-1}-\eta_{k}}.$
(39)

For $k\in[1,T/2]$, by the graph of the step-size, we know that
$\eta_{k}/\eta_{k-1}\leq\eta_{k-1}/\eta_{k-2}\leq 1$ and
$\eta_{k-2}-\eta_{k-1}\leq\eta_{k-1}-\eta_{k}$, we have $\psi_{k}<1$. If
$k\in[T/2,T)$, we can see that $\eta_{k}/\eta_{k-1}\geq\eta_{k-1}/\eta_{k-2}$,
then

$\displaystyle\psi_{k}\leq\frac{1}{2}\frac{\eta_{k-2}-\eta_{k-1}}{\eta_{k-1}-\eta_{k}}$
$\displaystyle=\frac{\sin(\frac{(2k-3)\pi}{2T})}{2\sin(\frac{(2k-1)\pi}{2T})}=\frac{1}{2}\left(\cos(\frac{\pi}{T})-\frac{\cos(\frac{(2k-1)\pi}{2T})\sin(\frac{\pi}{T})}{\sin(\frac{(2k-1)\pi}{2T})}\right)$
$\displaystyle\leq\frac{1}{2}\left(\cos(\frac{\pi}{T})+\frac{\cos(\frac{3\pi}{2T})\sin(\frac{\pi}{T})}{\sin(\frac{3\pi}{2T})}\right)=\frac{1}{2}\cos(\frac{\pi}{T})\left(1+\frac{\tan(\frac{\pi}{2T})}{\tan(\frac{3\pi}{2T})}\right)<1.$

That is for $k\in[1,T)$, we have $\psi_{k}<1$. Thus
$\left(\frac{\eta_{k}}{\eta_{k-1}}\right)^{2}-\frac{\eta_{k-1}}{\eta_{k-2}}<0$,
then we have $\eta_{k}\tau_{k}-\eta_{k-1}\tau_{k-1}<0$. Next we turn to
estimate $1-\tau_{k}$:

$\displaystyle 1-\tau_{k}$
$\displaystyle=1-\frac{\eta_{k}}{\eta_{k-1}}=1-\frac{A+B\cos(k\pi/T)}{A+B\cos((k-1)\pi/T)}=\frac{B\left(\cos((k-1)\pi/T)-\cos(k\pi/T)\right)}{A+B\cos((k-1)\pi/T)}$
$\displaystyle=\frac{2B\sin(\pi/(2T))\sin((2k-1)\pi/(2T))}{\left(A+B\cos((k-1)\pi/T)\right)}\leq\frac{2B\left(\frac{\pi}{2T}\right)}{\left(A+B\cos(k\pi/T)\right)}=\frac{2B\left(\frac{\pi}{2T}\right)}{\eta_{k}}$

Let $\eta_{\min}=c/\sqrt{T}$. To make sure that
$1-\tau_{k}\leq\frac{\theta_{1}}{2}\eta_{k}$, we let
$c\geq\left(\frac{\eta_{\max}^{2}\pi^{2}}{2\theta_{1}}\right)^{1/2}$. Then for
any $k\in[1,T)$, we have

$\displaystyle\mathbb{E}[W_{k+1}\mid\mathcal{F}_{k}]$ $\displaystyle\leq
W_{k}-\theta_{1}\eta_{k}\left\|x_{k}-x^{\ast}\right\|^{2}+2\theta_{2}\eta_{k}+\left((1-\beta)^{2}+1\right)\sigma^{2}\eta_{k}^{2}.$

  * •

Exponential decaying step-size $\eta_{k}=\eta_{1}/\alpha^{k-1}$ where
$\alpha=(\nu/T)^{-1/T}>1$ and $\nu\geq 1$. In this case, we have
$\tau_{k}=\eta_{k}/\eta_{k-1}=1/\alpha$ and

$\displaystyle 1-\tau_{k}=1-1/\alpha\leq\frac{\ln\left(T/\nu\right)}{T}$

where $1-x\leq\ln(\frac{1}{x})$ for any $x>0$.

$\displaystyle\eta_{k}\tau_{k}-\eta_{k-1}\tau_{k-1}=\eta_{1}\left(\frac{1}{\alpha^{k-1}}\frac{1}{\alpha}-\frac{1}{\alpha^{k-2}}\frac{1}{\alpha}\right)=\frac{\eta_{1}}{\alpha^{k}}(1-\alpha)<0$

Let $\eta_{1}\geq\frac{2\ln(T/\nu)}{\theta_{1}\nu}$, then

$\displaystyle
1-\tau_{k}\leq\frac{\ln(T/\nu)}{T}\leq\frac{\theta_{1}}{2}\eta_{k}$

for any $1\leq k\leq T$ and $\nu\in[1,T]$, we have

$\displaystyle\mathbb{E}[W_{k+1}\mid\mathcal{F}_{k}]$ $\displaystyle\leq
W_{k}-\theta_{1}\eta_{k}\left\|x_{k}-x^{\ast}\right\|^{2}+2\theta_{2}\eta_{k}+\left((1-\beta)^{2}+1\right)\sigma^{2}\eta_{k}^{2}.$

For the above four cases, we let

$\displaystyle
r^{2}=\max\left\\{R^{2},\frac{2\theta_{2}}{\theta_{1}}+\frac{((1-\beta^{2})+1)\sigma^{2}\eta_{k}}{\theta_{1}}\right\\},$

the step-size satisfies the following condition:

$\displaystyle\eta_{k}\leq\min\left\\{\frac{\theta_{1}}{2(\rho+1)((1-\beta)^{2}+1)L^{2}},\frac{1-\beta^{2}}{L\beta(1-\beta+(1-\beta)^{-1})}\right\\}.$

Once $\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]\geq r^{2}$, we have
$\mathbb{E}[W_{k+1}]$ is decreasing. Following the same discussion as the
constant step-size in Theorem 3.2, for the decaying modes mentioned above, we
can conclude that the quantities $\mathbb{E}[W_{k}]$,
$\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]$,
$\mathbb{E}[f(x_{k})-f^{\ast}]$ is uniformly bounded. Note that for the cosine
decaying mode, the above results only hold for $k\in[1,T)$. At the final
iterate $k=T$, we next show that $\mathbb{E}[W_{T+1}]$ is also bounded:

$\displaystyle\mathbb{E}[W_{T+1}]$
$\displaystyle\leq\mathbb{E}[W_{T}]-\left(\frac{3\theta_{1}\eta_{T}}{2}-(1-\tau_{T})\right)\mathbb{E}[\left\|x_{T}-x^{\ast}\right\|^{2}]+2\theta_{2}\eta_{T}+\left((1-\beta)^{2}+1\right)\sigma^{2}\eta_{T}^{2}$
$\displaystyle\quad+2\gamma_{\beta}\left(\eta_{T}\tau_{T}-\eta_{T-1}\tau_{T-1}\right)\mathbb{E}[f(x_{T-1})-f^{\ast}].$

where $\tau_{T}=\eta_{T}/\eta_{T-1}\leq 1$,
$\eta_{T}\tau_{T}-\eta_{T-1}\tau_{T-1}>0$, and $\eta_{T}=\eta_{\min}$. Because
$\mathbb{E}[W_{k+1}]$ is uniformly bounded for all $k\in[1,T)$, by the
previous discussion, we know that $\mathbb{E}[W_{T}]$,
$\mathbb{E}[\left\|x_{T}-x^{\ast}\right\|^{2}]$, and
$\mathbb{E}[f(x_{T-1})-f^{\ast}]$ are uniformly bounded. Firstly, we know that

$\displaystyle 1-\tau_{T}$
$\displaystyle=1-\frac{\eta_{T}}{\eta_{T-1}}=\frac{B(\cos((T-1)\pi/T)+1)}{A+B\cos((T-1)\pi/T)}=\frac{B(-\cos(\pi/T)+1)}{A-B\cos(\pi/T)}$
$\displaystyle\mathop{\leq}^{(a)}\frac{B\left(\frac{\pi}{T}\right)^{2}/2}{A-B}=\frac{\eta_{\max}-\eta_{\min}}{2\eta_{\min}}\cdot\frac{\pi^{2}}{2T^{2}}\mathop{\leq}^{(b)}\frac{\eta_{\max}}{4c}\frac{\pi^{2}}{T^{3/2}}$

where $(a)$ follows from the fact that by the Taylor series of
$\cos(x)=1-\frac{x^{2}}{2}+\frac{x^{4}}{4!}+\cdots$, we have
$1-\cos(\pi/T)\leq\frac{\pi^{2}}{2T^{2}}$ and $(b)$ uses the fact that
$\eta_{\min}=c/\sqrt{T}$. Recalling that
$c\geq\left(\frac{\eta_{\max}^{2}\pi^{2}}{2\theta_{1}}\right)^{1/2}$, we know
that this bound
$\frac{\eta_{\max}}{4c}\frac{\pi^{2}}{T^{3/2}}\ll\frac{3\theta_{1}\eta_{T}}{2}$.
This means that the scalar term $\frac{3\theta_{1}\eta_{T}}{2}-(1-\tau_{T})$
of $\mathbb{E}[\left\|x_{T}-x^{\ast}\right\|^{2}]$ is positive. Next we turn
to estimate $\eta_{T}\tau_{T}-\eta_{T-1}\tau_{T-1}$:

$\displaystyle\eta_{T}\tau_{T}-\eta_{T-1}\tau_{T-1}=\tau_{T-1}\eta_{T-1}\left(\frac{\tau_{T}\eta_{T}}{\tau_{T-1}\eta_{T-1}}-1\right)=\tau_{T-1}\eta_{T-1}\left(\frac{\eta_{T}^{2}}{\eta_{T-1}^{2}}\cdot\left(\frac{\eta_{T-1}}{\eta_{T-2}}\right)^{-1}-1\right)$

Recall the definition of $\psi_{k}$ in (39) at $k=T$, we have

$\displaystyle\psi_{T}$
$\displaystyle=\frac{1-\frac{\eta_{T-1}}{\eta_{T-2}}}{1-\left(\frac{\eta_{T}}{\eta_{T-1}}\right)^{2}}=\frac{\frac{\eta_{T-1}}{\eta_{T-2}}}{\frac{\eta_{T}}{\eta_{T-1}}+1}\cdot\frac{\eta_{T-2}-\eta_{T-1}}{\eta_{T-1}-\eta_{T}}\leq\frac{1}{2}\frac{\eta_{T-2}-\eta_{T-1}}{\eta_{T-1}-\eta_{T}}$
$\displaystyle\leq\frac{\sin(\frac{(2T-3)\pi}{2T})}{2\sin(\frac{(2T-1)\pi}{2T})}=\frac{\sin(\frac{3\pi}{2T})}{2\sin(\frac{\pi}{2T})}=\frac{1}{2}\left(\cos(\frac{\pi}{T})+\frac{\cos(\frac{\pi}{2T})}{\sin(\frac{\pi}{2T})}\sin(\frac{\pi}{T})\right)$
$\displaystyle=\frac{1}{2}\left(\cos(\frac{\pi}{T})+\frac{2\cos(\frac{\pi}{2T})}{\sin(\frac{\pi}{2T})}\sin(\frac{\pi}{2T})\cos(\frac{\pi}{2T})\right)=\frac{1}{2}\left(2\cos(\frac{\pi}{T})+1\right)<\frac{3}{2}.$

Then

$\displaystyle\left(\frac{\eta_{T}}{\eta_{T-1}}\right)^{2}\cdot\left(\frac{\eta_{T-1}}{\eta_{T-2}}\right)^{-1}-1$
$\displaystyle\leq\frac{\left(\frac{\eta_{T}}{\eta_{T-1}}\right)^{2}}{1-\frac{3}{2}(1-\left(\frac{\eta_{T}}{\eta_{T-1}}\right)^{2})}-1=\frac{(1-\left(\frac{\eta_{T}}{\eta_{T-1}}\right)^{2}}{3\left(\frac{\eta_{T}}{\eta_{T-1}}\right)^{2}-1}$
$\displaystyle\leq\frac{\frac{B\pi^{2}}{2(A-B)T^{2}}}{2-\frac{B\pi^{2}}{2(A-B)T^{2}}}\leq
1$

where $\eta_{T-1}/\eta_{T}=1+\frac{B}{A-B}(1-\cos(\pi/T))\leq
1+\frac{B\pi^{2}}{2(A-B)T^{2}}\leq 2$ for sufficient large
$c\geq\frac{\eta_{\max}\pi^{2}}{4T^{3/2}}$. Then we can see that
$\eta_{T}\tau_{T}-\eta_{T-1}\tau_{T-1}\leq\eta_{T-1}\tau_{T-1}$. Recall the
definition of $\mathbb{E}[W_{T}]$, we know that
$2\gamma_{\beta}\eta_{T-1}\tau_{T-1}\mathbb{E}[f(x_{T-1})-f^{\ast}]\leq\mathbb{E}[W_{T}]$.
By the above analysis, we can get that

$\displaystyle\mathbb{E}[W_{T+1}]$
$\displaystyle\leq\mathbb{E}[W_{T}]+2\gamma_{1}\theta_{2}\eta_{T}+\left((1-\beta)^{2}+1\right)\sigma^{2}\eta_{T}^{2}+2\gamma_{\beta}\left(\eta_{T}\tau_{T}-\eta_{T-1}\tau_{T-1}\right)\mathbb{E}[f(x_{T-1})-f^{\ast}]$
$\displaystyle\leq\mathbb{E}[W_{T}]+2\theta_{2}\eta_{\min}+\left((1-\beta)^{2}+1\right)\sigma^{2}\eta_{\min}^{2}+2\gamma_{\beta}\eta_{T-1}\tau_{T-1}\mathbb{E}[f(x_{T-1})-f^{\ast}]$
$\displaystyle\leq\mathbb{E}[W_{T}]+2\theta_{2}\eta_{\min}+\left((1-\beta)^{2}+1\right)\sigma^{2}\eta_{\min}^{2}+\mathbb{E}[W_{T}]$
$\displaystyle=2\mathbb{E}[W_{T}]+2\theta_{2}\eta_{\min}+\left((1-\beta)^{2}+1\right)\sigma^{2}\eta_{\min}^{2}$

For the cosine decaying step-size, $\mathbb{E}[W_{T+1}]$ is also bounded. That
is to say, for all $k\in[1,T+1]$, the quantities $\mathbb{E}[W_{k}]$ generated
from the cosine decaying mode is uniformly bounded. ∎

###### Proof.

(Bandwidth-based Step-Size)

At each stage, we assume that the step-size is decreasing
($\eta_{k}\leq\eta_{k-1}\leq\eta_{k-2}$) for all $k\in((t-1)S,tS]$. Then
considering the step-size modes discussed in Theorems 3.2 and 3.3, we can see
that:

  * •

Step-decay step-size: $\eta_{k}=\eta_{1}/\alpha^{t-1}$ for $k\in(S(t-1),St]$
where $S=T/N$ and $t\in[N]$. At each stage $t$, we know that the step-size is
a constant for all $k\in((t-1)S,tS]$. By applying the results for constant
step-sizes in Theorem 3.2, we can see that at each stage $t\in[N]$, the
quantity $W_{k}$ is uniformly bounded for $k\in((t-1)S+2,tS]$, that is

$\displaystyle\mathbb{E}[W_{k+1}]\leq\left(\frac{1+\beta^{2}}{(1-\beta)^{2}}+2\right)\left(\Delta_{t}^{2}+r^{2}\right)+\eta_{k}L\beta(1-\beta+(1-\beta)^{-1})r^{2}$

where
$\Delta_{t}^{2}=3\left((1+\beta)^{2}+\beta^{2}\right)r^{2}+3\eta_{k}^{2}(1-\beta)^{2}(\sigma^{2}+(\rho+1)L^{2}r^{2})$.
Therefore, as we discussed in Theorem 3.2, at each stage, the quantities

$\displaystyle\mathbb{E}[\left\|\tilde{x}_{k+1}-x^{\ast}\right\|]\leq\mathbb{E}[W_{k+1}],$
$\displaystyle\quad\mathbb{E}[\left\|x_{k+1}-x_{k}\right\|^{2}]\leq\mathbb{E}[W_{k+1}];$
$\displaystyle\mathbb{E}[\left\|x_{k+1}-x^{\ast}\right\|^{2}]\leq
2\left(1+\frac{\beta^{2}}{(1-\beta)^{2}}\right)\mathbb{E}[W_{k+1}],$
$\displaystyle\quad\mathbb{E}[f(x_{k+1})-f^{\ast}]\leq
L\left(1+\frac{\beta^{2}}{(1-\beta)^{2}}\right)\mathbb{E}[W_{k+1}]$

are also uniformly bounded for all $k\in((t-1)S+2,tS]$. By the definition of
$\tau_{k}$, at $k=(t-1)S+1$, we have
$\tau_{(t-1)S+1}=\eta_{(t-1)S+1}/\eta_{(t-1)S}=1/\alpha$, then we define

$\displaystyle
W_{(t-1)S+2}=\left\|\tilde{x}_{(t-1)S+2}-x^{\ast}\right\|^{2}+\left\|x_{(t-1)S+2}-x_{(t-1)S+1}\right\|^{2}+2\frac{\eta_{(t-1)S+1}}{\alpha}\gamma_{\beta}\left(f(x_{(t-1)S+1})-f^{\ast}\right).$

Similar to Theorem 3.3 (see (B)), we can estimate $\mathbb{E}[W_{(t-1)S+2}]$
as

$\displaystyle\mathbb{E}[W_{(t-1)S+2}]$
$\displaystyle:=\mathbb{E}\left[\left\|\tilde{x}_{(t-1)S+2}-x^{\ast}\right\|^{2}+\left\|x_{(t-1)S+2}-x_{(t-1)S+1}\right\|^{2}+\frac{2\eta_{(t-1)S+1}}{\alpha}\gamma_{\beta}\left(f(x_{(t-1)S+1})-f^{\ast}\right)\right]$
$\displaystyle=W_{(t-1)S+1}-\left(\frac{3\theta_{1}\eta_{(t-1)S+1}}{2}-\left(1-\frac{1}{\alpha}\right)\right)\left\|x_{(t-1)S+1}-x^{\ast}\right\|^{2}+\left((1-\beta)^{2}+1\right)\sigma^{2}\eta_{(t-1)S+1}^{2}$
$\displaystyle\quad+2\theta_{2}\eta_{(t-1)S+1}+2\gamma_{\beta}\left(\eta_{(t-1)S+1}\tau_{(t-1)S+1}-\eta_{{(t-1)S}}\tau_{{(t-1)S}}\right)(f(x_{{(t-1)S}})-f^{\ast})$
$\displaystyle\leq
W_{(t-1)S+1}+2(1-\frac{1}{\alpha})^{2}\left(1+\frac{\beta^{2}}{(1-\beta)^{2}}\right)\mathbb{E}[W_{(t-1)S+1}]+\frac{2\theta_{2}\eta_{1}}{\alpha^{t-1}}+\frac{\left((1-\beta)^{2}+1\right)\sigma^{2}\eta_{1}^{2}}{\alpha^{2(t-1)}}$

where $\mathbb{E}[\left\|x_{(t-1)S+1}-x^{\ast}\right\|^{2}]\leq
2\left(1+\frac{\beta^{2}}{(1-\beta)^{2}}\right)\mathbb{E}[W_{(t-1)S+1}]$ which
are uniformly bounded, then we can conclude that $\mathbb{E}[W_{(t-1)S+2}]$
can be bounded by $\mathbb{E}[W_{(t-1)S+1}]$ plus a constant term. Thus in
this case, we can derive that $\mathbb{E}[W_{k}]$ is uniformly bounded for all
$k\in[1,T+1]$.

  * •

We then consider the three decaying modes: polynomial decay, linear decay, and
cosine decay modes discussed in Theorem 3.3 at each stages. First, we consider
polynomial decaying and linear decay. From the results of Theorem 3.3, we can
see that $\mathbb{E}[W_{k+1}]$ is uniformly bounded for $k\in((t-1)S+2,tS]$
and its bound can be derived similar to Theorem 3.2, that is

$\displaystyle\mathbb{E}[W_{k+1}]\leq\left(\frac{1+\beta^{2}}{(1-\beta)^{2}}+2\right)\left(\Delta_{t}^{2}+r^{2}\right)+\eta_{k}\tau_{k}L\gamma_{\beta}r^{2}$

where
$\Delta_{t}^{2}=3\left((1+\tau_{k}\beta)^{2}+\beta^{2}\tau_{k}^{2}\right)r^{2}+3\eta_{k}^{2}(1-\beta)^{2}(\sigma^{2}+(\rho+1)L^{2}r^{2})$
and $0<\tau_{k}\leq 1$. Because
$\eta_{\min}^{t}\leq\eta_{k}\leq\eta_{\max}^{t}$ for all $k$, the upper bound
is non-expanding for each stage $t$. However, at $k=(t-1)S+1$, we have
$\tau_{(t-1)S+1}=\eta_{(t-1)S+1}/\eta_{(t-1)S}\leq\eta_{\max}^{t}/\eta_{\min}^{t}\leq
s_{0}$. Similar to the above discussion for step-decay, we get that

$\displaystyle\mathbb{E}[W_{(t-1)S+2}]$
$\displaystyle:=\mathbb{E}\left[\left\|\tilde{x}_{(t-1)S+2}-x^{\ast}\right\|^{2}+\left\|x_{(t-1)S+2}-x_{(t-1)S+1}\right\|^{2}+\frac{2\eta_{(t-1)S+1}}{\alpha}\gamma_{\beta}\left(f(x_{(t-1)S+1})-f^{\ast}\right)\right]$
$\displaystyle=W_{(t-1)S+1}-\left(\frac{3\theta_{1}\eta_{(t-1)S+1}}{2}-(1-s_{0})\right)\left\|x_{(t-1)S+1}-x^{\ast}\right\|^{2}+\left((1-\beta)^{2}+1\right)\sigma^{2}\eta_{(t-1)S+1}^{2}$
$\displaystyle\quad+2\theta_{2}\eta_{(t-1)S+1}+2\gamma_{\beta}\left(\eta_{(t-1)S+1}\tau_{(t-1)S+1}-\eta_{{(t-1)S}}\tau_{{(t-1)S}}\right)(f(x_{{(t-1)S}})-f^{\ast})$
$\displaystyle\leq
W_{(t-1)S+1}+2(1-s_{0})\left(1+\frac{\beta^{2}}{(1-\beta)^{2}}\right)\mathbb{E}[W_{(t-1)S+1}]+2\theta_{2}\eta_{\max}^{t}+\left((1-\beta)^{2}+1\right)\sigma^{2}\left(\eta_{\max}^{t}\right)^{2}$
$\displaystyle\quad+2\gamma_{\beta}s_{0}\eta_{\max}^{t}\left(f(x_{(t-1)S})-f^{\ast}\right).$

As we know $\mathbb{E}[W_{(t-1)S+1}]$ and $\mathbb{E}[f(x_{(t-1)S})-f^{\ast}]$
are uniformly bounded and $\eta_{\max}^{t}$ is also upper bounded, we can
conclude that $\mathbb{E}[W_{(t-1)S+2}]$ is also bounded.

However, for the cosine decay mode, the only difference from polynomial and
linear decay modes lies on the last iterate of each stage. In Theorem 3.3, we
show that

$\displaystyle\mathbb{E}[W_{(t-1)S+1}]\leq
2\mathbb{E}[W_{(t-1)S}]+2\theta_{2}\eta_{\min}^{t}+((1-\beta)^{2}+1)\sigma^{2}\left(\eta_{\min}^{t}\right)^{2}.$

The estimation of $\mathbb{E}[W_{(t-1)S+2}]$ for the cosine decay mode is same
as polynomial and linear modes. Thus, we also can make a conclusion that
$\mathbb{E}[W_{k}]$ is uniformly bounded for the bandwidth step-size with the
cosine decay mode.

∎

##  Appendix C Supplementary Material for Functions with Slower Growth

###### Proof.

(of Remark 6) When $x^{\ast}=0$, the two conditions are the same. Suppose that
$\left\|x^{\ast}\right\|>0$, then

$\displaystyle\left\langle\nabla
f(x),x\right\rangle\geq\theta_{1}^{{}^{\prime}}\left\|x\right\|^{p}-\theta_{2}^{{}^{\prime}}=\theta_{1}^{{}^{\prime}}\left(\left\|x-x^{\ast}+x^{\ast}\right\|^{p}\right)-\theta_{2}^{{}^{\prime}}$
(40)

We apply Young’s inequality and $\left\|\nabla
f(x)\right\|^{2}\leq\theta_{3}(1+\left\|x-x^{\ast}\right\|^{2\tau})$ and
assume that $R\geq 1$, then for any $x\in\mathbb{R}^{d}$ that
$\left\|x-x^{\ast}\right\|\geq R$

$\displaystyle\left\langle\nabla f(x),x^{\ast}\right\rangle$
$\displaystyle\leq\frac{s^{\alpha_{1}}\left\|\nabla
f(x)\right\|^{\alpha_{1}}}{\alpha_{1}}+\frac{\left\|x^{\ast}\right\|^{\alpha_{2}}}{s^{\alpha_{2}}\alpha_{2}}\leq\frac{s^{\alpha_{1}}\theta_{3}^{\alpha_{1}/2}\left(1+\left\|x-x^{\ast}\right\|^{2\tau}\right)^{\alpha_{1}/2}}{\alpha_{1}}+\frac{\left\|x^{\ast}\right\|^{\alpha_{2}}}{s^{\alpha_{2}}\alpha_{2}}$
$\displaystyle\leq\frac{s^{\alpha_{1}}(2\theta_{3})^{\alpha_{1}/2}\left\|x-x^{\ast}\right\|^{\tau\alpha_{1}}}{\alpha_{1}}+\frac{\left\|x^{\ast}\right\|^{\alpha_{2}}}{s^{\alpha_{2}}\alpha_{2}}$
(41)

where $1/\alpha_{1}+1/\alpha_{2}=1$, $\alpha_{1},\alpha_{2}>0$ and $s>0$.

$\displaystyle\left\|x-x^{\ast}+x^{\ast}\right\|^{p}=\left(\left\|x-x^{\ast}+x^{\ast}\right\|^{2}\right)^{p/2}$
$\displaystyle\geq\left(\left\|x-x^{\ast}\right\|^{2}+\left\|x^{\ast}\right\|^{2}-2\left\|x-x^{\ast}\right\|\left\|x^{\ast}\right\|\right)^{p/2}$
$\displaystyle=\left(\left(\left\|x-x^{\ast}\right\|-\left\|x^{\ast}\right\|\right)^{2}\right)^{p/2}=|\left\|x-x^{\ast}\right\|-\left\|x^{\ast}\right\||^{p}$
(42)

If we assume that $R\geq\max\left\\{2\left\|x^{\ast}\right\|,1\right\\}$, then
for any $\left\|x-x^{\ast}\right\|\geq R$, applying (C) we have

$\displaystyle\left\|x-x^{\ast}+x^{\ast}\right\|^{p}\geq\frac{1}{2^{p}}\left\|x-x^{\ast}\right\|^{p}.$
(43)

Then applying the above result and (40) and (C), we can get that

$\displaystyle\left\langle\nabla
f(x),x-x^{\ast}\right\rangle\geq\frac{\theta_{1}^{{}^{\prime}}}{2^{p}}\left\|x-x^{\ast}\right\|^{p}-\theta_{2}^{{}^{\prime}}-\frac{s^{\alpha_{1}}(2\theta_{3})^{\alpha_{1}/2}\left\|x-x^{\ast}\right\|^{\tau\alpha_{1}}}{\alpha_{1}}-\frac{\left\|x^{\ast}\right\|^{\alpha_{2}}}{s^{\alpha_{2}}\alpha_{2}}$

Let $\alpha_{1}=p/\tau$ and $s=\left(\frac{\theta_{1}^{{}^{\prime}}p}{\tau
2^{p+1}}\right)^{\tau/p}/\sqrt{2\theta_{3}}$, we have

$\displaystyle\frac{s^{\alpha_{1}}(2\theta_{3})^{\alpha_{1}/2}\left\|x-x^{\ast}\right\|^{\tau\alpha_{1}}}{\alpha_{1}}=\frac{1}{2}\cdot\frac{\theta_{1}^{{}^{\prime}}}{2^{p}}\left\|x-x^{\ast}\right\|^{p}$

Therefore,

$\displaystyle\left\langle\nabla
f(x),x-x^{\ast}\right\rangle\geq\frac{\theta_{1}^{{}^{\prime}}}{2^{p+1}}\left\|x-x^{\ast}\right\|^{p}-\theta_{2}^{{}^{\prime}}-\frac{\left\|x^{\ast}\right\|^{\alpha_{2}}}{s^{\alpha_{2}}\alpha_{2}}:=\theta_{1}\left\|x-x^{\ast}\right\|^{p}-\theta_{2}$
(44)

where $\theta_{1}=\frac{\theta_{1}^{{}^{\prime}}}{2^{p+1}}$ and
$\theta_{2}=\theta_{2}^{{}^{\prime}}+\frac{\left\|x^{\ast}\right\|^{\alpha_{2}}}{s^{\alpha_{2}}\alpha_{2}}$
with $\alpha_{2}=\frac{p}{p-\tau}$ and
$s=\left(\frac{\theta_{1}^{{}^{\prime}}p}{\tau
2^{p+1}}\right)^{\tau/p}/\sqrt{2\theta_{3}}$.

∎

###  C.1 Proofs of SGD Under Generalized $R$-dissipativity

###### Proof.

(of Theorem 4.1) Let

$\displaystyle
r^{2}=\max\left\\{R^{2},\left(\eta_{\max}(\rho+1)\frac{\theta_{3}}{\theta_{1}}\right)^{1/(p-2\tau)},\left(\frac{2\theta_{2}}{\theta_{1}}+\frac{\left(\sigma^{2}+(\rho+1)\theta_{3}\right)\eta_{\max}}{\theta_{1}}\right)^{2/p}\right\\}.$
(45)

First, we consider the initial point $x_{1}$ that
$\left\|x_{1}-x^{\ast}\right\|\leq r$. Suppose that there exist an iteration
$k$ such that $\left\|x_{k-1}-x^{\ast}\right\|^{2}\leq r^{2}$ and
$\left\|x_{k}-x^{\ast}\right\|^{2}>r^{2}$, then the generalized
$R$-dissipativity holds at $x_{k}$ and its gradient is also $\tau$-growth.
Applying the recursion of SGD, we have

$\displaystyle\mathbb{E}[\left\|x_{k+1}-x^{\ast}\right\|^{2}]$
$\displaystyle=\mathbb{E}[\left\|x_{k}-\eta_{k}g_{k}-x^{\ast}\right\|^{2}]=\left\|x_{k}-x^{\ast}\right\|^{2}-2\eta_{k}\mathbb{E}[\left\langle
x_{k}-x^{\ast},g_{k}\right\rangle]+\eta_{k}^{2}\mathbb{E}[\left\|g_{k}\right\|^{2}]$
$\displaystyle\leq\left\|x_{k}-x^{\ast}\right\|^{2}-2\eta_{k}\left\langle
x_{k}-x^{\ast},\nabla
f(x_{k})\right\rangle+\eta_{k}^{2}\left(\mathbb{E}[\left\|g_{k}-\nabla
f(x_{k})\right\|^{2}]+\left\|\nabla f(x_{k})\right\|^{2}\right)$
$\displaystyle\leq\left\|x_{k}-x^{\ast}\right\|^{2}-2\eta_{k}\left(\theta_{1}\left\|x_{k}-x^{\ast}\right\|^{p}-\theta_{2}\right)+\eta_{k}^{2}\left(\sigma^{2}+(\rho+1)\left\|\nabla
f(x_{k})\right\|^{2}\right)$
$\displaystyle\leq\left\|x_{k}-x^{\ast}\right\|^{2}-2\eta_{k}\left(\theta_{1}\left\|x_{k}-x^{\ast}\right\|^{p}-\theta_{2}\right)+\eta_{k}^{2}\left(\sigma^{2}+(\rho+1)\theta_{3}\left(1+\left\|x_{k}-x^{\ast}\right\|^{2\tau}\right)\right)$
$\displaystyle=\left\|x_{k}-x^{\ast}\right\|^{2}-\eta_{k}\left(2\theta_{1}\left\|x_{k}-x^{\ast}\right\|^{p}-\eta_{k}(\rho+1)\theta_{3}\left\|x_{k}-x^{\ast}\right\|^{2\tau}\right)+2\theta_{2}\eta_{k}+\left(\sigma^{2}+(\rho+1)\theta_{3}\right)\eta_{k}^{2}.$

By the assumption that $\tau\leq p/2$ and
$\left\|x_{k}-x^{\ast}\right\|^{2}\geq r^{2}$ at iteration $x_{k}$ and
$r^{2(p-2\tau)}\geq\eta_{k}(\rho+1)\frac{\theta_{3}}{\theta_{1}}$, we can
achieve that

$\displaystyle
2\theta_{1}\left\|x_{k}-x^{\ast}\right\|^{p}-\eta_{k}(\rho+1)\theta_{3}\left\|x_{k}-x^{\ast}\right\|^{2\tau}$
$\displaystyle\geq\theta_{1}\left\|x_{k}-x^{\ast}\right\|^{p},$

Then

$\displaystyle\mathbb{E}[\left\|x_{k+1}-x^{\ast}\right\|^{2}]$
$\displaystyle\leq\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}-\eta_{k}\theta_{1}\left\|x_{k}-x^{\ast}\right\|^{p}+2\theta_{2}\eta_{k}+\left(\sigma^{2}+(\rho+1)\theta_{3}\right)\eta_{k}^{2}.$

Once $\left\|x_{k}-x^{\ast}\right\|^{2}\geq r^{2}$, by the definition of
$r^{2}$, we know

$\displaystyle
r^{p}\geq\frac{2\theta_{2}}{\theta_{1}}+\frac{\left(\sigma^{2}+(\rho+1)\theta_{3}\right)\eta_{k}}{\theta_{1}}$

then $\mathbb{E}[\left\|x_{k+1}-x^{\ast}\right\|^{2}]$ is decreasing until
$\mathbb{E}[\left\|x_{k+1}-x^{\ast}\right\|^{2}]\leq r^{2}$. At the iterates
$k$, we know that $\left\|x_{k-1}-x^{\ast}\right\|\leq r^{2}$, then the
distance of the next iteration with optimal solution $x^{\ast}$ can be bounded
via:

$\displaystyle\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k-1}]$
$\displaystyle=\mathbb{E}[\left\|x_{k-1}-\eta_{k-1}g_{k-1}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k-1}]=2\left\|x_{k-1}-x^{\ast}\right\|^{2}+2\eta_{k-1}^{2}\mathbb{E}[\left\|g_{k-1}\right\|^{2}\mid\mathcal{F}_{k-1}]$
$\displaystyle\leq
2r^{2}+2\eta_{k-1}^{2}\left(\mathbb{E}[\left\|g_{k-1}-\nabla
f(x_{k-1})\right\|^{2}]+\left\|\nabla f(x_{k-1})\right\|^{2}\right)$
$\displaystyle\leq
2r^{2}+2\eta_{k-1}^{2}\left(\sigma^{2}+(\rho+1)\left\|\nabla
f(x_{k-1})\right\|^{2}\right)$ $\displaystyle\leq
2r^{2}+2\eta_{\max}^{2}\left(\sigma^{2}+(\rho+1)\theta_{3}\left(1+\left\|x_{k-1}-x^{\ast}\right\|^{2}\right)\right)$
$\displaystyle\leq
2(1+\eta_{\max}^{2}(\rho+1)\theta_{3})r^{2}+2\eta_{\max}^{2}\left(\sigma^{2}+(\rho+1)\theta_{3}\right).$

If the initial point $x_{1}$ is far from the optimal point $x^{\ast}$, that is
$\left\|x_{1}-x^{\ast}\right\|>r$ but is bounded, by the above analysis, we
can see that the follow-up $\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]$ is
decreasing until $\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]\leq r^{2}$.

Therefore, by the above discussion, we can conclude that

$\displaystyle\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]\leq\min\left\\{\left\|x_{1}-x^{\ast}\right\|^{2},2(1+\eta_{\max}^{2}(\rho+1)\theta_{3})r^{2}+2\eta_{\max}^{2}\left(\sigma^{2}+(\rho+1)\theta_{3}\right)\right\\}$

where $r^{2}$ is given in (45).

∎

###  C.2 Proofs of Momentum Under Generalized $R$-dissipativity

Now, we turn to estimate the SGD algorithm with momentum under Assumption 3.
The basic assumptions include the stochastic gradient $g_{k}$ satisfies
Assumption 1 and the objective function is $L$-smooth. Beyond these, here we
also assume that Assumption 3 holds. The procedure of the proof in this part
is similar to the proof of momentum under $R$-dissipativity. Therefore, we
will omit proofs which are similar to Section 3.3 but only stress the
differences.

Because the $L$-smoothness holds, we still can apply Lemma B.1 to estimate
$\mathbb{E}[\left\|x_{k}-x_{k-1}\right\|^{2}]$.

We assume the function value and its gradient satisfy the following
assumptions: there exist $\theta_{1}>0,\theta_{2}\geq 0,\theta_{3}>0$ and
$R\geq 0$, such that for all $x$ that $\left\|x-x^{\ast}\right\|\geq R$

$\displaystyle\left\langle\nabla
f(x),x-x^{\ast}\right\rangle\geq\theta_{1}\left\|x-x^{\ast}\right\|^{p}-\theta_{2},\,\,\,\left\|\nabla
f(x)\right\|^{2}\leq\theta_{3}(1+\left\|x-x^{\ast}\right\|^{2\tau})$

with $0\leq\tau\leq p/2$ and $p\in[0,2)$.

One obvious change we made is how to estimate
$\mathbb{E}[\left\|g_{k}\right\|^{2}\mid\mathcal{F}_{k}]$:

$\displaystyle\mathbb{E}[\left\|g_{k}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle=\mathbb{E}[\left\|g_{k}-\nabla f(x_{k})+\nabla
f(x_{k})\right\|^{2}]=\mathbb{E}[\left\|g_{k}-\nabla
f(x_{k})\right\|^{2}]+\left\|\nabla f(x_{k})\right\|^{2}$
$\displaystyle\leq(\rho+1)\left\|\nabla
f(x_{k})\right\|^{2}+\sigma^{2}\leq(\rho+1)\theta_{3}\left\|x_{k}-x^{\ast}\right\|^{2\tau}+(\rho+1)\theta_{3}+\sigma^{2}.$
(46)

Then we turn to estimate
$\mathbb{E}[\left\|\tilde{x}_{k+1}-x^{\ast}\right\|^{2}]$. The only change
compared to Lemma B.2 is to estimate

$\displaystyle-\mathbb{E}[\left\langle
x_{k}-x^{\ast},g_{k}\right\rangle=-\left\langle x_{k}-x^{\ast},\nabla
f(x_{k})\right\rangle\leq-\theta_{1}\left\|x_{k}-x^{\ast}\right\|^{p}+\theta_{2}.$

We then make these changes in Lemma B.2 and give the following results.

######  Lemma C.1.

We define $\tilde{x}_{k+1}:=\frac{x_{k+1}-\beta x_{k}}{1-\beta}$. Suppose that
Assumption 1 and (3) hold at current iterations $x_{k}$ and
$\tau_{k}=\eta_{k}/\eta_{k-1}\in(0,1]$, then

  * (i)

If $\tau_{k}=1$, _i.e._ , $\eta_{k}=\eta$ for all $k\geq 1$, we have

$\displaystyle\mathbb{E}[\left\|\tilde{x}_{k+1}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle\leq\left\|\tilde{x}_{k}-x^{\ast}\right\|^{2}-2\theta_{1}\eta_{k}\left\|x_{k}-x^{\ast}\right\|^{p}+2\theta_{2}\eta_{k}+\eta_{k}^{2}\mathbb{E}[\left\|g_{k}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle\quad+\frac{2\beta\eta_{k}}{1-\beta}\left(f(x_{k-1})-f(x_{k})+\frac{L}{2}\left\|x_{k}-x_{k-1}\right\|^{2}\right).$

  * (ii)

else if $\tau_{k}\in(0,1)$, we have

$\displaystyle\mathbb{E}[\left\|\tilde{x}_{k+1}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle\leq\tau_{k}\left\|\tilde{x}_{k}-x^{\ast}\right\|^{2}-2\eta_{k}\theta_{1}\left\|x_{k}-x^{\ast}\right\|^{p}+\left(1-\tau_{k}\right)\left\|x_{k}-x^{\ast}\right\|^{2}+2\eta_{k}\theta_{2}$
$\displaystyle\quad+\eta_{k}^{2}\mathbb{E}[\left\|g_{k}\right\|^{2}\mid\mathcal{F}_{k}]+\frac{2\beta
L}{1-\beta}\eta_{k}\tau_{k}\left\|x_{k-1}-x_{k}\right\|^{2}+\frac{2\beta\tau_{k}\eta_{k}}{1-\beta}\left(f(x_{k-1})-f(x_{k})\right).$

for any $\omega_{1}>0$.

###### Proof.

(of Theorem 4.2) In this case, we consider the constant step-size, that is
$\eta_{k}=\eta$ and $\tau_{k}=\eta_{k}/\eta_{k-1}=1$. Here we define the
Lyapunov function $W_{k+1}$ as

$\displaystyle\mathbb{E}[W_{k+1}]=\mathbb{E}[\left\|\tilde{x}_{k+1}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k}]+\mathbb{E}[\left\|x_{k+1}-x_{k}\right\|^{2}\mid\mathcal{F}_{k}]+\gamma_{\beta}\mathbb{E}[f(x_{k})-f^{\ast}]$

where $\gamma_{\beta}=\beta(1-\beta+(1-\beta)^{-1})$. Incorporating the
results of Lemma B.1, (C.2) and (i) of Lemma C.1, we can get that

$\displaystyle\mathbb{E}[W_{k+1}\mid\mathcal{F}_{k}]=\mathbb{E}[\left\|\tilde{x}_{k+1}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k}]+\mathbb{E}[\left\|x_{k+1}-x_{k}\right\|^{2}\mid\mathcal{F}_{k}]+2\eta\gamma_{\beta}\left(f(x_{k})-f^{\ast}\right)$
$\displaystyle\leq\left\|\tilde{x}_{k}-x^{\ast}\right\|^{2}+\left(\beta^{2}+\eta\beta(1-\beta)L+\eta\frac{\beta
L}{(1-\beta)}\right)\left\|x_{k-1}-x_{k}\right\|^{2}-2\theta_{1}\eta\left\|x_{k}-x^{\ast}\right\|^{p}+2\eta\theta_{2}$
$\displaystyle\quad+\eta^{2}\left((1-\beta)^{2}+1\right)\left(\sigma^{2}+(\rho+1)\theta_{3}+(\rho+1)\theta_{3}\left\|x_{k}-x^{\ast}\right\|^{2\tau}\right)+2\eta\gamma_{\beta}\left(f(x_{k-1})-f^{\ast}\right)$
$\displaystyle\mathop{\leq}^{(a)}\mathbb{E}[W_{k}]-2\theta_{1}\eta\left\|x_{k}-x^{\ast}\right\|^{p}+\eta^{2}\left((1-\beta)^{2}+1\right)(\rho+1)\theta_{3}\left\|x_{k}-x^{\ast}\right\|^{2\tau}$
$\displaystyle\quad+\eta^{2}\left((1-\beta)^{2}+1\right)\left(\sigma^{2}+(\rho+1)\theta_{3}\right)+2\theta_{2}\eta.$
(47)

where $(a)$ follows from $\eta\leq\frac{1-\beta^{2}}{L\gamma_{\beta}}$ to make
sure that

$\displaystyle\beta^{2}+\eta\beta(1-\beta)L+\eta\frac{\beta L}{(1-\beta)}\leq
1$

First, we consider the initial point $x_{1}$ such that
$\left\|x_{1}-x^{\ast}\right\|\leq r$. Assume that there exist an iteration
$k$ such that $\left\|x_{k-1}-x^{\ast}\right\|^{2}\leq r^{2}$ and
$\left\|x_{k}-x^{\ast}\right\|^{2}>r^{2}$, then the above analysis holds. By
the assumption that $\tau\leq p/2$, $\left\|x_{k}-x^{\ast}\right\|^{2}>r^{2}$,
and $r^{2(p-2\tau)}\geq\eta(1+(1-\beta)^{2})(\rho+1)\theta_{3}/\theta_{1}$,
then

$\displaystyle-\theta_{1}\eta\left\|x_{k}-x^{\ast}\right\|^{p}+\eta^{2}\left((1-\beta)^{2}+1\right)(\rho+1)\theta_{3}\left\|x_{k}-x^{\ast}\right\|^{2\tau}<0$

The main inequality (C.2) can be re-written as

$\displaystyle\mathbb{E}[W_{k+1}\mid\mathcal{F}_{k}]\leq\mathbb{E}[W_{k}]-\theta_{1}\eta\left\|x_{k}-x^{\ast}\right\|^{p}+\eta^{2}\left((1-\beta)^{2}+1\right)\left(\sigma^{2}+(\rho+1)\theta_{3}\right)+2\theta_{2}\eta.$

We can see that if

$\displaystyle
r^{2}=\max\left\\{R^{2},\left(\frac{\eta(1+(1-\beta)^{2})(\rho+1)\theta_{3}}{\theta_{1}}\right)^{1/(p-2\tau)},\left(\frac{2\theta_{2}}{\theta_{1}}+\left((1-\beta)^{2}+1\right)\left(\sigma^{2}+\eta(\rho+1)\theta_{3}\right)\right)^{2/p}\right\\}$

once $\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]>r^{2}$, the sequence of
$\mathbb{E}[W_{k+1}]$ will decrease until
$\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]\leq r^{2}$. Similar to the
analysis of Theorem 3.2, we get the conclusion that the sequences of
$\mathbb{E}[W_{k}]$, $\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]$, and
$\mathbb{E}[f(x_{k})-f^{\ast}]$ are uniformly bounded for all $k\geq 1$. ∎

###### Proof.

(of Theorem 4.3) Different from the proof of Theorem 4.2, we have additional
positive term $(1-\tau_{k})\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]$ to
deal with. We then need to estimate
$\mathbb{E}[\left\|x_{k+1}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k}]$.

$\displaystyle\mathbb{E}[\left\|x_{k+1}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle=\mathbb{E}\left[\left\|x_{k}-\eta_{k}\left(\beta\frac{x_{k-1}-x_{k}}{\eta_{k-1}}+(1-\beta)g_{k}\right)-x^{\ast}\right\|^{2}\right]$
$\displaystyle=\mathbb{E}\left[\left\|x_{k}-x^{\ast}-\beta\tau_{k}(x_{k-1}-x_{k})-(1-\beta)\eta_{k}g_{k}\right\|^{2}\right]$
$\displaystyle=\mathbb{E}[\left\|x_{k}-x^{\ast}-\beta\tau_{k}(x_{k-1}-x_{k})\right\|^{2}]+\eta_{k}^{2}(1-\beta)^{2}\mathbb{E}[\left\|g_{k}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle\quad+2\beta(1-\beta)\tau_{k}\eta_{k}\mathbb{E}[\left\langle
x_{k-1}-x_{k},g_{k}\right\rangle]-2(1-\beta)\eta_{k}\mathbb{E}[\left\langle
x_{k}-x^{\ast},g_{k}\right\rangle]$
$\displaystyle=\mathbb{E}\left[\left\|x_{k}-x^{\ast}+\beta\tau_{k}\frac{1-\beta}{\beta}(\tilde{x}_{k}-x_{k})\right\|^{2}\right]+\eta_{k}^{2}(1-\beta)^{2}\mathbb{E}[\left\|g_{k}\right\|^{2}\mid\mathcal{F}_{k}]$
$\displaystyle\quad+2\beta(1-\beta)\tau_{k}\eta_{k}\mathbb{E}[\left\langle
x_{k-1}-x_{k},g_{k}\right\rangle]-2(1-\beta)\eta_{k}\mathbb{E}[\left\langle
x_{k}-x^{\ast},g_{k}\right\rangle].$

By the convexity of $\left\|\cdot\right\|^{2}$, we have

$\displaystyle\mathbb{E}\left[\left\|x_{k}-x^{\ast}+\beta\tau_{k}(1-\beta)\beta^{-1}(\tilde{x}_{k}-x_{k})\right\|^{2}\right]$
$\displaystyle=\mathbb{E}\left[\left\|(1-\tau_{k}(1-\beta))(x_{k}-x^{\ast})+\tau_{k}(1-\beta)(\tilde{x}_{k}-x^{\ast})\right\|^{2}\right]$
$\displaystyle\leq(1-\tau_{k}(1-\beta))\mathbb{E}\left[\left\|(x_{k}-x^{\ast})\right\|^{2}\right]+\tau_{k}(1-\beta)\mathbb{E}\left[\left\|\tilde{x}_{k}-x^{\ast}\right\|^{2}\right].$

Then we turn to estimate

$\displaystyle-\mathbb{E}[\left\langle
x_{k}-x^{\ast},g_{k}\right\rangle]=-\left\langle x_{k}-x^{\ast},\nabla
f(x_{k})\right\rangle\leq-\theta_{1}\left\|x_{k}-x^{\ast}\right\|^{p}+\theta_{2}.$

and

$\displaystyle\mathbb{E}[\left\langle
x_{k-1}-x_{k},g_{k}\right\rangle]=\left\langle x_{k-1}-x_{k},\nabla
f(x_{k})\right\rangle\leq
f(x_{k-1})-f(x_{k})+\frac{L}{2}\left\|x_{k}-x_{k-1}\right\|^{2}.$

Then we define the Lyapunov function $W_{k+1}$ below:

$\displaystyle\mathbb{E}[W_{k+1}\mid\mathcal{F}_{k}]$
$\displaystyle=\mathbb{E}[\left\|\tilde{x}_{k+1}-x^{\ast}\right\|^{2}]+c_{k+1}\mathbb{E}[\left\|x_{k+1}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k}]+\mathbb{E}[\left\|x_{k+1}-x_{k}\right\|^{2}\mid\mathcal{F}_{k}]+u_{k}\mathbb{E}[f(x_{k})-f^{\ast}\mid\mathcal{F}_{k}]$

where $c_{k+1}>0$, $\gamma_{\beta}=\beta(1-\beta+(1-\beta)^{-1})$,
$u_{k}=2\gamma_{\beta}\tau_{k}\eta_{k}+2\beta(1-\beta)\tau_{k}\eta_{k}c_{k+1}$.
Then incorporating the above results gives:

$\displaystyle\mathbb{E}[W_{k+1}\mid\mathcal{F}_{k}]=\mathbb{E}[\left\|\tilde{x}_{k+1}-x^{\ast}\right\|^{2}]+c_{k+1}\mathbb{E}[\left\|x_{k+1}-x^{\ast}\right\|^{2}\mid\mathcal{F}_{k}]+\mathbb{E}[\left\|x_{k+1}-x_{k}\right\|^{2}\mid\mathcal{F}_{k}]+u_{k}\mathbb{E}[f(x_{k})-f^{\ast}\mid\mathcal{F}_{k}]$
$\displaystyle\leq\left(\tau_{k}+c_{k+1}\tau_{k}(1-\beta)\right)\left\|\tilde{x}_{k}-x^{\ast}\right\|^{2}+c_{k}\left\|x_{k}-x^{\ast}\right\|^{2}+\left(c_{k+1}-c_{k}-c_{k+1}\tau_{k}(1-\beta)+(1-\tau_{k})\right)\left\|x_{k}-x^{\ast}\right\|^{2}$
$\displaystyle\quad+\left(\tau_{k}^{2}\beta^{2}+\beta(1-\beta)\tau_{k}\eta_{k}L+c_{k+1}\beta(1-\beta)\tau_{k}\eta_{k}L+\frac{2\beta
L\eta_{k}\tau_{k}}{1-\beta}\right)\left\|x_{k}-x_{k-1}\right\|^{2}-2\eta_{k}\theta_{1}\left\|x_{k}-x^{\ast}\right\|^{p}+2\eta_{k}\theta_{2}$
$\displaystyle\quad+2(1-\beta)\eta_{k}c_{k+1}\left(-\theta_{1}\left\|x_{k}-x^{\ast}\right\|^{p}+\theta_{2}\right)+\left(\eta_{k}^{2}(1-\beta)^{2}+\eta_{k}^{2}+\eta_{k}^{2}c_{k+1}(1-\beta)^{2}\right)\mathbb{E}[\left\|g_{k}\right\|^{2}]$
$\displaystyle\quad+2\gamma_{\beta}\left(\tau_{k}\eta_{k}-\tau_{k-1}\eta_{k-1}\right)\left(f(x_{k-1})-f^{\ast}\right)+2\beta(1-\beta)\left(\tau_{k}\eta_{k}c_{k+1}-\tau_{k-1}\eta_{k-1}c_{k}\right)\left(f(x_{k-1})-f^{\ast}\right)$
$\displaystyle\quad+u_{k-1}(f(x_{k-1})-f^{\ast}).$ (48)

First, we properly choose $c_{k+1}=(1-\tau_{k})/(\tau_{k}(1-\beta))$ to make
the scalar of $\left\|\tilde{x}_{k}-x^{\ast}\right\|^{2}$ is smaller than 1.
We make the following discussion on the two popular decaying modes:

  * •

The step-size is polynomial decaying $\eta_{k}=\eta_{1}/k^{r}$ for all
$r\in(0,1]$, then
$c_{k+1}=(1-\tau_{k})/(\tau_{k}(1-\beta))\leq\frac{1}{(k-1)^{r}(1-\beta)}$ is
decreasing with $k$. The scalar
$c_{k+1}-c_{k}-c_{k+1}\tau_{k}(1-\beta)+(1-\tau_{k})$ is negative. By properly
choosing the step-size

$\displaystyle\eta_{k}\leq\frac{1-\beta^{2}}{\beta
L((1-\beta)(1+c_{k+1})+2(1-\beta)^{-1})}\leq\frac{1-\beta^{2}}{2\beta
L((1-\beta)+(1-\beta)^{-1})}$

to ensure the coefficient of $\mathbb{E}[\left\|x_{k}-x_{k-1}\right\|^{2}]$ is
smaller than 1. By case 1 of Theorem 3.3, we know that
$\tau_{k}\eta_{k}-\tau_{k-1}\eta_{k-1}$ is negative for all $k$. Because
$c_{k+1}$ is decreasing, we can get that
$\tau_{k}\eta_{k}c_{k+1}-\tau_{k-1}\eta_{k-1}c_{k}\leq
c_{k}(\tau_{k}\eta_{k}-\tau_{k-1}\eta_{k-1})$ which is also negative. Then the
main inequality (C.2) can be evaluated as:

$\displaystyle\mathbb{E}[W_{k+1}\mid\mathcal{F}_{k}]$ $\displaystyle\leq
W_{k}-2\eta_{k}\theta_{1}\left\|x_{k}-x^{\ast}\right\|^{p}+2\eta_{k}\theta_{2}+2(1-\beta)\eta_{k}c_{k+1}\left(-\theta_{1}\left\|x_{k}-x^{\ast}\right\|^{p}+\theta_{2}\right)$
$\displaystyle\quad+\left(\eta_{k}^{2}(1-\beta)^{2}+\eta_{k}^{2}+\eta_{k}^{2}c_{k+1}(1-\beta)^{2}\right)\mathbb{E}[\left\|g_{k}\right\|^{2}]$

Incorporating (C.2) into the above inequality, we get that

$\displaystyle\mathbb{E}[W_{k+1}\mid\mathcal{F}_{k}]$ $\displaystyle\leq
W_{k}-2\eta_{k}\theta_{1}\left\|x_{k}-x^{\ast}\right\|^{p}+2\eta_{k}\theta_{2}+2(1-\beta)\eta_{k}c_{k+1}\left(-\theta_{1}\left\|x_{k}-x^{\ast}\right\|^{p}+\theta_{2}\right)$
$\displaystyle\quad+\left(\eta_{k}^{2}(1-\beta)^{2}+\eta_{k}^{2}+\eta_{k}^{2}c_{k+1}(1-\beta)^{2}\right)\left((\rho+1)\theta_{3}\left\|x_{k}-x^{\ast}\right\|^{2\tau}+(\rho+1)\theta_{3}+\sigma^{2}\right)$
(49)

Assume that there exist an iteration $k$ such that
$\left\|x_{k-1}-x^{\ast}\right\|^{2}\leq r^{2}$ and
$\left\|x_{k}-x^{\ast}\right\|^{2}>r^{2}$, then the above analysis holds. Due
to the assumption that $\tau\leq p/2$, then we choose

$\displaystyle
r^{(p-2\tau)}\geq\max\left\\{\frac{\eta_{1}((1-\beta)^{2}+1)(\rho+1)\theta_{3}}{\theta_{1}},\frac{\eta_{1}(1-\beta)(\rho+1)\theta_{3}}{2\theta_{1}}\right\\}=\frac{\eta_{1}((1-\beta)^{2}+1)(\rho+1)\theta_{3}}{\theta_{1}}$

to make sure that
$(\eta_{k}^{2}(1-\beta)^{2}+\eta_{k}^{2})(\rho+1)\theta_{3}\left\|x_{k}-x^{\ast}\right\|^{2\tau}\leq\theta_{1}\eta_{k}\left\|x_{k}-x^{\ast}\right\|^{p}$
and
$\eta_{k}^{2}(1-\beta)^{2}c_{k+1}(\rho+1)\theta_{3}\left\|x_{k}-x^{\ast}\right\|^{2\tau}\leq
2(1-\beta)\eta_{k}c_{k+1}\theta_{1}\left\|x_{k}-x^{\ast}\right\|^{p}$. Then
the inequality (• ‣ C.2) can be estimated as

$\displaystyle\mathbb{E}[W_{k+1}\mid\mathcal{F}_{k}]$ $\displaystyle\leq
W_{k}-\eta_{k}\theta_{1}\left\|x_{k}-x^{\ast}\right\|^{p}+2\eta_{k}\theta_{2}+2(1-\beta)\eta_{k}c_{k+1}\theta_{2}$
$\displaystyle\quad+\left(\eta_{k}^{2}(1-\beta)^{2}+\eta_{k}^{2}+\eta_{k}^{2}c_{k+1}(1-\beta)^{2}\right)\left((\rho+1)\theta_{3}+\sigma^{2}\right)$

By properly choosing

$\displaystyle
r^{p}\leq\frac{4\theta_{2}}{\theta_{1}}+\frac{\eta_{1}(2-\beta)^{2}((\rho+1)\theta_{3}+\sigma^{2})}{\theta_{1}}$

once $\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]>r^{2}$, we have
$\mathbb{E}[W_{k}]$ is decreasing. Overall, we set

$\displaystyle
r^{2}=\max\left\\{R^{2},\left(\frac{4\theta_{2}}{\theta_{1}}+\frac{\eta_{1}(2-\beta)^{2}((\rho+1)\theta_{3}+\sigma^{2})}{\theta_{1}}\right)^{2/p},\left(\frac{\eta_{1}((1-\beta)^{2}+1)(\rho+1)\theta_{3}}{\theta_{1}}\right)^{2/(p-2\tau)}\right\\}.$

Similar to the discussion of Theorem 3.3, we can conclude that
$\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]$ and
$\mathbb{E}[f(x_{k})-f^{\ast}]$ are uniformly bounded for all $k\geq 1$.

  * •

The step-size is exponentially decaying with $\eta_{k}=\eta_{1}/\alpha^{k-1}$
and $\alpha=(\nu/T)^{-1/T}$ with $\nu\geq 1$. In this case,
$c_{k+1}=(1-\tau_{k})/(\tau_{k}(1-\beta))=(1-\alpha)/(\alpha(1-\beta))$ where
$\tau_{k}=\eta_{k}/\eta_{k-1}=\alpha$. The the coefficient of
$c_{k+1}-c_{k}-c_{k+1}\tau_{k}(1-\beta)+(1-\tau_{k})=0$. By properly choosing
step-size

$\displaystyle\eta_{k}\leq\frac{1-\beta^{2}\tau_{k}^{2}}{\beta
L((1-\beta)\tau_{k}+(1-\tau_{k})+2\tau_{k}(1-\beta)^{-1})}=\frac{1-\beta^{2}\tau_{k}^{2}}{\beta
L((1-\beta\tau_{k}+2\tau_{k}(1-\beta)^{-1})},$

which is decreasing with $\tau_{k}$, that is

$\displaystyle\eta_{k}\leq\frac{1-\beta^{2}}{\beta
L(1-\beta+2(1-\beta)^{-1})}$ (50)

we can make sure the coefficient of
$\mathbb{E}[\left\|x_{k}-x_{k-1}\right\|^{2}]$ is smaller than 1. By the Case
3 of Theorem 3.3, we know that $\tau_{k}\eta_{k}-\tau_{k-1}\eta_{k-1}$ is
negative. Similar to the polynomial step-size, combining (C.2), the main
inequality (• ‣ C.2) will be

$\displaystyle\mathbb{E}[W_{k+1}\mid\mathcal{F}_{k}]$ $\displaystyle\leq
W_{k}-2\eta_{k}\theta_{1}\left\|x_{k}-x^{\ast}\right\|^{p}+2\eta_{k}\theta_{2}+2(1-\beta)\eta_{k}c_{k+1}\left(-\theta_{1}\left\|x_{k}-x^{\ast}\right\|^{p}+\theta_{2}\right)$
$\displaystyle\quad+\left(\eta_{k}^{2}(1-\beta)^{2}+\eta_{k}^{2}+\eta_{k}^{2}c_{k+1}(1-\beta)^{2}\right)\left((\rho+1)\theta_{3}\left\|x_{k}-x^{\ast}\right\|^{2\tau}+(\rho+1)\theta_{3}+\sigma^{2}\right)$

Assume that there exists the iterate $k$ such that
$\mathbb{E}[\left\|x_{k-1}-x^{\ast}\right\|^{2}]\leq r^{2}$ and
$\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]>r^{2}$, then by properly
setting

$\displaystyle
r^{2}=\max\left\\{R^{2},\left(\frac{2\theta_{2}}{\alpha\theta_{1}}+\frac{\eta_{1}((1-\beta)^{2}+\alpha^{-1})((\rho+1)\theta_{3}+\sigma^{2})}{\theta_{1}}\right)^{2/p},\left(\frac{\eta_{1}((1-\beta)^{2}+1)(\rho+1)\theta_{3}}{\theta_{1}}\right)^{2/(p-2\tau)}\right\\},$

we can conclude that once
$\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]>r^{2}$, we have
$\mathbb{E}[W_{k+1}]$ is decreasing. Similar to Case 3 of Theorem 3.3, the
quantities $\mathbb{E}[\left\|x_{k}-x^{\ast}\right\|^{2}]$ and
$\mathbb{E}[f(x_{k})-f^{\ast}]$ are uniformly bounded for all $k\geq 1$.

∎

##  Appendix D Applications

###  D.1 Examples in Section 3

  * •

A fully connected 2-layer neural network (hidden nodes $m$) with a weight
decay: let $\sigma_{1}$ and $\sigma_{2}(\cdot)$ denote the inner and output
layer activation functions, respectively. We use cross-entropy to measure the
output with its true label $CE(\cdot)$. Given $n$ pairs input data
$\left\\{a_{j},b_{j}\right\\}_{j=1}^{n}$, we revise the input data as
$a_{j}=[a_{j},1]\in\mathbb{R}^{d}$ then

$\displaystyle
F(x)=\frac{1}{n}\sum_{j=1}^{n}CE(\sigma_{2}(X_{2}\sigma_{1}(X_{1}a_{j})))+\frac{\lambda}{2}\left\|X\right\|^{2}$

where $X=[X_{1},X_{2}]\in\mathbb{R}^{dm+sm}$, $X_{1}\in\mathbb{R}^{m\times d}$
and $X_{2}\in\mathbb{R}^{s\times m}$. For simplicity, we consider the binary
dataset $b_{j}\in\left\\{-1,+1\right\\}$ and $s=1$, and
$\sigma_{2}(\cdot)=1/(1+\exp(-\cdot))$, then

$\displaystyle
F(x)=\frac{1}{n}\sum_{j=1}^{n}\log\left(1+\exp(-b_{j}\sum_{i=1}^{m}X_{2}[i]\sigma_{1}(X_{1}[i]^{T}a_{j}))\right)+\frac{\lambda}{2}\left\|X\right\|^{2}$

Then we turn to compute the gradient (sub-gradient) of each component function
$F_{j}$ with regarding to data $(a_{j},b_{j})$

$\displaystyle\frac{\partial F_{j}}{\partial X_{1}[i]}$
$\displaystyle=\frac{b_{j}\exp(-b_{j}\sum_{i=1}^{m}X_{2}[i]\sigma_{1}(X_{1}[i]^{T}a_{j}))}{1+\exp(-b_{j}\sum_{i=1}^{m}X_{2}[i]\sigma_{1}(X_{1}[i]^{T}a_{j})}\cdot-
X_{2}[i]\partial\sigma_{1}(X_{1}[i]^{T}a_{j})a_{j}+\lambda
X_{1}[i]\in\mathbb{R}^{d}$ $\displaystyle\frac{\partial F_{j}}{\partial
X_{2}[i]}$
$\displaystyle=\frac{b_{j}\exp(-b_{j}\sum_{i=1}^{m}X_{2}[i]\sigma_{1}(X_{1}[i]^{T}a_{j}))}{1+\exp(-b_{j}\sum_{i=1}^{m}X_{2}[i]\sigma_{1}(X_{1}[i]^{T}a_{j})}\cdot-\sigma_{1}(X_{1}[i]^{T}a_{j})+\lambda
X_{2}[i]$

Let $u=b_{j}\sum_{i=1}^{m}X_{2}[i]\sigma_{1}(X_{1}[i]^{T}a_{j})$, we have

$\displaystyle\left\langle X,\nabla F_{j}(X)\right\rangle$
$\displaystyle=\sum_{i=1}^{m}\left(\left\langle X_{1}[i],\frac{\partial
F_{j}}{\partial X_{1}[i]}\right\rangle+\left\langle X_{2}[i],\frac{\partial
F_{j}}{\partial X_{2}[i]}\right\rangle\right)$
$\displaystyle=\lambda\left\|X\right\|^{2}-\frac{b_{j}\exp(-u)}{1+\exp(-u)}\sum_{i=1}^{m}\left(X_{2}[i]\partial\sigma_{1}(X_{1}[i]^{T}a_{j})X_{1}[i]^{T}a_{j}+X_{2}[i]\sigma_{1}(X_{1}[i]^{T}a_{j})\right).$

    * –

If $\sigma_{1}(x)=\max(0,x)$, then its gradient
$\partial\sigma_{1}(x)=\chi_{x\geq 0}$. We get the relationship of
$\sigma_{1}$ with its gradient $\sigma_{1}(x)=(x)_{+}=x\cdot\chi_{x\geq
0}=x\cdot\partial\sigma_{1}(x)$. Then the above product can be estimated as

$\displaystyle\left\langle X,\nabla F_{j}(X)\right\rangle$
$\displaystyle=\lambda\left\|X\right\|^{2}-\frac{b_{j}\exp(-u)}{1+\exp(-u)}\sum_{i=1}^{m}\left(X_{2}[i]\partial\sigma_{1}(X_{1}[i]^{T}a_{j})X_{1}[i]^{T}a_{j}+X_{2}[i]\sigma_{1}(X_{1}[i]^{T}a_{j})\right)$
$\displaystyle=\lambda\left\|X\right\|^{2}-\frac{b_{j}\exp(-u)}{1+\exp(-u)}\sum_{i=1}^{m}\left(X_{2}[i]\sigma_{1}(X_{1}[i]^{T}a_{j})+X_{2}[i]\sigma_{1}(X_{1}[i]^{T}a_{j})\right)$
$\displaystyle=\lambda\left\|X\right\|^{2}-\frac{2u\exp(-u)}{1+\exp(-u)}.$

No matter $u\geq 0$ or not, we all have

$\displaystyle\frac{\exp(-u)u}{1+\exp(-u)}=\frac{u}{1+\exp(u)}<1.$

In this case, we have

$\displaystyle\left\langle X,\nabla
F(X)\right\rangle=\frac{1}{n}\sum_{j=1}^{n}\left\langle X,\nabla
F_{j}(X)\right\rangle\geq\lambda\left\|X\right\|^{2}-2.$

    * –

If $\sigma_{1}(x)=1/(1+\exp(-x))$ is a sigmoid loss function, we have
$\frac{\partial\sigma_{1}(x)}{\partial x}=\sigma_{1}(x)(1-\sigma_{1}(x))$. In
this case, we have

$\displaystyle\left\langle X,\nabla F_{j}(X)\right\rangle$
$\displaystyle=\lambda\left\|X\right\|^{2}-\frac{b_{j}\exp(-u)}{1+\exp(-u)}\sum_{i=1}^{m}\left(X_{2}[i]\partial\sigma_{1}(X_{1}[i]^{T}a_{j})X_{1}[i]^{T}a_{j}+X_{2}[i]\sigma_{1}(X_{1}[i]^{T}a_{j})\right)$
$\displaystyle=\lambda\left\|X\right\|^{2}-\frac{u\exp(-u)}{1+\exp(-u)}-\frac{b_{j}\exp(-u)}{1+\exp(-u)}\sum_{i=1}^{m}X_{2}[i]\sigma_{1}(X_{1}[i]^{T}a_{j})(1-\sigma_{1}(X_{1}[i]^{T}a_{j}))X_{1}[i]^{T}a_{j}$

We consider different situations to show how to estimate the last term. We let
$A=\left\\{i:b_{j}X_{2}[i]\geq 0\right\\}$.

      * *

If $A=[m]$, then

$\displaystyle\frac{\exp(-u)}{1+\exp(-u)}\sum_{i=1}^{m}b_{j}X_{2}[i]\sigma_{1}(X_{1}[i]^{T}a_{j})(1-\sigma_{1}(X_{1}[i]^{T}a_{j}))X_{1}[i]^{T}a_{j}$
$\displaystyle\leq\frac{\exp(-u)}{1+\exp(-u)}\sum_{i=1}^{m}b_{j}X_{2}[i]$
$\displaystyle=\frac{u\exp(-u)}{1+\exp(-u)}.$

where the inequality follows from the facts that $\sigma_{1}(x)\in[0,1]$ and

$\displaystyle(1-\sigma_{1}(X_{1}[i]^{T}a_{j}))X_{1}[i]^{T}a_{j}=\frac{X_{1}[i]^{T}a_{j}}{1+\exp(X_{1}[i]^{T}a_{j})}<1$
(51)

      * *

If some of $b_{j}X_{2}[i]\geq 0$ are negative. That is $A\subseteq[m]$. Then
we can split the sum into two cases

        * ·

For the term that $i\in A$, we have $b_{j}X_{2}[i]\geq 0$. Let
$B=\left\\{i:X_{1}[i]^{T}a_{j}\geq 0\right\\}$. We can also achieve that

$\displaystyle\frac{\exp(-u)}{1+\exp(-u)}\sum_{i=1}^{m}b_{j}X_{2}[i]\sigma_{1}(X_{1}[i]^{T}a_{j})(1-\sigma_{1}(X_{1}[i]^{T}a_{j}))X_{1}[i]^{T}a_{j}$
$\displaystyle=\frac{\exp(-u)}{1+\exp(-u)}\sum_{i\in
A}^{m}b_{j}X_{2}[i]\sigma_{1}(X_{1}[i]^{T}a_{j})(1-\sigma_{1}(X_{1}[i]^{T}a_{j}))X_{1}[i]^{T}a_{j}$
$\displaystyle\quad+\frac{\exp(-u)}{1+\exp(-u)}\sum_{i\in([m]\setminus A)\cap
B}b_{j}X_{2}[i]\sigma_{1}(X_{1}[i]^{T}a_{j})(1-\sigma_{1}(X_{1}[i]^{T}a_{j}))X_{1}[i]^{T}a_{j}$
$\displaystyle\quad+\frac{\exp(-u)}{1+\exp(-u)}\sum_{i\in([m]\setminus
A)\cap(m\setminus
B)}b_{j}X_{2}[i]\sigma_{1}(X_{1}[i]^{T}a_{j})(1-\sigma_{1}(X_{1}[i]^{T}a_{j}))X_{1}[i]^{T}a_{j}.$
(52)

By (51), the first term of (· ‣ * ‣ – ‣ • ‣ D.1) can be bounded by

$\displaystyle\sum_{i\in
A}^{m}b_{j}X_{2}[i]\sigma_{1}(X_{1}[i]^{T}a_{j})(1-\sigma_{1}(X_{1}[i]^{T}a_{j}))X_{1}[i]^{T}a_{j}\leq\sum_{i\in
A}^{m}b_{j}X_{2}[i]\sigma_{1}(X_{1}[i]^{T}a_{j}).$

We turn to estimate the second term of (· ‣ * ‣ – ‣ • ‣ D.1):

$\displaystyle\sum_{i\in([m]\setminus A)\cap
B}b_{j}X_{2}[i]\sigma_{1}(X_{1}[i]^{T}a_{j})(1-\sigma_{1}(X_{1}[i]^{T}a_{j}))X_{1}[i]^{T}a_{j}\leq
0.$

The last term of (· ‣ * ‣ – ‣ • ‣ D.1) is estimated as:

$\displaystyle\sum_{i\in([m]\setminus A)\cap(m\setminus
B)}b_{j}X_{2}[i]\sigma_{1}(X_{1}[i]^{T}a_{j})(1-\sigma_{1}(X_{1}[i]^{T}a_{j}))X_{1}[i]^{T}a_{j}$
$\displaystyle=\sum_{i\in([m]\setminus A)\cap(m\setminus
B)}(-b_{j}X_{2}[i])\sigma_{1}(X_{1}[i]^{T}a_{j})(1-\sigma_{1}(X_{1}[i]^{T}a_{j}))(-X_{1}[i]^{T}a_{j})$
$\displaystyle=\sum_{i\in([m]\setminus A)\cap(m\setminus
B)}(-b_{j}X_{2}[i])(1-\sigma_{1}(-X_{1}[i]^{T}a_{j}))\sigma_{1}(-X_{1}[i]^{T}a_{j})(-X_{1}[i]^{T}a_{j})$
$\displaystyle\leq\sum_{i\in([m]\setminus A)\cap([m]\setminus
B)}(-b_{j}X_{2}[i])\sigma_{1}(-X_{1}[i]^{T}a_{j})).$

Applying the above results gives

$\displaystyle\frac{\exp(-u)}{1+\exp(-u)}\sum_{i=1}^{m}b_{j}X_{2}[i]\sigma_{1}(X_{1}[i]^{T}a_{j})(1-\sigma_{1}(X_{1}[i]^{T}a_{j}))X_{1}[i]^{T}a_{j}$
$\displaystyle\leq\frac{\exp(-u)}{1+\exp(-u)}\left(\sum_{i\in
A}^{m}b_{j}X_{2}[i]\sigma_{1}(X_{1}[i]^{T}a_{j})+\sum_{i\in([m]\setminus
A)\cap([m]\setminus B)}(-b_{j}X_{2}[i])\sigma_{1}(-X_{1}[i]^{T}a_{j}))\right)$
$\displaystyle\leq\frac{\exp(-u)}{1+\exp(-u)}\left(\frac{c_{1}}{2}\left(\sum_{i=1}^{m}\left\|X_{2}[i]\right\|^{2}\right)+\frac{1}{2c_{1}}\left(\sum_{i\in
A}\sigma_{1}^{2}(X_{1}[i]^{T}a_{j})+\sum_{i\in([m]\setminus
A)\cap([m]\setminus B)}\sigma_{1}^{2}(-X_{1}[i]^{T}a_{j})\right)\right)$
$\displaystyle\leq\left(\frac{c_{1}}{2}\left\|X_{2}\right\|^{2}+\frac{m}{2c_{1}}\right).$

Let $c_{1}=\lambda$, then

$\displaystyle\left\langle X,\nabla
F(X)\right\rangle=\frac{1}{n}\sum_{j=1}^{n}\left\langle X,\nabla
F_{j}(X)\right\rangle$
$\displaystyle\geq\lambda\left\|X\right\|^{2}-\frac{u\exp(-u)}{1+\exp(-u)}-\left(\frac{\lambda}{2}\left\|X_{2}\right\|^{2}+\frac{m}{2\lambda}\right)$
$\displaystyle\geq\frac{\lambda}{2}\left\|X\right\|^{2}-\left(1+\frac{m}{2\lambda}\right).$

    * –

If the neural networks are three layers, we consider ReLU as the activation
function of the inner layers.

$\displaystyle
F(X)=\frac{1}{n}\sum_{j=1}^{n}\log\left(1+\exp\left(-b_{j}\sum_{i=1}^{m_{2}}X_{3}[i]\sigma_{2}\left(X_{2}[i]^{T}\sigma_{1}\left(X_{1}^{T}a_{j}\right)\right)\right)\right)+\frac{\lambda}{2}\left\|X\right\|^{2}.$

Next we choose one component function $F_{j}$ which is related to the $j$-th
dataset to analyze its gradient and product term. Let
$u=b_{j}\sum_{i=1}^{m_{2}}X_{3}[i]\sigma_{2}\left(X_{2}[i]^{T}\sigma_{1}\left(X_{1}^{T}a_{j}\right)\right)$

$\displaystyle\frac{\partial F_{j}}{\partial X_{1}[l]}$
$\displaystyle=\frac{\exp(-u)}{1+\exp(-u)}\cdot-
b_{j}\sum_{i=1}^{m_{2}}X_{3}[i]\partial\sigma_{2}\left(X_{2}[i]^{T}\sigma_{1}\left(X_{1}^{T}a_{j}\right)\right)X_{2}[i][l]\partial\sigma_{1}(X_{1}[l]^{T}a_{j})a_{j}+\lambda
X_{1}[l]$ $\displaystyle\frac{\partial F_{j}}{\partial X_{2}[i]}$
$\displaystyle=\frac{\exp(-u)}{1+\exp(-u)}\cdot-
b_{j}X_{3}[i]\partial\sigma_{2}\left(X_{2}[i]^{T}\sigma_{1}\left(X_{1}^{T}a_{j}\right)\right)\sigma_{1}(X_{1}^{T}a_{j})+\lambda
X_{2}[i]$ $\displaystyle\frac{\partial F_{j}}{\partial X_{3}[i]}$
$\displaystyle=\frac{\exp(-u)}{1+\exp(-u)}\cdot-
b_{j}\sigma_{2}\left(X_{2}[i]^{T}\sigma_{1}\left(X_{1}^{T}a_{j}\right)\right)+\lambda
X_{3}[i].$

Then

$\displaystyle\left\langle X,\nabla
F_{j}(X)\right\rangle=\sum_{l=1}^{m_{1}}\left\langle X_{1}[l],\frac{\partial
F_{j}(X)}{\partial X_{1}[l]}\right\rangle+\sum_{i=1}^{m_{2}}\left\langle
X_{2}[i],\frac{\partial F_{j}(X)}{\partial
X_{2}[i]}\right\rangle+\sum_{i=1}^{m_{2}}\left\langle X_{3}[i],\frac{\partial
F_{j}(X)}{\partial X_{3}[i]}\right\rangle.$

Let $\sigma_{1}(x)=\sigma_{2}(x)=\max(0,x)$, then their gradients
$\partial\sigma_{1}(x)=\partial\sigma_{2}(x)=\chi_{x\geq 0}$. Then the
activation functions with their gradient satisfy that
$\sigma_{i}(x)=x\partial\sigma_{i}(x)$ for $i=1$ and $2$. Then

$\displaystyle\sum_{l=1}^{m_{1}}\left\langle X_{1}[l],\frac{\partial
F_{j}(X)}{\partial X_{1}[l]}\right\rangle$
$\displaystyle=\sum_{l=1}^{m_{1}}\frac{-b_{j}\exp(-u)}{1+\exp(-u)}\cdot\sum_{i=1}^{m_{2}}X_{3}[i]\partial\sigma_{2}\left(X_{2}[i]^{T}\sigma_{1}\left(X_{1}^{T}a_{j}\right)\right)X_{2}[i][l]\partial\sigma_{1}(X_{1}[l]^{T}a_{j})X_{1}[l]^{T}a_{j}+\lambda\left\|X_{1}[l]\right\|^{2}$
$\displaystyle=\sum_{l=1}^{m_{1}}\frac{-b_{j}\exp(-u)}{1+\exp(-u)}\cdot\sum_{i=1}^{m_{2}}X_{3}[i]\partial\sigma_{2}\left(X_{2}[i]^{T}\sigma_{1}\left(X_{1}^{T}a_{j}\right)\right)X_{2}[i][l]\sigma_{1}(X_{1}[l]^{T}a_{j})+\lambda\left\|X_{1}[l]\right\|^{2}$
$\displaystyle=\frac{-b_{j}\exp(-u)}{1+\exp(-u)}\cdot\sum_{i=1}^{m_{2}}X_{3}[i]\sigma_{2}\left(X_{2}[i]^{T}\sigma_{1}\left(X_{1}^{T}a_{j}\right)\right)+\lambda\left\|X_{1}\right\|^{2}$
$\displaystyle=\frac{\exp(-u)}{1+\exp(-u)}\cdot-u+\lambda\left\|X_{1}\right\|^{2}.$
$\displaystyle\sum_{i=1}^{m_{2}}\left\langle X_{2}[i],\frac{\partial
F_{j}(X)}{\partial X_{2}[i]}\right\rangle$
$\displaystyle=\sum_{i=1}^{m_{2}}\frac{-b_{j}\exp(-u)}{1+\exp(-u)}\cdot
X_{3}[i]\partial\sigma_{2}\left(X_{2}[i]^{T}\sigma_{1}\left(X_{1}^{T}a_{j}\right)\right)X_{2}[i]^{T}\sigma_{1}(X_{1}^{T}a_{j})+\lambda\left\|X_{2}[i]\right\|^{2}$
$\displaystyle=\sum_{i=1}^{m_{2}}\frac{-b_{j}\exp(-u)}{1+\exp(-u)}X_{3}[i]\sigma_{2}\left(X_{2}[i]^{T}\sigma_{1}\left(X_{1}^{T}a_{j}\right)\right)+\lambda\left\|X_{2}[i]\right\|^{2}$
$\displaystyle=\frac{\exp(-u)}{1+\exp(-u)}\cdot-u+\lambda\left\|X_{2}\right\|^{2}.$
$\displaystyle\sum_{i=1}^{m_{2}}\left\langle X_{3}[i],\frac{\partial
F_{j}(X)}{\partial X_{3}[i]}\right\rangle$
$\displaystyle=\sum_{i=1}^{m_{2}}\frac{\exp(-u)}{1+\exp(-u)}\cdot-
b_{j}X_{3}[i]\sigma_{2}\left(X_{2}[i]^{T}\sigma_{1}\left(X_{1}^{T}a_{j}\right)\right)+\lambda\left\|X_{3}[i]\right\|^{2}$
$\displaystyle=\frac{\exp(-u)}{1+\exp(-u)}\cdot-u+\lambda\left\|X_{3}\right\|^{2}.$

Incorporating the above results, we can achieve that

$\displaystyle\left\langle X,\nabla
F_{j}(X)\right\rangle=\lambda\left\|X\right\|^{2}-\frac{3u\exp(-u)}{1+\exp(-u)}.$

For any $u$, we can estimate

$\displaystyle\frac{u\exp(-u)}{1+\exp(-u)}=\frac{u}{1+\exp(u)}\leq 1.$

Finally, we get that

$\displaystyle\left\langle X,\nabla F(X)\right\rangle$
$\displaystyle=\frac{1}{n}\sum_{j=1}^{n}\left\langle X,\nabla
F_{j}(X)\right\rangle\geq\lambda\left\|X\right\|^{2}-3.$

    * –

If the neural networks are $S$ layers, we consider ReLU as the activation
function in the inner layers and softmax as the activation function of the
output layer. We use cross-entropy to estimate the true label and prediction
output. Given the data set $\left\\{(a_{j},b_{j})\right\\}_{j=1}^{n}$, the
function can be formulated as below:

$\displaystyle
F(X)=\frac{1}{n}\sum_{j=1}^{n}\log\left(1+\exp\left(-b_{j}X_{S}^{T}\sigma_{S-1}\left(X_{S-1}^{T}\sigma_{S-2}\left(\cdots
X_{1}^{T}a_{j}\right)\right)\right)\right)+\frac{\lambda}{2}\left\|X\right\|^{2}.$

From the output of layer $s$ to the next layer, the product of the weight
matrix $X_{s}$ and $\sigma_{s}(X_{s-1}$ can be re-written as
$X_{s}^{T}\sigma_{s}(X_{s-1}^{T}\sigma_{s-1}(\cdots))=\sum_{i=1}^{m_{s-1}}X_{s}[:][i]\sigma_{s}(X_{s-1}[i]^{T}\sigma_{s-1}(\cdots))\in\mathbb{R}^{m_{s}}$.