# Provable Benefit of Adaptivity in Adam

Firstname1 Lastname1  Firstname2 Lastname2  Firstname3 Lastname3  Firstname4
Lastname4  Firstname5 Lastname5  Firstname6 Lastname6  Firstname7 Lastname7
Firstname8 Lastname8  Firstname8 Lastname8

###### Abstract

Adam is widely adopted in practical applications due to its fast convergence.
However, its theoretical analysis is still far from satisfactory. Existing
convergence analyses for Adam rely on the bounded smoothness assumption,
referred to as the _L-smooth condition_. Unfortunately, this assumption does
not hold for many deep learning tasks. Moreover, we believe that this
assumption obscures the true benefit of Adam, as the algorithm can adapt its
update magnitude according to local smoothness. This important feature of Adam
becomes irrelevant when assuming globally bounded smoothness. This paper
studies the convergence of randomly reshuffled Adam (RR Adam) with diminishing
learning rate, which is the major version of Adam adopted in deep learning
tasks. We present the first convergence analysis of RR Adam without the
bounded smoothness assumption. We demonstrate that RR Adam can maintain its
convergence properties when smoothness is linearly bounded by the gradient
norm, referred to as the _$(L_{0},L_{1})$ -smooth condition_. We further
compare Adam to SGD when both methods use diminishing learning rate. We refine
the existing lower bound of SGD and show that SGD can be slower than Adam. To
our knowledge, this is the first time that Adam and SGD are rigorously
compared in the same setting and the advantage of Adam is revealed.

Machine Learning, ICML

##  1 Introduction

Machine learning tasks are often formulated as solving the following finite-
sum problem:

$\min_{\bm{w}\in\mathbb{R}^{d}}f(\bm{w})=\frac{1}{n}\sum_{i=0}^{n-1}f_{i}(\bm{w}),$
(1)

where $n$ denotes the number of samples or mini-batches, and $\bm{w}$ denotes
the trainable parameters. Recently, it is noted that adaptive gradient methods
including Adaptive Moment estimation (Adam) (kingma2014adam) are widely used
to train modern deep neural networks including GANs (brock2018large), BERTs
(kenton2019bert), GPTs (brown2020language) and ViTs (dosovitskiy2020image). It
is often observed that Adam converges considerably faster than vanilla
Stochastic Gradient Descent (SGD) for the training of Transformers, as seen in
Figure 1(a). Similar phenomena are also reported in (zhang2024transformers).

Despite its practical success, the theoretical analysis of Adam is less than
satisfactory. Existing analyses rely on bounded smoothness assumption, i.e.,
the Lipschitz coefficient of gradients (or the spectrum norm of the Hessian)
is globally upper bounded by constant $L$, referred to as _$L$ -smooth
condition_. However, recent studies show that the $L$-smooth condition does
not hold in practical deep learning tasks such as LSTM (zhang2019gradient) and
Transformers (crawshaw2022robustness).

Moreover, such an assumption hides the benefit of Adam. Intuitively, Adam can
overcome the issue of unbounded smoothness using adaptive learning rate.
First, Adam uses the reciprocal of the square root of the exponential moving
averages of past squared gradients as an effective learning rate (see
Algorithm 1 for the update rule). Thus, the effective learning rate would be
adapted to the local gradient norm. Second, there is a strong correlation
between the Lipschitz coefficient and the gradient norm of deep neural
networks (zhang2019gradient; cohen2021gradient; crawshaw2022robustness). As a
result, Adam can adapt the update magnitude to the local Lipschitz coefficient
and is empirically observed to converge fast (Figure 1(a) and
(zhang2019gradient)). Unfortunately, such benefit is hidden because existing
theories of Adam are built upon $L$-smooth condition.

To reveal the theoretical benefit of Adam, we analyze its convergence under a
relaxed smoothness condition called $(L_{0},L_{1})$-smooth condition
(zhang2019gradient):

$\|\nabla^{2}f_{i}(\bm{w})\|\leq L_{0}+L_{1}\|\nabla f_{i}(\bm{w})\|.$ (2)

When $L_{1}=0$, Eq. equation 2 degenerates into classical $L$-smooth
condition. The $(L_{0},L_{1})$-smooth condition allows the spectral norm of
the Hessian (Lipschitz coefficient of gradients) to linearly grow with the
gradient norm of $\bm{w}$, so it is a relaxed version of $L$-smooth condition.
The $(L_{0},L_{1})$-smooth condition is empirically observed to hold in LSTM
(zhang2019gradient; zhang2020improved) and Transformers (Figure 1(b) and
(crawshaw2022robustness)).

(a) Training loss

(b) Gradient vs. smoothness

Figure 1: Experiments on the WMT 2014 dataset trained with the transformer.
(a): The training loss of SGD and Adam. (b): The gradient norm vs. the local
smoothness on the training trajectory. The blue line in (b) stands for
$\log(\text{local smoothness})=\log(\text{gradient norm})+1.4$. It can be
observed that $(e^{1.4},0)$-smooth condition holds in this task. Similar
results can be seen in zhang2019gradient.

Our Contribution: Under the $(L_{0},L_{1})$-smooth condition, we establish the
convergence of randomly-reshuffled Adam. Specifically, our contributions are
summarized as follows.

  * •

We establish the first convergence result of Adam without “$L$-smoothness”. We
prove that Adam converges under the $(L_{0},L_{1})$-smooth condition.

  * •

Our convergence result enjoys several good properties. First,there is no need
for the bounded gradient assumption (i.e. $\|\nabla f(\bm{w})\|\leq C$).
Eliminating this assumption is essential since the $(L_{0},L_{1})$-smooth
condition would otherwise degenerate to the $L$-smooth condition. Second, our
result does not rely on other assumptions such as a bounded adaptor or a large
regularizer for numerical stability. Lastly, the convergence holds for every
possible trajectory, which is not only technically demanding but also much
stronger than “convergence in expectation”.

  * •

We further compare Adam to SGD when both methods use diminishing learning
rate. We present an improved lower bound for (S)GD under the
$(L_{0},L_{1})$-smooth condition. In this lower bound, there is a factor
related to the gradient norm of the initial point, which does not exist in the
upper bound of Adam. This indicates that (S)GD can converge slow under the
$(L_{0},L_{1})$-smooth condition, showing the advantage of Adam over (S)GD. To
our knowledge, this is the first time that Adam and SGD are rigorously
compared in the same setting where the advantage of Adam can be revealed. We
believe these results shed new light on understanding the benefit of Adam.

Organization of this paper. The rest of this paper is organized as follows: In
Section 2, we review related works on the convergence analysis for Adam, the
relaxed smoothness assumption, and the variants of Adam. In Section 3, we
define notations, present the psedocode of Adam, and provide the assumptions
that our result rests on. In Section 4, we provide our main result on the
convergence of RR Adam under non-uniform smoothness together with explanations
regarding the result. In Section 5, we then state the proof ideas of the main
result. In Section 7, we provide discussions on intuitions of why non-adaptive
optimizers can be used for fine-tuning tasks, comparison of Adam and Clipped
SGD, insights for practioners and limitations of Theorem 1.

##  2 Related works

Convergence analysis for Adam. Adam is firstly proposed in kingma2015adam with
a convergence proof. However, the proof is pointed out to have flaws by
(reddi2018convergence) and (reddi2018convergence) further provide simple
counterexamples with which Adam diverges. This discovery caused the
convergence analysis of Adam to stagnate for a while and motivated a series of
works developing variants of Adam without divergent issues (see discussion
latter in this section). On the other hand, vanilla Adam works well in
practice and  divergence is not empirically observed. This phenomenon
motivates researchers to rethink the counterexamples. The counterexamples
states “for every $\beta_{1}<\sqrt{\beta_{2}}$, there exists a problem that
Adam diverges”. That is to say, the divergence statement requires picking
$(\beta_{1},\beta_{2})$ before fixing the problem, while in practice, the
algorithmic parameters are often picked according to the problem. Based on
this observation, a recent work (Zhang2022Adam) proves that Adam can converge
with $(\beta_{1},\beta_{2})$ picked after the problem is given.

We categorize the existing results of Adam into two classes based on the
sampling strategy: with-replacement sampling (a.k.a., i.i.d. sampling,
abbreviated as “WR”) and RR Adam. We believe both sampling strategies are
worth studying: WR is more favored among the theory community due to its
simple form, whereas RR is widely used among practitioners because it is easy
to implement. Further, RR guarantees to pass each data at least once and
brings good performance (bottou2009curiously; bottou2012stochastic).

The first line of work analyzes WR Adam. For instance, (zaheer2018adaptive)
shows that WR RMSProp (a simplified version of Adam with $\beta_{1}=0$)
converges to the neighborhood of the stationary points. (de2018convergence)
prove the convergence of WR RMSProp by assuming the signs of the gradients to
remain the same along the trajectory. However, this condition is not
guaranteed to hold in practice. (defossez2020simple) prove the convergence of
WR Adam with $\beta_{1}<\beta_{2}$. However, their convergence bound is
inversely proportional to $\xi$, which is the hyperparameter for numerical
stability. Consequently, their bound becomes vacuous as $\xi$ approaches zero.
This result does not match practical observations because small values of
$\xi$, like $10^{-8}$, often yield satisfactory performance. Moreover,
employing large values of $\xi$ obscures the effect of $\sqrt{v_{k}}$, and
thus the proof is largely reduced to the proof of SGD. (huang2021super;
guo2021novel) provide simple convergence proof for WR Adam with $\beta_{1}$
close to $1$. However, their results require the $\sqrt{v_{k}}$ to be bounded
in a certain interval $[C_{l},C_{u}]$. This condition changes Adam into
AdaBound (luo2019adaptive). In summary, all the above works require certain
strong conditions such as bounded $\sqrt{v_{k}}$ or large $\xi$. Further, they
all require bounded gradient ($\|\nabla f(x)\|\leq C$) and bounded smoothness
($L$-smooth) condition.

Our analysis falls into the second line of works, which focus on RR Adam.
(shi2021rmsprop) prove the trajectory-wise convergence of RR RMSProp and
(Zhang2022Adam) prove the in-expectation convergence of RR Adam. However,
these works both require $L$-smooth condition. Our analysis follows this line
of works and provides the first convergence result of RR Adam under relaxed
smoothness condition.

Relaxed smoothness assumption. There are several attempts on relaxing
$L$-smooth condition. zhang2019gradient proposes $(L_{0},L_{1})$-smooth
condition to theoretically explain the acceleration effect of clipped SGD over
SGD. Similar results are also extended to clipped SGD with momentum
(zhang2020improved), distributionally-robust optimization (jin2021non) ,
differentially-private SGD (yang2022normalized) and generalized SignSGD
(crawshaw2022robustness).  However, they did not theoretically analyze Adam in
this setting. Considering the great empirical impact of Adam, we believe it is
important to study Adam in its original form.

One concurrent work (li2023convergence) studies the convergence of WR Adam
under $(L_{0},L_{1})$-smooth condition by cleverly constructing certain
stopping time. They also propose a variance-reduced variant with better
convergence rate. However, their bound on Adam not only assumes the noise is
deterministically bounded, but also has polynomial dependence over $1/\xi$
(the hyperparameter for numerical stability). Similarly to
(de2018convergence), this result does not match practice observations, since
Adam performs well even when $\xi$ is as small as $10^{-8}$.

Variants of Adam. Ever since the counter-example of the convergence of Adam
raised by (reddi2018convergence), many new variants of Adam have been
designed. For instance, zou2019sufficient; gadat2020asymptotic;
chen2018convergence; chen2021towards replaced the constant hyperparameters by
iterate-dependent ones e.g. $\beta_{1t}$ or $\beta_{2t}$. AMSGrad
(reddi2019convergence) and AdaFom (chen2018convergence) enforced $\\{v_{t}\\}$
to be non-decreasing. Similarly, AdaBound (luo2019adaptive) imposed
constraints $v_{t}\in[C_{l},C_{u}]$ to prevent the learning rate from
vanishing or exploding. Similarly, (zhou2018adashift) adopted a new estimate
of $v_{t}$ to correct the bias. In addition, there are attempts to combine
Adam with Nesterov momentum (dozat2016incorporating) as well as warm-up
techniques (Liu2020On). There are also some works providing theoretical
analysis on the variants of Adam. For instance, zhou2018convergence studied
the convergence of AdaGrad and AMSGrad. gadat2020asymptotic studied the
asymptotic behavior of a subclass of adaptive gradient methods from landscape
point of view. Their analysis applies to RMSprop-variants with iterate-
dependent $\beta_{2t}$. In summary, all these works study variants of Adam,
which is different from our work since we focus on vanilla Adam.

##  3 Preliminaries

This section introduces notations, definitions, and assumptions that are used
throughout this work.

Notations. We list the notations that are used in the formal definition of the
randomly-shuffled Adam and its convergence analysis.

  * •

(Vector) We define $\bm{a}\odot\bm{b}$ as the Hadamard product (i.e.,
component-wise product) between two vectors $\bm{a}$ and $\bm{b}$ with the
same dimension. We also define $\langle\bm{a},\bm{b}\rangle$ as the $\ell^{2}$
inner product between $\bm{a}$ and $\bm{b}$. We define $\mathds{1}_{d}$ as an
all-one vector with dimension $d$.

  * •

(Array) We define $[m_{1},m_{2}]\triangleq\\{m_{1},\cdots,m_{2}\\}$, $\forall
m_{1},m_{2}\in\mathbb{N},m_{1}\leq m_{2}$. Specifically, we use $[m]$
$\triangleq\\{1,\cdots,m\\}$.

  * •

(Asymptotic notation) We define $A_{1}(x)=\mathcal{O}_{x\rightarrow
a}(A_{2}(x))$ if $\left|\frac{A_{1}(x)}{A_{2}(x)}\right|$ is bounded when
$x\rightarrow$ $a$. We define $A_{2}(x)=\Omega_{x\rightarrow a}(A_{1}(x))$
when $A_{1}(x)$$=\mathcal{O}_{x\rightarrow a}(A_{2}(x))$. We use
$\tilde{\mathcal{O}}$ to denote $\mathcal{O}$ with logarithmic factors hidden,
i.e., $A_{1}(x)=\tilde{\mathcal{O}}_{x\rightarrow a}(A_{2}(x))$ if
$A_{1}(x)=\mathcal{O}_{x\rightarrow a}(A_{2}(x)\log|A_{2}(x)|)$. When the
context is clear, we hide ”$x\rightarrow a$” and only use
$\mathcal{O},\Omega,\tilde{\mathcal{O}}$.

Pseudocode. To facilitate the analysis, we provide the pseudocode of Adam in
Algorithm 1.

Algorithm 1 Randomly reshuffled Adam (RR-Adam)

Input: Objective function
$f(\bm{w}):=\frac{1}{n}\sum_{i=0}^{n-1}f_{i}(\bm{w})$, learning rate series
$\\{\eta_{k}\\}_{k=1}^{T}$ and hyperparameters
$(\beta_{1},\beta_{2})\in[0,1)^{2}$. Initialize the parameter
$\bm{w}_{1,0}\in\mathbb{R}^{d}$, the conditioner
$\bm{\nu}_{1,-1}\in\mathbb{R}^{d,\geq 0}$, and the momentum
$\bm{m}_{1,-1}\in\mathbb{R}^{d}$.

for $k=1$ to $T$ do

Randomly shuffle $[0,n-1]$ to get $\\{\tau_{k,j}\\}_{j=0}^{n-1}$

for $i=0$ to $n-1$ do

Calculate $g_{k,i}=\nabla f_{\tau_{k,i}}(\bm{w}_{\tau_{k,i}})$

Update $\bm{\nu}_{k,i}=\beta_{2}\bm{\nu}_{k,i-1}+(1-\beta_{2})g_{k,i}^{\odot
2}$,

Update $\bm{m}_{k,i}=\beta_{1}\bm{m}_{k,i-1}+(1-\beta_{1})g_{k,i}$

Update
$\bm{w}_{k,i+1}=\bm{w}_{k,i}-\eta_{k}\frac{1}{\sqrt{\bm{\nu}_{k,i}}+\xi}\odot\bm{m}_{k,i}$

end for

Update $\bm{\nu}_{k+1,-1}=\bm{\nu}_{k,n-1}$, $\bm{m}_{k+1,-1}=\bm{m}_{k,n-1}$,
$\bm{w}_{k+1,0}=\bm{w}_{k,n}$

end for

$\bm{m}_{k,i}$ and $\bm{\nu}_{k,i}$ are weighted averages with hyperparamter
$\beta_{1}\in[0,1)$ and $\beta_{2}\in[0,1)$, respectively. $\xi$ is adopted
for numerical stability and it is often chosen to be $10^{-8}$ in practice. In
our theory, we allow $\xi$ to be an arbitrary non-negative constant including
0.

Algorithm 1 follows a without-replacement sampling strategy (also known as
shufﬂing), which is the default strategy used in CV, NLP, GANs, etc. However,
it is not necessarily easy to analyze shuffling strategy, because the
stochastic gradients sampled by random-shuffling lack statistical
unbiasedness, i.e. $\mathbb{E}\left[\nabla
f_{k,i}(x_{k,i})|x_{k,i}\right]\neq\nabla f(x_{k,i})$. This bias requires a
much different analysis from its with-replacement counterpart. Even for SGD,
the analysis for shuffling is often known to be “more challenging”
(tran2021smg; mishchenko2020random). However, we choose to study this version
as it is closer to the practice.

Assumptions. Here we state the assumptions that our result will rest on. The
first one is the $(L_{0},L_{1})$-smooth condition introduced in Section 1.

######  Assumption 1 ($(L_{0},L_{1})$-smooth condition).

We assume that $f_{i}(\bm{w})$ is lower bounded by $0$, and $f_{i}(\bm{w})$
satisfies $(L_{0},L_{1})$-smooth condition, i.e., there exist positive
constants ($L_{0}$, $L_{1}$), such that,
$\forall\bm{w}_{1},\bm{w}_{2}\in\mathbb{R}^{d}$ satisfying
$\|\bm{w}_{1}-\bm{w}_{2}\|\leq\frac{1}{L_{1}}$,

$\|\nabla f_{i}(\bm{w}_{1})-\nabla f_{i}(\bm{w}_{2})\|\leq(L_{0}+L_{1}\|\nabla
f_{i}(\bm{w}_{1})\|)\|\bm{w}_{1}-\bm{w}_{2}\|.$ (3)

Eq. (3) is firstly introduced by zhang2020improved, and is the weakest version
of $(L_{0},L_{1})$-smooth condition to our best knowledge since it does not
require $f_{i}(\bm{w})$ to be twice differentiable. When $f_{i}(\bm{w})$ is
twice differentiable, Eq. (3) is equivalent to Eq. equation 2
(zhang2020improved). $(L_{0},L_{1})$-smooth condition generalizes the
$L$-smooth condition (i.e., $(L_{0},L_{1})$-smooth condition with $L_{0}=L$
and $L_{1}=0$) in classical non-convex optimization literature
(ghadimi2013stochastic; liu2020improved) and allows the smoothness to be
unbounded globally.

######  Assumption 2 (Affine Noise Variance).

$\forall\bm{w}\in\mathbb{R}^{d}$, the gradients of
$\\{f_{i}(\bm{w})\\}_{i=0}^{n-1}$ has the following connection with the
gradient of $f(\bm{w})$:

$\frac{1}{n}\sum_{i=0}^{n-1}\left\|\nabla f_{i}(\bm{w})\right\|^{2}\leq
D_{1}\|\nabla f(\bm{w})\|^{2}+D_{0}.$

Assumption 2 is one of the weakest assumption on gradient noise in existing
literature. It not only generalizes the “bounded variance” assumption (which
requires $D_{1}=1/n$, and thus further generalizes the ”bounded gradient”
assumption (defossez2020simple)) (ghadimi2016mini; Manzil2018adaptive;
huang2021super), but also is weaker than the “strongly growth condition”
(which requires $D_{0}=0$) (schmidt2013fast; vaswani2019fast). Assumption 2
allows flexible choices of $D_{0}$ & $D_{1}$ and thus it is among the weakest
assumption of this kind.

##  4  Adam Converges under the $(L_{0},L_{1})$-smooth condition

In this section, we provide our main result on the convergence of RR Adam
under $(L_{0},L_{1})$-smooth condition. As discussed in Section 1, even for
the simpler with-replacement sampling Adam, the establishment of the
convergence under $(L_{0},L_{1})$-smooth condition requires restrictive
assumptions such as a large $\xi$ (the constant introduced for numerical
stability and is as small as $10^{-8}$ in practice), and deterministically
bounded noise (li2023convergence). Such assumptions make the corresponding
results hard to apply to practical setting. As for the harder randomly-
reshuffled setting, there is no convergence result for Adam under non-uniform
smoothness. Our result tackles the limitation in existing works and propose
the first convergence result for RR Adam under non-uniform smoothness,
provided as follows.

######  Theorem 1.

Consider RR Adam defined as Algorithm 1 with diminishing learning rate
$\eta_{k}=\frac{\eta_{1}}{\sqrt{k}}$. Let Assumptions 1 and 2 hold. Suppose
the hyperparamters satisfy: $0\leq\beta_{1}^{2}<\beta_{2}<1$ and $\beta_{2}$
is larger than a threshold $\gamma(D_{1})$. Then, we have

$\displaystyle\min_{k\in[1,T]}\left\\{\frac{\|\nabla
f(\bm{w}_{k,0})\|}{\sqrt{D_{1}}},\frac{\|\nabla
f(\bm{w}_{k,0})\|^{2}}{\sqrt{D_{0}}}\right\\}\leq$
$\displaystyle\tilde{\mathcal{O}}\left(\frac{f(\bm{w}_{1,0})-\min_{\bm{w}}f(\bm{w})}{\sqrt{T}}\right)$
$\displaystyle+\mathcal{O}((1-\beta_{2})^{2}\sqrt{D_{0}}).$ (4)

For simplicity, we defer the concrete form of $\gamma$ to Appendix B.2. We
provide some remarks on the results as follows, and state the proof idea in
the next section.

Explanation for Theorem 1. Theorem 1 is pioneering in demonstrating that RR
Adam is capable of converging under the non-uniform smoothness condition, a
finding that is novel to our best knowledge. Observing the right-hand side of
inequality (4), one can see that as $T\to\infty$, it approaches
$\mathcal{O}((1-\beta_{2})^{2}\sqrt{D_{0}})$. This suggests that Adam’s
convergence to the vicinity of stationary points is inversely related to the
proximity of $\beta_{2}$ to 1. This theoretical insight corroborates the
common practice of choosing $\beta_{2}$ close to $0.99$. A counterexample
provided later will further illustrate that convergence to a neighborhood,
rather than an exact point, is an intrinsic characteristic of the algorithm.

Beyond the $(L_{0},L_{1})$-smooth condition, Theorem 1 presupposes only that
the gradient noise exhibits affine variance as per Assumption 2, which is a
relatively mild constraint that eschews the need for a bounded gradient norm.
This is crucial, as imposing a bound would reduce the $(L_{0},L_{1})$-smooth
condition to an $(L_{0}+L_{1}M)$-smooth condition with a gradient norm capped
by $M$. Additionally, we do not require the adaptive learning rate
$\eta_{k}/\sqrt{\hat{\nu}_{k}}$ to be upper bounded, nor do we stipulate a
large regularizer $\xi$—aligning with common practices in deep learning
libraries where a small $\xi$ such as $10^{-8}$ is often effective. Our
theorem permits any non-negative $\xi$, including zero. Finally, Theorem 1
asserts convergence for every possible trajectory, a guarantee that exceeds
the typical ”convergence in expectation” results and poses a significant
technical challenge.

On the Comparison to Existing Analyses of RR Adam. Our analysis extends the
applicability of RR Adam by ensuring convergence under the $(L_{0},L_{1})$
smooth condition, which inherently encompasses the traditional $L$-smooth
condition. This broadened perspective allows our results to guarantee
convergence for RR Adam even under the more general $L$-smooth scenario. When
juxtaposed with the state-of-the-art analysis of RR Adam under the $L$-smooth
condition by Zhang2022Adam, our findings advance the field in two significant
ways. Firstly, we elevate the notion of convergence from the expected sense to
the more stringent trajectory-wise convergence. Secondly, we refine the
estimated convergence neighborhood, tightening it from
$(1-\beta_{2})\sqrt{D_{0}}$ to $(1-\beta_{2})^{2}\sqrt{D_{0}}$. Collectively,
our analysis not only operates under a less restrictive assumption—the
$(L_{0},L_{1})$-smooth condition—but also delivers substantively enhanced
convergence results.

On the range of hyperparameters. Theorem 1 indicates that Adam can work when
$\beta_{2}$ is close enough to $1$. This matches the practical choice of
$\beta_{2}$ (e.g., $0.999$ in default setting, $0.95$ in the GPT-3 training
(brown2020language)). Note that our result does not contradict the
counterexamples of Adam’s non-convergence (reddi2018convergence;
Zhang2022Adam), as these divergence results require $\beta_{2}$ to be small
and thus not close to $1$. Rather, these counterexamples suggest that large
$\beta_{2}$ is necessary for convergence. As for $\beta_{1}$, Theorem 1 needs
$\beta_{1}^{2}<\beta_{2}$. When $\beta_{2}$ is large, Theorem 1 allows a wide
range of candidates of $\beta_{1}$ (e.g., $0.9$ in default setting and $0.5$
in GAN (radford2015unsupervised)).

Figure 2:  Reconduct of experimental results from (Zhang2022Adam). The
objective function is defined in Eq. (5). One can observe that while letting
$\beta_{2}$ closer to $1$ can make the limiting gradient norm smaller, the
limiting gradient norm always stabilizes beyond 0.

On the neighborhood of stationary points. When $D_{0}\neq 0$, Theorem 1 only
ensures that Adam converges to a neighborhood of stationary points
$\\{\bm{w}:\min$ $\\{\frac{\|\nabla f(\bm{w}))\|}{\sqrt{D_{1}}},\frac{\|\nabla
f(\bm{w})\|^{2}}{\sqrt{D_{0}}}\\}\leq\mathcal{O}((1-\beta_{2})\sqrt{D_{0}})\\}$.
Since SGD converges to the stationary points with diminishing learning rate,
one may wonder if Theorem 1 can be improved to obtain the same conclusion as
SGD. Unfortunately, there is a counterexample in the existing literature (
function (9) in Zhang2022Adam) showing that Adam does not converge to
stationary points even if all the conditions in Theorem 1 are satisfied.
Specifically, (Zhang2022Adam) consider the following function:

$\displaystyle f(x)=\sum_{j=0}^{9}f_{j}(x)=\frac{1}{10}x^{2}-1,$ (5)
$\displaystyle\text{ where }f_{j}(x)=\left\\{\begin{array}[]{l}(x-1)^{2}\text{
if }j=0\\\ -0.1\left(x-\frac{10}{9}\right)^{2}\text{ if }1\leq j\leq
9\end{array}\right..$

One can easily verify such an example satisfies Assumptions 2 and 1 with
$D_{0}>0$. As shown in Figure 2, when running Adam (with $\beta_{1}=0.9$,
$\eta_{k}=0.1/\sqrt{k},a=3,x_{0}=-2$), it does not converge to exact
stationary points. Instead, it converges to a neighborhood of stationary
points with size inversely proportional to $\beta_{2}$. Therefore, the non-
vanishing term in Theorem 1 is not due to the limitation of the proof. Rather,
it is an intrinsic property of Adam.

Why cannot Adam converge to exact stationary points when $D_{0}>0$?
Intuitively, this is because even with diminishing $\eta_{k}$, the effective
learning rate $\frac{\eta_{k}}{\xi\mathds{1}_{d}+\sqrt{\bm{\nu}_{k,i}}}$ may
not diminish due to the potentially decreasing $\sqrt{\bm{\nu}_{k,i}}$. The
good news is that $\mathcal{O}((1-\beta_{2})\sqrt{D_{0}})$ approaches $0$ as
$\beta_{2}$ gets close to $1$. This means that the neighborhood shrinks as
$\beta_{2}\rightarrow 1$ (this is also observed in Figure 2). As discussed
above, the practical use of $\beta_{2}$ is close to $1$, and thus
$O((1-\beta_{2})\sqrt{D_{0}})$ is tolerable.

On the Diminishing Learning Rate. In Theorem 1, we consider a diminishing
learning rate of the form $\eta_{k}=\frac{\eta_{1}}{\sqrt{k}}$ to maintain
consistency with existing works on RR Adam, such as those by (shi2021rmsprop;
Zhang2022Adam), which also employ diminishing learning rates. Nonetheless, our
results can be readily extended to RR Adam with a constant learning rate. By
adhering to the same proof strategy outlined in Theorem 1, one can demonstrate
that with a constant learning rate $\eta$, the conclusion (as given in Eq.
(4)) of Theorem 1 is modified to $\min_{k\in[1,T]}\\{\frac{\|\nabla
f(w_{k,0})\|}{\sqrt{D_{0}}},\frac{\|\nabla
f(w_{k,0})\|2}{\sqrt{D_{1}}}\\}\leq\tilde{\mathcal{O}}\left(\frac{f(\bm{w}_{1,0})-\min_{\bm{w}}f(\bm{w})}{\eta
T}\right)+\mathcal{O}(\sqrt{D_{0}}(1-\beta_{2})^{2})+\mathcal{O}(\eta)$. In
essence, while Adam may converge more rapidly to a neighborhood (with the rate
improving from $1/\sqrt{t}$ to $1/t$), the size of this neighborhood is
increased by an additional term $\mathcal{O}(\eta)$, which is attributable to
the constant step size.

##  5 Proof sketch

In this section, we briefly explain our proof idea for Theorem 1, which can be
divided into two stages. In Stage I, we will prove Theorem 1 for Adam with
$\beta_{1}=0$ to show the challenge brought by $(L_{0},L_{1})$-smooth
condition and how we tackle it. In Stage II, we then show the additional
difficulty when adding the momentum and our corresponding intuition to solve
it.

Stage I: Convergence of Adam with $\beta_{1}=0$. By the descent lemma,

$\displaystyle\begin{matrix}f(\bm{w}_{k+1,0})-f(\bm{w}_{k,0})\leq&\\\
\quad\vspace{2mm}\end{matrix}$
$\displaystyle\begin{matrix}\underbrace{\langle\bm{w}_{k+1,0}-\bm{w}_{k,0},\nabla
f(\bm{w}_{k,0})\rangle}\\\ \text{First Order}\end{matrix}\begin{matrix}\\\
\quad\vspace{2mm}\end{matrix}$
$\displaystyle\begin{matrix}\underbrace{+\frac{L_{loc}}{2}\|\bm{w}_{k+1,0}-\bm{w}_{k,0}\|^{2},}\\\
\text{Second Order}\end{matrix}$ (6)

where $L_{loc}$ is the local smoothness. We bound the first-order and the
second-order term respectively. The upper bound on second-order term is
relatively simple. Due to the limited space, we only show the idea of bounding
first-order term here.

The ever-changing adaptive learning rate poses a challenge on deriving the
bound. It is even noted that with small $\beta_{2}$, the first order term can
be positive (reddi2018convergence). However, we notice that if
$\bm{\nu}_{k,i}$ is stationary, i.e., RMSProp degenerates to SGD with
preconditioning, the first order term equals to
$-\eta_{k}\langle\sum_{i}\frac{1}{\xi\mathds{1}_{d}+\sqrt{\bm{\nu}_{k,0}}}\odot\nabla
f_{\tau_{k,i}}(\bm{w}_{k,i}),\nabla
f(\bm{w}_{k,0})\rangle\approx-\eta_{k}\langle\sum_{i}\frac{1}{\xi\mathds{1}_{d}+\sqrt{\bm{\nu}_{k,0}}}\odot\nabla
f_{\tau_{k,i}}(\bm{w}_{k,0}),\nabla f(\bm{w}_{k,0})\rangle$, which is indeed
negative. While that ”$\bm{\nu}_{k,i}$ is stationary” is too good to be true,
we prove that $\bm{\nu}_{k,i}$ changes little when $\beta_{2}$ is close to
$1$, assuming that the gradient is large. Below we denote $\bm{\nu}_{l,k,i}$
as the $l$-th component of $\bm{\nu}_{k,i}$.

######  Lemma 1 (Informal).

For any $l\in[d]$ and $i\in[0,n-1]$, if
$\max_{p\in[0,n-1]}|\partial_{l}f_{p}(\bm{w}_{k,0})|=\Omega(\sum_{r=1}^{k-1}\beta_{2}^{\frac{(k-1-r)}{2}}\eta_{r}$
$\|\nabla f(\bm{w}_{r,0})\|+\eta_{k})$, then
$|\bm{\nu}_{l,k,i}-\bm{\nu}_{l,k,0}|=\mathcal{O}((1-\beta_{2})\bm{\nu}_{l,k,0})$.

The idea of Lemma 1 is simple: since
$\bm{\nu}_{k,i}=\beta_{2}\bm{\nu}_{k,i-1}+(1-\beta_{2})\nabla
f_{\tau_{k,i}}(\bm{w}_{\tau_{k,i}})^{\odot 2}$, the change of $\bm{\nu}_{k,i}$
w.r.t. $i$ should be small when $\beta_{2}$ is large. However, we need to
check that the relative size of $\nabla
f_{\tau_{k,i}}(\bm{w}_{\tau_{k,i}})^{\odot 2}$ w.r.t. $\bm{\nu}_{k,i-1}$ is
uniformly bounded across varying $\beta_{2}$, otherwise the term
$(1-\beta_{2})\nabla f_{\tau_{k,i}}(\bm{w}_{\tau_{k,i}})^{\odot 2}$ may not go
to zero when $\beta_{2}\rightarrow 1$. We resolve this challenge by expanding
$\bm{\nu}_{k,i}$ in terms of squared gradients and bounding the gap between
each of the terms and $\nabla f_{\tau_{k,i}}(\bm{w}_{\tau_{k,i}})^{\odot 2}$
by echoing $(L_{0},L_{1})$-smooth condition. We defer a detailed proof to
Corollary 5 for details.

As a conclusion, if we denote those dimensions with large gradients (i.e.,
satisfying the requirement of Lemma 1) as $\mathbb{L}_{large}^{k}$ and the
rest as $\mathbb{L}_{small}^{k}$, Lemma 1 indicates that the
$\mathbb{L}_{large}^{k}$ part (i.e.,
$\sum_{l\in\mathbb{L}_{large}^{k}}(\bm{w}_{l,k+1,0}-\bm{w}_{l,k,0})\partial_{l}f(\bm{w}_{k,0})$)
in the first order term can be bounded as

$\displaystyle-\eta_{k}\sum_{l\in\mathbb{L}_{large}^{k}}\frac{\partial_{l}f(\bm{w}_{k,0})}{\sqrt{\bm{\nu}_{l,k,i}}+\xi}\sum_{i}\partial_{l}f_{\tau_{k,i}}(\bm{w}_{k,i})$
$\displaystyle\approx$
$\displaystyle-\eta_{k}\sum_{l\in\mathbb{L}_{large}^{k}}\left(\frac{\partial_{l}f(\bm{w}_{k,0})^{2}}{\sqrt{\bm{\nu}_{l,k,0}}+\xi}+\mathcal{O}\left((1-\beta_{2})\frac{\partial_{l}|f(\bm{w}_{k,0})|\sum_{i}|\partial_{l}f_{\tau_{k,i}}(\bm{w}_{k,i})|}{\sqrt{\bm{\nu}_{l,k,0}}+\xi}\right)\right)$
$\displaystyle=$ $\displaystyle-\Omega\left(\eta_{k}\min\left\\{\frac{\|\nabla
f(\bm{w}_{k,0})\|}{\sqrt{D_{1}}},\frac{\|\nabla
f(\bm{w}_{k,0})\|^{2}}{\sqrt{D_{0}}}\right\\}\right)+O(\eta_{k}(1-\beta_{2})\sqrt{D_{0}}).$

The last equation uses the affine noise assumption (Assumption 2), and we
defer a detailed proof to Appendix B.4. A remaining problem is how to deal
with those components in $\mathbb{L}_{small}^{k}$. We treat them as error
terms. Concretely, $l\in\mathbb{L}_{small}^{k}$ indicates that
$\partial_{l}f(\bm{w}_{k,0})=\mathcal{O}(\sum_{r=1}^{k-1}\beta_{2}^{\frac{(k-1-r)}{2}}$
$\eta_{r}\|\nabla f(\bm{w}_{r,0})\|+\eta_{k})$. Applying it directly into
$\sum_{l\in\mathbb{L}_{small}^{k}}(\bm{w}_{l,k+1,0}-\bm{w}_{l,k,0})\partial_{l}f(\bm{w}_{k,0})$,
we have

$\displaystyle-\eta_{k}\sum_{l\in\mathbb{L}_{large}^{k}}\frac{\partial_{l}f(\bm{w}_{k,0})}{\sqrt{\bm{\nu}_{l,k,i}}+\xi}\sum_{i}\partial_{l}f_{\tau_{k,i}}(\bm{w}_{k,i})$
$\displaystyle=$
$\displaystyle\mathcal{O}\left(\eta_{k}\left(\sum_{r=1}^{k-1}\beta_{2}^{\frac{(k-1-r)}{2}}\eta_{r}\|\nabla
f(\bm{w}_{r,0})\|+\eta_{k}\right)\right),$

where the equation is because
$\frac{\partial_{l}f_{\tau_{k,i}}(\bm{w}_{k,i})}{\sqrt{\bm{\nu}_{l,k,i}}+\xi}$
is bounded (proved by Lemma 4).

In order to upper bound the first order term, we then need to prove that
$-\Omega(\eta_{k}\min\\{\frac{\|\nabla
f(\bm{w}_{k,0})\|}{\sqrt{D_{1}}},\frac{\|\nabla
f(\bm{w}_{k,0})\|^{2}}{\sqrt{D_{0}}}\\})$ dominates
$\mathcal{O}(\eta_{k}(\sum_{r=1}^{k-1}\beta_{2}^{\frac{(k-1-r)}{2}}\eta_{r}\|\nabla
f(\bm{w}_{r,0})\|+\eta_{k}))$. This is not necessarily true, as the historical
gradient norms in the latter term can be large.

######  Remark 1.

We recognize this as the challenge brought by $(L_{0},L_{1})$-smooth
condition, since the latter term degenerates to $\mathcal{O}(\eta_{k}^{2})$
with $L$-smooth condition, which is minor ($\sum_{k=1}^{T}\eta_{k}^{2}$ is
only in order $\log T$).

We address this challenge by noting that what we need to bound is the sum of
the first order term. Fortunately, although we cannot upper bound the first
order term in one single epoch, we can bound the sum of it across epochs. By a
sum order change, the sum of
$\mathcal{O}(\eta_{k}(\sum_{r=1}^{k-1}\beta_{2}^{\frac{(k-1-r)}{2}}\eta_{r}\|\nabla
f(\bm{w}_{r,0})\|+\eta_{k}))$ over $k$ equals to $\mathcal{O}(\sum_{k=1}^{T}$
$\eta_{k}^{2}\|\nabla f(\bm{w}_{k,0})\|+\ln T)$. This is smaller by the sum of
$-\Omega(\eta_{k}\min\\{\frac{\|\nabla
f(\bm{w}_{k,0})\|}{\sqrt{D_{1}}},\frac{\|\nabla
f(\bm{w}_{k,0})\|^{2}}{\sqrt{D_{0}}}\\})$ by order of $\eta_{k}$ except a $\ln
T$ term due to the mean value inequality, i.e.,

$\eta_{k}^{2}\|\nabla
f(\bm{w}_{k,0})\|\leq\mathcal{O}(\eta_{k}^{2})+\mathcal{O}\left(\eta_{k}^{2}\sqrt{\frac{D_{1}}{D_{0}}}\|\nabla
f(\bm{w}_{k,0})\|^{2}\right).$

We then conclude the sum of the first order term can be bounded by
$-\Omega(\eta_{k}\min\\{\frac{\|\nabla
f(\bm{w}_{k,0})\|}{\sqrt{D_{1}}},\frac{\|\nabla
f(\bm{w}_{k,0})\|^{2}}{\sqrt{D_{0}}}\\})+\mathcal{O}(\ln T)$.

######  Remark 2 (Difficulty compared to the analysis under $L$-smooth
condition).

Here we illustrate the challenge brought by stepping beyond $L$-smooth
condition. First of all, the change of $\bm{\nu}_{k,i}$ is easier to bound
without the historical gradient term due to the absence of the gradient norm
in the bound of local smoothness. Secondly, under $L$-smooth condition, the
error does not contain historical gradient information and is only in order of
$\mathcal{O}(\eta_{k}^{2})$, which is easy to bound.

Stage II: adding the momentum. The second order term of Adam can be bounded
similarly. However, the analysis of the first order term becomes more
challenging even though we still have $\bm{\nu}_{k,i}\approx\bm{\nu}_{k,0}$.
Specifically, even with constant $\bm{\nu}_{k,i}=\bm{\nu}_{k,0}$,
$-\eta_{k}\langle\sum_{i}\frac{\bm{m}_{k,i}}{\sqrt{\bm{\nu}_{k,i}}+\xi},-\nabla
f(\bm{w}_{k,0})\rangle>0$ is not necessarily correct, as the momentum
$\bm{m}_{k,i}$ contains a heavy historical signal, and may push the update
away from the negative gradient direction.

We resolve this challenge by observing that the alignment of
$\bm{w}_{k+1,0}-\bm{w}_{k,0}$ and $-\nabla f(\bm{w}_{k,0})$ is required due to
that our analysis is based on the potential function $f(\bm{w}_{k,0})$.
However, while this potential function is suitable for the analysis of
RMSProp, it is no longer appropriate for Adam based on the above discussion.
We need to construct another potential function. Our construction of the
potential function is based on the following observation: we revisit the
update rule in Algorithm 1 and rewrite it as
$\frac{\bm{m}_{k,i}-\beta_{1}\bm{m}_{k,i-1}}{1-\beta_{1}}=\nabla
f_{\tau_{k,i}}(\bm{w}_{k,i}).$

Notice that the right-hand-side of the above equation contains no historical
gradients but only the gradient of the current step! By dividing
$(\sqrt{\bm{\nu}_{k,i}}+\xi)/\eta_{k}$ above,

$\displaystyle\frac{\bm{w}_{k,i+1}-\bm{w}_{k,i}-\beta_{1}(\bm{w}_{k,i}-\bm{w}_{k,i-1})}{1-\beta_{1}}\approx$
$\displaystyle-\frac{\eta_{k}}{\sqrt{\bm{\nu}_{k,0}}+\xi\mathds{1}_{d}}\odot\frac{\bm{m}_{k,i}-\beta_{1}\bm{m}_{k,i-1}}{1-\beta_{1}}$
$\displaystyle=$
$\displaystyle-\frac{\eta_{k}}{\sqrt{\bm{\nu}_{k,0}}+\xi\mathds{1}_{d}}\odot\nabla
f_{\tau_{k,i}}(\bm{w}_{k,i}).$

After simple rearrangement, one can see that the sequence
$\\{\frac{\bm{w}_{k,i}-\beta_{1}\bm{w}_{k,i-1}}{1-\beta_{1}}\\}$ are
(approximately) doing SGD within one epoch (with coordinate-wise but constant
learning rate $\bm{\nu}_{k,i}$)! We define

$\bm{u}_{k,i}\triangleq\frac{\bm{w}_{k,i}-\beta_{1}\bm{w}_{k,i-1}}{1-\beta_{1}}.$

Then, further notice that the distance between
$\bm{u}_{k,i}=\bm{w}_{k,i}+\beta_{1}\frac{\bm{w}_{k,i}-\bm{w}_{k,i-1}}{1-\beta_{1}}$
and $\bm{w}_{k,i}$ is in order of one step’s update, and thus
$\bm{u}_{k,i}\approx\bm{w}_{k,i}$ . Therefore, we choose our potential
function as $f(\bm{u}_{k,i})$. The Taylor’s expansion of $f$ at $\bm{u}_{k,0}$
then provides a new descent lemma, i.e.,

$\displaystyle\begin{matrix}f(\bm{u}_{k+1,0})-f(\bm{u}_{k,0})\leq\\\
\quad\vspace{2mm}\end{matrix}$
$\displaystyle\begin{matrix}\underbrace{\langle\bm{u}_{k+1,0}-\bm{u}_{k,0},\nabla
f(\bm{u}_{k,0})\rangle}\\\ \text{First Order}\end{matrix}\begin{matrix}\\\
\quad\vspace{2mm}\end{matrix}$
$\displaystyle\begin{matrix}\underbrace{~{}+~{}\frac{L_{0}+L_{1}\|\nabla
f(\bm{w}_{k,0})\|}{2}\|\bm{w}_{k+1,0}-\bm{w}_{k,0}\|^{2},}\\\ \text{Second
Order}\end{matrix}$ (7)

By noticing $\bm{w}_{k,i}\approx\bm{u}_{k,i}\approx\bm{u}_{k,0}$, the first
order term can be further approximated by
$-\langle\frac{\eta_{k}}{\sqrt{\bm{\nu}_{k,0}}+\xi\mathds{1}_{d}}\odot\nabla
f(\bm{w}_{k,0}),\nabla f(\bm{w}_{k,0})\rangle$ which is negative. The rest of
the proof is the same as that of Stage I.

######  Remark 3 (On Why State-of-the-Art Results Do Not Achieve Trajectory-
Wise Convergence as Ours).

The state-of-the-art analysis of RR Adam under the $L$-smooth condition, as
presented by Zhang2022Adam, also addresses the misalignment between
$\bm{w}_{k+1,0}-\bm{w}_{k,0}$ and $-\nabla f(\bm{w}_{k,0})$. However, their
approach does not employ a potential function, resulting in convergence
results that are restricted to in-expectation guarantees. Specifically,
Zhang2022Adam manage this misalignment by assuming a uniform distribution over
all possible shuffling orders and demonstrating that, under this assumption,
the expected value of $\bm{w}_{k+1,0}-\bm{w}_{k,0}$ is approximately equal to
$-\nabla f(\bm{w}_{k,0})$. In contrast, our methodology introduces an
auxiliary function, $f(\bm{u}_{k,i})$, and examines the dynamics of
$\bm{u}_{k,i}$. This approach shifts the challenge from aligning
$\bm{w}_{k+1,0}-\bm{w}_{k,0}$ with $-\nabla f(\bm{w}_{k,0})$ to aligning
$\bm{u}_{k+1,0}-\bm{u}_{k,0}$ with $-\nabla f(\bm{w}_{k,0})$. Such a strategy
simplifies the analytical process and facilitates the demonstration of
trajectory-wise convergence.

######  Remark 4 (Similar potential functions in the existing literature.).

We notice that similar potential functions have already been applied in the
analysis of other momentum-based optimizers, e.g., momentum (S)GD in
(ghadimi2015global) and (liu2020improved). However, extending the proof to
Adam is highly-nontrivial. The key difficulty lies in showing that the first-
order expansion of $f(\bm{u}_{k,0})$ is positive, which further requires that
the adaptive learning rate does not change much within one epoch. This is hard
for Adam as the adaptive learning rate of Adam can be non-monotonic. The lack
of L-smooth condition makes the proof even challenging due to the unbounded
error brought by gradient norms.

##  6 Comparison Between Adam and SGD

Now we compare the convergence rate of Adam with SGD. To do so, we need a
lower bound of SGD in the same setting as Theorem 1. There are several
existing lower bounds of SGD under $(L_{0},L_{1})$ smoothness condition (e.g.,
(zhang2019gradient; crawshaw2022robustness)). However, we find these lower
bounds cannot be directly applicable for comparison with Adam. This is
because:

  * •

1) In the lower bound of (zhang2019gradient; crawshaw2022robustness), they
pick the learning rate _before_ the construction of the objective function and
initialization point (we restate their lower bound in Appendix B.1 for
completeness). In other words, it is possible that if we fix the objective
function and tune the learning rate (which is a common practice in the
training of deep neural networks), SGD can converge very fast. For rigorous
comparison with Adam, we need a lower bound with reversed ordering. That is,
we need the following statement: “consider a fixed objective function and
initialization point, then no matter how we pick the learning rate, SGD
suffers from a certain rate. ”

  * •

2) The lower bounds of SGD in (zhang2019gradient; crawshaw2022robustness)
require constant learning rate. However, since Adam in Theorem 1 uses
diminishing-learning-rate, we aim to establish a lower bound of SGD with
diminishing learning rate.

Unfortunately, there is no existing lower bound that satisfies the above two
properties. In the following theorem, we provide a refined lower bound of SGD
in the setup that we desired.

######  Theorem 2.

For any $L_{0},L_{1},T>0$, there exists an objective function $f$ obeying
Assumption 1, and an initialized parameter $\bm{w}_{0}$ satisfying
$M=\sup\\{\|\nabla f(\bm{w})\|:f(\bm{w})\leq f(\bm{w}_{0})\\}$, such that
$\forall\eta_{1}>0$, the iterations of SGD $\\{\bm{w}_{t}\\}_{t=0}^{\infty}$
satsifies $\min_{t\in T}\|\nabla
f(\bm{w}_{t})\|^{2}=\Omega(M(f(\bm{w}_{0})-\min_{\bm{w}\in\mathbb{R}^{d}}f(\bm{w}))/\sqrt{T})$.

The proof can be in Appendix A. The proof idea is mainly motivated by
(zhang2019adam). We highlight some differences when we try to reach the two
properties mentioned previously.

  * •

To reverse the ordering of “picking learning rate and functions &
initialization”, we simply augment the worst-case example in (zhang2019adam)
into 2 dimensional space. It turns out this simple trick is effective in the
proof.

  * •

To change constant learning rate into diminishing learning rate, we show that:
when the initial learning rate $\eta_{0}$ is larger than a certain threshold,
the decay rate of the learning rate cannot offset the curvature explosion
along the iteration, causing divergence; on the other hand, when initial
$\eta_{0}$ is small, it would lead to slow convergence. This is a new finding
in $(L_{0},L_{1})$ setting. We prove this result by mathematical induction.
This part of the discussion is not required in the lower bound of
(zhang2019adam) with constant learning rate.

#### Comparison between Adam and SGD.

Finally, we discuss the implication the lower bound of SGD (Theorem 2) and the
upper bound of Adam (Theorem 1). In the lower bound of SGD, there is an extra
constant $M$ which does not appear in the upper bound of Adam. This allows us
to compare the convergence rates of these two algorithms.

We summarize our findings as follows. We emphasize that Theorem 1 and Theorem
2 share exactly the same setting: both consider function class under the same
assumptions; both SGD and Adam use diminishing learning rate. Therefore, the
following comparison is rigorous.

Finding 1:  When $D_{0}=0$. Adam converges to stationary point with rate
$\mathcal{O}\left(\frac{1}{T}\right)$ while GD converges with rate
$\mathcal{O}\left(\frac{1}{\sqrt{T}}\right)$. So Adam converges (to stationary
points) faster.

Finding 2:  When $D_{0}>0$. There exists a set of $\bm{w}$ with infinite
Lebesgue measure, such that, when starting at any $\bm{w}$ in this set, Adam
converges (to the neighborhood of stationary points) faster than SGD.

Note that the above statement “algorithm 1 converges faster than algorithm 2”
does not mean that algorithm 1 always converges faster than algorithm 2. For
sure, rarely can anyone make such a strong statement. The above statement
actually means that “the worst-case complexity of algorithm 1 is faster than
that of algorithm 2, and both complexity bounds can be simultaneously achieved
when working on the same function and starting at the same initialization”.
This definition is adopted from (sun2021worst), and it is a widely accepted
definition in the optimization field.

###### Proof.

Finding 1 can be directly proved by plugging $D_{0}=0$ into Theorem 1 and
squaring the inequality. We now prove Finding 2. First, we state an important
fact from the proof of Theorem 2.

#### Fact 1:

For the counter-example we constructed in Theorem 2. $M=\sup\\{\|\nabla
f(\bm{w})\|:f(\bm{w})\leq f(\bm{w}_{0})\\}$ goes to infinity as $\|\bm{w}\|$
goes to infinity. Further, for any $C>0$, the set $\\{\bm{w}:M>C\\}$ is of
infinite Lebesgue measure.

Based on Fact 1, for the worst-case example in Theorem 2, there must exist a
region in $\mathbb{R}^{d}$ where $M$ is larger than all the constant terms in
the upper bound of Adam in Theorem 1. Further, Such region is of infinite
Lebesgue measure. When running Adam and SGD simultaneously on this worst-case
example starting from any $\bm{w}$ in this region, the constants in the upper
bound of Adam is smaller than the constants in the lower bound of SGD. Since
the upper and lower bounds share the same rate, so Adam is faster. Note that
there is an additional constant term in the upper bound of Adam equation 4, so
we conclude that Adam converges to the neighborhood of stationary points
faster than SGD. ∎

Note that when $D_{0}>0$, Adam is still guaranteed to converge faster, but
only to the neighborhood in lieu of the exact stationary points. We emphasize
that this “neighborhood” cannot be eliminated since there is a counter-example
showing that Adam cannot reach 0 gradient when $D_{0}>0$ (see Figure 2). So
this is an intrinsic property of Adam, rather than the limitation of the
theory. Nevertheless, we believe the effect of “not converging to exact
stationary points” is minor in practice. This is because: 1) As shown in
Theorem 1 and Figure 2, the size of the “ambiguity zone” is inversely
proportional to $\beta_{2}$. Since $\beta_{2}$ is often chosen to be close to
1, the ambiguity zone shrinks and becomes negligible. 2) Machine learning
tasks do not pursue high-precision solutions (as much as other fields like
PDE). Practitioners usually aim to efficiently find approximate solutions,
rather than exact solutions that over-fit the training data.

To our knowledge, the discussion above is the first time that Adam and SGD are
rigorously compared in the same setting where the advantage of Adam can be
revealed. We believe these results shed new light on understanding the benefit
of Adam.

Finally, we briefly explain why the upper bound of Adam is independent of $M$.
Intuitively, this is because: (1) it uses different learning rates for
different components of $\bm{w}$. (2) For each component of $\bm{w}$, the
effective learning rate adjusts according to the gradient norm (thus according
to the local smoothness). Even though the initial effective learning rate is
small, it gets larger when moving in a flat landscape. Combining together, the
initial learning rate of Adam can be independent of $M$, and so is its
convergence rate.

##  7 Discussion

Adam’s Advantage over Gradient Descent with Gradient Clipping.
zhang2019gradient established that gradient descent (GD) and stochastic
gradient descent (SGD) with gradient clipping are convergent under the
$(L_{0},L_{1})$ smooth condition. A natural inquiry arises concerning the
benefits of Adam over GD/SGD when gradient clipping is employed. While we lack
robust theoretical backing to fully answer this question, one discernible
advantage of Adam, as inferred from our results, is its capability to manage
more intricate noise profiles that adhere to the affine variance noise
assumption. In contrast, the current analyses of GD/SGD with gradient clipping
within the $(L_{0},L_{1})$-smooth framework presuppose that the deviation
between the stochastic gradient and the true gradient is uniformly bounded
with certainty—an assumption more stringent than the one we consider. Indeed,
a recent work (faw2022power) demonstrates that there exists a counterexample
satisfying Assumption 2 over which SGD with gradient clipping fails to
converge. Together with Theorem 1, their result demonstrate that a wide range
of application scenario of Adam than SGD with gradient clipping.

Insights for Practitioners. Here we discuss the insights our Theorem 1 can
provide to practitioners. Firstly, the widespread adoption of Adam among
practitioners, evidenced by its extensive citation record, underscores the
importance of a theoretical understanding of the algorithm.

Secondly, our findings offer theoretical support for a prevalent practice
among practitioners: for tasks involving architectures like Transformers and
LSTMs, Adam is often favored over SGD.

Lastly, in light of the convergence criteria delineated in Theorem 1, we
propose practical guidance for hyperparameter selection when employing Adam.
Specifically, we recommend increasing $\beta_{2}$ and experimenting with
various $\beta_{1}$ values that satisfy $\beta_{1}<\sqrt{\beta_{2}}$. This
heuristic could potentially reduce the computational burden associated with
exhaustive hyperparameter exploration across the $(\beta_{1},\beta_{2})$
space.

Limitations of Theorem 1. While Theorem 1 represents a significant advancement
in establishing the convergence of RR Adam under non-uniform smoothness
conditions, it is not without its limitations. Specifically, Theorem 1 applies
to cases where $\beta_{1}=0$, implying the absence of momentum. The theorem
does not distinguish between the convergence rates when $\beta_{1}=0$ and when
$\beta_{1}>0$, thus not demonstrating the benefits of momentum. The
theoretical elucidation of momentum’s advantage within Adam’s convergence
analysis remains a complex question. The role of momentum is not fully
understood even in momentum SGD for non-convex optimization (liu2020improved),
much less so for Adam. We acknowledge the importance of this question but
consider it beyond the scope of this paper, leaving it for future research.

##  8 Conclusions and Future directions

In this paper, we have taken a pioneering step towards a theoretical
understanding of the adaptivity inherent in the Adam optimization algorithm.
We present the first convergence results for RR Adam under the ($L_{0}$,
$L_{1}$)-smooth condition, which is both realistic and closely aligned with
practical scenarios. In contrast to existing analyses of RR Adam under the
stronger $L$-smooth condition, our results further demonstrate a more robust
form of convergence, specifically trajectory-wise convergence, and indicate a
reduced distance to the stationary point.

Future Directions. An intriguing avenue for future research lies in
delineating the advantages of incorporating momentum in Adam. Our Theorem 1
indicates an identical convergence rate for both $\beta_{1}=0$ (RMSProp) and
$\beta_{1}>0$ (Adam), implying that the current analysis does not
differentiate between the iteration complexities of Adam and RMSProp.
Consequently, the specific benefits of momentum in Adam remain elusive. This
presents a substantial challenge, given that the impact of momentum is not yet
fully understood even in the context of SGD with momentum. A possible strategy
could be to first establish a theoretical foundation for the advantages of
momentum in SGD, followed by extending these insights to the analysis of Adam.
Moreover, it would be compelling to explore whether Adam can effectively
manage more severe smoothness conditions, such as those bounded by a higher-
order polynomial of the gradient norm.

#### Supplementary materials

Supplementary materials including proofs can be found at
https://arxiv.org/abs/2208.09900.

#### Acknowledgement

This work is founded by the Strategic Priority Research Program of the Chinese
Academy of Sciences under Grant No. XDB0680101, CAS Project for Young
Scientists in Basic Research under Grant No. YSBR-034, Innovation Project of
ICT CAS under Grants No. E261090, NSFC under Grant No. 12326608, Hetao
Shenzhen-Hong Kong Science and Technology Innovation Cooperation Zone Project
under Grant No.HZQSWS-KCCYB-2024016.

##  Appendix A Proof of Theorem 2

In this section, we prove Theorem 2. We consider the following function with
variable $\bm{w}=(x,y)\in\mathbb{R}^{2}$:
$f(\bm{w})=f((x,y))=f_{1}(x)+f_{2}(y)$, where

$f_{1}(x)=\left\\{\begin{aligned}
&\frac{L_{0}\exp^{L_{1}x-1}}{L_{1}^{2}}&,x\in[\frac{1}{L_{1}},\infty),\\\
&\frac{L_{0}x^{2}}{2}+\frac{L_{0}}{2L_{1}^{2}}&,x\in[-\frac{1}{L_{1}},\frac{1}{L_{1}}],\\\
&\frac{L_{0}\exp^{-L_{1}x-1}}{L_{1}^{2}}&,x\in(-\infty,-\frac{1}{L_{1}}].\end{aligned}\right.$
(8) $f_{2}(y)=\left\\{\begin{aligned}
&\varepsilon(y-1)+\frac{\varepsilon}{2}&,y\in[1,\infty),\\\
&\frac{\varepsilon}{2}y^{2}&,y\in[-1,1],\\\
&-\varepsilon(y+1)+\frac{\varepsilon}{2}&,y\in(-\infty,-1].\end{aligned}\right.$
(9)

The construction of both functions equation 8 and equation 9 are motivated by
zhang2019gradient. One improvement here is that we introduce a single function
with variable $\bm{w}\in\mathbb{R}^{2}$
$f(\bm{w})=f((x,y))=f_{1}(x)+f_{2}(y)$, which helps us to derive a stronger
conclusion, i.e., the constructed $f$ is independent of $\eta_{1}$. It is easy
to see that this $f(\bm{w})$ satisfies $(L_{0},L_{1})$ condition with
$L_{0}=L_{0}$ and $L_{1}=L_{1}$. We now restate Theorem 2 as follows with
constants specified.

######  Theorem 3 (Theorem 2, restated).

Consider function $f(\bm{w})=f((x,y))=f_{1}(x)+f_{2}(y)$ with $f_{1}(x)$ and
$f_{2}(y)$ defined in equation 8 and equation 9. Consider gradient descent
with diminishing learning rates: $\bm{w}_{k+1}=\bm{w}_{k}-\eta_{k}\nabla
f(\bm{w}_{k})$, where $\eta_{k}=\frac{\eta_{1}}{\sqrt{k}}$. Then for any
$T,M,\bar{f}>0$, denote
$\varepsilon=\sqrt{\frac{\frac{L_{1}M}{2}+\frac{L_{0}}{4}}{2(1+\sqrt{2})(\log(\frac{L_{1}M}{2L_{0}}+\frac{1}{4})+1)}\frac{\bar{f}}{4\sqrt{T}}}$.
As long as $M>\\{\frac{2(e^{\frac{\log
2}{\sqrt{2}-1}-1}-\frac{1}{4})L_{0}}{L_{1}},\varepsilon\\}$ and
$\frac{\bar{f}}{\varepsilon}>6$, there exists an initialization
$\bm{w}_{0}=(x_{0},y_{0})$ such that, $M=\sup\\{\|\nabla
f(\bm{w})\|:\bm{w}\text{ such that }f(\bm{w})\leq f(\bm{w}_{0})\\}$ and
$f(\bm{w}_{0})-f(\bm{w})=\bar{f}$, and for any $\eta_{1}>0$, $\|\nabla
f(\bm{w}_{k})\|\geq\epsilon$ whenever $k<T$.

One can immediately see from the above theorem that
$\varepsilon^{2}=\tilde{\Theta}(\frac{M(f(\bm{w}_{0})-f^{*})}{\sqrt{T}})$,
which gives Theorem 2. Before giving the proof of Theorem 3, we briefly
discuss the difference between ours and (zhang2019gradient, Theorem 4).
Generally speaking, our result is stronger than (zhang2019gradient, Theorem
4). This is because we pick the function before the learning rate: we prove
that there exists a function $f$ and an initialization, such that with any
learning rate GD takes a long time to reach the stationary point, while
(zhang2019gradient, Theorem 4) picks the learning rate before the function:
they prove that with any learning rate, there exists a function $f$ and an
initialization, such that GD takes a long time to reach the stationary point.

We next present the proof of Theorem 3 in Part I and Part II as follows. For
simplicity, we let $\|\cdot\|$ to be the $\ell_{\infty}$ norm, and the proof
can be easily extended to other norms given the equivalence between norms in
$\mathbb{R}^{2}$. We pick
$x_{0}=\frac{\log(\frac{L_{1}M}{2L_{0}}+\frac{1}{4})+1}{L_{1}}$ and
$y_{0}=\frac{f_{1}(x_{0})-\frac{L_{0}}{2L_{1}^{2}}}{\varepsilon}-\frac{1}{2}$.
We have $f_{1}(x_{0})-\min_{x}f_{1}(x)=f_{2}(y_{0})-\min_{y}f_{2}(y)$, and
thus
$f((x_{0},y_{0}))-\min_{x,y}f((x,y))=2\left(f_{1}(x_{0})-\min_{x}f_{1}(x)\right)$.
As $M>\varepsilon$, $\sup\\{\|\nabla f(\bm{w})\|:\bm{w}\text{ such that
}f(\bm{w})\leq f(\bm{w}_{0})\\}$ is achieved at $(x_{0}^{\prime},0)$ where
$x_{0}^{\prime}$ satisfies
$f_{1}(x_{0}^{\prime})-\min_{x}f_{1}(x)=2\left(f_{1}(x_{0})-\min_{x}f_{1}(x)\right)$.
By simple calculation, we have $\sup\\{\|\nabla f(\bm{w})\|:\bm{w}\text{ such
that }f(\bm{w})\leq f(\bm{w}_{0})\\}=M$.

In the proof, we use $x_{k}$ to denote the value of $x$ (i.e., the first
component of $\bm{w}\in\mathbb{R}$) in the $k$-th iteration of gradient
descent. Similarly for $y_{k}$.

#### Part I: Large $\eta_{1}$ can cause divergence.

In this part, we prove that: when using the large initial learning rate
$\eta_{1}\geq\frac{L_{1}(1+\sqrt{2})|x_{0}|}{L_{0}\exp^{L_{1}|x_{0}|-1}}$,
decay-learning-rate gradient descent will never reach stationary points.

We prove this claim by induction. When $k=1$, we claim the following two
statements are true:

(1-I): $|x_{1}|\geq\sqrt{2}|x_{0}|$.

(1-II):
$\eta_{2}=\frac{\eta_{1}}{\sqrt{2}}\geq\frac{L_{1}(1+\sqrt{2})|x_{1}|}{L_{0}\exp^{L_{1}|x_{1}|-1}}$.

We first prove (1-I): without loss of generality, we assume $x_{1}>0$. By the
update rule of gradient descent, we have

$\displaystyle x_{1}$ $\displaystyle=$ $\displaystyle
x_{0}-\eta_{1}\frac{\partial f(x_{0})}{\partial x}$
$\displaystyle\overset{equation~{}\ref{lowerbound_f1}}{=}$ $\displaystyle
x_{0}-\eta_{1}\frac{L_{0}\exp^{L_{1}x_{0}-1}}{L_{1}}$ $\displaystyle\leq$
$\displaystyle
x_{0}-\frac{L_{1}(1+\sqrt{2})|x_{0}|}{L_{0}\exp^{L_{1}|x_{0}|-1}}\frac{L_{0}\exp^{L_{1}x_{0}-1}}{L_{1}}=-\sqrt{2}x_{0}.$

So $|x_{1}|\geq\sqrt{2}|x_{0}|$ and (1-1) is proved. We now prove (1-II).
Before that, we introduce the following lemma.

######  Lemma 2.

Consider any $x,y\in\\{z:|z|\geq\frac{\log
2}{(\sqrt{2}-1)L_{1}},z\in\mathbb{R}\\}$. When $|y|>\sqrt{2}|x|$, then we have
$\frac{|y|}{\exp^{L_{1}|y|}}\leq\frac{1}{\sqrt{2}}\frac{|x|}{\exp^{L_{1}|x|}}$.

###### Proof.

Let $g(z)=\frac{z}{\exp^{L_{1}z}}$. It is easy to see that $\nabla g(z)<0$
when $z>0$. Therefore, when $z_{1}\geq\sqrt{2}z_{2}$, we have $g(z_{1})\leq
g(\sqrt{2}z_{2})$. When $z_{2}\geq\frac{\log 2}{(\sqrt{2}-1)L_{1}}$, we have

$\displaystyle z_{2}\geq\frac{\log 2}{(\sqrt{2}-1)L_{1}}$
$\displaystyle\Leftrightarrow$ $\displaystyle\sqrt{2}L_{1}z_{2}>\log
2+L_{1}z_{2}$ $\displaystyle\Leftrightarrow$
$\displaystyle\exp^{\sqrt{2}L_{1}z_{2}}\geq 2\exp^{L_{1}z_{2}}$
$\displaystyle\Leftrightarrow$
$\displaystyle\frac{1}{\exp^{\sqrt{2}L_{1}z_{2}}}\geq\frac{1}{2\exp^{L_{1}z_{2}}}$
$\displaystyle\Leftrightarrow$
$\displaystyle\frac{\sqrt{2}z_{2}}{\exp^{\sqrt{2}L_{1}z_{2}}}\geq\frac{z_{2}}{\sqrt{2}\exp^{L_{1}z_{2}}}.$

Therefore, we have
$\frac{z_{1}}{\exp^{z_{1}L_{1}}}\leq\frac{\sqrt{2}z_{2}}{\exp^{\sqrt{2}L_{1}z_{2}}}\geq\frac{z_{2}}{\sqrt{2}\exp^{L_{1}z_{2}}}.$
Proof of Lemma 2 is completed.

∎

Now we prove (1-II):

$\displaystyle\eta_{2}=\frac{\eta_{1}}{\sqrt{2}}$ $\displaystyle\geq$
$\displaystyle\frac{L_{1}(1+\sqrt{2})|x_{0}|}{L_{0}\exp^{L_{1}|x_{0}|-1}}\frac{1}{\sqrt{2}}$
$\displaystyle\overset{\text{(1-I) and Lemma
\ref{lemma_lower_bound_decay_lr}}}{\geq}$
$\displaystyle\frac{L_{1}(1+\sqrt{2})|x_{1}|}{L_{0}\exp^{L_{1}|x_{1}|-1}}\sqrt{2}\frac{1}{\sqrt{2}}$
$\displaystyle=$
$\displaystyle\frac{L_{1}(1+\sqrt{2})|x_{1}|}{L_{0}\exp^{L_{1}|x_{1}|-1}}$

So (1-II) is proved. Now we suppose the following two claims hold for $k=2m$
where $m\in\mathbb{N}^{+}$.

(2m-I): $|x_{2m+1}|\geq\sqrt{2}|x_{2m}|$.

(2m-II):
$\eta_{2m+2}=\frac{\eta_{1}}{\sqrt{2m+2}}\geq\frac{L_{1}(1+\sqrt{2})|x_{2m+1}|}{L_{0}\exp^{L_{1}|x_{2m+1}|-1}}$

Then for $k=2m+1$, we prove the following claims hold for $k=2m+1$.

((2m+1)-I): $|x_{2m+2}|\geq\sqrt{2}|x_{2m+1}|$.

((2m+1)-II):
$\eta_{2m+3}=\frac{\eta_{1}}{\sqrt{2m+3}}\geq\frac{L_{1}(1+\sqrt{2})|x_{2m+2}|}{L_{0}\exp^{L_{1}|x_{2m+2}|-1}}$.

We first prove ((2m+1)-I):

$\displaystyle x_{2m+2}$ $\displaystyle=$ $\displaystyle
x_{2m+1}-\eta_{2m+2}\frac{\partial f(x_{2m+1})}{\partial x}$
$\displaystyle\overset{equation~{}\ref{lowerbound_f1}}{=}$ $\displaystyle
x_{2m+1}-\eta_{2m+2}\frac{L_{0}}{L_{1}}\exp^{L_{1}x_{2m+1}-1}$
$\displaystyle\overset{\text{(2m-II)}}{\leq}$ $\displaystyle
x_{2m+1}-\frac{L_{1}(1+\sqrt{2})|x_{2m+1}|}{L_{0}\exp^{L_{1}|x_{2m+1}|-1}}\frac{L_{0}\exp^{L_{1}x_{2m+1}-1}}{L_{1}}$
$\displaystyle\leq$ $\displaystyle-\sqrt{2}x_{2m+1}.$

So $|x_{2m+2}|\geq\sqrt{2}|x_{2m+1}|$ and ((2m+1)-I) is proved. We now prove
((2m+1)-II).

$\displaystyle\eta_{2m+3}$ $\displaystyle=$
$\displaystyle\eta_{2m+2}\sqrt{\frac{2m+2}{2m+3}}$
$\displaystyle\overset{\text{(2m-II)}}{\geq}$
$\displaystyle\frac{L_{1}(1+\sqrt{2})|x_{2m+1}|}{L_{0}\exp^{L_{1}|x_{2m+1}|-1}}\sqrt{\frac{2m+2}{2m+3}}$
$\displaystyle\overset{\text{(2m-I) and Lemma
\ref{lemma_lower_bound_decay_lr}}}{\geq}$
$\displaystyle\frac{L_{1}(1+\sqrt{2})|x_{2m+2}|}{L_{0}\exp^{L_{1}|x_{2m+2}|-1}}\sqrt{2}\sqrt{\frac{2m+2}{2m+3}}$
$\displaystyle\geq$
$\displaystyle\frac{L_{1}(1+\sqrt{2})|x_{2m+2}|}{L_{0}\exp^{L_{1}|x_{2m+2}|-1}}.$

So ((2m+1)-II) is proved. We can derive a similar claim when $k$ is odd. By
the principle of induction, we know that $|x_{k+1}|\geq\sqrt{2}|x_{k}|$ for
any $k\geq 1$. Since $f_{1}(x)$ grows exponentially, gradient descent in Part
I will never reach stationary points.

#### Part II: Small $\eta_{1}$ can cause slow convergence.

In this part, we prove that: when using initialization $\bm{w}\in\Omega$,
decay-learning-rate gradient descent with small initial learning rate
$\eta_{1}<\frac{L_{1}(1+\sqrt{2})|x_{0}|}{L_{0}\exp^{L_{1}|x_{0}|-1}}=\frac{(1+\sqrt{2})(\log(\frac{L_{1}M}{2L_{0}}+\frac{1}{4})+1)}{\frac{L_{1}M}{2}+\frac{L_{0}}{4}}$
will cause slow convergence. For any $k\geq 1$, we have

$\displaystyle y_{k}-y_{k+1}$ $\displaystyle=$
$\displaystyle\eta_{k}\frac{\partial f(\bm{w}_{k})}{\partial y}$
$\displaystyle\overset{equation~{}\ref{lowerbound_f2}}{=}$
$\displaystyle\varepsilon\frac{\eta_{1}}{\sqrt{k}}$ $\displaystyle<$
$\displaystyle\varepsilon\frac{L_{1}(1+\sqrt{2})|x_{0}|}{L_{0}\exp^{L_{1}|x_{0}|-1}}\frac{1}{\sqrt{k}}$

Therefore, we have

$\displaystyle\sum_{k=1}^{K}(y_{k+1}-y_{k})=\sum_{k=1}^{K}\varepsilon\frac{\eta_{1}}{\sqrt{k}}<2\sqrt{k}\varepsilon\eta_{1}<2\sqrt{k}\varepsilon\frac{L_{1}(1+\sqrt{2})|x_{0}|}{L_{0}\exp^{L_{1}|x_{0}|-1}}$

When using initialization $y_{0}$, it is easy to have the following
conclusion: when
$2\frac{(1+\sqrt{2})(\log(\frac{L_{1}M}{2L_{0}}+\frac{1}{4})+1)}{\frac{L_{1}M}{2}+\frac{L_{0}}{4}}\sqrt{k}=2\varepsilon\sqrt{k}\frac{L_{1}(1+\sqrt{2})|x_{1}|}{L_{0}\exp^{L_{1}|x_{1}|-1}}<y_{0}-1=\frac{\left(f_{1}(x_{0})-\min_{x}f_{1}(x)\right)}{\varepsilon}-\frac{3}{2}$,
we have $\frac{\partial f(\bm{w}_{k})}{\partial y}=\varepsilon$. In other
words, we have: $\|\nabla f(\bm{w}_{k})\|\geq\varepsilon$ for all
$k<(\frac{\frac{L_{1}M}{2}+\frac{L_{0}}{4}}{2(1+\sqrt{2})(\log(\frac{L_{1}M}{2L_{0}}+\frac{1}{4})+1)})^{2}\frac{(\frac{f_{2}(y_{0})-\min_{y}f_{2}(y)}{\varepsilon}-\frac{3}{2})^{2}}{\varepsilon^{2}}$.
Recall that
$f(\bm{w}_{1})-\min_{\bm{w}}f(\bm{w})=2(f_{2}(y_{0})-\min_{x}f_{2}(x))$ and
$(\frac{\frac{L_{1}M}{2}+\frac{L_{0}}{4}}{2(1+\sqrt{2})(\log(\frac{L_{1}M}{2L_{0}}+\frac{1}{4})+1)})^{2}\frac{(\frac{f_{2}(y_{0})-\min_{y}f_{2}(y)}{\varepsilon}-\frac{3}{2})^{2}}{\varepsilon^{2}}<T$
by the definition of $\varepsilon$, the proof is completed.

##  Appendix B Proof of Theorem 1

This appendix provides the formal proof of Theorem 1, which is organized as
follows. In Section B.1, we first introduce notations that are used in the
proof. In Section B.2, We restate Theorem 1 with constants specified. In
Section B.3, we then make preparations by proving auxiliary lemmas. Finally,
in Section B.4, we prove Theorem 1.

###  B.1 Notations

Here we provide a complete list of notations used in the appendix for a clear
reference.

  * •

We use $(k_{1},i_{1})\leq(<)(k_{2},i_{2})$ for $\forall
k_{1},k_{2}\in\mathbb{N}^{+}$ and $i_{1},i_{2}\in\\{0,\cdots,n-1\\}$, if
either $k_{1}<k_{2}$ or $k_{1}=k_{2}$ and $i_{1}\leq(<)i_{2}$

  * •

We define function $g(x):[0,1]\rightarrow\mathbb{R}^{/-}$ as

$\displaystyle
g(\beta_{2})\triangleq\max\left\\{\frac{1}{\sqrt{\beta_{2}^{n-1}}}-1,1-\frac{1}{\sqrt{\beta_{2}^{n-1}+8n\frac{1-\beta_{2}^{n-1}}{\beta_{2}^{n}}}},1-\sqrt{\beta_{2}},\sqrt{\frac{\beta_{2}}{\left(1-(1-\beta_{2})\frac{2n}{\beta_{2}^{n}}\right)}}-1\right\\}.$

  * •

We define constants $\\{C_{i}\\}_{i=1}^{10}$ as follows:

$\displaystyle C_{1}$
$\displaystyle\triangleq\frac{(1-\beta_{1})^{2}}{1-\beta_{2}}\frac{1}{1-\frac{\beta_{1}^{2}}{\beta_{2}}}+1,$
(10) $\displaystyle C_{2}$ $\displaystyle\triangleq
nC_{1}+\frac{\beta_{1}}{1-\beta_{1}}C_{1}\left(1+\sqrt{2}\right),$
$\displaystyle C_{3}$ $\displaystyle\triangleq
C_{1}\left(n(L_{0}+L_{1}\sqrt{D_{0}})+2\sqrt{2}(L_{0}+L_{1}\sqrt{D_{0}})\frac{\sqrt{1-\beta_{2}}}{1-\sqrt{\beta_{2}}}\frac{\sqrt{\beta_{2}}}{1-\sqrt{\beta_{2}}}+8\sqrt{2n}L_{0}\frac{1}{1-\beta_{2}^{n}}\right),$
$\displaystyle C_{4}$ $\displaystyle\triangleq
4L_{1}C_{1}\sqrt{D_{1}}\frac{\sqrt{1-\beta_{2}}}{1-\sqrt{\beta_{2}}}$
$\displaystyle C_{5}$ $\displaystyle\triangleq
n^{2}(1+n\sqrt{d}C_{1}\eta_{1}L_{1}\sqrt{n}\sqrt{D_{1}})\left(C_{4}+\frac{dC_{4}\sqrt{D_{1}}}{1-\sqrt{\beta_{2}^{n}}}\right),$
$\displaystyle C_{6}$
$\displaystyle\triangleq\left(dC_{3}+\frac{C_{4}n\sqrt{D_{1}}}{1-\sqrt{\beta_{2}^{n}}}\right)\eta^{2}_{1},$
$\displaystyle C_{7}$ $\displaystyle\triangleq
3n\left(C_{4}+\frac{dC_{4}}{1-\sqrt{\beta_{2}^{n}}}\right)\left(nL_{0}+L_{1}\sqrt{n}\sqrt{D_{0}}\right)n^{2}\sqrt{d}C_{1}\eta_{1}^{3}+\left(dC_{3}+\frac{C_{2}C_{4}n\sqrt{D_{1}}}{1-\sqrt{\beta_{2}^{n}}}\right)\eta^{2}_{1},$
$\displaystyle C_{8}$
$\displaystyle\triangleq\sqrt{\frac{2n^{2}}{\beta_{2}^{n}}}L_{1}\sqrt{D_{1}}n\sqrt{n}+dg(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{\sqrt{2}n}{\beta_{2}^{\frac{n}{2}}}L_{1}C_{1}\sqrt{D_{1}}\left(1+\frac{1}{1-\beta_{2}^{n}}\right)(n+n^{\frac{5}{2}}\sqrt{d}C_{1}\eta_{1}L_{1}\sqrt{D_{1}})+2\frac{\beta_{1}}{(1-\beta_{1})\eta_{1}}\sqrt{d}C_{1},$
$\displaystyle C_{9}$
$\displaystyle\triangleq\sqrt{\frac{2n^{2}}{\beta_{2}^{n}}}d(n^{2}L_{0}+n\sqrt{n}L_{1}\sqrt{D_{0}})C_{1}\eta_{1}^{2}+g(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{\sqrt{2}n}{\beta_{2}^{\frac{n}{2}}}\left(n+\frac{2\sqrt{2}\beta_{1}}{1-\beta_{1}}\right)C_{1}(L_{0}+L_{1}\sqrt{D_{0}})d\sqrt{d}\eta^{2}_{1},$
$\displaystyle C_{10}$ $\displaystyle\triangleq
3dg(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{\sqrt{2}n}{\beta_{2}^{\frac{n}{2}}}L_{1}C_{1}\sqrt{D_{1}}\left(1+\frac{1}{1-\beta_{2}^{n}}\right)n\left(nL_{0}+L_{1}\sqrt{n}\sqrt{D_{0}}\right)n\sqrt{d}C_{1}\eta_{1}^{3}+C_{9},$
$\displaystyle C_{11}$
$\displaystyle\triangleq(\frac{1}{2}+C_{2})C_{5}+C_{8}+\frac{3L_{1}\sqrt{n}\sqrt{D_{1}}C_{2}^{2}d}{2},$
$\displaystyle C_{12}$
$\displaystyle\triangleq(\frac{1}{2}+C_{2})C_{6}+C_{9}+\frac{nL_{0}+L_{1}\sqrt{n}\sqrt{D_{0}}}{2}3C_{2}^{2}d\eta_{1}^{2},$
$\displaystyle C_{13}$
$\displaystyle\triangleq(\frac{1}{2}+C_{2})C_{7}+C_{10}+\frac{nL_{0}+L_{1}\sqrt{n}\sqrt{D_{0}}}{2}3C_{2}^{2}d\eta_{1}^{2}.$

###  B.2 Restate Theorem 1

Here we restate Theorem 1 with constants specified.

######  Theorem 4 (Theorem 1, restated).

Consider Adam defined as Alg. (1) with diminishing learning rate
$\eta_{k}\equiv\frac{\eta_{1}}{\sqrt{k}}$. Let Assumptions 1 and 2 hold.
Suppose the hyperparamters satisfy: $\gamma<\beta_{2}<1$ and
$0\leq\beta_{1}^{2}<\beta_{2}$, where $\gamma$ is defined as the solution of
$\sqrt{d}g(x)\frac{n}{x^{\frac{n}{2}}}=\frac{1}{2(4+\sqrt{2})\sqrt{D_{1}}\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)}$
with respect to $x$. Then, either

$\min_{k\in[1,T]}\|\nabla f(\bm{w}_{k,0})\|\leq
2\sqrt{d}(2\sqrt{2}+1)\sqrt{D_{0}}g(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\sqrt{\frac{2n}{\beta_{2}^{n}}},$

or

$\displaystyle\min_{k\in[1,T]}\left\\{\frac{\|\nabla
f(\bm{w}_{k,0})\|}{\sqrt{D_{1}}},\frac{\|\nabla
f(\bm{w}_{k,0})\|^{2}}{\sqrt{D_{0}}+\xi}\right\\}\leq(4(2\sqrt{2}+1))\frac{f(\bm{w}_{1,0})-\min_{\bm{w}}f(\bm{w})}{\eta_{1}\sqrt{T}}$
$\displaystyle~{}~{}~{}+4(2\sqrt{2}+1)\left(C_{12}+\frac{\sqrt{D_{0}}+\xi}{4\sqrt{D_{1}}}C_{11}\eta_{1}^{2}\right)\frac{\ln
T}{\eta_{1}\sqrt{T}}+4(2\sqrt{2}+1)\frac{C_{13}+\frac{\sqrt{D_{0}}+\xi}{4\sqrt{D_{1}}}C_{11}}{\eta_{1}\sqrt{T}}.$

###  B.3 Auxiliary Lemmas

In this section, we introduce auxiliary lemmas that will be latter used. In
the remaining proof of this paper, we assume without the loss of generality
that $\eta_{1}$ is small enough, such that the following requirements are
fulfilled: ($C_{1}$ and $C_{2}$ are defined in Eq. (10)).

  * •

$2C_{2}\sqrt{d}\eta_{1}\leq\frac{1}{L_{1}}$. This will latter ensure that we
can directly apply the definition of $(L_{0},L_{1})$-smooth condition
(Assumption 1) to parameter sequence $\\{\bm{w}_{k,i}\\}_{k,i}$;

  * •

$\frac{1}{4(2\sqrt{2}+1)}\geq\sqrt{D_{1}}C_{11}\eta_{1}$. This will latter
ensure the second-order term is smaller than the first-order term at the end
of the proof.

The proof can be easily extended to general cases by selecting large enough
$K$ and using the epoch $K$ as a new start point and derive the results after
epoch $K$, because the epochs before epoch $K$ can be uniformly bounded due to
$\eta_{k}$ decaying and $K$ finite, and we then derive the desired result for
all epochs.

Without the loss of generality, we also take the following initialization:
$\bm{w}_{1,0}=\bm{w}_{0}$, $\bm{m}_{1,-1}=\nabla f_{\tau_{1,-1}}(\bm{w}_{0})$
where $\tau_{1,-1}$ can be any integer in $[0,n-1]$, and
$\bm{\nu}_{l,1,-1}=\max_{j}\\{\partial_{l}f_{j}(\bm{w}_{0})^{2}\\}~{}\forall
l$ where the maximum is taken component-wisely. We take the initialization to
have a more concise proof, while the proof can be easily extended to all the
initialization as the information of the initialization in the exponentially
decayed average of Adam (both in $\bm{m}_{k,i}$ and $\bm{\nu}_{k,i}$) decays
rapidly with $k$ increasing.

The following lemma shows that $f$ is also $(L_{0},L_{1})$-smooth under
Assumptions 1 and 2 (while the $L_{0}$ and $L_{1}$ are different from those of
$f_{i}$).

######  Lemma 3.

With Assumptions 1 and 2, $f$ satisfies
$(nL_{0}+L_{1}\sqrt{n}\sqrt{D_{0}},L_{1}\sqrt{n}\sqrt{D_{1}})$-smooth
condition.

###### Proof.

$\forall\bm{w}_{1},\bm{w}_{2}\in\mathbb{R}^{d}$ satisfying
$\|\bm{w}_{1}-\bm{w}_{2}\|\leq\frac{1}{L_{1}}$,

$\displaystyle\|\nabla f(\bm{w}_{1})-\nabla
f(\bm{w}_{2})\|\leq\sum_{i=0}^{n-1}\|\nabla f_{i}(\bm{w}_{1})-\nabla
f_{i}(\bm{w}_{2})\|\leq\sum_{i=0}^{n-1}(L_{0}+L_{1}\|\nabla
f_{i}(\bm{w}_{1})\|)\|\bm{w}_{1}-\bm{w}_{2}\|$ $\displaystyle\leq$
$\displaystyle\left(nL_{0}+L_{1}\sqrt{n}\sqrt{\sum_{i=0}^{n-1}\|\nabla
f_{i}(\bm{w}_{1})\|^{2}}\right)\|\bm{w}_{1}-\bm{w}_{2}\|\leq(nL_{0}+L_{1}\sqrt{n}\sqrt{D_{0}+D_{1}\|\nabla
f(\bm{w}_{1})\|^{2}})\|\bm{w}_{1}-\bm{w}_{2}\|$ $\displaystyle\leq$
$\displaystyle(nL_{0}+L_{1}\sqrt{n}(\sqrt{D_{0}}+\sqrt{D_{1}}\|\nabla
f(\bm{w}_{1})\|))\|\bm{w}_{1}-\bm{w}_{2}\|\leq(nL_{0}+L_{1}\sqrt{n}\sqrt{D_{0}}+L_{1}\sqrt{n}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{1})\|)\|\bm{w}_{1}-\bm{w}_{2}\|.$

The proof is completed. ∎

The following lemma bounds the update norm of Adam.

######  Lemma 4 (Bounded Update).

If $\beta_{1}<\sqrt{\beta_{2}}$, we have $\forall k\in\mathbb{N}^{+}$,
$i\in\\{0,\cdots,n-1\\}$,

$\frac{|\bm{m}_{l,k,i}|}{\sqrt{\bm{\nu}_{l,k,i}}+\xi}\leq C_{1},$

where $C_{1}$ is defined in Eq. (10).

Furthermore, we have $|\bm{w}_{l,k,i+1}-\bm{w}_{l,k,i}|\leq C_{1}\eta_{k}$,
and thus $\|\bm{w}_{k,i+1}-\bm{w}_{k,i}\|\leq C_{1}\eta_{k}\sqrt{d}$.

###### Proof.

By the definition of $\bm{m}_{k,i}$, we have

$\displaystyle(\bm{m}_{l,k,i})^{2}$ $\displaystyle=$
$\displaystyle\left((1-\beta_{1})\sum_{j=0}^{i}\beta_{1}^{(k-1)n+i-((k-1)n+j)}\partial_{l}f_{\tau_{k,j}}(\bm{w}_{k,j})\right.$
$\displaystyle+\left.(1-\beta_{1})\sum_{m=1}^{k-1}\sum_{j=0}^{n-1}\beta_{1}^{(k-1)n+i-((m-1)n+j)}\partial_{l}f_{\tau_{m,j}}(\bm{w}_{m,j})+\beta_{1}^{(k-1)n+i+1}\partial_{l}f_{\tau_{1,-1}}(\bm{w}_{1,0})\right)^{2}$
$\displaystyle\leq$
$\displaystyle\left((1-\beta_{1})\sum_{j=0}^{i}\beta_{1}^{(k-1)n+i-((k-1)n+j)}|\partial_{l}f_{\tau_{k,j}}(\bm{w}_{k,j})|\right.$
$\displaystyle+\left.(1-\beta_{1})\sum_{m=1}^{k-1}\sum_{j=0}^{n-1}\beta_{1}^{(k-1)n+i-((m-1)n+j)}|\partial_{l}f_{\tau_{m,j}}(\bm{w}_{m,j})|+\beta_{1}^{(k-1)n+i+1}\max_{s\in[n]}|\partial_{l}f_{s}(\bm{w}_{1,0})|\right)^{2}$
$\displaystyle\overset{(\star)}{\leq}$
$\displaystyle\left((1-\beta_{2})\sum_{j=0}^{i}\beta_{2}^{(k-1)n+i-((k-1)n+j)}|\partial_{l}f_{\tau_{k,j}}(\bm{w}_{k,j})|^{2}\right.$
$\displaystyle+\left.(1-\beta_{2})\sum_{m=1}^{k-1}\sum_{j=0}^{n-1}\beta_{2}^{(k-1)n+i-((m-1)n+j)}|\partial_{l}f_{\tau_{m,j}}(\bm{w}_{m,j})|^{2}+\beta_{2}^{(k-1)n+i+1}\max_{s\in[n]}|\partial_{l}f_{s}(\bm{w}_{1,0})|^{2}\right)$
$\displaystyle\cdot\left(\frac{(1-\beta_{1})^{2}}{1-\beta_{2}}\sum_{j=0}^{(k-1)n+i}\left(\frac{\beta_{1}^{2}}{\beta_{2}}\right)^{j}+\left(\frac{\beta_{1}^{2}}{\beta_{2}}\right)^{(k-1)n+i+1}\right)$
$\displaystyle\overset{(\ast)}{=}$
$\displaystyle\left(\frac{(1-\beta_{1})^{2}}{1-\beta_{2}}\sum_{j=0}^{(k-1)n+i}\left(\frac{\beta_{1}^{2}}{\beta_{2}}\right)^{j}+\left(\frac{\beta_{1}^{2}}{\beta_{2}}\right)^{(k-1)n+i+1}\right)\bm{\nu}_{l,k,i}$
$\displaystyle\leq$
$\displaystyle\left(\frac{(1-\beta_{1})^{2}}{1-\beta_{2}}\frac{1}{1-\frac{\beta_{1}^{2}}{\beta_{2}}}+1\right)\bm{\nu}_{l,k,i}=C_{1}\bm{\nu}_{l,k,i},$

where Eq. ($\star$) is due to the Cauchy-Schwartz’s Inequality, and  Eq.
($\ast$) is due to the definition of $\bm{\nu}_{l,1,-1}$. We complete the
proof of the first claim. The second claim then follows directly from the
update rule

$\bm{w}_{l,k,i+1}-\bm{w}_{l,k,i}=\eta_{k}\frac{\bm{m}_{l,k,i}}{\sqrt{\bm{\nu}_{l,k,i}}+\xi}.$

The proof is completed. ∎

Define
$\bm{u}_{k}\triangleq\frac{\bm{w}_{k,0}-\beta_{1}\bm{w}_{k,-1}}{1-\beta_{1}}$
(with $\bm{w}_{1,-1}\triangleq\bm{w}_{1,0}$), and let $\bm{u}_{l,k}$ be the
$i$-th component of $\bm{u}_{k}$, $\forall k\in\mathbb{N}^{+}$, $l\in[d]$. The
following lemma bounds the distance between $\bm{u}_{l,k}$ and
$\bm{w}_{l,k,0}$ and the distance between $\bm{u}_{l,k+1}$ and $\bm{u}_{l,k}$.

######  Lemma 5.

$\forall k\geq 1$,

$\displaystyle|\bm{u}_{l,k}-\bm{w}_{l,k,0}|\leq C_{2}\eta_{k},$ (11)
$\displaystyle|\bm{u}_{l,k+1}-\bm{u}_{l,k}|\leq C_{2}\eta_{k},$ (12)

where $C_{2}$ is defined in Eq. (10).

###### Proof.

By Lemma 4, we immediately have $\forall l\in[d]$,
$|\bm{u}_{l,k}-\bm{w}_{l,k,0}|$ is bounded as

$\displaystyle|\bm{u}_{l,k}-\bm{w}_{l,k,0}|=\left|\frac{\bm{w}_{l,k,0}-\beta_{1}\bm{w}_{l,k,-1}}{1-\beta_{1}}-\bm{w}_{l,k,0}\right|$
$\displaystyle=$
$\displaystyle\frac{\beta_{1}}{1-\beta_{1}}\left|\bm{w}_{l,k,0}-\bm{w}_{l,k,-1}\right|\leq\frac{\beta_{1}}{1-\beta_{1}}C_{1}\eta_{1}\frac{1}{\sqrt{k-1}}\leq\frac{\sqrt{2}\beta_{1}}{1-\beta_{1}}C_{1}\eta_{1}\frac{1}{\sqrt{k}}\leq\frac{\sqrt{2}\beta_{1}}{1-\beta_{1}}C_{1}\eta_{k}\leq
C_{2}\eta_{k},$

and

$\displaystyle|\bm{u}_{l,k+1}-\bm{u}_{l,k}|$ $\displaystyle=$
$\displaystyle\left|\frac{\bm{w}_{l,k+1,0}-\beta_{1}\bm{w}_{l,k+1,-1}}{1-\beta_{1}}-\frac{\bm{w}_{l,k,0}-\beta_{1}\bm{w}_{l,k,-1}}{1-\beta_{1}}\right|$
$\displaystyle=$
$\displaystyle\left|\left(\bm{w}_{l,k+1,0}-\bm{w}_{l,k,0}\right)+\frac{\beta_{1}}{1-\beta_{1}}\left(\bm{w}_{l,k+1,0}-\bm{w}_{l,k+1,-1}\right)-\frac{\beta_{1}}{1-\beta_{1}}\left(\bm{w}_{l,k,0}-\bm{w}_{l,k,-1}\right)\right|$
$\displaystyle\leq$
$\displaystyle\left|\left(\bm{w}_{l,k+1,0}-\bm{w}_{l,k,0}\right)+\frac{\beta_{1}}{1-\beta_{1}}\left(\bm{w}_{l,k+1,0}-\bm{w}_{l,k+1,-1}\right)-\frac{\beta_{1}}{1-\beta_{1}}\left(\bm{w}_{l,k,0}-\bm{w}_{l,k,-1}\right)\right|$
$\displaystyle\leq$ $\displaystyle
nC_{1}\eta_{1}\frac{1}{\sqrt{k}}+\frac{\beta_{1}}{1-\beta_{1}}C_{1}\eta_{1}\left(\frac{1}{\sqrt{k}}+\frac{\sqrt{2}}{\sqrt{k}}\right)=C_{2}\eta_{1}\frac{1}{\sqrt{k}}=C_{2}\eta_{k}.$

∎

In the following lemma, we bound the change of the gradient within one epoch.

######  Lemma 6.

$\forall k\in\mathbb{N}^{+},i\in\\{0,\cdots,n-1\\}$,

$\|\nabla
f(\bm{w}_{k,i})\|\leq(1+n\sqrt{d}C_{1}\eta_{1}L_{1}\sqrt{n}\sqrt{D_{1}})\|\nabla
f(\bm{w}_{k,0})\|+\left(nL_{0}+L_{1}\sqrt{n}\sqrt{D_{0}}\right)n\sqrt{d}C_{1}\eta_{k},$

where $C_{1}$ is defined in Eq. (10).

###### Proof.

By Assumption 1 and Lemma 3, we have

$\displaystyle\|\nabla f(\bm{w}_{k,i})\|\leq$ $\displaystyle\|\nabla
f(\bm{w}_{k,0})\|+\left(nL_{0}+L_{1}\sqrt{n}\sqrt{D_{0}}+L_{1}\sqrt{n}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k,0})\|\right)\|\bm{w}_{k,i}-\bm{w}_{k,0}\|$ $\displaystyle\leq$
$\displaystyle\|\nabla
f(\bm{w}_{k,0})\|+\left(nL_{0}+L_{1}\sqrt{n}\sqrt{D_{0}}+L_{1}\sqrt{n}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k,0})\|\right)i\sqrt{d}C_{1}\eta_{k}$ $\displaystyle\leq$
$\displaystyle(1+n\sqrt{d}C_{1}\eta_{1}L_{1}\sqrt{n}\sqrt{D_{1}})\|\nabla
f(\bm{w}_{k,0})\|+\left(nL_{0}+L_{1}\sqrt{n}\sqrt{D_{0}}\right)n\sqrt{d}C_{1}\eta_{k}.$

The proof is completed. ∎

We further need a descent lemma assuming $(L_{0},L_{1})$-smooth condition
similar to the case assuming $L$ smoothness. Specifically, for a function $h$
satisfying $L$-smooth condition and two points $\bm{w}$ and $\bm{v}$, by
Taylor’s expansion, we have

$h(\bm{w})\leq h(\bm{v})+\langle\nabla
h(\bm{v}),\bm{w}-\bm{v}\rangle+\frac{L}{2}\|\bm{w}-\bm{v}\|^{2}.$

This is called ”Descent Lemma” by existing literature (sra2014slides), as it
guarantees that the loss decreases with proper parameter update. Paralleling
to the above inequality, we establish the following descent lemma under the
$(L_{0},L_{1})$-smooth condition.

######  Lemma 7.

Assume that function $h:\mathcal{X}\rightarrow\mathbb{R}$ satisfies the
$(L_{0},L_{1})$-smooth condition, i.e., $\forall\bm{w},\bm{v}\in\mathcal{X}$
satisfying $\|\bm{w}-\bm{v}\|\leq\frac{1}{L_{1}}$,

$\|\nabla h(\bm{w})-\nabla h(\bm{v})\|\leq(L_{0}+L_{1}\|\nabla
h(\bm{v})\|)\|\bm{w}-\bm{v}\|.$

Then, for any three points $\bm{u},\bm{w},\bm{v}\in\mathcal{X}$ satisfying
$\|\bm{w}-\bm{u}\|\leq\frac{1}{L_{1}}$ and
$\|\bm{v}-\bm{u}\|\leq\frac{1}{L_{1}}$, we have

$h(\bm{w})\leq h(\bm{v})+\langle\nabla
h(\bm{u}),\bm{w}-\bm{v}\rangle+\frac{1}{2}(L_{0}+L_{1}\|\nabla
h(\bm{u})\|)(\|\bm{v}-\bm{u}\|+\|\bm{w}-\bm{u}\|)\|\bm{w}-\bm{v}\|.$

###### Proof.

By the Fundamental Theorem of Calculus, we have

$\displaystyle h(\bm{w})=$ $\displaystyle h(\bm{v})+\int_{0}^{1}\langle\nabla
h(\bm{v}+a(\bm{w}-\bm{v})),\bm{w}-\bm{v}\rangle\mathrm{d}a$ $\displaystyle=$
$\displaystyle h(\bm{v})+\langle\nabla
h(\bm{u}),\bm{w}-\bm{v}\rangle+\int_{0}^{1}\langle\nabla
h(\bm{v}+a(\bm{w}-\bm{v}))-\nabla h(\bm{u}),\bm{w}-\bm{v}\rangle\mathrm{d}a$
$\displaystyle\leq$ $\displaystyle h(\bm{v})+\langle\nabla
h(\bm{u}),\bm{w}-\bm{v}\rangle+\int_{0}^{1}\|\nabla
h(\bm{v}+a(\bm{w}-\bm{v}))-\nabla h(\bm{u})\|\|\bm{w}-\bm{v}\|\mathrm{d}a$
$\displaystyle\overset{(\star)}{\leq}$ $\displaystyle h(\bm{v})+\langle\nabla
h(\bm{u}),\bm{w}-\bm{v}\rangle+\int_{0}^{1}(L_{0}+L_{1}\|\nabla
h(\bm{u})\|)\|\bm{v}+a(\bm{w}-\bm{v})-\bm{u}\|\|\bm{w}-\bm{v}\|\mathrm{d}a$
$\displaystyle\leq$ $\displaystyle h(\bm{v})+\langle\nabla
h(\bm{u}),\bm{w}-\bm{v}\rangle+\int_{0}^{1}(L_{0}+L_{1}\|\nabla
h(\bm{u})\|)((1-a)\|\bm{v}-\bm{u}\|+a\|\bm{w}-\bm{u}\|)\|\bm{w}-\bm{v}\|\mathrm{d}a$
$\displaystyle\leq$ $\displaystyle h(\bm{v})+\langle\nabla
h(\bm{u}),\bm{w}-\bm{v}\rangle+\frac{1}{2}(L_{0}+L_{1}\|\nabla
h(\bm{u})\|)(\|\bm{v}-\bm{u}\|+\|\bm{w}-\bm{u}\|)\|\bm{w}-\bm{v}\|,$

where Inequality $(\star)$ is due to

$\|\bm{v}+a(\bm{w}-\bm{v})-\bm{u}\|=\|(1-a)(\bm{v}-\bm{u})+a(\bm{w}-\bm{u})\|\leq(1-a)\|\bm{v}-\bm{u}\|+a\|\bm{w}-\bm{u}\|\leq\frac{1}{L_{1}}.$

Thus the definition of $(L_{0},L_{1})$-smooth condition can be applied and the
proof is completed. ∎

Based on Lemma 4, we bound the momentum using the gradient of the current step
plus some error terms.

######  Lemma 8 (Estimation of the norm of the momentum).

We have for all $l\in[d],k\in\mathbb{Z}^{+},i\in[n]$,

$\displaystyle|\bm{m}_{l,k,i}|\leq$
$\displaystyle\max_{i^{\prime}\in[n]}|\partial_{l}f_{i^{\prime}}(\bm{w}_{k,0})|+\left(n+\frac{2\sqrt{2}\beta_{1}}{1-\beta_{1}}\right)C_{1}(L_{0}+L_{1}\sqrt{D_{0}})\sqrt{d}\eta_{k}+L_{1}C_{1}\sqrt{D_{1}}\eta_{k}\sum_{j=0}^{i-1}\|\nabla
f(\bm{w}_{k,j})\|$
$\displaystyle+L_{1}C_{1}\sqrt{D_{1}}\sum_{t=1}^{k-1}\eta_{k-t}\sum_{j=0}^{n-1}\beta_{1}^{tn+i-j}\|\nabla
f(\bm{w}_{k-t,j})\|,$

where $C_{1}$ is defined in Eq. (10). Similarly,
$l\in[d],k\in\mathbb{Z}^{+}/\\{1\\}$,

$|\bm{m}_{l,k-1,n-1}|\leq\max_{i^{\prime}\in[n]}|\partial_{l}f_{i^{\prime}}(\bm{w}_{k,0})|+\sum_{t=1}^{k-1}\sum_{j=0}^{n-1}\beta_{1}^{tn-1-j}C_{1}\eta_{k-t}\sqrt{d}L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-t,j})\|+\frac{2\sqrt{2}(L_{0}+L_{1}\sqrt{D_{0}})C_{1}\sqrt{d}\eta_{k}}{1-\beta_{1}}.$

###### Proof.

To begin with, for any $t\in[k-1]$ and any $j\in[0,n-1]$, we have the
following estimation for $\partial_{l}f_{i}(\bm{w}_{k-t,j})$:

$\displaystyle|\partial_{l}f_{i}(\bm{w}_{k-t,j})|$ $\displaystyle\leq$
$\displaystyle|\partial_{l}f_{i}(\bm{w}_{k,0})|+\sum_{p=j}^{n-1}|\partial_{l}f_{i}(\bm{w}_{k-t,p})-\partial_{l}f_{i}(\bm{w}_{k-t,p+1})|+\sum_{r=1}^{t-1}\sum_{p=0}^{n-1}|\partial_{l}f_{i}(\bm{w}_{k-r,p})-\partial_{l}f_{i}(\bm{w}_{k-r,p+1})|$
$\displaystyle\overset{(\star)}{\leq}$
$\displaystyle|\partial_{l}f_{i}(\bm{w}_{k,0})|+\sum_{p=j}^{n-1}(L_{0}+L_{1}\|\nabla
f_{i}(\bm{w}_{k-t,p})\|)\|\bm{w}_{k-t,p}-\bm{w}_{k-t,p+1}\|$
$\displaystyle+\sum_{r=1}^{t-1}\sum_{p=0}^{n-1}(L_{0}+L_{1}\|\nabla
f_{i}(\bm{w}_{k-r,p})\|)\|\bm{w}_{k-r,p}-\bm{w}_{k-r,p+1}\|$
$\displaystyle\leq$
$\displaystyle|\partial_{l}f_{i}(\bm{w}_{k,0})|+\sum_{p=j}^{n-1}(L_{0}+L_{1}\|\nabla
f_{i}(\bm{w}_{k-t,p})\|)C_{1}\eta_{k-t}\sqrt{d}+\sum_{r=1}^{t-1}\sum_{p=0}^{n-1}(L_{0}+L_{1}\|\nabla
f_{i}(\bm{w}_{k-r,p})\|)C_{1}\eta_{k-r}\sqrt{d}$ $\displaystyle\leq$
$\displaystyle|\partial_{l}f_{i}(\bm{w}_{k,0})|+\sum_{p=j}^{n-1}\left(L_{0}+L_{1}\sqrt{\sum_{i^{\prime}\in[n]}\|\nabla
f_{i^{\prime}}(\bm{w}_{k-t,p})\|^{2}}\right)C_{1}\eta_{k-t}\sqrt{d}$
$\displaystyle+\sum_{r=1}^{t-1}\sum_{p=0}^{n-1}\left(L_{0}+L_{1}\sqrt{\sum_{i^{\prime}\in[n]}\|\nabla
f_{i^{\prime}}(\bm{w}_{k-r,p})\|^{2}}\right)C_{1}\eta_{k-r}\sqrt{d},$

where Inequality $(\star)$ is due to $(L_{0},L_{1})$-smooth condition. By
Assumption 2, the RHS of the above inequality can be bounded as

$\displaystyle|\partial_{l}f_{i}(\bm{w}_{k,0})|+\sum_{p=j}^{n-1}\left(L_{0}+L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-t,p})\|+L_{1}\sqrt{D_{0}}\right)C_{1}\eta_{k-t}\sqrt{d}$
$\displaystyle+\sum_{r=1}^{t-1}\sum_{p=0}^{n-1}\left(L_{0}+L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-r,p})\|+L_{1}\sqrt{D_{0}}\right)C_{1}\eta_{k-r}\sqrt{d}$
$\displaystyle\overset{(*)}{\leq}$
$\displaystyle|\partial_{l}f_{i}(\bm{w}_{k,0})|+\sum_{p=j}^{n-1}L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-t,p})C_{1}\eta_{k-t}\sqrt{d}+\sum_{r=1}^{t-1}\sum_{p=0}^{n-1}L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-r,p})\|C_{1}\eta_{k-r}\sqrt{d}$
$\displaystyle+2(L_{0}+L_{1}\sqrt{D_{0}})C_{1}\sqrt{d}\eta_{k-1}(tn-j)$
$\displaystyle\leq$
$\displaystyle|\partial_{l}f_{i}(\bm{w}_{k,0})|+\sum_{p=j}^{n-1}L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-t,p})C_{1}\eta_{k-t}\sqrt{d}+\sum_{r=1}^{t-1}\sum_{p=0}^{n-1}L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-r,p})\|C_{1}\eta_{k-r}\sqrt{d}$
$\displaystyle+2\sqrt{2}(L_{0}+L_{1}\sqrt{D_{0}})C_{1}\sqrt{d}\eta_{k}(tn-j).$

where Inequality $(*)$ is due to $\forall a,b\in\mathbb{N}^{+},a>b$,
$\sum_{i=0}^{b}\frac{1}{\sqrt{a-i}}\leq 2\frac{b+1}{a}$. Similarly, we have
that for any $j\in[0,n-1]$,

$\displaystyle|\partial_{l}f_{i}(\bm{w}_{k,j})|\leq|\partial_{l}f_{i}(\bm{w}_{k,0})|+\sum_{p=0}^{j-1}|\partial_{l}f_{i}(\bm{w}_{k,p+1})-\partial_{l}f_{i}(\bm{w}_{k,p})|$
$\displaystyle\leq$
$\displaystyle|\partial_{l}f_{i}(\bm{w}_{k,0})|+\sum_{p=0}^{j-1}\left(L_{0}+L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k,p})\|+L_{1}\sqrt{D_{0}}\right)C_{1}\eta_{k}\sqrt{d}$
$\displaystyle=$
$\displaystyle|\partial_{l}f_{i}(\bm{w}_{k,0})|+\sum_{p=0}^{j-1}L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k,p})\|C_{1}\eta_{k}\sqrt{d}+j(L_{0}+L_{1}\sqrt{D}_{0})C_{1}\sqrt{d}\eta_{k}.$

Therefore, the norm of $\bm{m}_{l,k,i}$ can be bounded as

$\displaystyle|\bm{m}_{l,k,i}|$ $\displaystyle\leq$
$\displaystyle(1-\beta_{1})\sum_{j=0}^{i}\beta_{1}^{(k-1)n+i-((k-1)n+j)}|\partial_{l}f_{\tau_{k,j}}(\bm{w}_{k,j})|+(1-\beta_{1})\sum_{t=1}^{k-1}\sum_{j=0}^{n-1}\beta_{1}^{tn+i-j}|\partial_{l}f_{\tau_{k-t,j}}(\bm{w}_{k-t,j})|$
$\displaystyle+\beta_{1}^{(k-1)n+i+1}|\partial_{l}f_{\tau_{1,0}}(\bm{w}_{1,0})|$
$\displaystyle\leq$
$\displaystyle(1-\beta_{1})\sum_{j=0}^{i}\beta_{1}^{(k-1)n+i-((k-1)n+j)}|\partial_{l}f_{\tau_{k,j}}(\bm{w}_{k,0})|+(1-\beta_{1})\sum_{t=1}^{k-1}\sum_{j=0}^{n-1}\beta_{1}^{tn+i-j}|\partial_{l}f_{\tau_{k-t,j}}(\bm{w}_{k,0})|$
$\displaystyle+\beta_{1}^{(k-1)n+i+1}|\partial_{l}f_{\tau_{1,0}}(\bm{w}_{k,0})|$
$\displaystyle+(1-\beta_{1})\sum_{j=0}^{i}\beta_{1}^{(k-1)n+i-((k-1)n+j)}\left(\sum_{p=0}^{j-1}C_{1}\eta_{k}\sqrt{d}L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k,p})\|+(L_{0}+L_{1}\sqrt{D_{0}})C_{1}\eta_{k}\sqrt{d}j\right)$
$\displaystyle+(1-\beta_{1})\sum_{t=1}^{k-1}\sum_{j=0}^{n-1}\beta_{1}^{tn+i-j}\left(\sum_{p=j}^{n-1}C_{1}\eta_{k-t}\sqrt{d}L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-t,p})\|\right.$
$\displaystyle\left.+\sum_{r=1}^{t-1}\sum_{p=0}^{n-1}C_{1}\eta_{k-r}\sqrt{d}L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-r,p})\|+2\sqrt{2}(L_{0}+L_{1}\sqrt{D_{0}})C_{1}\sqrt{d}\eta_{k}(tn-j)\right)$
$\displaystyle+\beta_{1}^{(k-1)n+i+1}\left(\sum_{t=1}^{k-1}\sum_{p=0}^{n-1}L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-r,p})\|C_{1}\eta_{k-r}\sqrt{d}+2\sqrt{2}(L_{0}+L_{1}\sqrt{D_{0}})C_{1}\sqrt{d}\eta_{k}(k-1)n\right)$
$\displaystyle\overset{(\star)}{\leq}$
$\displaystyle\max_{i\in[n]}\left|\partial_{l}f_{i}(\bm{w}_{k,0})\right|+\left(n+\frac{2\sqrt{2}\beta_{1}}{1-\beta_{1}}\right)\sqrt{d}C_{1}(L_{0}+L_{1}\sqrt{D_{0}})\eta_{k}+L_{1}C_{1}\sqrt{D_{1}}\eta_{k}\sum_{j=0}^{i-1}\|\nabla
f(\bm{w}_{k,j})\|$
$\displaystyle+L_{1}C_{1}\sqrt{D_{1}}\sum_{t=1}^{k-1}\eta_{k-t}\sum_{j=0}^{n-1}\beta_{1}^{tn+i-j}\|\nabla
f(\bm{w}_{k-t,j})\|,$

where Inequality $(\star)$ is due to an exchange in the sum order.

Following the same routine, we have

$\displaystyle|\bm{m}_{l,k,-1}|$ $\displaystyle\leq$
$\displaystyle(1-\beta_{1})\sum_{t=1}^{k-1}\sum_{j=0}^{n-1}\beta_{1}^{tn-1-j}|\partial_{l}f_{\tau_{k-t,j}}(\bm{w}_{k-t,j})|+\beta_{1}^{(k-1)n}|\partial_{l}f_{\tau_{1,0}}(\bm{w}_{1,0})|$
$\displaystyle\leq$
$\displaystyle(1-\beta_{1})\sum_{t=1}^{k-1}\sum_{j=0}^{n-1}\beta_{1}^{tn-1-j}|\partial_{l}f_{\tau_{k-t,j}}(\bm{w}_{k,0})|+\beta_{1}^{(k-1)n}|\partial_{l}f_{\tau_{1,0}}(\bm{w}_{k,0})|$
$\displaystyle+(1-\beta_{1})\sum_{t=1}^{k-1}\sum_{j=0}^{n-1}\beta_{1}^{tn-1-j}C_{1}\sqrt{d}\left(\sum_{p=j}^{n-1}L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-t,p})\|\eta_{k-t}+\sum_{r=1}^{t-1}\sum_{p=0}^{n-1}L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-r,p})\|\eta_{k-r}\right.$
$\displaystyle+\left.2\sqrt{2}(L_{0}+L_{1}\sqrt{D_{0}})C_{1}\sqrt{d}\eta_{k}(tn-j)\right)$
$\displaystyle+\beta_{1}^{(k-1)n}\left(\sum_{t=1}^{k-1}\sum_{p=0}^{n-1}L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-r,p})\|C_{1}\eta_{k-r}\sqrt{d}+2\sqrt{2}(L_{0}+L_{1}\sqrt{D_{0}})C_{1}\sqrt{d}\eta_{k}(k-1)n\right)$
$\displaystyle\leq$
$\displaystyle\max_{i\in[n]}\left|\partial_{l}f_{i}(\bm{w}_{k,0})\right|+\sum_{t=1}^{k-1}\sum_{j=0}^{n-1}\beta_{1}^{tn-1-j}C_{1}\eta_{k-t}\sqrt{d}L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-t,j})\|~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$
$\displaystyle+\frac{2\sqrt{2}(L_{0}+L_{1}\sqrt{D_{0}})C_{1}\sqrt{d}\eta_{k}}{1-\beta_{1}}.$

The proof is completed. ∎

Similarly, we can upper and lower bound the adaptor $\bm{\nu}_{k,0}$ by the
gradient plus some error terms.

######  Lemma 9 (Estimation of the norm of the adaptor).

We have for all $l\in[d],k\in\mathbb{Z}^{+}$,

$\displaystyle|\bm{\nu}_{l,k,0}|\geq$
$\displaystyle\beta_{2}^{n}\frac{1-\beta_{2}}{1-\beta_{2}^{n}}\sum_{i\in[n]}\partial_{l}f_{i}(\bm{w}_{k,0})^{2}-\sqrt{\sum_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})^{2}|}\left(8\sqrt{2n}\eta_{k}C_{1}L_{0}\frac{1-\beta_{2}}{(1-\beta_{2}^{n})^{2}}\beta_{2}^{n}\right.$
$\displaystyle+\left.4L_{1}C_{1}\frac{1-\beta_{2}}{1-\beta_{2}^{n}}\frac{\sqrt{1-\beta_{2}}}{1-\sqrt{\beta_{2}}}\left(\sum_{t=1}^{k-1}\beta_{2}^{n}\sqrt{\beta_{2}}^{(r-1)n}\eta_{k-t}\sum_{j=0}^{n-1}(\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-t,j})\|+\sqrt{D_{0}})\right)\right),$

and

$\displaystyle|\bm{\nu}_{l,k,0}|\leq$ $\displaystyle
2\max_{i\in[n]}\partial_{l}f_{i}(\bm{w}_{k,0})^{2}+2\left(2\sqrt{2}\eta_{k}C_{1}(L_{0}+L_{1}\sqrt{D_{0}})\frac{\sqrt{1-\beta_{2}}}{1-\sqrt{\beta_{2}}}\frac{\sqrt{\beta_{2}}}{1-\sqrt{\beta_{2}}}\right.$
$\displaystyle+\left.L_{1}C_{1}\sqrt{D_{1}}\sum_{t=1}^{k-1}\eta_{k-t}\frac{\sqrt{1-\beta_{2}}}{1-\sqrt{\beta_{2}}}\sum_{j=0}^{n-1}\sqrt{\beta_{2}}^{(t-1)n}\|\nabla
f(\bm{w}_{k-t,j})\|\right)^{2},$

where $C_{1}$ is defined in Eq. (10).

###### Proof.

By the definition of $\bm{\nu}_{l,k,0}$, we have

$\displaystyle\bm{\nu}_{l,k,0}$ $\displaystyle=$
$\displaystyle(1-\beta_{2})\partial_{l}f_{\tau_{k,0}}(\bm{w}_{k,0})^{2}+\sum_{t=1}^{k-1}\sum_{j=0}^{n-1}(1-\beta_{2})\beta_{2}^{tn-j}\partial_{l}f_{\tau_{k-t,j}}(\bm{w}_{k-t,j})^{2}+\beta_{2}^{(k-1)n+1}\max_{i\in[n]}\partial_{l}f_{i}(\bm{w}_{1,0})^{2}$
$\displaystyle\geq$
$\displaystyle(1-\beta_{2})\partial_{l}f_{\tau_{k,0}}(\bm{w}_{k,0})^{2}+\sum_{t=1}^{k-1}\sum_{j=0}^{n-1}(1-\beta_{2})\beta_{2}^{tn}\partial_{l}f_{\tau_{k-t,j}}(\bm{w}_{k-t,j})^{2}+\beta_{2}^{(k-1)n+1}\frac{1}{n}\sum_{i=1}^{n}\partial_{l}f_{i}(\bm{w}_{1,0})^{2}$
$\displaystyle=$
$\displaystyle(1-\beta_{2})\partial_{l}f_{\tau_{k,0}}(\bm{w}_{k,0})^{2}+\sum_{t=1}^{k-1}\sum_{j=0}^{n-1}(1-\beta_{2})\beta_{2}^{tn}(\partial_{l}f_{\tau_{k-t,j}}(\bm{w}_{k,0})+\partial_{l}f_{\tau_{k-t,j}}(\bm{w}_{k-t,j})-\partial_{l}f_{\tau_{k-t,j}}(\bm{w}_{k,0}))^{2}$
$\displaystyle+\beta_{2}^{(k-1)n+1}\frac{1}{n}\sum_{i=1}^{n}(\partial_{l}f_{i}(\bm{w}_{k,0})+\partial_{l}f_{i}(\bm{w}_{1,0})-\partial_{l}f_{i}(\bm{w}_{k,0}))^{2}$
$\displaystyle\geq$
$\displaystyle(1-\beta_{2})\partial_{l}f_{\tau_{k,0}}(\bm{w}_{k,0})^{2}+\sum_{t=1}^{k-1}\sum_{j=0}^{n-1}(1-\beta_{2})\beta_{2}^{tn}\partial_{l}f_{\tau_{k-t,j}}(\bm{w}_{k,0})^{2}+\beta_{2}^{(k-1)n+1}\frac{1}{n}\sum_{i=1}^{n}\partial_{l}f_{i}(\bm{w}_{k,0})^{2}$
$\displaystyle-\sum_{t=1}^{k-1}\sum_{j=0}^{n-1}(1-\beta_{2})\beta_{2}^{tn}|\partial_{l}f_{\tau_{k-t,j}}(\bm{w}_{k,0})||\partial_{l}f_{\tau_{k-t,j}}(\bm{w}_{k,0})-\partial_{l}f_{\tau_{k-t,j}}(\bm{w}_{k-t,j})|$
$\displaystyle-\beta_{2}^{(k-1)n+1}\frac{1}{n}\sum_{i=1}^{n}|\partial_{l}f_{i}(\bm{w}_{k,0})||\partial_{l}f_{i}(\bm{w}_{k,0})-\partial_{l}f_{i}(\bm{w}_{1,0})|$

Since $f_{i}$ is $(L_{0},L_{1})$-smooth, the RHS of the above inequality can
be further lower bounded as follows:

$\displaystyle\left(\beta_{2}^{n}\frac{1-\beta_{2}^{(k-1)n}}{1-\beta_{2}^{n}}(1-\beta_{2})+\frac{\beta_{2}^{(k-1)n+1}}{n}\right)\sum_{i\in[n]}\partial_{l}f_{i}(\bm{w}_{k,0})^{2}$
$\displaystyle-\sum_{t=1}^{k-1}\sum_{j=0}^{n-1}(1-\beta_{2})\beta_{2}^{tn}|\partial_{l}f_{\tau_{k-t,j}}(\bm{w}_{k,0})|\left(\sum_{r=1}^{t}\sum_{p=0}^{n-1}L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-r,p})\|C_{1}\eta_{k-r}\sqrt{d}+2\sqrt{2}(L_{0}+L_{1}\sqrt{D_{0}})C_{1}\sqrt{d}\eta_{k}tn\right)$
$\displaystyle-\beta_{2}^{(k-1)n+1}\frac{1}{n}\sum_{i=1}^{n}|\partial_{l}f_{i}(\bm{w}_{k,0})|\left(\sum_{r=1}^{k-1}\sum_{p=0}^{n-1}L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-r,p})\|C_{1}\eta_{k-r}\sqrt{d}+2\sqrt{2}(L_{0}+L_{1}\sqrt{D_{0}})C_{1}\sqrt{d}\eta_{k}(k-1)n\right)$
$\displaystyle\geq$
$\displaystyle\beta_{2}^{n}\frac{1-\beta_{2}}{1-\beta_{2}^{n}}\sum_{i\in[n]}\partial_{l}f_{i}(\bm{w}_{k,0})^{2}$
$\displaystyle-\sum_{t=1}^{k-1}\sum_{j=0}^{n-1}(1-\beta_{2})\beta_{2}^{tn}|\partial_{l}f_{\tau_{k-t,j}}(\bm{w}_{k,0})|\left(\sum_{r=1}^{t}\sum_{p=0}^{n-1}L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-r,p})\|C_{1}\eta_{k-r}\sqrt{d}+2\sqrt{2}(L_{0}+L_{1}\sqrt{D_{0}})C_{1}\sqrt{d}\eta_{k}tn\right)$
$\displaystyle-\beta_{2}^{(k-1)n+1}\frac{1}{n}\sum_{i=1}^{n}|\partial_{l}f_{i}(\bm{w}_{k,0})|\left(\sum_{r=1}^{k-1}\sum_{p=0}^{n-1}L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-r,p})\|C_{1}\eta_{k-r}\sqrt{d}+2\sqrt{2}(L_{0}+L_{1}\sqrt{D_{0}})C_{1}\sqrt{d}\eta_{k}(k-1)n\right),$

where the last inequality we use
$\beta_{2}^{n}\frac{1-\beta_{2}^{(k-1)n}}{1-\beta_{2}^{n}}(1-\beta_{2})+\frac{\beta_{2}^{(k-1)n+1}}{n}\geq\beta_{2}^{n}\frac{1-\beta_{2}}{1-\beta_{2}^{n}}$.

$\displaystyle\geq$
$\displaystyle\beta_{2}^{n}\frac{1-\beta_{2}}{1-\beta_{2}^{n}}\sum_{i\in[n]}\partial_{l}f_{i}(\bm{w}_{k,0})^{2}-8\sqrt{2}\eta_{k}C_{1}L_{0}\frac{1-\beta_{2}}{(1-\beta_{2}^{n})^{2}}\beta_{2}^{n}\sum_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|$
$\displaystyle-4L_{1}C_{1}\frac{1-\beta_{2}}{1-\beta_{2}^{n}}\sum_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|\left(\sum_{r=1}^{k-1}\beta_{2}^{rn}\eta_{k-r}\sum_{j=0}^{n-1}\|\nabla
f_{i}(\bm{w}_{k-r,j})\|\right)$ $\displaystyle\geq$
$\displaystyle\beta_{2}^{n}\frac{1-\beta_{2}}{1-\beta_{2}^{n}}\sum_{i\in[n]}\partial_{l}f_{i}(\bm{w}_{k,0})^{2}-8\sqrt{2}\eta_{k}C_{1}L_{0}\frac{1-\beta_{2}}{(1-\beta_{2}^{n})^{2}}\beta_{2}^{n}\sum_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|$
$\displaystyle-4L_{1}C_{1}\frac{1-\beta_{2}}{1-\beta_{2}^{n}}\|\nabla
f_{i}(\bm{w}_{k,0})\|\left(\sum_{r=1}^{k-1}\beta_{2}^{rn}\eta_{k-r}\sum_{j=0}^{n-1}(\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-r,j})\|+\sqrt{D_{0}})\right)$ $\displaystyle\geq$
$\displaystyle\beta_{2}^{n}\frac{1-\beta_{2}}{1-\beta_{2}^{n}}\sum_{i\in[n]}\partial_{l}f_{i}(\bm{w}_{k,0})^{2}-8\sqrt{2n}\eta_{k}C_{1}L_{0}\frac{1-\beta_{2}}{(1-\beta_{2}^{n})^{2}}\beta_{2}^{n}\sqrt{\sum_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})^{2}|}$
$\displaystyle-4L_{1}C_{1}\frac{1-\beta_{2}}{1-\beta_{2}^{n}}\sqrt{\sum_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})^{2}|}\left(\sum_{r=1}^{k-1}\beta_{2}^{rn}\eta_{k-r}\sum_{j=0}^{n-1}(\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-r,j})\|+\sqrt{D_{0}})\right)$ $\displaystyle\geq$
$\displaystyle\beta_{2}^{n}\frac{1-\beta_{2}}{1-\beta_{2}^{n}}\sum_{i\in[n]}\partial_{l}f_{i}(\bm{w}_{k,0})^{2}-8\sqrt{2n}\eta_{k}C_{1}L_{0}\frac{1-\beta_{2}}{(1-\beta_{2}^{n})^{2}}\beta_{2}^{n}\sqrt{\sum_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})^{2}|}$
$\displaystyle-4L_{1}C_{1}\frac{1-\beta_{2}}{1-\beta_{2}^{n}}\frac{\sqrt{1-\beta_{2}}}{1-\sqrt{\beta_{2}}}\sqrt{\sum_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})^{2}|}\left(\sum_{r=1}^{k-1}\beta_{2}^{n}\sqrt{\beta_{2}}^{(r-1)n}\eta_{k-r}\sum_{j=0}^{n-1}(\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-r,j})\|+\sqrt{D_{0}})\right).$

The first claim is proved.

As for the upper bound, we have

$\displaystyle\bm{\nu}_{l,k,0}$ $\displaystyle=$
$\displaystyle(1-\beta_{2})\partial_{l}f_{\tau_{k,0}}(\bm{w}_{k,0})^{2}+\sum_{t=1}^{k-1}\sum_{j=0}^{n-1}(1-\beta_{2})\beta_{2}^{tn-j}\partial_{l}f_{\tau_{k-t,j}}(\bm{w}_{k-t,j})^{2}+\beta_{2}^{(k-1)n+1}\max_{i\in[n]}\partial_{l}f_{i}(\bm{w}_{1,0})^{2}$
$\displaystyle\leq$ $\displaystyle
2(1-\beta_{2})\partial_{l}f_{\tau_{k,0}}(\bm{w}_{k,0})^{2}+2\sum_{t=1}^{k-1}\sum_{j=0}^{n-1}(1-\beta_{2})\beta_{2}^{tn-j}\partial_{l}f_{\tau_{k-t,j}}(\bm{w}_{k,0})^{2}+2\beta_{2}^{(k-1)n+1}\max_{i\in[n]}\partial_{l}f_{i}(\bm{w}_{k,0})^{2}$
$\displaystyle+2\sum_{t=1}^{k-1}\sum_{j=0}^{n-1}(1-\beta_{2})\beta_{2}^{tn-j}\left(\sum_{p=j}^{n-1}L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-t,p})C_{1}\eta_{k-t}\sqrt{d}\right.$
$\displaystyle\left.+\sum_{r=1}^{t-1}\sum_{p=0}^{n-1}L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-r,p})\|C_{1}\eta_{k-r}\sqrt{d}+2\sqrt{2}(L_{0}+L_{1}\sqrt{D_{0}})C_{1}\sqrt{d}\eta_{k}(tn-j)\right)^{2}$
$\displaystyle+2\beta_{2}^{(k-1)n+1}\left(\sum_{r=1}^{k-1}\sum_{p=0}^{n-1}L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-r,p})\|C_{1}\eta_{k-r}\sqrt{d}+2\sqrt{2}(L_{0}+L_{1}\sqrt{D_{0}})C_{1}\sqrt{d}\eta_{k}(k-1)n\right)^{2}$
$\displaystyle\leq$ $\displaystyle
2\max_{i\in[n]}\partial_{l}f_{i}(\bm{w}_{k,0})^{2}+2\left(\sum_{t=1}^{k-1}\sum_{j=0}^{n-1}\sqrt{1-\beta_{2}}\sqrt{\beta_{2}}^{tn-j}\left(\sum_{p=j}^{n-1}L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-t,p})C_{1}\eta_{k-t}\sqrt{d}\right.\right.$
$\displaystyle\left.+\sum_{r=1}^{t-1}\sum_{p=0}^{n-1}L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-r,p})\|C_{1}\eta_{k-r}\sqrt{d}+2\sqrt{2}(L_{0}+L_{1}\sqrt{D_{0}})C_{1}\sqrt{d}\eta_{k}(tn-j)\right)$
$\displaystyle+\left.\sqrt{\beta_{2}}^{(k-1)n+1}\left(\sum_{r=1}^{k-1}\sum_{p=0}^{n-1}L_{1}\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-r,p})\|C_{1}\eta_{k-r}\sqrt{d}+2\sqrt{2}(L_{0}+L_{1}\sqrt{D_{0}})C_{1}\sqrt{d}\eta_{k}(k-1)n\right)\right)^{2}$
$\displaystyle\leq$ $\displaystyle
2\max_{i\in[n]}\partial_{l}f_{i}(\bm{w}_{k,0})^{2}+2\left(2\sqrt{2}\eta_{k}C_{1}(L_{0}+L_{1}\sqrt{D_{0}})\frac{\sqrt{1-\beta_{2}}}{1-\sqrt{\beta_{2}}}\frac{\sqrt{\beta_{2}}}{1-\sqrt{\beta_{2}}}\right.$
$\displaystyle+\left.L_{1}C_{1}\sqrt{D_{1}}\sum_{t=1}^{k-1}\eta_{k-t}\frac{\sqrt{1-\beta_{2}}}{1-\sqrt{\beta_{2}}}\sum_{j=0}^{n-1}\sqrt{\beta_{2}}^{tn-j}\|\nabla
f(\bm{w}_{k-t,j})\|\right)^{2}$ $\displaystyle\leq$ $\displaystyle
2\max_{i\in[n]}\partial_{l}f_{i}(\bm{w}_{k,0})^{2}+2\left(2\sqrt{2}\eta_{k}C_{1}(L_{0}+L_{1}\sqrt{D_{0}})\frac{\sqrt{1-\beta_{2}}}{1-\sqrt{\beta_{2}}}\frac{\sqrt{\beta_{2}}}{1-\sqrt{\beta_{2}}}\right.$
$\displaystyle+\left.L_{1}C_{1}\sqrt{D_{1}}\sum_{t=1}^{k-1}\eta_{k-t}\frac{\sqrt{1-\beta_{2}}}{1-\sqrt{\beta_{2}}}\sum_{j=0}^{n-1}\sqrt{\beta_{2}}^{(t-1)n}\|\nabla
f(\bm{w}_{k-t,j})\|\right)^{2}.$

The proof is completed. ∎

We then immediately have the following corollary when
$\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|$ is large enough compared to
the error term.

######  Corollary 5 (Lemma 1, formal).

If

$\displaystyle\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|\geq$
$\displaystyle
4L_{1}C_{1}\frac{\sqrt{1-\beta_{2}}}{1-\sqrt{\beta_{2}}}\left(\sum_{r=1}^{k-1}\sqrt{\beta_{2}}^{(r-1)n}\eta_{k-r}\sum_{j=0}^{n-1}(\sqrt{D_{1}}\|\nabla
f(\bm{w}_{k-r,j})\|+\sqrt{D_{0}})\right)$
$\displaystyle+2\sqrt{2}\eta_{k}C_{1}(L_{0}+L_{1}\sqrt{D_{0}})\frac{\sqrt{1-\beta_{2}}}{1-\sqrt{\beta_{2}}}\frac{\sqrt{\beta_{2}}}{1-\sqrt{\beta_{2}}}+8\sqrt{2n}\eta_{k}C_{1}L_{0}\frac{1}{1-\beta_{2}^{n}}$
$\displaystyle+\eta_{k}C_{1}\left(n(L_{0}+L_{1}\sqrt{D_{0}})+L_{1}\sqrt{D_{1}}\left(\sum_{p=0}^{n-1}\|\nabla
f(\bm{w}_{k,p})\|\right)\right),$ (13)

then

$\frac{\beta_{2}^{n}}{2}\frac{1}{n}\sum_{i\in[n]}\partial_{l}f_{i}(\bm{w}_{k,0})^{2}\leq\bm{\nu}_{l,k,0}\leq
4\max_{i\in[n]}\partial_{l}f_{i}(\bm{w}_{k,0})^{2},$

where $C_{1}$ is defined in Eq. (10). Furthermore, if Eq. (13) holds, we have
$\forall i\in\\{0,\cdots,n-1\\}$,

$\beta_{2}^{n-1}\bm{\nu}_{l,k,0}\leq\bm{\nu}_{l,k,i}\leq\left(\beta_{2}^{n-1}+8n\frac{1-\beta_{2}^{n-1}}{\beta_{2}^{n}}\right)\bm{\nu}_{l,k,0},$

and

$\frac{1}{\beta_{2}}\left(1-(1-\beta_{2})\frac{2n}{\beta_{2}^{n}}\right)\bm{\nu}_{l,k,0}\leq\bm{\nu}_{l,k,-1}\leq\frac{1}{\beta_{2}}\bm{\nu}_{l,k,0},$

###### Proof.

The first claim is derived by directly applying the range of
$\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|$ into Lemma 9.

As for the second claim, we have

$\bm{\nu}_{l,k,i}=\beta_{2}^{i}\bm{\nu}_{l,k,0}+(1-\beta_{2})(\partial_{l}f_{\tau_{k,i}}(\bm{w}_{k,i})^{2}+\cdots+\beta_{2}^{i-1}\partial_{l}f_{\tau_{k,i}}(\bm{w}_{k,1})^{2}).$

On the other hand, since $\forall j\in\\{0,\cdots,n-1\\}$

$\displaystyle|\partial_{l}f_{i}(\bm{w}_{k,j})|\leq$
$\displaystyle\max_{p\in[n]}|\partial_{l}f_{p}(\bm{w}_{k,0})|+\eta_{k}C_{1}\left(j(L_{0}+L_{1}\sqrt{D_{0}})+L_{1}\sqrt{D_{1}}\left(\sum_{p=0}^{j-1}\|\nabla
f(\bm{w}_{k,p})\|\right)\right)$ $\displaystyle\leq$
$\displaystyle\max_{p\in[n]}|\partial_{l}f_{p}(\bm{w}_{k,0})|+\eta_{k}C_{1}\left(n(L_{0}+L_{1}\sqrt{D_{0}})+L_{1}\sqrt{D_{1}}\left(\sum_{p=0}^{n-1}\|\nabla
f(\bm{w}_{k,p})\|\right)\right),$

we have

$\displaystyle\beta_{2}^{n-1}\bm{\nu}_{l,k,0}\leq\bm{\nu}_{l,k,i}$
$\displaystyle\leq$
$\displaystyle\beta_{2}^{i}\bm{\nu}_{l,k,0}+2(1-\beta_{2})\max_{p\in[n]}\partial_{l}f_{p}(\bm{w}_{k,0})^{2}(1+\cdots+\beta_{2}^{i-1})$
$\displaystyle+2(1-\beta_{2})(1+\cdots+\beta_{2}^{i-1})\eta_{k}^{2}C_{1}^{2}\left(n(L_{0}+L_{1}\sqrt{D_{0}})+L_{1}\sqrt{D_{1}}\left(\sum_{p=0}^{n-1}\|\nabla
f(\bm{w}_{k,p})\|\right)\right)^{2}$ $\displaystyle=$
$\displaystyle\beta_{2}^{i}\bm{\nu}_{l,k,0}+2(1-\beta_{2}^{i})\max_{p\in[n]}\partial_{l}f_{p}(\bm{w}_{k,0})^{2}+2(1-\beta_{2}^{i})\eta_{k}^{2}C_{1}^{2}\left(n(L_{0}+L_{1}\sqrt{D_{0}})+L_{1}\sqrt{D_{1}}\left(\sum_{p=0}^{n-1}\|\nabla
f(\bm{w}_{k,p})\|\right)\right)^{2}.$

Therefore, if Eq. (13) holds, we then have

$\displaystyle\bm{\nu}_{l,k,i}\leq$
$\displaystyle\beta_{2}^{i}\bm{\nu}_{l,k,0}+4(1-\beta_{2}^{i})\max_{p\in[n]}\partial_{l}f_{p}(\bm{w}_{k,0})^{2}$
$\displaystyle\leq$
$\displaystyle\beta_{2}^{i}\bm{\nu}_{l,k,0}+4\frac{n}{n}(1-\beta_{2}^{i})\sum_{p\in[n]}\partial_{l}f_{p}(\bm{w}_{k,0})^{2}\leq\left(\beta_{2}^{i}+8n\frac{1-\beta_{2}^{i}}{\beta_{2}^{n}}\right)\bm{\nu}_{l,k,0}$
$\displaystyle\leq$
$\displaystyle\left(\beta_{2}^{n-1}+8n\frac{1-\beta_{2}^{n-1}}{\beta_{2}^{n}}\right)\bm{\nu}_{l,k,0}.$

Following the same routine, we have

$\beta_{2}\bm{\nu}_{l,k,-1}\leq\bm{\nu}_{l,k,0},$

and if Eq. (13) holds,

$\displaystyle\bm{\nu}_{l,k,-1}=$
$\displaystyle\frac{1}{\beta_{2}}\left(\bm{\nu}_{l,k,0}-(1-\beta_{2})\partial_{l}f_{\tau_{k,0}}(\bm{w}_{k,0})^{2}\right)\geq\frac{1}{\beta_{2}}\left(\bm{\nu}_{l,k,0}-(1-\beta_{2})\max_{p}\partial_{l}f_{p}(\bm{w}_{k,0})^{2}\right)$
$\displaystyle\geq$
$\displaystyle\bm{\nu}_{l,k,0}\frac{1}{\beta_{2}}\left(1-(1-\beta_{2})\frac{2n}{\beta_{2}^{n}}\right).$

The proof of the second claim is completed. ∎

######  Remark 5.

By the notations in Eq. (10)., Eq. (13) can be translated into

$\displaystyle\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|\geq$
$\displaystyle
C_{3}\eta_{k}+C_{4}\sum_{r=1}^{k-1}\sqrt{\beta_{2}}^{(r-1)n}\eta_{k-r}\sum_{j=0}^{n-1}\|\nabla
f(\bm{w}_{k-r,j})\|$
$\displaystyle+C_{4}n\sum_{r=1}^{k-1}\sqrt{\beta_{2}}^{(r-1)n}\eta_{k-r}+\eta_{k}C_{4}\left(\sum_{j=0}^{n-1}\|\nabla
f(\bm{w}_{k,j})\|\right).$ (14)

Furthermore, we define $g(\beta_{2})$ as

$\displaystyle
g(\beta_{2})\triangleq\max\left\\{\frac{1}{\sqrt{\beta_{2}}^{n-1}}-1,1-\frac{1}{\sqrt{\beta_{2}^{n-1}+8n\frac{1-\beta_{2}^{n-1}}{\beta_{2}^{n}}}},1-\sqrt{\beta_{2}},\sqrt{\frac{\beta_{2}}{\left(1-(1-\beta_{2})\frac{2n}{\beta_{2}^{n}}\right)}}-1\right\\},$

and the conclusion of Corollary 5 can be translated into that if Eq. (14)
holds,

$\left|\frac{1}{\sqrt{\bm{\nu}_{l,k,i}}}-\frac{1}{\sqrt{\bm{\nu}_{l,k,0}}}\right|\leq
g(\beta_{2})\frac{1}{\sqrt{\bm{\nu}_{l,k,0}}},$

and

$\left|\frac{1}{\sqrt{\bm{\nu}_{l,k,-1}}}-\frac{1}{\sqrt{\bm{\nu}_{l,k,0}}}\right|\leq
g(\beta_{2})\frac{1}{\sqrt{\bm{\nu}_{l,k,0}}}.$

Based on whether Eq. (14) is fulfilled, we divide $[d]$ into
$\mathbb{L}_{large}^{k}$ and $\mathbb{L}_{small}^{k}$ ($\forall k\geq 1$),
which are respectively defined as

$\displaystyle\mathbb{L}_{large}^{k}=\\{l:l\in[d],\text{s.t. Eq. (\ref{eq:
translated_crit}) holds}\\},$
$\displaystyle\mathbb{L}_{small}^{k}=\\{l:l\in[d],\text{s.t. Eq. (\ref{eq:
translated_crit}) doesn't hold}\\}.$

The following lemma characterizes the property of $\mathbb{L}_{small}^{k}$.

######  Lemma 10.

Define
$\bm{u}_{k}\triangleq\frac{\bm{w}_{k,0}-\beta_{1}\bm{w}_{k,-1}}{1-\beta_{1}}$
(with $\bm{w}_{1,-1}\triangleq\bm{w}_{1,0}$). Then,

$\sum_{k=1}^{T}\left|\sum_{l\in\mathbb{L}_{small}^{k}}\partial_{l}f(\bm{w}_{k,0})(\bm{u}_{l,k+1}-\bm{u}_{l,k})\right|\leq
C_{2}\left(C_{5}\sum_{k=1}^{T}\eta_{k}^{2}\|\nabla f(\bm{w}_{k,0})\|+C_{6}\ln
T+C_{7}\right),$

where $C_{2}$, $C_{5}$, $C_{6}$, and $C_{7}$ are defined in Eq. (10).

###### Proof.

By directly applying the definition of $\mathbb{L}_{large}^{k}$ and Lemma 5,
we have

$\displaystyle\frac{1}{n}\left|\sum_{l\in\mathbb{L}_{small}^{k}}\partial_{l}f(\bm{w}_{k,0})(\bm{u}_{l,k+1}-\bm{u}_{l,k})\right|$
$\displaystyle\leq$ $\displaystyle
dC_{2}\eta_{k}\left(C_{3}\eta_{k}+C_{4}\sum_{r=1}^{k-1}\sqrt{\beta_{2}}^{(r-1)n}\eta_{k-r}\sum_{j=0}^{n-1}\|\nabla
f(\bm{w}_{k-r,j})\|\right.\left.+C_{4}n\sum_{r=1}^{k-1}\sqrt{\beta_{2}}^{(r-1)n}\eta_{k-r}+\eta_{k}C_{4}\left(\sum_{p=0}^{n-1}\|\nabla
f(\bm{w}_{k,p})\|\right)\right).$

Summing over $k$ from $1$ to $t$ then leads to

$\displaystyle\frac{1}{n}\sum_{k=1}^{T}\left|\sum_{l\in\mathbb{L}_{small}^{k}}\partial_{l}f(\bm{w}_{k,0})(\bm{u}_{l,k+1}-\bm{u}_{l,k})\right|$
$\displaystyle\leq$
$\displaystyle\sum_{k=1}^{T}dC_{2}C_{3}\eta^{2}_{k}+dC_{2}C_{4}\sum_{k=1}^{T}\eta_{k}\sum_{r=1}^{k-1}\sqrt{\beta_{2}}^{(r-1)n}\eta_{k-r}\sum_{j=0}^{n-1}\|\nabla
f(\bm{w}_{k-r,j})\|+C_{2}C_{4}n\sum_{k=1}^{T}\eta_{k}\sum_{r=1}^{k-1}\sqrt{\beta_{2}}^{(r-1)n}\eta_{k-r}$
$\displaystyle+C_{2}C_{4}\sum_{k=1}^{T}\eta_{k}^{2}\sum_{p=0}^{n-1}\|\nabla
f(\bm{w}_{k,p})\|$ $\displaystyle\leq$
$\displaystyle\sum_{k=1}^{T}dC_{2}C_{3}\eta^{2}_{k}+\frac{dC_{2}C_{4}}{1-\sqrt{\beta_{2}^{n}}}\sum_{k=1}^{T-1}\eta_{k}^{2}\sum_{j=0}^{n-1}\|\nabla
f(\bm{w}_{k,j})\|+\frac{C_{2}C_{4}n}{1-\sqrt{\beta_{2}^{n}}}\sum_{k=1}^{T-1}\eta_{k}^{2}+C_{2}C_{4}\sum_{k=1}^{T}\eta_{k}^{2}\sum_{p=0}^{n-1}\|\nabla
f(\bm{w}_{k,p})\|$ $\displaystyle\leq$
$\displaystyle\left(dC_{2}C_{3}+\frac{C_{2}C_{4}n}{1-\sqrt{\beta_{2}^{n}}}\right)\eta^{2}_{1}(1+\ln
T)+\left(C_{2}C_{4}+\frac{dC_{2}C_{4}}{1-\sqrt{\beta_{2}^{n}}}\right)\sum_{k=1}^{T}\eta_{k}^{2}\sum_{j=0}^{n-1}\|\nabla
f(\bm{w}_{k,j})\|,$

where in the second inequality we exchange the sum order. By Lemma 6, the
above inequality further leads to

$\displaystyle\sum_{k=1}^{T}\left|\sum_{l\in\mathbb{L}_{small}^{k}}\partial_{l}f(\bm{w}_{k,0})(\bm{u}_{l,k+1}-\bm{u}_{l,k})\right|$
$\displaystyle\leq$ $\displaystyle
n\left(C_{2}C_{4}+\frac{dC_{2}C_{4}}{1-\sqrt{\beta_{2}^{n}}}\right)\sum_{k=1}^{T}\eta_{k}^{2}\sum_{j=0}^{n-1}\left((1+n\sqrt{d}C_{1}\eta_{1}L_{1}\sqrt{n})\|\nabla
f(\bm{w}_{k,0})\|+\left(nL_{0}+L_{1}\sqrt{n}\sqrt{D_{0}}\right)n\sqrt{d}C_{1}\eta_{k}\right)$
$\displaystyle+n\left(dC_{2}C_{3}+\frac{C_{2}C_{4}n}{1-\sqrt{\beta_{2}^{n}}}\right)\eta_{1}^{2}(1+\ln
T)$ $\displaystyle\leq$ $\displaystyle
n^{2}(1+n\sqrt{d}C_{1}\eta_{1}L_{1}\sqrt{n})\left(C_{2}C_{4}+\frac{dC_{2}C_{4}}{1-\sqrt{\beta_{2}^{n}}}\right)\sum_{k=1}^{T}\eta_{k}^{2}\|\nabla
f(\bm{w}_{k,0})\|+\left(dC_{2}C_{3}+\frac{C_{2}C_{4}n}{1-\sqrt{\beta_{2}^{n}}}\right)\eta_{1}^{2}(1+\ln
T)$
$\displaystyle+n\left(C_{2}C_{4}+\frac{dC_{2}C_{4}}{1-\sqrt{\beta_{2}^{n}}}\right)\left(nL_{0}+L_{1}\sqrt{n}\sqrt{D_{0}}\right)n^{2}\sqrt{d}C_{1}\sum_{k=1}^{T}\eta_{k}^{3}$
$\displaystyle\leq$ $\displaystyle
n^{2}(1+n\sqrt{d}C_{1}\eta_{1}L_{1}\sqrt{n}\sqrt{D_{1}})\left(C_{2}C_{4}+\frac{dC_{2}C_{4}\sqrt{D_{1}}}{1-\sqrt{\beta_{2}^{n}}}\right)\sum_{k=1}^{T}\eta_{k}^{2}\|\nabla
f(\bm{w}_{k,0})\|+\left(dC_{2}C_{3}+\frac{C_{2}C_{4}n\sqrt{D_{1}}}{1-\sqrt{\beta_{2}^{n}}}\right)$
$\displaystyle\times\eta^{2}_{1}(1+\ln
T)+3n\left(C_{2}C_{4}+\frac{dC_{2}C_{4}}{1-\sqrt{\beta_{2}^{n}}}\right)\left(nL_{0}+L_{1}\sqrt{n}\sqrt{D_{0}}\right)n^{2}\sqrt{d}C_{1}\eta_{1}^{3}.$
(15)

By the notations in Eq. (10), the proof is completed. ∎

The next lemma characterizes the property of $\mathbb{L}^{k}_{large}$.

######  Lemma 11.

Define
$\bm{u}_{k}\triangleq\frac{\bm{w}_{k,0}-\beta_{1}\bm{w}_{k,-1}}{1-\beta_{1}}$
(with $\bm{w}_{1,-1}\triangleq\bm{w}_{1,0}$). We have

$\displaystyle\sum_{k=1}^{T}\sum_{l\in\mathbb{L}_{large}^{k}}\partial_{l}f(\bm{w}_{k,0})(\bm{u}_{l,k+1}-\bm{u}_{l,k})$
$\displaystyle\leq$
$\displaystyle-\sum_{k=1}^{T}\sum_{l\in[d]}\frac{\eta_{k}\partial_{l}f(\bm{w}_{k,0})^{2}}{2\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|+\xi}$
$\displaystyle+\sum_{k=1}^{T}\sum_{l\in\mathbb{L}_{large}^{k}}\eta_{k}g(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{|\partial_{l}f(\bm{w}_{k,0})|}{\sqrt{\frac{\beta_{2}^{n}}{2n}}\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|+\xi}\left(\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|\right)$
$\displaystyle+\left((C_{8}+\frac{1}{2}C_{5})\sum_{k=1}^{T}\eta_{k}^{2}\|\nabla
f(\bm{w}_{k,0})\|+(C_{9}+\frac{1}{2}C_{6})\ln
T+(C_{10}+\frac{1}{2}C_{7})\right).$

###### Proof.

Compared to the proof of Lemma 10, the proof of this lemma is more
complicated. To begin with, we provide a decomposition of
$\bm{u}_{k+1}-\bm{u}_{k}$. According to the definition of $\bm{u}_{k}$, we
have

$\displaystyle\bm{u}_{k+1}-\bm{u}_{k}$ $\displaystyle=$
$\displaystyle\frac{(\bm{w}_{k+1,0}-\beta_{1}\bm{w}_{k+1,-1})-(\bm{w}_{k,0}-\beta_{1}\bm{w}_{k,-1})}{1-\beta_{1}}$
$\displaystyle=$
$\displaystyle\frac{(\bm{w}_{k+1,0}-\bm{w}_{k,0})-\beta_{1}(\bm{w}_{k+1,-1}-\bm{w}_{k,-1})}{1-\beta_{1}}$
$\displaystyle=$
$\displaystyle\frac{\sum_{i=0}^{n-1}(\bm{w}_{k,i+1}-\bm{w}_{k,i})-\beta_{1}\sum_{i=0}^{n-1}(\bm{w}_{k,i}-\bm{w}_{k,i-1})}{1-\beta_{1}}$
$\displaystyle=$
$\displaystyle\frac{(\bm{w}_{k+1,0}-\bm{w}_{k+1,-1})+(1-\beta_{1})\sum_{i=0}^{n-2}(\bm{w}_{k,i+1}-\bm{w}_{k,i})-\beta_{1}(\bm{w}_{k,0}-\bm{w}_{k,-1})}{1-\beta_{1}}$
$\displaystyle\overset{(\star)}{=}$
$\displaystyle-\frac{\frac{\eta_{k}}{\sqrt{\bm{\nu}_{k,n-1}}}\odot\bm{m}_{k,n-1}+(1-\beta_{1})\sum_{i=0}^{n-2}\frac{\eta_{k}}{\sqrt{\bm{\nu}_{k,i}}}\odot\bm{m}_{k,i}-\beta_{1}\frac{\eta_{k-1}}{\sqrt{\bm{\nu}_{k-1,n-1}}}\odot\bm{m}_{k-1,n-1}}{1-\beta_{1}}$
$\displaystyle=$
$\displaystyle-\frac{\eta_{k}}{\sqrt{\bm{\nu}_{k,0}}}\odot\frac{\bm{m}_{k,n-1}+(1-\beta_{1})\sum_{i=0}^{n-2}\bm{m}_{k,i}-\beta_{1}\bm{m}_{k-1,n-1}}{1-\beta_{1}}-\eta_{k}\left(\left(\frac{1}{\sqrt{\bm{\nu}_{k,n-1}}}-\frac{1}{\sqrt{\bm{\nu}_{k,0}}}\right)\odot\frac{\bm{m}_{k,n-1}}{1-\beta_{1}}\right.$
$\displaystyle~{}~{}~{}\left.+\sum_{i=0}^{n-2}\left(\frac{1}{\sqrt{\bm{\nu}_{k,i}}}-\frac{1}{\sqrt{\bm{\nu}_{k,0}}}\right)\odot\bm{m}_{k,i}-\frac{\beta_{1}}{1-\beta_{1}}\left(\frac{1}{\sqrt{\bm{\nu}_{k-1,n-1}}}-\frac{1}{\sqrt{\bm{\nu}_{k,0}}}\right)\odot{\bm{m}_{k-1,n-1}}\right)$
$\displaystyle~{}~{}~{}-\frac{\beta_{1}}{1-\beta_{1}}(\eta_{k-1}-\eta_{k})\frac{1}{\sqrt{\bm{\nu}_{k-1,n-1}}}\odot{\bm{m}_{k-1,n-1}}.$
(16)

Here equation ($\star$) is due to a direct application of the update rule of
$\bm{w}_{k,i}$. We then analyze the above three terms respectively, namely, we
define

$\displaystyle
a^{1}_{l}\triangleq-\frac{\eta_{k}}{\sqrt{\bm{\nu}_{l,k,0}}}\frac{\bm{m}_{l,k,n-1}+(1-\beta_{1})\sum_{i=0}^{n-2}\bm{m}_{l,k,i}-\beta_{1}\bm{m}_{l,k-1,n-1}}{1-\beta_{1}}=-\frac{\eta_{k}}{\sqrt{\bm{\nu}_{l,k,0}}}\sum_{i=0}^{n-1}\partial_{l}f_{\tau_{k,i}}(\bm{w}_{k,i}),$
$\displaystyle
a^{2}_{l}\triangleq-\eta_{k}\left(\left(\frac{1}{\sqrt{\bm{\nu}_{l,k,n-1}}}-\frac{1}{\sqrt{\bm{\nu}_{l,k,0}}}\right)\frac{\bm{m}_{l,k,n-1}}{1-\beta_{1}}+\sum_{i=0}^{n-2}\left(\frac{1}{\sqrt{\bm{\nu}_{l,k,i}}}-\frac{1}{\sqrt{\bm{\nu}_{l,k,0}}}\right)\bm{m}_{l,k,i}\right.~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}-\left.\frac{\beta_{1}}{1-\beta_{1}}\left(\frac{1}{\sqrt{\bm{\nu}_{l,k-1,n-1}}}-\frac{1}{\sqrt{\bm{\nu}_{l,k,0}}}\right){\bm{m}_{l,k-1,n-1}}\right),$
$\displaystyle
a^{3}_{l}\triangleq-\frac{\beta_{1}}{1-\beta_{1}}(\eta_{k-1}-\eta_{k})\frac{1}{\sqrt{\bm{\nu}_{l,k-1,n-1}}}{\bm{m}_{l,k-1,n-1}}.$

One can then easily observe that by Eq. (16),

$\sum_{l\in\mathbb{L}_{large}^{k}}\partial_{l}f(\bm{w}_{k,0})(\bm{u}_{l,k+1}-\bm{u}_{l,k})=\sum_{l\in\mathbb{L}_{large}^{k}}\partial_{l}f(\bm{w}_{k,0})a_{l}^{1}+\sum_{l\in\mathbb{L}_{large}^{k}}\partial_{l}f(\bm{w}_{k,0})a_{l}^{2}+\sum_{l\in\mathbb{L}_{large}^{k}}\partial_{l}f(\bm{w}_{k,0})a_{l}^{3}.$

① Tackling Term
$\sum_{l\in\mathbb{L}_{large}^{k}}\partial_{l}f(\bm{w}_{k,0})a_{l}^{1}$:

We have

$\displaystyle\sum_{l\in\mathbb{L}_{large}^{k}}\partial_{l}f(\bm{w}_{k,0})a_{l}^{1}$
$\displaystyle=$
$\displaystyle-\sum_{l\in\mathbb{L}_{large}^{k}}\partial_{l}\frac{\eta_{k}}{\sqrt{\bm{\nu}_{l,k,0}}}\partial_{l}f(\bm{w}_{k,0})\left(\sum_{i=0}^{n-1}\partial_{l}f_{\tau_{k,i}}(\bm{w}_{k,0})\right)-\sum_{l\in\mathbb{L}_{large}^{k}}\frac{\eta_{k}}{\sqrt{\bm{\nu}_{l,k,0}}}\partial_{l}f(\bm{w}_{k,0})\left(\sum_{i=0}^{n-1}(\partial_{l}f_{\tau_{k,i}}(\bm{w}_{k,i})-\partial_{l}f_{\tau_{k,i}}(\bm{w}_{k,0}))\right)$
$\displaystyle=$
$\displaystyle-\sum_{l\in\mathbb{L}_{large}^{k}}\frac{\eta_{k}}{\sqrt{\bm{\nu}_{l,k,0}}}\partial_{l}f(\bm{w}_{k,0})^{2}-\sum_{l\in\mathbb{L}_{large}^{k}}\frac{\eta_{k}}{\sqrt{\bm{\nu}_{l,k,0}}}\partial_{l}f(\bm{w}_{k,0})\left(\sum_{i=0}^{n-1}(\partial_{l}f_{\tau_{k,i}}(\bm{w}_{k,i})-\partial_{l}f_{\tau_{k,i}}(\bm{w}_{k,0}))\right)$
$\displaystyle\overset{(\star)}{=}$
$\displaystyle-\sum_{l\in\mathbb{L}_{large}^{k}}\frac{\eta_{k}}{\sqrt{\bm{\nu}_{l,k,0}}}\partial_{l}f(\bm{w}_{k,0})^{2}+\mathcal{O}\left(\eta_{k}^{2}\right)+\mathcal{O}\left(\eta_{k}^{2}\|\nabla
f(\bm{w}_{k,0})\|\right),$

where Eq. ($\star$) is due to

$\displaystyle\left|\sum_{l\in\mathbb{L}_{large}^{k}}\frac{\eta_{k}}{\sqrt{\bm{\nu}_{l,k,0}}}\partial_{l}f(\bm{w}_{k,0})\left(\sum_{i=0}^{n-1}(\partial_{l}f_{\tau_{k,i}}(\bm{w}_{k,i})-\partial_{l}f_{\tau_{k,i}}(\bm{w}_{k,0}))\right)\right|$
$\displaystyle\overset{(\ast)}{\leq}$
$\displaystyle\eta_{k}\sqrt{\frac{2n^{2}}{\beta_{2}^{n}}}\left(\sum_{l\in\mathbb{L}_{large}^{k}}\sum_{i=0}^{n-1}|\partial_{l}f_{\tau_{k,i}}(\bm{w}_{k,i})-\partial_{l}f_{\tau_{k,i}}(\bm{w}_{k,0})|\right)$
$\displaystyle\leq$
$\displaystyle\eta_{k}\sqrt{\frac{2n^{2}}{\beta_{2}^{n}}}\left(\sqrt{d}\sum_{i=0}^{n-1}\|\nabla
f_{\tau_{k,i}}(\bm{w}_{k,i})-\nabla f_{\tau_{k,i}}(\bm{w}_{k,0})\|\right)$
$\displaystyle\overset{(\circ)}{\leq}$
$\displaystyle\eta_{k}\sqrt{\frac{2n^{2}}{\beta_{2}^{n}}}\sqrt{d}\sum_{i=0}^{n-1}(L_{0}+L_{1}\|\nabla
f_{\tau_{k,i}}(\bm{w}_{k,0})\|)\|\bm{w}_{k,i}-\bm{w}_{k,0}\|$
$\displaystyle\leq$
$\displaystyle\eta_{k}\sqrt{\frac{2n^{2}}{\beta_{2}^{n}}}\sqrt{d}(nL_{0}+L_{1}\sqrt{D_{1}}\sqrt{n}\|\nabla
f(\bm{w}_{k,0})\|+\sqrt{n}L_{1}\sqrt{D_{0}})n\sqrt{d}C_{1}\eta_{k}$
$\displaystyle\overset{(\bullet)}{\leq}$
$\displaystyle\sqrt{\frac{2n^{2}}{\beta_{2}^{n}}}d(n^{2}L_{0}+n\sqrt{n}L_{1}\sqrt{D_{0}})C_{1}\eta_{k}^{2}+\eta_{k}^{2}d\sqrt{\frac{2n^{2}}{\beta_{2}^{n}}}L_{1}\sqrt{D_{1}}n\sqrt{n}\|\nabla
f(\bm{w}_{k,0})\|.$

Here Eq. ($\ast$) is due to Corollary 5, Eq. ($\circ$) is due to $f_{i}$ is
$(L_{0},L_{1})$-smooth, $\forall i$, and Eq. ($\bullet$) is due to Lemma 4.

② Tackling Term
$\sum_{l\in\mathbb{L}_{large}^{k}}\partial_{l}f(\bm{w}_{k,0})a_{l}^{2}$:

We have for any $l\in\mathbb{L}_{max}$,

$\displaystyle|\partial_{l}f(\bm{w}_{k,0})a_{l}^{2}|$ $\displaystyle\leq$
$\displaystyle\eta_{k}|\partial_{l}f(\bm{w}_{k,0})|\left(\left|\frac{1}{\sqrt{\bm{\nu}_{l,k,n-1}}}-\frac{1}{\sqrt{\bm{\nu}_{l,k,0}}}\right|\frac{|\bm{m}_{l,k,n-1}|}{1-\beta_{1}}+\sum_{i=0}^{n-2}\left|\frac{1}{\sqrt{\bm{\nu}_{l,k,i}}}-\frac{1}{\sqrt{\bm{\nu}_{l,k,0}}}\right||\bm{m}_{l,k,i}|\right.$
$\displaystyle-\left.\frac{\beta_{1}}{1-\beta_{1}}\left|\frac{1}{\sqrt{\bm{\nu}_{l,k-1,n-1}}}+\frac{1}{\sqrt{\bm{\nu}_{l,k,0}}}\right|{|\bm{m}_{l,k-1,n-1}|}\right)$
$\displaystyle\overset{(\star)}{\leq}$
$\displaystyle\eta_{k}g(\beta_{2})\frac{|\partial_{l}f(\bm{w}_{k,0})|}{\sqrt{\bm{\nu}_{l,k,0}}}\left(\frac{|\bm{m}_{l,k,n-1}|}{1-\beta_{1}}+\sum_{i=0}^{n-2}|\bm{m}_{l,k,i}|+\frac{\beta_{1}}{1-\beta_{1}}{|\bm{m}_{l,k-1,n-1}|}\right)$
$\displaystyle\overset{(\ast)}{\leq}$
$\displaystyle\eta_{k}g(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{|\partial_{l}f(\bm{w}_{k,0})|}{\sqrt{\bm{\nu}_{l,k,0}}}\left(\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|\right)$
$\displaystyle+\eta_{k}^{2}g(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{\sqrt{2}n}{\beta_{2}^{\frac{n}{2}}}\left(n+\frac{2\sqrt{2}\beta_{1}}{1-\beta_{1}}\right)C_{1}(L_{0}+L_{1}\sqrt{D_{0}})\sqrt{d}$
$\displaystyle+\eta_{k}^{2}g(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{\sqrt{2}n}{\beta_{2}^{\frac{n}{2}}}L_{1}C_{1}\sqrt{D_{1}}\sum_{j=0}^{n-1}\|\nabla
f(\bm{w}_{k,j})\|$
$\displaystyle+\eta_{k}g(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{\sqrt{2}n}{\beta_{2}^{\frac{n}{2}}}L_{1}C_{1}\sqrt{D_{1}}\sum_{t=1}^{k-1}\eta_{k-t}\sum_{j=0}^{n-1}\beta_{1}^{tn-1-j}\|\nabla
f(\bm{w}_{k-t,j})\|,$

where Inequality ($\star$) is due to Corollary 5, and $g(\beta_{2})$ is
defined in Lemma 5 , and Inequality $(\ast)$ is due to Lemma 8, by which we
have $\forall i\in\\{-1,\cdots,n-1\\}$

$\displaystyle|\bm{m}_{l,k,i}|\leq$
$\displaystyle\max_{i^{\prime}\in[n]}|\partial_{l}f_{i^{\prime}}(\bm{w}_{k,0})|+\left(n+\frac{2\sqrt{2}\beta_{1}}{1-\beta_{1}}\right)C_{1}(L_{0}+L_{1}\sqrt{D_{0}})\sqrt{d}\eta_{k}+L_{1}C_{1}\sqrt{D_{1}}\eta_{k}\sum_{j=0}^{n-1}\|\nabla
f(\bm{w}_{k,j})\|$
$\displaystyle+L_{1}C_{1}\sqrt{D_{1}}\sum_{t=1}^{k-1}\eta_{k-t}\sum_{j=0}^{n-1}\beta_{1}^{tn-1-j}\|\nabla
f(\bm{w}_{k-t,j})\|.$

Therefore, summing over $\mathbb{L}_{large}^{k}$ and $k$ leads to

$\displaystyle\sum_{k=1}^{T}\left|\sum_{l\in\mathbb{L}_{large}^{k}}\partial_{l}f(\bm{w}_{k,0})a_{l}^{2}\right|$
$\displaystyle\leq$
$\displaystyle\sum_{k=1}^{T}\sum_{l\in\mathbb{L}_{large}^{k}}\eta_{k}g(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{|\partial_{l}f(\bm{w}_{k,0})|}{\sqrt{\bm{\nu}_{l,k,0}}}\left(\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|\right)$
$\displaystyle+\sum_{k=1}^{T}\eta_{k}^{2}g(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{\sqrt{2}n}{\beta_{2}^{\frac{n}{2}}}\left(n+\frac{2\sqrt{2}\beta_{1}}{1-\beta_{1}}\right)C_{1}(L_{0}+L_{1}\sqrt{D_{0}})d\sqrt{d}$
$\displaystyle+dg(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{\sqrt{2}n}{\beta_{2}^{\frac{n}{2}}}L_{1}C_{1}\sqrt{D_{1}}\sum_{k=1}^{T}\eta_{k}^{2}\sum_{j=0}^{n-1}\|\nabla
f(\bm{w}_{k,j})\|$
$\displaystyle+dg(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{\sqrt{2}n}{\beta_{2}^{\frac{n}{2}}}L_{1}C_{1}\sqrt{D_{1}}\sum_{k=1}^{T}\eta_{k}\sum_{t=1}^{k-1}\eta_{k-t}\sum_{j=0}^{n-1}\beta_{1}^{(t-1)n}\|\nabla
f(\bm{w}_{k-t,j})\|$ $\displaystyle\leq$
$\displaystyle\sum_{k=1}^{T}\sum_{l\in\mathbb{L}_{large}^{k}}\eta_{k}g(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{|\partial_{l}f(\bm{w}_{k,0})|}{\sqrt{\bm{\nu}_{l,k,0}}}\left(\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|\right)$
$\displaystyle+g(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{\sqrt{2}n}{\beta_{2}^{\frac{n}{2}}}\left(n+\frac{2\sqrt{2}\beta_{1}}{1-\beta_{1}}\right)C_{1}(L_{0}+L_{1}\sqrt{D_{0}})d\sqrt{d}\eta_{1}(1+\ln
T)$
$\displaystyle+dg(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{\sqrt{2}n}{\beta_{2}^{\frac{n}{2}}}L_{1}C_{1}\sqrt{D_{1}}\left(1+\frac{1}{1-\beta_{2}^{n}}\right)\sum_{k=1}^{T}\eta_{k}^{2}\sum_{j=0}^{n-1}\|\nabla
f(\bm{w}_{k,j})\|$ $\displaystyle\overset{(\star)}{\leq}$
$\displaystyle\sum_{k=1}^{T}\sum_{l\in\mathbb{L}_{large}^{k}}\eta_{k}g(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{|\partial_{l}f(\bm{w}_{k,0})|}{\sqrt{\bm{\nu}_{l,k,0}}}\left(\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|\right)$
$\displaystyle+g(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{\sqrt{2}n}{\beta_{2}^{\frac{n}{2}}}\left(n+\frac{2\sqrt{2}\beta_{1}}{1-\beta_{1}}\right)C_{1}(L_{0}+L_{1}\sqrt{D_{0}})d\sqrt{d}\eta_{1}(1+\ln
T)$
$\displaystyle+dg(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{\sqrt{2}n}{\beta_{2}^{\frac{n}{2}}}L_{1}C_{1}\sqrt{D_{1}}\left(1+\frac{1}{1-\beta_{2}^{n}}\right)$
$\displaystyle\cdot\sum_{k=1}^{T}\eta_{k}^{2}\sum_{j=0}^{n-1}\left((1+n\sqrt{d}C_{1}\eta_{1}L_{1}\sqrt{n}\sqrt{D_{1}})\|\nabla
f(\bm{w}_{k,0})\|+\left(nL_{0}+L_{1}\sqrt{n}\sqrt{D_{0}}\right)n\sqrt{d}C_{1}\eta_{k}\right)$
$\displaystyle\leq$
$\displaystyle\sum_{k=1}^{T}\sum_{l\in\mathbb{L}_{large}^{k}}\eta_{k}g(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{|\partial_{l}f(\bm{w}_{k,0})|}{\sqrt{\bm{\nu}_{l,k,0}}}\left(\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|\right)$
$\displaystyle+g(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{\sqrt{2}n}{\beta_{2}^{\frac{n}{2}}}\left(n+\frac{2\sqrt{2}\beta_{1}}{1-\beta_{1}}\right)C_{1}(L_{0}+L_{1}\sqrt{D_{0}})d\sqrt{d}\eta^{2}_{1}(1+\ln
T)$
$\displaystyle+dg(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{\sqrt{2}n}{\beta_{2}^{\frac{n}{2}}}L_{1}C_{1}\sqrt{D_{1}}\left(1+\frac{1}{1-\beta_{2}^{n}}\right)(n+n^{\frac{5}{2}}\sqrt{d}C_{1}\eta_{1}L_{1}\sqrt{D_{1}})\sum_{k=1}^{T}\eta_{k}^{2}\|\nabla
f(\bm{w}_{k,0})\|$
$\displaystyle+3dg(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{\sqrt{2}n}{\beta_{2}^{\frac{n}{2}}}L_{1}C_{1}\sqrt{D_{1}}\left(1+\frac{1}{1-\beta_{2}^{n}}\right)n\left(nL_{0}+L_{1}\sqrt{n}\sqrt{D_{0}}\right)n\sqrt{d}C_{1}\eta_{1}^{3}.$

where Inequality $(\star)$ is due to Lemma 6.

③ Tackling Term
$\sum_{l\in\mathbb{L}_{large}^{k}}\partial_{l}f(\bm{w}_{k,0})a_{l}^{3}$:

For any $l\in\mathbb{L}_{large}^{k}$,

$\displaystyle|\partial_{l}f(\bm{w}_{k,0})a_{l}^{3}|\leq\frac{\beta_{1}}{1-\beta_{1}}|\eta_{k-1}-\eta_{k}|\frac{1}{\sqrt{\bm{\nu}_{l,k-1,n-1}}}|\bm{m}_{l,k-1,n-1}||\partial_{l}f(\bm{w}_{k,0})|$
$\displaystyle\leq$
$\displaystyle\frac{\beta_{1}\eta_{1}}{(1-\beta_{1})}\frac{1}{\sqrt{k}\sqrt{k-1}(\sqrt{k}+\sqrt{k-1})}C_{1}|\partial_{l}f(\bm{w}_{k,0})|$
$\displaystyle=$
$\displaystyle\frac{\beta_{1}\eta_{k}}{(1-\beta_{1})}\frac{1}{\sqrt{k-1}(\sqrt{k}+\sqrt{k-1})}C_{1}|\partial_{l}f(\bm{w}_{k,0})|.$

Summing over $k$ and $\mathbb{L}_{large}^{k}$ then leads to

$\displaystyle\sum_{k=1}^{T}\sum_{l\in\mathbb{L}_{large}^{k}}|\partial_{l}f(\bm{w}_{k,0})a_{l}^{3}|\leq\frac{\beta_{1}}{(1-\beta_{1})}\sum_{k=1}^{T}\sum_{l\in\mathbb{L}_{large}^{k}}\frac{\eta_{k}}{\sqrt{k-1}(\sqrt{k}+\sqrt{k-1})}C_{1}|\partial_{l}f(\bm{w}_{k,0})|$
$\displaystyle\leq$ $\displaystyle
2\frac{\beta_{1}}{(1-\beta_{1})\eta_{1}}\sqrt{d}C_{1}\sum_{k=1}^{T}\eta_{k}^{2}\|\nabla
f(\bm{w}_{k,0})\|.$

Put ①, ②, and ③ together and applying the notations in Eq. (10), we then have

$\displaystyle\sum_{k=1}^{T}\sum_{l\in\mathbb{L}_{large}^{k}}\partial_{l}f(\bm{w}_{k,0})(\bm{u}_{l,k+1}-\bm{u}_{l,k})$
$\displaystyle\leq$
$\displaystyle-\sum_{k=1}^{T}\sum_{l\in\mathbb{L}_{large}^{k}}\frac{\eta_{k}}{\sqrt{\bm{\nu}_{l,k,0}}}\partial_{l}f(\bm{w}_{k,0})^{2}+\sum_{k=1}^{T}\sum_{l\in\mathbb{L}_{large}^{k}}\eta_{k}g(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{|\partial_{l}f(\bm{w}_{k,0})|}{\sqrt{\bm{\nu}_{l,k,0}}}\left(\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|\right)$
$\displaystyle+C_{8}\sum_{k=1}^{T}\eta_{k}^{2}\|\nabla
f(\bm{w}_{k,0})\|+C_{9}\ln T+C_{10}.$ (17)

We then focus on the first two terms of the RHS of the above inequality.
Specifically, we have $\forall k\geq 1$,

$\displaystyle\sum_{l\in\mathbb{L}_{large}^{k}}\frac{\eta_{k}\partial_{l}f(\bm{w}_{k,0})^{2}}{\sqrt{\bm{\nu}_{l,k,0}}+\xi}-\sum_{l\in\mathbb{L}_{large}^{k}}\eta_{k}g(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{|\partial_{l}f(\bm{w}_{k,0})|}{\sqrt{\bm{\nu}_{l,k,0}}+\xi}\left(\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|\right)$
$\displaystyle\overset{(\star)}{\geq}$
$\displaystyle\sum_{l\in\mathbb{L}_{large}^{k}}\frac{\eta_{k}\partial_{l}f(\bm{w}_{k,0})^{2}}{\sqrt{\bm{\nu}_{l,k,0}}+\xi}-\sum_{l\in\mathbb{L}_{large}^{k}}\eta_{k}g(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{|\partial_{l}f(\bm{w}_{k,0})|}{\sqrt{\frac{\beta_{2}^{n}}{2n}}\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|+\xi}\left(\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|\right)$
$\displaystyle\geq$
$\displaystyle\sum_{l\in\mathbb{L}_{large}^{k}}\frac{\eta_{k}\partial_{l}f(\bm{w}_{k,0})^{2}}{2\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|+\xi}-\sum_{l\in\mathbb{L}_{large}^{k}}\eta_{k}g(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{|\partial_{l}f(\bm{w}_{k,0})|}{\sqrt{\frac{\beta_{2}^{n}}{2n}}\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|+\xi}\left(\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|\right)$
$\displaystyle\overset{(\circ)}{=}$
$\displaystyle\sum_{l\in[d]}\frac{\eta_{k}\partial_{l}f(\bm{w}_{k,0})^{2}}{2\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|+\xi}-\sum_{l\in\mathbb{L}_{large}^{k}}\eta_{k}g(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{|\partial_{l}f(\bm{w}_{k,0})|}{\sqrt{\frac{\beta_{2}^{n}}{2n}}\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|+\xi}\left(\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|\right)$
$\displaystyle-\frac{nd\eta_{k}}{2}\left(C_{3}\eta_{k}+C_{4}\sum_{r=1}^{k-1}\sqrt{\beta_{2}}^{(r-1)n}\eta_{k-r}\sum_{j=0}^{n-1}\|\nabla
f(\bm{w}_{k-r,j})\|+C_{4}n\sum_{r=1}^{k-1}\sqrt{\beta_{2}}^{(r-1)n}\eta_{k-r}+\eta_{k}C_{4}\sum_{j=0}^{n-1}\|\nabla
f(\bm{w}_{k,j})\|\right),$

where Inequality $(\star)$ is due to Corollary 5 and Equality $(\circ)$ is due
to

$\displaystyle\sum_{l\in\mathbb{L}_{small}^{k}}\frac{\eta_{k}\partial_{l}f(\bm{w}_{k,0})^{2}}{2\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|+\xi}\leq\sum_{l\in\mathbb{L}_{small}^{k}}\frac{\eta_{k}\partial_{l}f(\bm{w}_{k,0})^{2}}{2\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|+\xi}\leq\frac{n}{2}\eta_{k}\sum_{l\in\mathbb{L}_{small}^{k}}\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|$
$\displaystyle\leq$
$\displaystyle\frac{nd\eta_{k}}{2}\left(C_{3}\eta_{k}+C_{4}\sum_{r=1}^{k-1}\sqrt{\beta_{2}}^{(r-1)n}\eta_{k-r}\sum_{j=0}^{n-1}\|\nabla
f(\bm{w}_{k-r,j})\|+C_{4}n\sum_{r=1}^{k-1}\sqrt{\beta_{2}}^{(r-1)n}\eta_{k-r}+\eta_{k}C_{4}\sum_{j=0}^{n-1}\|\nabla
f(\bm{w}_{k,j})\|\right).$

Summing the both sides of the above inequality then leads to

$\displaystyle\sum_{k=1}^{T}\sum_{l\in\mathbb{L}_{large}^{k}}\frac{\eta_{k}\partial_{l}f(\bm{w}_{k,0})^{2}}{\sqrt{\bm{\nu}_{l,k,0}}+\xi}-\sum_{k=1}^{T}\sum_{l\in\mathbb{L}_{large}^{k}}\eta_{k}g(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{|\partial_{l}f(\bm{w}_{k,0})|}{\sqrt{\bm{\nu}_{l,k,0}}+\xi}\left(\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|\right)$
$\displaystyle\geq$
$\displaystyle\sum_{k=1}^{T}\sum_{l\in[d]}\frac{\eta_{k}\partial_{l}f(\bm{w}_{k,0})^{2}}{2\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|+\xi}$
$\displaystyle-\sum_{k=1}^{T}\sum_{l\in\mathbb{L}_{large}^{k}}\eta_{k}g(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{|\partial_{l}f(\bm{w}_{k,0})|}{\sqrt{\frac{\beta_{2}^{n}}{2n}}\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|+\xi}\left(\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|\right)$
$\displaystyle-\sum_{k=1}^{T}\frac{nd\eta_{k}}{2}\left(C_{3}\eta_{k}+C_{4}\sum_{r=1}^{k-1}\sqrt{\beta_{2}}^{(r-1)n}\eta_{k-r}\sum_{j=0}^{n-1}\|\nabla
f(\bm{w}_{k-r,j})\|+C_{4}n\sum_{r=1}^{k-1}\sqrt{\beta_{2}}^{(r-1)n}\eta_{k-r}+\eta_{k}C_{4}\sum_{j=0}^{n-1}\|\nabla
f(\bm{w}_{k,j})\|\right)$ $\displaystyle\geq$
$\displaystyle\sum_{k=1}^{T}\sum_{l\in[d]}\frac{\eta_{k}\partial_{l}f(\bm{w}_{k,0})^{2}}{2\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|+\xi}$
$\displaystyle-\sum_{k=1}^{T}\sum_{l\in\mathbb{L}_{large}^{k}}\eta_{k}g(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\frac{|\partial_{l}f(\bm{w}_{k,0})|}{\sqrt{\frac{\beta_{2}^{n}}{2n}}\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|+\xi}\left(\max_{i\in[n]}|\partial_{l}f_{i}(\bm{w}_{k,0})|\right)$
$\displaystyle-\frac{1}{2}\left(C_{5}\sum_{k=1}^{T}\eta_{k}^{2}\|\nabla
f(\bm{w}_{k,0})\|+C_{6}\ln T+C_{7}\right).$

Applying the above inequality back to Eq. (17), the proof is completed. ∎

The following lemma will be useful when translating $\langle\nabla
f(\bm{w}_{k,0}),\frac{1}{\sqrt{\bm{\nu}_{k,0}}}\odot\nabla
f(\bm{w}_{k,0})\rangle$ to $\min\left\\{\frac{\|\nabla
f(\bm{w}_{k,0})\|}{\sqrt{D_{1}}},\frac{\|\nabla
f(\bm{w}_{k,0})\|^{2}}{\sqrt{D_{0}}}\right\\}$.

######  Lemma 12.

Let all conditions in Theorem 1 hold. Then, either there exists a iteration
$k\in[T]$, such that either

$\|\nabla f(\bm{w}_{k,0})\|\leq
2\sqrt{d}(2\sqrt{2}+1)\sqrt{D_{0}}g(\beta_{2})\left(n-1+\frac{1+\beta_{1}}{1-\beta_{1}}\right)\sqrt{\frac{2n}{\beta_{2}^{n}}},$

or for all iteration $k\in[1,T]$, we have that