# On the Convergence of Adam under Non-uniform Smoothness: Separability from
SGDM and Beyond

Bohan Wang  Huishuai Zhang  Qi Meng  Ruoyu Sun  Zhi-Ming Ma  Wei Chen

###### Abstract

This paper aims to clearly distinguish between Stochastic Gradient Descent
with Momentum (SGDM) and Adam in terms of their convergence rates. We
demonstrate that Adam achieves a faster convergence compared to SGDM under the
condition of non-uniformly bounded smoothness. Our findings reveal that: (1)
in deterministic environments, Adam can attain the known lower bound for the
convergence rate of deterministic first-order optimizers, whereas the
convergence rate of Gradient Descent with Momentum (GDM) has higher order
dependence on the initial function value; (2) in stochastic setting, Adam’s
convergence rate upper bound matches the lower bounds of stochastic first-
order optimizers, considering both the initial function value and the final
error, whereas there are instances where SGDM fails to converge with any
learning rate. These insights distinctly differentiate Adam and SGDM regarding
their convergence rates. Additionally, by introducing a novel stopping-time
based technique, we further prove that if we consider the minimum gradient
norm during iterations, the corresponding convergence rate can match the lower
bounds across all problem hyperparameters. The technique can also help proving
that Adam with a specific hyperparameter scheduler is parameter-agnostic,
which hence can be of independent interest.

Machine Learning, ICML

##  1 Introduction

Among various optimization techniques, the Adam optimizer (Kingma & Ba, 2014;
Loshchilov & Hutter, 2019) stands out due to its empirical success in a wide
range of deep learning applications, especially for pre-training large
foundation models with enormous data (Touvron et al., 2023; Brown et al.,
2020; Zhang et al., 2022a; Rae et al., 2021; Chowdhery et al., 2022; Du et
al., 2021). This popularity of Adam can be attributed to its adaptive learning
rate mechanism, which smartly adjusts the step size for each parameter,
allowing flexible and robust learning rate choices. Adam’s versatility is
further highlighted by its consistent performance in training various kinds of
models, making it a preferred optimizer in both academic and industrial
settings (Schneider et al., 2022). Its empirical success extends beyond
standard benchmarks to real-world challenges, where it often delivers state-
of-the-art results. This track record solidifies Adam’s position as a
fundamental tool for deep learning practitioners.

Exploring the theoretical foundations of the Adam optimizer, particularly why
it often outperforms traditional optimizers like Stochastic Gradient Descent
with Momentum (SGDM), is an intriguing yet complex task. Understanding Adam’s
convergence behavior is challenging, especially in settings defined by
standard convergence rate analysis. In these settings, assumptions include
uniformly bounded smoothness and finite gradient noise variance. Current
research indicates that under these conditions, SGDM can attain the lower
bound of the convergence rate for all first-order optimizers (Carmon et al.,
2017). This finding implies that, theoretically, Adam’s convergence rate
should not exceed that of SGDM. This theoretical result contrasts with
practical observations where Adam frequently excels, presenting a fascinating
challenge for researchers. It highlights the need for more refined theoretical
models that can bridge the gap between Adam’s empirical success and its
theoretical understanding.

Recent research by Zhang et al. (2019) has provided valuable insights into the
complexity of neural network optimization, particularly challenging the
assumption of uniform bounded smoothness. Their observations indicate that
smoothness often varies, showing a positive correlation with the norm of the
gradient and experiencing considerable fluctuations during the optimization
process. Building on this, they introduce the $(L_{0},L_{1})$-smooth condition
(detailed in our Assumption 1), which posits that local smoothness can be
bounded in relation to the gradient norm. This concept presents an exciting
opportunity to theoretically demonstrate that Adam could potentially converge
faster than SGDM. However, even in the relatively simpler deterministic
settings, no study has yet conclusively shown this to be the case.

To effectively compare the convergence rates of Adam and Stochastic Gradient
Descent with Momentum (SGDM), it’s essential to establish an upper bound on
Adam’s convergence rate and a lower bound for SGDM, and then prove Adam’s
superiority. This endeavor faces several challenges. First, the known lower
bound for SGDM’s convergence rate is only available in deterministic settings
without momentum (Zhang et al., 2019; Crawshaw et al., 2022). Moreover, this
result is based on a scenario where the counter-example objective function is
selected after fixing the learning rate. This procedure deviates from more
common practices where the learning rate is adjusted after defining the
objective function (Drori & Shamir, 2020; Carmon et al., 2017; Arjevani et
al., 2022), casting doubts on the standard applicability of this lower bound.
Secondly, for Adam, the current assumptions required to derive an upper bound
for its convergence rate are quite strict. These include assumptions like
bounded adaptive learning rates or deterministically bounded noise (Wang et
al., 2022; Li et al., 2023a). However, even under these constraints, the
convergence rates obtained for Adam are weaker than those of algorithms like
clipped SGDM (Zhang et al., 2019).

These complexities hinder a straightforward comparison between the convergence
rates of Adam and SGDM, highlighting a significant gap in the theoretical
understanding that remains to be bridged.

Our contributions. In this paper, we aim to bridge the gap and summarize our
contributions as follows.

  * •

We separate the convergence rate of Adam and SGDM under $(L_{0},L_{1})$-smooth
condition both in the deterministic setting and in the stochastic setting.

    * –

In the deterministic setting, for the first time, we prove that under the
$(L_{0},L_{1})$-smooth condition, the convergence rate of the Adam optimizer
can match the existing lower bound for first-order deterministic optimizers,
up to numerical constants. Additionally, we establish a new lower bound for
the convergence rate of GDM, where one is allowed to tune the learning rate
and the momentum coefficient after the problem is fixed. The lower bound
exhibits a higher order dependence on the initial function value gap compared
to the upper bound of Adam. This distinction clearly separates Adam and GDM
for the deterministic setting.

    * –

In the stochastic setting, for the first time, we prove that under the
$(L_{0},L_{1})$-smooth condition, the convergence rate of Adam matches the
existing lower bound for first-order stochastic optimizers regarding the
initial function value $f(\bm{w}_{1})-f^{*}$ and the final error
$\varepsilon$. In contrast, counterexamples exist where SGDM fails to
converge, irrespective of the learning rate and momentum coefficient. These
findings distinctly separate the convergence properties of Adam and SGDM in
stochastic settings.

  * •

With the aid of a novel stopping time based technique, we further demonstrate
that the convergence rate of minimum error point of Adam can match the lower
bound across all problem hyperparameters. We demonstrate that such a technique
can be of independent interest by proving that Adam with specific scheduler is
parameter-agnostic based on the stopping time.

##  2 Related Works

Convergence analysis under non-uniform smoothness. Observations from empirical
studies on deep neural network training indicate that local smoothness can
vary significantly throughout the optimization process. In response to this,
Zhang et al. (2019) introduced the $(L_{0},L_{1})$-smooth condition, which
posits that local smoothness can be bounded by a linear function of the
gradient norm. Subsequent works have extended this concept by generalizing the
linear function to polynomials (Chen et al., 2023; Li et al., 2023a), or to
more general functions (Mei et al., 2021). Under non-uniform smoothness,
convergence properties of various optimizers have been studied. For instance,
upper bounds on the convergence rate have been established for optimizers such
as Clipped SGDM (Zhang et al., 2020), sign-based optimizers (Jin et al., 2021;
Hübler et al., 2023; Sun et al., 2023), AdaGrad (Faw et al., 2023; Wang et
al., 2023b), variance-reduction methods (Reisizadeh et al., 2023; Chen et al.,
2023), and trust-region methods (Xie et al., 2023). However, research on lower
bounds has been comparatively limited, with results primarily focusing on
Gradient Descent.

Convergence analysis of Adam. The development of convergence analysis for Adam
has been quite tortuous. While Adam was originally proposed with a convergence
guarantee (Kingma & Ba, 2014), subsequent analysis by Reddi et al. (2018)
pointed out flaws in this initial analysis and provided counterexamples
claiming that Adam could fail to converge. Only recently, Shi et al. (2021)
and Zhang et al. (2022b) have shown that the counterexamples in Reddi et al.
(2018) only rule out the possibility that Adam can converge problem-
agnostically, and it is still possible that Adam can converge with problem-
dependent hyperparameters.

So far, several works have established the convergence of Adam under the
$L$-smooth condition. Zaheer et al. (2018) proved that Adam without momentum
can converge to the neighborhood of stationary points by additionally assuming
that $\lambda$ is large. De et al. (2018) showed that Adam without momentum
can converge to stationary points but under the strong assumption that the
sign of gradients does not change during the optimization. Zou et al. (2019),
Défossez et al. (2022), and Guo et al. (2021) derived the convergence of Adam
by assuming the stochastic gradient is bounded. Shi et al. (2021) and Zhang et
al. (2022b) characterized the convergence of random-reshuffling Adam but
suffer from sub-optimal rates. He et al. (2023) studied the non-ergodic
convergence of Adam under a bounded gradient assumption, while Hong & Lin
(2023) provided high-probability guarantees for Adam under a deterministically
bounded noise assumption. A concurrent work by Wang et al. (2023a) shows that
Adam can achieve the lower bound of first-order optimizers with respect to the
final error $\varepsilon$ under standard assumptions, but it is unknown
whether Adam can match the lower bound with respect to other problem
specifics.

On the other hand, closely related to our work, there are only two works
studying the convergence of Adam under non-uniform smoothness (Wang et al.,
2022; Li et al., 2023a), both with restricted assumptions and results. We will
provide a detailed discussion in Section 4.

Parameter-agnostic optimization. The term ”parameter-agnostic” implies that
the optimizer is capable of converging without the need for extensive
hyperparameter tuning or detailed knowledge of the task characteristics.
Designing parameter-agnostic or parameter-free optimizers is a significant
challenge, as it can help avoid the extensive cost associated with
hyperparameter search. Existing works on parameter-agnostic optimization can
be categorized into several streams based on the settings they are predicated
upon. In the deterministic offline setting, it is widely acknowledged that GD
is not parameter-agnostic, even under an $L$-smooth condition (Nesterov et
al., 2018). However, this can be rectified by combining the GD with the
Backtracking Line Search technique (Armijo, 1966). In the stochastic offline
setting, under the $L$-smooth condition, multiple algorithms have been shown
to be parameter-agnostic (Yang et al., 2023; Ward et al., 2020; Faw et al.,
2022; Wang et al., 2023b; Cutkosky & Mehta, 2020). More recently, Hübler et
al. (2023) demonstrated that Normalized-SGDM can be parameter-agnostic even
under an $(L_{0},L_{1})$-smooth condition. In the realm of online convex
optimization, Orabona & Pál (2016); Orabona & Tommasi (2017) have shown there
exist parameter-free algorithms achieving optimal dependence regarding not
only the final error but also other problem specifics.

##  3 Preliminary

Notations. In this paper, we will use asymptotic notations
$\mathcal{O},\Omega,\Theta$ to respectively denote asymptotically smaller,
larger , and equivalent. We also use
$\tilde{\mathcal{O}},\tilde{\Omega},\tilde{\Theta}$ to indicate that there is
logarithmic factor hidden. We denote ${\mathcal{F}}_{t}$ as the filter given
by $\bm{w}_{1},\cdots,\bm{w}_{t}$.

Problem and Algorithm. We study the unconstrained minimization problem
$\min_{\bm{w}}f(\bm{w})$. We present the psedo-code of Adam as follows.

Algorithm 1 Adam Optimizer

Input: Stochastic oracle $\bm{O}$, learning rate $\eta>0$, initial point
$\bm{w}_{1}\in\mathbb{R}^{d}$, initial conditioner
$\bm{\nu}_{0}\in\mathbb{R}^{+}$, initial momentum $\bm{m}_{0}$, momentum
parameter $\beta_{1}$, conditioner parameter $\beta_{2}$, number of epoch $T$

for $t=1$ to $T$ do

Generate a random $z_{t}$, and query stochastic oracle
$\bm{g}_{t}=\bm{O}_{f}(\bm{w}_{t},z_{t})$

Calculate
$\bm{\nu}_{t}=\beta_{2}\bm{\nu}_{t-1}+(1-\beta_{2})\|\bm{g}_{t}\|^{2}$

Calculate $\bm{m}_{t}=\beta_{1}\bm{m}_{t-1}+(1-\beta_{1})\bm{g}_{t}$

Update
$\bm{w}_{t+1}=\bm{w}_{t}-\eta\frac{1}{\lambda+\sqrt{\bm{\nu}_{t}}}\bm{m}_{t}$

end for

In our paper, we present a slightly altered version of the Adam optimizer as
delineated in Algorithm 1, diverging from the canonical form described by
(Kingma & Ba, 2014). We assert that these modifications are implemented not to
undermine the generality of the algorithm but to facilitate more streamlined
proofs. Furthermore, our analysis retains applicability to the conventional
Adam algorithm, largely following the same approach, albeit with a more
elaborate proof process. Specifically, our first modification involves the
omission of the bias-correction factors $1-\beta_{1}^{t}$ and
$1-\beta_{2}^{t}$ from the first and second momentum terms, respectively. It
is important to note that incorporating bias correction would not alter the
convergence rate, as these terms approach unity at an exponential rate, thus
having a negligible impact on convergence.

Our second adjustment pertains to adopting a scalar-based adaptive learning
rate, in contrast to the per-coordinate modification utilized in the typical
Adam algorithm. Employing a scalar—or ”norm”—version of adaptive optimizers is
a recognized simplification strategy in the analysis of adaptive optimizers,
as evidenced by literature such as (Xing et al., 2021; Faw et al., 2022, 2023;
Wang et al., 2023b). Our proof is readily adaptable to the per-coordinate
version by entailing a separate analysis for each dimension 111It is worth
mentioning that the convergence rate for the per-coordinate Adam is subject to
the dimensionality $d$. Addressing the challenge of decoupling the convergence
rate of per-coordinate adaptive optimizers from dimensionality remains an
unresolved issue, one that we acknowledge but reserve for future
investigation..

We would like to highlight that all the analysis in this paper is for
$\lambda=0$. This is because $\lambda=0$ means we do not require the adaptive
learning rate to be upper bounded (a restrictive assumption in existing works
(Li et al., 2023a; Guo et al., 2021)) and is most challenging. The proof can
be immediately extended to $\lambda>0$ without any modification.

Meanwhile, we briefly state the SGDM optimizer as follows: with initial point
$\bm{w}_{1}$ and initial momentum $\bm{m}_{0}$, the update of $t$-th iteration
of SGDM is given by

$\displaystyle\bm{m}_{t}=\beta\bm{m}_{t-1}+(1-\beta)\bm{g}_{t},\bm{w}_{t+1}=\bm{w}_{t}-\eta\bm{m}_{t}.$

Assumptions. In this paper, all the analyses are established under the
following two standard assumptions.

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

We assume $f$ is differentiable and lower bounded, and there exist non-
negative constants $L_{0},L_{1}>0$, 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(\bm{w}_{1})-\nabla f(\bm{w}_{2})\|\leq(L_{0}+L_{1}\|\nabla
f(\bm{w}_{1})\|)\|\bm{w}_{1}-\bm{w}_{2}\|.$

######  Assumption 2 (Affine noise variance).

We assume that the stochastic noise $\bm{g}_{t}$ is unbiased, i.e.,
$\mathbb{E}^{|\mathcal{F}_{t}}\bm{g}_{t}=\bm{G}_{t}$. We further assume
$\bm{g}_{t}$ has affine variance, i.e., there exists $\sigma_{0}\geq
0,\sigma_{1}\geq 1$,
$\mathbb{E}^{|{\mathcal{F}}_{t}}[\|\bm{g}_{t}\|^{2}]\leq\sigma_{0}^{2}+\sigma_{1}^{2}\|\nabla
f(\bm{w}_{t})\|^{2}$.

Assumption 1 is a more general form of $(L_{0},L_{1})$-smooth condition and is
equivalent to the Hessian-bound form (Zhang et al., 2019) when Hessian exists.
Assumption 2 is one of the weakest assumptions on the noise in existing
literature, and generalizes bounded variance assumption (Li et al., 2023b),
bounded gradient assumption (Défossez et al., 2022), bounded noise assumption
(Li et al., 2023a).

##  4 Separating the convergence rates of Adam and (S)GD

In this section, we elucidate the disparate convergence rates of Adam and
(S)GD under Assumptions 1 and 2, examining both deterministic and stochastic
settings. We commence with the deterministic scenario before delving into the
stochastic complexities.

###  4.1 Analysis for the deterministic setting

As discussed in the introduction section, to discern the differential
convergence rates of deterministic Adam and GD, it is necessary to establish
not only Adam’s upper bound but also GD’s lower bound, given a consistent set
of assumptions. Crucially, these bounds must be sufficiently tight to ensure
that Adam’s upper bound is indeed the lesser. To date, only a couple of
studies have addressed the convergence of deterministic Adam. The first,
referenced in (Wang et al., 2022), indicates a convergence rate of
$\mathcal{O}(\frac{(f(\bm{w}_{1})-f^{*})^{2}}{\varepsilon^{4}})$, which is
sub-optimal compared to the classical deterministic rate of
$\mathcal{O}(\frac{f(\bm{w}_{1})-f^{*}}{\varepsilon^{2}})$ (Zhang et al.,
2019, 2020) regarding both final error $\varepsilon$ and the initial function
value gap $(f(\bm{w}_{1})-f^{*})$. The second study, (Li et al., 2023a),
presents a convergence rate that depends polynomially on $\frac{1}{\lambda}$,
where $\lambda$ is the small constant introduced to prevent the adaptive
learning rate from becoming infinity. Therefore, their result is only non-
vacuous when $\lambda$ is large, which deviates from practical settings.
Additionally, their bound exhibits an exaggerated dependency on the initial
function value gap, yielding $\min_{t\in[T]}\|\nabla
f(\bm{w}_{t})\|=\mathcal{O}(\frac{(f(\bm{w}_{1})-f^{*})^{3}}{\varepsilon^{2}})$.
As we will see later, such dependencies create upper bounds that surpass the
lower bounds of GD, making them unable to serve our purpose. To overcome these
limitations and accurately assess the performance of deterministic Adam, we
propose a new theorem that establishes an improved convergence rate for
deterministic Adam.

An upper bound for the convergence rate of deterministic Adam.

######  Theorem 1 (Informal).

Let Assumption 1 hold. Then, $\forall\beta_{1},\beta_{2}\geq 0$ satisfying
$\beta_{1}^{2}<\beta_{2}<1$, $\lambda=0$, and
$\varepsilon=\mathcal{O}(L_{0}/L_{1})$, if
$T\geq\Theta\left(\frac{L_{0}(f(\bm{w}_{1})-f^{*})}{\varepsilon^{2}}\right)$,
then Algorithm 1 satisfies

$\frac{1}{T}\sum_{t=1}^{T}\|\nabla f(\bm{w}_{t})\|\leq\varepsilon.$

###### Proof.

Please see Appendix B.1 for the formal statement of theorem and the proof. ∎

Our result offers a tighter bound than those presented in prior studies (Wang
et al., 2022; Li et al., 2023a). It is noteworthy that under the uniform
smoothness constraint—where the objective function’s smoothness is capped at
$L$ (that is, when $L_{0}=L$ and $L_{1}=0$ as per Assumption 1, referred to as
the $L$-smooth condition in existing literature (Arjevani et al., 2022; Carmon
et al., 2017; Faw et al., 2022))—Assumption 1 is met with $L_{0}=L$ and any
$L_{1}\geq 0$. Consequently, the established lower bound for all first-order
optimizers (Carmon et al., 2017) pertaining to the $L$-smooth condition
inherently provides a lower bound for the $(L_{0},L_{1})$-smooth condition,
which is
$\Omega\left(\frac{\sqrt{L_{0}(f(\mathbf{w}_{1})-f^{*})}}{\sqrt{T}}\right)$.
This coincides with our upper bound up to numerical constants. Such
correspondence suggests that our proposed bound is, in fact, optimal.

Our proof strategy utilizes a distinctive Lyapunov function,
$f(\bm{w}_{t})+\frac{\beta_{1}}{2(1-\beta_{1})\sqrt[4]{\beta_{2}}}\eta\frac{||\bm{m}_{t-1}||^{2}}{\lambda+\sqrt{\bm{\nu}_{t-1}}}$,
which draws inspiration from the current analysis of Gradient Descent with
Momentum (GDM) under the $L$-smooth condition (Sun et al., 2019). However, we
have introduced significant modifications to accommodate the integration of an
adaptive learning rate. This carefully crafted Lyapunov function enables us to
effectively control the deviation between the momentum term and the current
gradient, even under $(L_{0},L_{1})$-smooth condition. Through this approach,
we successfully establish the final optimal bound.

######  Remark 1 (On the comparison with AdaGrad).

Our result also suffices to separate Adam from AdaGrad. It is important to
note that the convergence rate of AdaGrad under the $(L_{0},L_{1})$-smooth
condition in a deterministic setting, as reported in(Wang et al., 2023b), is
$\frac{(f(\bm{w}_{1})-f^{*})^{2}}{\varepsilon^{2}}$. This rate is outperformed
by that of Adam222The state-of-art rate of AdaGrad under
$(L_{0},L_{1})$-smooth condition and stochastic setting is
$\frac{(f(\bm{w}_{1})-f^{*})^{2}}{\varepsilon^{4}}$, which is also worse than
the rate of Adam established latter in Theorem 3.. In Appendix B.3, we show
that the rate in (Wang et al., 2023b) is tight by providing a counterexample.
The comparatively slower convergence rate of AdaGrad can be attributed to that
$(L_{0},L_{1})$-smooth condition demands the update norm to be bounded by
$\mathcal{O}(1)$ to prevent the local smoothness from exponentially
increasing. This, in turn, necessitates a learning rate of $\mathcal{O}(1)$.
However, the adaptive conditioner in AdaGrad, which accumulates over time,
causes the adaptive learning rate to become excessively small during later
training stages, resulting in reduced convergence speed. Conversely, Adam
utilizes an exponential moving average for its adaptive learning rate, which
prevents the conditioner from accumulating excessively. Consequently, Adam
does not suffer from the aforementioned issue.

A lower bound for the convergence rate of GDM

With Adam’s upper bound, we then move on to a lower bound for the convergence
rate of GDM. In fact, there has already been such lower bounds for GD in the
existing literature (Zhang et al., 2019; Crawshaw et al., 2022), which we
restate as follows:

######  Proposition 1 (Theorem 2, (Crawshaw et al., 2022)).

Fix $\varepsilon,L_{0},L_{1}$, and $\Delta_{1}$, with learning rate $\eta$,
there exists objective function $f$ satisfying $(L_{0},L_{1})$-smooth
condition and $f(\bm{w}_{1})-f^{*}=\Delta_{1}$, such that the minimum step $T$
of GD to achieve final error $\varepsilon$ (i.e., let
$\\{\bm{w}_{t}\\}_{t=1}^{\infty}$ be the iterates of GD, and
$T\triangleq\min\\{t:\|\nabla f(\bm{w}_{t})\|<\varepsilon\\}$) satisfies

$T=\tilde{\Omega}\left(\frac{L_{1}^{2}\Delta_{1}^{2}+L_{0}\Delta_{1}}{\varepsilon^{2}}\right).$

However, the proposition presents a limitation: the counter-example is chosen
after the learning rate has been determined. This approach is inconsistent
with standard practices, where hyperparameters are usually adjusted based on
the specific task, and deviates from conventional lower bounds (Carmon et al.,
2017; Arjevani et al., 2022) that offer assurances for optimally-tuned
hyperparameters. This type of result does not eliminate the possibility that,
if the learning rate were adjusted after selecting the objective function—as
is common practice—Gradient Descent (GD) could potentially achieve a markedly
faster convergence rate. This misalignment raises concerns about the
appropriateness of the proposition’s methodology. Moreover, this proposition
does not take momentum into account, a technique that is commonly employed in
conjunction with GD in practice.

To address these shortcomings, we introduce a new lower bound for GDM. This
lower bound is applicable under the standard practice of adjusting
hyperparameters after the objective function has been selected. Moreover, it
encompasses scenarios where momentum is incorporated.

######  Theorem 2 (Informal).

Fixing $\varepsilon,L_{0},L_{1}$, and $\Delta_{1}$, there exists an objective
function $f$ satisfying $(L_{0},L_{1})$-smooth condition and
$f(\bm{w}_{1})-f^{*}=\Delta_{1}$, such that for any learning rate $\eta>0$ and
$\beta\in[0,1]$, the minimum step $T$ of GDM to achieve final error
$\varepsilon$ satisfies

$T=\tilde{\Omega}\left(\frac{L_{1}^{2}\Delta_{1}^{2}+L_{0}\Delta_{1}}{\varepsilon^{2}}\right).$

###### Proof.

Please see Appendix B.2 for the formal statement of theorem and the proof. ∎

It should be noticed in the above theorem, the hyperparameters (i.e., the
learning rate and the momentum coefficient) are chosen after the objective
function is determined, which agrees with practice and the settings of common
lower bounds, and overcomes the shortcoming of Proposition 1. Moreover, as
shown in Zhang et al. (2019), it is easy to prove that the upper bound of GD’s
convergence rate is also
$\mathcal{O}\left(\frac{L_{1}^{2}\Delta_{1}^{2}+L_{0}\Delta_{1}}{\varepsilon^{2}}\right)$,
which indicates such a lower bound is optimal.

The proof addresses two primary challenges outlined above. The first challenge
involves handling momentum. To tackle this, we extend the counterexample
provided in Proposition 1 for cases where the momentum coefficient $\beta$ is
small. Additionally, we introduce a new counterexample for situations with a
large $\beta$, demonstrating how large momentum can bias the optimization
process and decelerate convergence. The second challenge is how to derive a
universal counterexample such that every hyperparameter setting will lead to
slow convergence. We overcome this by a simple but effective trick: we
independently put counterexamples for different hyperparameters in Proposition
1 over different coordinates and make it a whole counterexample. Therefore,
for different hyperparameters, there will be at least one coordinate converge
slowly, which leads to the final result.

Separating deterministic Adam and GDM. Upon careful examination of Theorem 1
and Theorem 2, it becomes apparent that the convergence rate of GDM is
inferior to that of Adam since
$\frac{\sum_{t=1}^{T}\|\bm{G}_{t}\|}{T}\geq\min_{t\in[T]}\|\bm{G}_{t}\|$.
Notably, GDM exhibits a more pronounced dependency on the initial function
value gap in comparison to Adam. This implies that with a sufficiently poor
initial point, the convergence of GDM can be significantly slower than that of
Adam. The underlying reason for this disparity can be attributed to GDM’s
inability to adeptly manage varying degrees of sharpness within the
optimization landscape. Consequently, GDM necessitates a learning rate
selection that is conservative, tailored to the most adverse sharpness
encountered—often present during the initial optimization stages.

###  4.2 Analysis for the stochastic setting

Transitioning to the more complex stochastic setting, we extend our analysis
beyond the deterministic framework. As with our previous approach, we start by
reviewing the literature to determine if the existing convergence rates for
Adam under the $(L_{0},L_{1})$-smooth condition can delineate a clear
distinction between the convergence behaviors of Adam and Stochastic Gradient
Descent with Momentum (SGDM). In fact, the only two studies that delve into
this problem are the ones we discussed in Section 4.1, i.e., (Wang et al.,
2022; Li et al., 2023a). However, these results pertaining to Adam are
contingent upon rather stringent assumptions. Wang et al. (2022) postulates
that stochastic gradients not only conform to the $(L_{0},L_{1})$-smooth
condition but are also limited to a finite set of possibilities. These
assumptions are more restrictive than merely assuming that the true gradients
satisfy the $(L_{0},L_{1})$-smooth condition, and such strong prerequisites
are seldom employed outside of the analysis of variance-reduction algorithms.
Meanwhile, Li et al. (2023a) aligns its findings on stochastic Adam with those
on deterministic Adam, leading to a polynomial dependency on $1/\lambda$,
which deviates from practical scenarios as discussed in Section 4.1.
Furthermore, it presumes an a.s. bounded difference between stochastic
gradients and true gradients, an assumption that closely resembles the
boundedness of stochastic gradients and is more limiting than the standard
assumption of bounded variance for stochastic gradients.

These more restricted and non-standard assumptions cast challenges in
establishing a lower bound for the convergence of SGDM in the relevant
contexts, let alone attempting a comparison between SGDM and Adam. In addition
to the fact that these upper bounds fail to facilitate a clear comparison
between Adam and SGDM, there are also concerns regarding their convergence
rates. Wang et al. (2022) reports a convergence rate of
$\frac{(f(\bm{w}_{1})-f^{*})^{2}}{\varepsilon^{8}}$, which has a higher-order
dependence on the initial function value gap and the final error than the
$\frac{(f(\bm{w}_{1})-f^{*})}{\varepsilon^{4}}$ rate established for Clipped
SGDM under the $(L_{0},L_{1})$-smooth condition (Zhang et al., 2020)333While
Zhang et al. (2020) also assumes an a.s. bounded gap between stochastic
gradients and true gradients.. Furthermore, Li et al. (2023a) indicates a
convergence rate of
$\mathcal{O}(\frac{(f(\bm{w}_{1})-f^{*})^{4}\operatorname{poly}(1/\lambda)}{\varepsilon^{4}})$,
which, aside from the previously mentioned dependency issues on $1/\lambda$,
shows a significantly stronger dependence over the initial function value gap
compared to the analysis of Clipped SGDM. This naturally leads to the question
of whether such rates for Adam can be improved to match Clipped SGDM.

To tackle these obstacles, we present the following upper bound for Adam.

An upper bound for the convergence rate of Adam.

######  Theorem 3 (Informal).

Let Assumptions 1 and 2 hold. Then, $\forall 1>\beta_{1}\geq 0$ and
$\lambda=0$, if
$\varepsilon\leq\frac{1}{\operatorname{poly}(f(\bm{w}_{1})-f^{*},L_{0},L_{1},\sigma_{0},\sigma_{1})}$,
with a proper choice of learning rate $\eta$ and momentum hyperparameter
$\beta_{2}$, we have if
$T\geq\Theta\left(\frac{(L_{0}+L_{1})\sigma_{0}^{3}\sigma_{1}^{2}(f(\bm{w}_{1})-f^{*})}{\varepsilon^{4}}\right)$,

$\frac{1}{T}\mathbb{E}\sum_{t=1}^{T}\|\nabla f(\bm{w}_{t})\|\leq\varepsilon.$

###### Proof.

Please see Appendix C.1 for the formal statement of theorem and the proof. ∎

Below we include several discussions regarding Theorem 3. To begin with, one
can immediately observe that Theorem 3 only requires Assumptions 1 and 2, and
the convergence rate with respect to the initial function value gap and the
final error $\frac{f(\bm{w}_{1})-f^{*}}{\varepsilon^{4}}$ matches that of
Clipped SGDM (Zhang et al., 2020) even with a weaker noise assumption.
Therefore, our result successfully mitigate these barriers raised above.
Indeed, to the best of our knowledge, it is for the first time that an
algorithm is shown to converge with rate
$\mathcal{O}\left(\frac{f(\bm{w}_{1})-f^{*}}{\varepsilon^{4}}\right)$ only
requiring Assumptions 1 and 2, showcasing the advantage of Adam.

We briefly sketch the proof here before moving on to the result of SGDM.
Specifically, the proof is inspired by recent analysis of Adam under
$L$-smooth condition (Wang et al., 2023a), but several challenges arise during
the proof:

  * •

The first challenge lies in the additional error introduced by the
$(L_{0},L_{1})$-smooth condition. We address this by demonstrating that the
telescoping sum involving the auxiliary function
$\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\bm{\nu}_{t-1}}}$, as employed in (Wang et
al., 2023a), can bound this additional error when the adaptive learning rate
is upper bounded. Although the adaptive learning rate in the Adam algorithm is
not inherently bounded, we establish that the deviation incurred by employing
a bounded surrogate adaptive learning rate is manageable;

  * •

The second challenge involves deriving the desired dependence on the initial
function value gap. Wang et al. (2023a) introduces two distinct proof
strategies for bounding the conditioner $\bm{\nu}_{t}$ and determining the
final convergence rate. However, one strategy introduces an additional
logarithmic dependence on $\varepsilon$, while the other exhibits sub-optimal
dependence on the initial function value gap. We propose a novel two-stage
divide-and-conquer approach to surmount this issue. In the first stage, we
bound $\bm{\nu}_{t}$ effectively. Subsequently, we leverage this bound within
the original descent lemma to achieve the optimal dependence on
$f(\bm{w}_{1})-f^{*}$.

######  Remark 2 (On the limitations).

Although Theorem 3 addresses certain deficiencies identified in prior studies
(Wang et al., 2022; Li et al., 2023a), it is not without its limitations. As
noted by Arjevani et al. (2022), the established lower bound for the
convergence rate of first-order optimization algorithms under the
$L_{0}$-smooth condition with bounded noise variance (specifically,
$\sigma_{0}=\sigma_{0}$ and $\sigma_{1}=1$ as stated in Assumption 2) is
$\mathcal{O}(\frac{(f(\bm{w}_{1})-f^{*})L_{0}\sigma_{0}^{2}}{\varepsilon^{4}})$.
This sets a benchmark for the performance under Assumptions 1 and 2. The upper
bound of Adam’s convergence rate as presented in Theorem 3 falls short when
compared to this benchmark, exhibiting a weaker noise scale dependency
($\sigma_{0}^{3}$ as opposed to $\sigma_{0}^{2}$) and additional dependencies
on $L_{1}$ and $\sigma_{1}$.

To address these issues, we demonstrate in the subsequent section that by
focusing on the convergence of the minimum gradient norm,
$\mathbb{E}\min_{t\in[T]}\|\nabla f(\bm{w}_{t})\|$, we can attain an improved
convergence rate of
$\mathcal{O}(\frac{(f(\bm{w}_{1})-f^{*})L_{0}\sigma_{0}^{2}}{\varepsilon^{4}})$.
This rate aligns with the aforementioned lower bound across all the problem
hyperparameters.

We now establish the lower bound of SGDM. This is, however, more challenging
than the deterministic case as to the best of our knowledge, there is no such
a lower bound in existing literature (despite that the lower bounds of GD
(Zhang et al., 2019; Crawshaw et al., 2022) naturally offer a lower bound of
SGD, which is considerably loose given the factor of $1/\varepsilon^{2}$).
Intuitively, stochasticity can make the convergence of GDM even worse, as
random fluctuations can inadvertently propel the iterations towards regions
characterized by high smoothness even with a good initialization. We formulate
this insight into the following theorem.

A lower bound for the convergence rate of SGDM.

######  Theorem 4 (Informal).

Fix $L_{0},L_{1}$, and $\Delta_{1}$, there exists objective function $f$
satisfying $(L_{0},L_{1})$-smooth condition and
$f(\bm{w}_{1})-f^{*}=\Delta_{1}$, and a gradient noise oracle satisfying
Assumption 2, such that for any learning rate $\eta>0$ and $\beta\in[0,1]$,
for all $T>0$,

$\min_{t\in[T]}\mathbb{E}\|\nabla f(\bm{w}_{t})\|=\|\nabla f(\bm{w}_{1})\|\geq
L_{1}\Delta_{1}.$

###### Proof.

Please see Appendix C.2 for the formal statement of theorem and the proof. ∎

Theorem 4 provides concrete evidence for the challenges inherent in the
convergence of SGDM. It shows that there are instances that comply with
Assumption 1 and Assumption 2 for which SGDM fails to converge, regardless of
the chosen learning rate and momentum coefficient. This outcome confirms our
earlier hypothesis: the stochastic elements within SGDM can indeed adversely
affect its convergence properties under non-uniform smoothness.

Our proof is founded upon a pivotal observation: an objective function that
escalates rapidly can effectively convert non-heavy-tailed noise into a
”heavy-tailed” one. In particular, under the $(L_{0},L_{1})$-smooth condition,
the magnitude of the gradient is capable of exponential growth. As a result,
even if the density diminishes exponentially, the expected value of the
gradient norm may still become unbounded. This situation mirrors what occurs
under the $L$-smooth condition when faced with heavy-tailed noise. Such a
dynamic can lead to the non-convergence of SGDM.

Separating Adam and SGDM. Considering that Adam can achieve convergence under
Assumptions 1 and 2, while SGD cannot, the superiority of Adam over SGDM
becomes evident. It is important to note, however, a recent study by (Li et
al., 2023b), which demonstrates that SGD can converge with high probability
under the same assumptions, provided the noise variance is bounded. We would
like to contextualize this finding in relation to our work as follows: First,
this result does not conflict with our Theorem 4, since our theorem pertains
to bounds in expectation rather than with high probability. Second, our
comparison of Adam and SGDM within an in-expectation framework is reasonable
and aligns with the convention of most existing lower bounds in the literature
(Carmon et al., 2017; Drori & Shamir, 2020; Arjevani et al., 2022). Moreover,
establishing high-probability lower bounds is technically challenging, and
there are few references to such bounds in the existing literature. Lastly,
while we have not derived a corresponding high-probability lower bound for
SGD, the upper bound provided by Li et al. (2023b) is
$\mathcal{O}(\frac{(f(\bm{w}_{1})-f^{*})^{4}}{\varepsilon^{4}})$, which
indicates a less favorable dependency on the initial function value gap
compared to the bound for Adam.

##  5 Can Adam reach the lower bound of the convergence rate under
$(L_{0},L_{1})$-smooth condition?

As we mentioned in Remark 2, although Theorem 3 matches the lower bound
established by Arjevani et al. (2022) with respect to the initial function
value gap $f(\bm{w}_{1})-f^{*}$, the final error $\varepsilon$, and the
smoothness coefficient $L_{0}$, it exhibits sub-optimal dependence on the
noise scale $\sigma_{0}$ and additional dependence on $L_{1}$ and
$\sigma_{1}$. One may wonder whether these dependencies are inherently
unavoidable or if they stem from technical limitations in our analysis.

Upon revisiting the proof, we identified that the sub-optimal dependencies
arise from our strategy of substituting the original adaptive learning rate
with a bounded surrogate. For example, the correlation between stochastic
gradient and adaptive learning rate will introduce an error term
$\eta\frac{\sigma_{0}^{2}(1-\beta_{2})\|\bm{g}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}\bm{\nu}_{t}}$,
detailed in Eq. (8). To bound this term, we add a constant $\lambda$ to
$\beta_{2}\bm{\nu}_{t-1}$, allowing us to upper bound
$\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{t-1}+\lambda}}$. Consequently, the term
$\eta\frac{\sigma_{0}^{2}(1-\beta_{2})\|\bm{g}_{t}\|2}{\sqrt{\beta_{2}\bm{\nu}_{t-1}+\lambda}\bm{\nu}_{t}}$
can be bounded by
$\eta\frac{\sigma_{0}^{2}(1-\beta_{2})\|\bm{g}_{t}\|^{2}}{\sqrt{\lambda}\bm{\nu}_{t}}$,
which has the same order as a second-order Taylor expansion. To control the
error introduced by adding $\lambda$, we cannot choose a value for $\lambda$
that is too large. The optimal choice of $\lambda$ for balancing the new error
against the original error is $(1-\beta_{2})\sigma_{0}^{2}$. This selection
results in the original error term
$\eta\frac{\sigma_{0}\sqrt{1-\beta_{2}}\|\bm{g}_{t}\|^{2}}{\bm{\nu}_{t}}$,
which induces an additional $\sigma_{0}$ factor, ultimately leading to the
sub-optimal dependence on $\sigma_{0}$. Therefore, we need to explore
alternative methods to handle the error term to eliminate the sub-optimal
dependence on $\sigma_{0}$.

We begin our analysis by observing that the term
$\frac{(1-\beta_{2})\|\bm{g}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}\bm{\nu}_{t}}$
can in fact be bounded by an ”approximate telescoping” series of
$\frac{1}{\sqrt{\bm{\nu}_{t}}}$ (noting an additional coefficient
$\frac{1}{\sqrt{\beta_{2}}}$ in comparison to standard telescoping):

$\frac{(1-\beta_{2})\|\bm{g}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}\bm{\nu}_{t}}\leq\mathcal{O}\left(\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}-\frac{1}{\sqrt{\bm{\nu}_{t}}}\right).$

Accordingly, summing
$\eta\frac{\sigma_{0}^{2}(1-\beta_{2})\|\bm{g}_{t}\|2}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}\bm{\nu}_{t}}$
over $t$ yields a bound of
$\mathcal{O}(\eta\sigma_{0}^{2}\sum_{t}(1-\beta_{2})\frac{1}{\sqrt{\bm{\nu}_{t}}})$.
However, this term could potentially be unbounded since $\sqrt{\bm{\nu}_{t}}$
is not lower bounded. To circumvent this issue, we consider the first-order
Taylor’s expansion of the descent lemma, which, gives
$-\sum_{t}\eta\frac{\|\nabla f(\bm{w}_{t})\|2}{\sqrt{\bm{\nu}_{t}}}$.
Intuitively, if any $\|\nabla f(\bm{w}_{t})\|^{2}$ is of the order
$\mathcal{O}(\sigma_{0}^{2}(1-\beta_{2}))$, our proof would be completed since
we choose $1-\beta_{2}=\Theta(\varepsilon^{4})$. In the other case, the term
$\mathcal{O}(\eta\sigma_{0}^{2}\sum_{t}(1-\beta_{2})\frac{1}{\sqrt{\bm{\nu}_{t}}})$
can be offset by the negative term $-\sum_{t}\eta\frac{\|\nabla
f(\bm{w}_{t})\|^{2}}{\sqrt{\bm{\nu}_{t}}}$. However, formalizing this
intuition into a proof is challenging in the context of stochastic analysis,
where the randomness across iterations complicates the analysis. Specifically,
if we condition on the event that ”no gradient norm is as small as
$\sigma_{0}^{2}(1-\beta_{2})$,” which is supported over the randomness of all
iterations, it becomes difficult to express many expected values (such as
those from the first-order Taylor expansion) in closed form.

We address this difficulty by introducing a stopping time
$\tau\triangleq\min\\{t:\|\nabla
f(\bm{w}_{t+1})\|^{2}\leq\mathcal{O}(\sigma_{0}^{2}(1-\beta_{2}))\\}$. By
applying the optimal stopping theorem (Durrett, 2019), we can maintain closed-
form expressions for the expected values up to the stopping time, allowing the
problematic error term to be absorbed within this interval. Building on this
methodology, we formulate the following theorem.

######  Theorem 5 (Informal).

Let Assumptions 1 and 2 hold. Then, $\forall 1>\beta_{1}\geq 0$, if
$\varepsilon\leq\frac{1}{\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})}$,
with a proper choice of learning rate $\eta$ and momentum hyperparameter
$\beta_{2}$, we have that if
$T\geq\Theta(\frac{L_{0}\sigma_{0}^{2}(f(\bm{w}_{1})-f^{*})}{\varepsilon^{4}})$

$\mathbb{E}\min_{t\in[1,T]}\|\nabla f(\bm{w}_{t})\|\leq\varepsilon.$

###### Proof.

Please see Appendix D.1 for the formal statement of theorem and the proof. ∎

One can easily see that the convergence rate of Theorem 5 matches the lower
bound in Arjevani et al. (2022) with respect to all problem hyperparameters up
to numerical constants even under the weaker $(L_{0},L_{1})$-smooth condition.
Therefore, such a rate is optimal and provides an affirmative answer to the
question raised in the beginning of this section.

One may notice that in the construction of the stopping time, we set the
threshold for the squared gradient norm to be $\mathcal{O}(1-\beta_{2})$. As
we set $1-\beta_{2}=\Theta(\varepsilon^{4})$, the threshold is actually much
smaller than what we aim for, since our goal is to have $\|\nabla
f(\mathbf{w}_{t})\|^{2}\leq\varepsilon^{2}$. Therefore, based on the stopping-
time technique, we can actually show that Adam can converge with an optimal
rate of $\mathcal{O}(\varepsilon^{-4})$ when $1-\beta_{2}=\varepsilon^{2}$, or
$1/\sqrt{T}$ if expressed in terms of the iteration number $T$. To the best of
our knowledge, this is the first time that Adam has been shown to converge
with an optimal rate under the condition that $1-\beta_{2}=\Omega(1/T)$, which
greatly enlarges the hyperparameter range. Moreover, as we select
$\eta=1/\sqrt{T}$, choosing $1-\beta_{2}=\Omega(1/T)$ has the advantage that
the update norm decreases with respect to $T$. This makes Adam parameter-
agnostic under the $(L_{0},L_{1})$-smooth condition, as the update norm will
eventually become smaller than $\frac{1}{L_{1}}$ as $T$ increases.

######  Theorem 6.

Let Assumptions 1 and 2 hold. Then, at the $t$-th iteration, setting
$\eta=\frac{1}{\sqrt{t}}$, $\beta_{2}=1-\frac{1}{\sqrt[4]{t^{3}}}$, we have
that Algorithm 1 satisfies

$\mathbb{E}\min_{t\in[1,T]}\|\nabla
f(\bm{w}_{t})\|\leq\tilde{\mathcal{O}}\left(\frac{1}{\sqrt[4]{T}}\right).$

It is shown in (Hübler et al., 2023) that Normed-SGDM is parameter-agnostic.
Here we show that Adam with a specific scheduler can achieve the same goal.

##  6 Conclusion

In this paper, we have conducted a mathematical examination of the performance
of the Adam optimizer and SGDM within the context of non-uniform smoothness.
Our convergence analysis reveals that Adam exhibits a faster rate of
convergence compared to SGDM under these conditions. Moreover, we introduce a
novel stopping time technique that demonstrates Adam’s capability to achieve
the existing lower bounds for convergence rates. This finding underscores the
robustness of Adam in complex optimization landscapes and contributes to a
deeper understanding of its theoretical properties.

## Impact Statement

This paper investigates convergence of Adam and SGDM under non-uniform
smoothness. The main contributions of this paper are theoretical. Thus, in our
opinion, the paper has no potential ethical and societal problems.

## References

  * Arjevani et al. (2022) Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. J., Srebro, N., and Woodworth, B.  Lower bounds for non-convex stochastic optimization.  _Mathematical Programming_ , pp. 1–50, 2022.
  * Armijo (1966) Armijo, L.  Minimization of functions having lipschitz continuous first partial derivatives.  _Pacific Journal of mathematics_ , 16(1):1–3, 1966.
  * Brown et al. (2020) Brown, T. B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D. M., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D.  Language models are few-shot learners, 2020.
  * Carmon et al. (2017) Carmon, Y., Duchi, J. C., Hinder, O., and Sidford, A.  Lower bounds for finding stationary points i.  _arXiv preprint arXiv:1710.11606_ , 2017.
  * Chen et al. (2023) Chen, Z., Zhou, Y., Liang, Y., and Lu, Z.  Generalized-smooth nonconvex optimization is as efficient as smooth nonconvex optimization.  _arXiv preprint arXiv:2303.02854_ , 2023.
  * Chowdhery et al. (2022) Chowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung, H. W., Sutton, C., Gehrmann, S., Schuh, P., Shi, K., Tsvyashchenko, S., Maynez, J., Rao, A., Barnes, P., Tay, Y., Shazeer, N., Prabhakaran, V., Reif, E., Du, N., Hutchinson, B., Pope, R., Bradbury, J., Austin, J., Isard, M., Gur-Ari, G., Yin, P., Duke, T., Levskaya, A., Ghemawat, S., Dev, S., Michalewski, H., Garcia, X., Misra, V., Robinson, K., Fedus, L., Zhou, D., Ippolito, D., Luan, D., Lim, H., Zoph, B., Spiridonov, A., Sepassi, R., Dohan, D., Agrawal, S., Omernick, M., Dai, A. M., Pillai, T. S., Pellat, M., Lewkowycz, A., Moreira, E., Child, R., Polozov, O., Lee, K., Zhou, Z., Wang, X., Saeta, B., Diaz, M., Firat, O., Catasta, M., Wei, J., Meier-Hellstern, K., Eck, D., Dean, J., Petrov, S., and Fiedel, N.  Palm: Scaling language modeling with pathways, 2022.
  * Crawshaw et al. (2022) Crawshaw, M., Liu, M., Orabona, F., Zhang, W., and Zhuang, Z.  Robustness to unbounded smoothness of generalized signSGD.  _arXiv preprint arXiv:2208.11195_ , 2022.
  * Cutkosky & Mehta (2020) Cutkosky, A. and Mehta, H.  Momentum improves normalized SGD.  In _International conference on machine learning_ , pp. 2260–2268. PMLR, 2020.
  * De et al. (2018) De, S., Mukherjee, A., and Ullah, E.  Convergence guarantees for RMSProp and ADAM in non-convex optimization and an empirical comparison to Nesterov acceleration.  _arXiv preprint arXiv:1807.06766_ , 2018.
  * Défossez et al. (2022) Défossez, A., Bottou, L., Bach, F., and Usunier, N.  A simple convergence proof of Adam and Adagrad.  _Transactions on Machine Learning Research_ , 2022.
  * Drori & Shamir (2020) Drori, Y. and Shamir, O.  The complexity of finding stationary points with stochastic gradient descent.  In _International Conference on Machine Learning_ , pp. 2658–2667. PMLR, 2020.
  * Du et al. (2021) Du, Z., Qian, Y., Liu, X., Ding, M., Qiu, J., Yang, Z., and Tang, J.  All NLP tasks are generation tasks: A general pretraining framework.  _CoRR_ , abs/2103.10360, 2021.  URL https://arxiv.org/abs/2103.10360.
  * Durrett (2019) Durrett, R.  _Probability: theory and examples_ , volume 49.  Cambridge university press, 2019.
  * Faw et al. (2022) Faw, M., Tziotis, I., Caramanis, C., Mokhtari, A., Shakkottai, S., and Ward, R.  The power of adaptivity in SGD: Self-tuning step sizes with unbounded gradients and affine variance.  In _Conference on Learning Theory_ , pp. 313–355. PMLR, 2022.
  * Faw et al. (2023) Faw, M., Rout, L., Caramanis, C., and Shakkottai, S.  Beyond uniform smoothness: A stopped analysis of adaptive sgd.  _arXiv preprint arXiv:2302.06570_ , 2023.
  * Guo et al. (2021) Guo, Z., Xu, Y., Yin, W., Jin, R., and Yang, T.  A novel convergence analysis for algorithms of the Adam family.  _arXiv preprint arXiv:2112.03459_ , 2021.
  * He et al. (2023) He, M., Liang, Y., Liu, J., and Xu, D.  Convergence of adam for non-convex objectives: Relaxed hyperparameters and non-ergodic case.  _arXiv preprint arXiv:2307.11782_ , 2023.
  * Hong & Lin (2023) Hong, Y. and Lin, J.  High probability convergence of adam under unbounded gradients and affine variance noise.  _arXiv preprint arXiv:2311.02000_ , 2023.
  * Hübler et al. (2023) Hübler, F., Yang, J., Li, X., and He, N.  Parameter-agnostic optimization under relaxed smoothness.  _arXiv preprint arXiv:2311.03252_ , 2023.
  * Jin et al. (2021) Jin, J., Zhang, B., Wang, H., and Wang, L.  Non-convex distributionally robust optimization: Non-asymptotic analysis.  _Advances in Neural Information Processing Systems_ , 34:2771–2782, 2021.
  * Kingma & Ba (2014) Kingma, D. P. and Ba, J.  Adam: A method for stochastic optimization, 2014.
  * Li et al. (2023a) Li, H., Jadbabaie, A., and Rakhlin, A.  Convergence of Adam under relaxed assumptions.  _arXiv preprint arXiv:2304.13972_ , 2023a.
  * Li et al. (2023b) Li, H., Qian, J., Tian, Y., Rakhlin, A., and Jadbabaie, A.  Convex and non-convex optimization under generalized smoothness.  _arXiv preprint arXiv:2306.01264_ , 2023b.
  * Loshchilov & Hutter (2019) Loshchilov, I. and Hutter, F.  Decoupled weight decay regularization.  In _International Conference on Learning Representations_ , 2019.
  * Mei et al. (2021) Mei, J., Gao, Y., Dai, B., Szepesvari, C., and Schuurmans, D.  Leveraging non-uniformity in first-order non-convex optimization.  In _International Conference on Machine Learning_ , pp. 7555–7564. PMLR, 2021.
  * Nesterov et al. (2018) Nesterov, Y. et al.  _Lectures on convex optimization_ , volume 137.  Springer, 2018.
  * Orabona & Pál (2016) Orabona, F. and Pál, D.  Coin betting and parameter-free online learning.  _Advances in Neural Information Processing Systems_ , 29, 2016.
  * Orabona & Tommasi (2017) Orabona, F. and Tommasi, T.  Training deep networks without learning rates through coin betting.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Rae et al. (2021) Rae, J. W., Borgeaud, S., Cai, T., Millican, K., Hoffmann, J., Song, F., Aslanides, J., Henderson, S., Ring, R., Young, S., et al.  Scaling language models: Methods, analysis & insights from training gopher.  _arXiv preprint arXiv:2112.11446_ , 2021.
  * Reddi et al. (2018) Reddi, S. J., Kale, S., and Kumar, S.  On the convergence of adam and beyond.  In _International Conference on Learning Representations_ , 2018.
  * Reisizadeh et al. (2023) Reisizadeh, A., Li, H., Das, S., and Jadbabaie, A.  Variance-reduced clipping for non-convex optimization.  _arXiv preprint arXiv:2303.00883_ , 2023.
  * Schneider et al. (2022) Schneider, F., Nado, Z., Agarwal, N., Dahl, G. E., and Hennig, P.  HITY workshop poll, NeurIPS 2022.  https://github.com/fsschneider/HITYWorkshopPoll, 2022.
  * Shi et al. (2021) Shi, N., Li, D., Hong, M., and Sun, R.  RMSprop converges with proper hyper-parameter.  In _International Conference on Learning Representations_ , 2021.
  * Sun et al. (2019) Sun, T., Yin, P., Li, D., Huang, C., Guan, L., and Jiang, H.  Non-ergodic convergence analysis of heavy-ball algorithms.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pp. 5033–5040, 2019.
  * Sun et al. (2023) Sun, T., Chen, C., Qiao, P., Shen, L., Liu, X., and Li, D.  Rethinking sign training: Provable nonconvex acceleration without first-and second-order gradient lipschitz.  _arXiv preprint arXiv:2310.14616_ , 2023.
  * Touvron et al. (2023) Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., et al.  Llama: Open and efficient foundation language models.  _arXiv preprint arXiv:2302.13971_ , 2023.
  * Wang et al. (2022) Wang, B., Zhang, Y., Zhang, H., Meng, Q., Ma, Z.-M., Liu, T.-Y., and Chen, W.  Provable adaptivity in Adam.  _arXiv preprint arXiv:2208.09900_ , 2022.
  * Wang et al. (2023a) Wang, B., Fu, J., Zhang, H., Zheng, N., and Chen, W.  Closing the gap between the upper bound and lower bound of adam’s iteration complexity.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023a.
  * Wang et al. (2023b) Wang, B., Zhang, H., Ma, Z., and Chen, W.  Convergence of adagrad for non-convex objectives: Simple proofs and relaxed assumptions.  In _The Thirty Sixth Annual Conference on Learning Theory_ , pp. 161–190. PMLR, 2023b.
  * Ward et al. (2020) Ward, R., Wu, X., and Bottou, L.  Adagrad stepsizes: Sharp convergence over nonconvex landscapes.  _The Journal of Machine Learning Research_ , 21(1):9047–9076, 2020.
  * Xie et al. (2023) Xie, C., Li, C., Zhang, C., Deng, Q., Ge, D., and Ye, Y.  Trust region methods for nonconvex stochastic optimization beyond lipschitz smoothness.  _arXiv preprint arXiv:2310.17319_ , 2023.
  * Xing et al. (2021) Xing, Y., He, X., et al.  On the convergence of msgd and adagrad for stochastic optimization.  In _International Conference on Learning Representations_ , 2021.
  * Yang et al. (2023) Yang, J., Li, X., Fatkhullin, I., and He, N.  Two sides of one coin: the limits of untuned sgd and the power of adaptive methods.  _arXiv preprint arXiv:2305.12475_ , 2023.
  * Zaheer et al. (2018) Zaheer, M., Reddi, S., Sachan, D., Kale, S., and Kumar, S.  Adaptive methods for nonconvex optimization.  _Advances in neural information processing systems_ , 31, 2018.
  * Zhang et al. (2020) Zhang, B., Jin, J., Fang, C., and Wang, L.  Improved analysis of clipping algorithms for non-convex optimization.  _Advances in Neural Information Processing Systems_ , 33:15511–15521, 2020.
  * Zhang et al. (2019) Zhang, J., He, T., Sra, S., and Jadbabaie, A.  Why gradient clipping accelerates training: A theoretical justification for adaptivity.  In _International Conference on Learning Representations_ , 2019.
  * Zhang et al. (2022a) Zhang, S., Roller, S., Goyal, N., Artetxe, M., Chen, M.-W., Chen, S., Dewan, C., Diab, M., Li, X., Lin, X. V., et al.  Opt: Open pre-trained transformer language models.  _arXiv preprint arXiv:2205.01068_ , 2022a.
  * Zhang et al. (2022b) Zhang, Y., Chen, C., Shi, N., Sun, R., and Luo, Z.-Q.  Adam can converge without any modification on update rules.  _arXiv preprint arXiv:2208.09632_ , 2022b.
  * Zou et al. (2019) Zou, F., Shen, L., Jie, Z., Zhang, W., and Liu, W.  A sufficient condition for convergences of Adam and RMSProp.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pp. 11127–11135, 2019.

##  Appendix A Auxiliary Lemmas

In this section, we provide auxiliary results which will be used in subsequent
results.

######  Lemma 1.

We have $\forall t\geq 1$,
$\|\bm{w}_{t+1}-\bm{w}_{t}\|\leq\eta\frac{1-\beta_{1}}{\sqrt{1-\beta_{2}}\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}}}}$.

###### Proof.

We have that

$\displaystyle\|\bm{w}_{t+1}-\bm{w}_{t}\|=\eta\left|\frac{\bm{m}_{t}}{\sqrt{\bm{\nu}_{t}}}\right|\leq\eta\frac{\sum_{i=0}^{t-1}(1-\beta_{1})\beta_{1}^{i}\|\bm{g}_{t-i}\|}{\sqrt{\sum_{i=0}^{t-1}(1-\beta_{2})\beta_{2}^{i}\|\bm{g}_{t-i}\|^{2}+\beta_{2}^{t}\bm{\nu}_{0}}}$
$\displaystyle\leq$
$\displaystyle\eta\frac{1-\beta_{1}}{\sqrt{1-\beta_{2}}}\frac{\sqrt{\sum_{i=0}^{t-1}\beta_{2}^{i}\|\bm{g}_{t-i}\|^{2}}\sqrt{\sum_{i=0}^{t-1}\frac{\beta_{1}^{2i}}{\beta_{2}^{i}}}}{\sqrt{\sum_{i=0}^{t-1}\beta_{2}^{i}\|\bm{g}_{t-i}\|^{2}}}\leq\eta\frac{1-\beta_{1}}{\sqrt{1-\beta_{2}}\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}}}}.$

Here the second inequality is due to Cauchy’s inequality. The proof is
completed. ∎

The following lemma provides a novel descent lemma under
$(L_{0},L_{1})$-smooth condition.

######  Lemma 2.

Let Assumption 1 hold. Then, for any three points
$\bm{w}^{1},\bm{w}^{2},\bm{w}^{3}\in\mathcal{X}$ satisfying
$\|\bm{w}^{1}-\bm{w}^{2}\|\leq\frac{1}{2L_{1}}$ and
$\|\bm{w}^{1}-\bm{w}^{3}\|\leq\frac{1}{2L_{1}}$, we have

$f(\bm{w}^{2})\leq f(\bm{w}^{3})+\langle\nabla
f(\bm{w}^{3}),\bm{w}^{2}-\bm{w}^{3}\rangle+\frac{1}{2}(L_{0}+L_{1}\|\nabla
f(\bm{w}^{1})\|)\|\bm{w}^{2}-\bm{w}^{3}\|(\|\bm{w}^{1}-\bm{w}^{3}\|+\|\bm{w}^{1}-\bm{w}^{2}\|).$

###### Proof.

By the Fundamental Theorem of Calculus, we have

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

where Inequality $(\star)$ is because due to

$\|\bm{w}^{3}+a(\bm{w}^{2}-\bm{w}^{3})-\bm{w}^{1}\|=\|a(\bm{w}^{2}-\bm{w}^{1})+(1-a)(\bm{w}^{3}-\bm{w}^{1})\|\leq\frac{1}{L_{1}},$

the definition of $(L_{0},L_{1})$-smooth condition can be applied.

The proof is completed. ∎

The following lemma is helpful when bounding the second-order term.

######  Lemma 3.

Assume we have $0<\beta_{1}^{2}<\beta_{2}<1$ and a sequence of real numbers
$(a_{n})_{n=1}^{\infty}$. Let $b_{0}>0$,
$b_{n}=\beta_{2}b_{n-1}+(1-\beta_{2})a_{n}^{2}$, $c_{0}=0$, and
$c_{n}=\beta_{1}c_{n-1}+(1-\beta_{1})a_{n}$. Then, we have

$\sum_{n=1}^{T}\frac{|c_{n}|^{2}}{b_{n}}\leq\frac{(1-\beta_{1})^{2}}{(1-\frac{\beta_{1}}{\sqrt{\beta_{2}}})^{2}(1-\beta_{2})}\left(\ln\left(\frac{b_{T}}{b_{0}}\right)-T\ln\beta_{2}\right).$

######  Lemma 4.

If $\beta_{2}\geq\beta_{1}$, then we have

$\frac{\|\bm{m}_{t}\|^{2}}{(\sqrt{\bm{\nu}_{t}})^{3}}\leq
4(1-\beta_{1})\left(\sum_{s=1}^{t}\sqrt[4]{\beta_{1}^{t-s}}\frac{2}{1-\beta_{2}}\left(\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{s-1}}}-\frac{1}{\sqrt{\bm{\nu}_{s}}}\right)\right).$

###### Proof.

To begin with, we have

$\displaystyle\frac{\|\bm{m}_{t}\|}{\sqrt[4]{\bm{\nu}_{t}^{3}}}\leq(1-\beta_{1})\sum_{s=1}^{t}\frac{\beta_{2}^{t-s}\|\bm{g}_{s}\|}{\sqrt[4]{\bm{\nu}_{t}^{3}}}\leq(1-\beta_{1})\sum_{s=1}^{t}\frac{\beta_{1}^{t-s}\|\bm{g}_{s}\|}{\sqrt[4]{\beta_{2}^{3(t-s)}}\sqrt[4]{\bm{\nu}_{s}^{3}}}.$

Here in the last inequality we use
$\bm{\nu}_{t}\geq\beta_{2}^{t-s}\bm{\nu}_{s}$.

By further applying Cauchy-Schwartz inequality, we obtain

$\displaystyle\frac{\|\bm{m}_{t}\|^{2}}{\sqrt{\bm{\nu}_{t}^{3}}}\leq$
$\displaystyle(1-\beta_{1})^{2}\left(\sum_{s=1}^{t}\frac{\beta_{1}^{t-s}\|\bm{g}_{s}\|^{2}}{\sqrt[4]{\beta_{2}^{3(t-s)}}\sqrt{\bm{\nu}_{s}^{3}}}\right)\left(\sum_{s=1}^{t}\frac{\beta_{1}^{t-s}}{\sqrt[4]{\beta_{2}^{3(t-s)}}}\right)$
$\displaystyle\leq$
$\displaystyle\frac{(1-\beta_{1})^{2}}{1-\frac{\beta_{1}}{\sqrt[4]{\beta_{2}^{3}}}}\left(\sum_{s=1}^{t}\frac{\beta_{1}^{t-s}\|\bm{g}_{s}\|^{2}}{\sqrt[4]{\beta_{2}^{3(t-s)}}\sqrt{\bm{\nu}_{s}^{3}}}\right)$
$\displaystyle\leq$ $\displaystyle
4(1-\beta_{1})\left(\sum_{s=1}^{t}\frac{\beta_{1}^{t-s}\|\bm{g}_{s}\|^{2}}{\sqrt[4]{\beta_{2}^{3(t-s)}}\sqrt{\bm{\nu}_{s}^{3}}}\right).$

As
$\frac{\|\bm{g}_{s}\|^{2}}{\sqrt{\bm{\nu}_{s}^{3}}}\leq\frac{2\|\bm{g}_{s}\|^{2}}{\sqrt{\bm{\nu}_{s}}\sqrt{\beta_{2}\bm{\nu}_{s-1}}(\sqrt{\bm{\nu}_{s}}+\sqrt{\beta_{2}\bm{\nu}_{s-1}})}=\frac{2}{1-\beta_{2}}\left(\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{s-1}}}-\frac{1}{\sqrt{\bm{\nu}_{s}}}\right)$,
the proof is completed. ∎

######  Lemma 5.

If $\beta_{2}\geq\beta_{1}$, then we have

$\frac{\|\bm{m}_{t}\|^{2}\|\bm{G}_{t}\|^{2}}{\bm{\nu}_{t}\sqrt{\beta_{2}\bm{\nu}_{t-1}}}\leq
4(1-\beta_{1})\left(\sum_{s=1}^{t}\frac{\sqrt[8]{\beta_{1}^{t-s}}\|\bm{g}_{s}\|^{2}\|\bm{G}_{s}\|^{2}}{\bm{\nu}_{s}\sqrt{\beta_{2}\bm{\nu}_{s-1}}}\right)+8\frac{1-\beta_{1}}{1-\beta_{2}}\frac{L_{1}^{2}}{L_{0}^{2}}\left(\sum_{s=1}^{t}\sqrt[8]{\beta_{1}^{t-s}}\left(\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{s-1}}}-\frac{1}{\sqrt{\bm{\nu}_{s}}}\right)\right).$

###### Proof.

Similar to the proof of Lemma 4, we have

$\displaystyle\frac{\|\bm{m}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}\bm{\nu}_{t}}\leq$
$\displaystyle
4(1-\beta_{1})\left(\sum_{s=1}^{t}\frac{\beta_{1}^{t-s}\|\bm{g}_{s}\|^{2}}{\sqrt[4]{\beta_{2}^{3(t-s)}}\sqrt{\beta_{2}\bm{\nu}_{s-1}}\bm{\nu}_{s}}\right).$
(1)

Meanwhile, according to Assumption 1, we have

$\displaystyle\|\bm{G}_{t}\|^{2}\leq$
$\displaystyle\|\bm{G}_{t-1}\|^{2}+2\|\bm{G}_{t-1}\|\|\bm{G}_{t}-\bm{G}_{t-1}\|+\|\bm{G}_{t}-\bm{G}_{t-1}\|^{2}$
$\displaystyle\leq$
$\displaystyle\|\bm{G}_{t-1}\|^{2}+2\|\bm{G}_{t-1}\|(L_{0}+L_{1}\|\bm{G}_{t-1}\|)\|\bm{w}_{t+1}-\bm{w}_{t}\|+2(L_{0}^{2}+L_{1}^{2}\|\bm{G}_{t-1}\|^{2})\|\bm{w}_{t+1}-\bm{w}_{t}\|^{2}$
$\displaystyle\leq$
$\displaystyle\|\bm{G}_{t-1}\|^{2}+\frac{1-\sqrt[8]{\beta_{1}}}{3\sqrt[8]{\beta_{1}}}\|\bm{G}_{t-1}\|^{2}+\frac{3\sqrt[8]{\beta_{1}}L_{0}^{2}}{1-\sqrt[8]{\beta_{1}}}\|\bm{w}_{t+1}-\bm{w}_{t}\|^{2}+2L_{1}\|\bm{G}_{t-1}\|^{2}\|\bm{w}_{t+1}-\bm{w}_{t}\|$
$\displaystyle+2(L_{0}^{2}+L_{1}^{2}\|\bm{G}_{t-1}\|^{2})\|\bm{w}_{t+1}-\bm{w}_{t}\|^{2}$
$\displaystyle\overset{(\star)}{\leq}$
$\displaystyle\|\bm{G}_{t-1}\|^{2}+\frac{1-\sqrt[8]{\beta_{1}}}{3\sqrt[8]{\beta_{1}}}\|\bm{G}_{t-1}\|^{2}+\frac{1-\sqrt[8]{\beta_{1}}}{2}\frac{L_{0}^{2}}{L_{1}^{2}}+\frac{1-\sqrt[8]{\beta_{1}}}{3\sqrt[8]{\beta_{1}}}\|\bm{G}_{t-1}\|^{2}$
$\displaystyle+\frac{1-\sqrt[8]{\beta_{1}}}{2}\frac{L_{0}^{2}}{L_{1}^{2}}+\frac{1-\sqrt[8]{\beta_{1}}}{3\sqrt[8]{\beta_{1}}}\|\bm{G}_{t-1}\|^{2}$
$\displaystyle\leq$
$\displaystyle\frac{1}{\sqrt[8]{\beta_{1}}}\|\bm{G}_{t-1}\|^{2}+(1-\sqrt[8]{\beta_{1}})\frac{L_{1}^{2}}{L_{0}^{2}}.$

Here inequality $(\star)$ is because
$\|\bm{w}_{t+1}-\bm{w}_{t}\|\leq\frac{1-\sqrt[8]{\beta_{1}}}{6L_{1}}$.
Recursively applying the above inequality, we obtain that

$\displaystyle\|\bm{G}_{t}\|^{2}\leq\frac{1}{\sqrt[8]{\beta_{1}^{t-s}}}\|\bm{G}_{s}\|^{2}+\left(\left(\frac{1}{\sqrt[8]{\beta_{1}}}\right)^{t-s}-1\right)\frac{L_{1}^{2}}{L_{0}^{2}},$

which by Eq. (1) further gives

$\displaystyle\frac{\|\bm{m}_{t}\|^{2}\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}\bm{\nu}_{t}}\leq$
$\displaystyle
4(1-\beta_{1})\left(\sum_{s=1}^{t}\frac{\beta_{1}^{t-s}\|\bm{g}_{s}\|^{2}\|\bm{G}_{t}\|^{2}}{\sqrt[4]{\beta_{2}^{3(t-s)}}\bm{\nu}_{s}\sqrt{\beta_{2}\bm{\nu}_{s-1}}}\right)$
$\displaystyle\leq$ $\displaystyle
4(1-\beta_{1})\left(\sum_{s=1}^{t}\frac{\sqrt[8]{\beta_{1}^{t-s}}\|\bm{g}_{s}\|^{2}\|\bm{G}_{s}\|^{2}}{\bm{\nu}_{s}\sqrt{\beta_{2}\bm{\nu}_{s-1}}}+\sum_{s=1}^{t}\frac{\sqrt[8]{\beta_{1}^{t-s}}\|\bm{g}_{s}\|^{2}}{\bm{\nu}_{s}\sqrt{\beta_{2}\bm{\nu}_{s-1}}}\frac{L_{1}^{2}}{L_{0}^{2}}\right)$
$\displaystyle\leq$ $\displaystyle
4(1-\beta_{1})\left(\sum_{s=1}^{t}\frac{\sqrt[8]{\beta_{1}^{t-s}}\|\bm{g}_{s}\|^{2}\|\bm{G}_{s}\|^{2}}{\bm{\nu}_{s}\sqrt{\beta_{2}\bm{\nu}_{s-1}}}\right)+8\frac{1-\beta_{1}}{1-\beta_{2}}\frac{L_{1}^{2}}{L_{0}^{2}}\left(\sum_{s=1}^{t}\sqrt[8]{\beta_{1}^{t-s}}\left(\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{s-1}}}-\frac{1}{\sqrt{\bm{\nu}_{s}}}\right)\right).$

Here the last inequality is based on the similar reasoning of Lemma 5.

The proof is completed. ∎

##  Appendix B Proofs for deterministic algorithms

###  B.1 Proof for deterministic Adam

We will first provide the formal statement of Theorem 1, and then show the
corresponding proof.

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

Let Assumption 1 hold. Then, $\forall\beta_{1},\beta_{2}$ satisfying
$0\leq\beta_{1}^{2}<\beta_{2}<1$, if
$T>\frac{L_{1}^{2}(f(\bm{w}_{1})-f^{*})(1-\frac{\beta_{1}^{2}}{\beta_{2}})}{L_{0}(1-\beta_{1})^{2}}$,
picking
$\eta=\frac{\sqrt{f(\bm{w}_{1})-f^{*}}\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}}}}{\sqrt{TL_{0}}(1-\beta_{1})}$,
we have

$\frac{1}{T}\sum_{t=1}^{T}\|\nabla
f(\bm{w}_{t})\|\leq\frac{64}{(1-\beta_{2})(1-\frac{\beta_{1}^{2}}{\beta_{2}})\left(1-\frac{\beta_{1}}{\sqrt[4]{\beta_{2}}}\right)^{2}}\left(\frac{\sqrt{L_{0}(f(\bm{w}_{1})-f^{*})}}{\sqrt{T}}\right).$

###### Proof.

To begin with, according to Lemma 1 and restriction on the value of $T$, we
obtain that

$\forall t\in\mathbb{N}~{}\&t~{}\geq
1,\|\bm{w}_{t+1}-\bm{w}_{t}\|\leq\frac{1}{4L_{1}}.$

Therefore, the descent lemma can then be applied and thus $\forall
t\in\mathbb{N}\&t\geq 1$,

$f(\bm{w}_{t+1})\leq
f(\bm{w}_{t})\underbrace{-\eta\left\langle\bm{G}_{t},\frac{\bm{m}_{t}}{\lambda+\sqrt{\bm{\nu}_{t}}}\right\rangle}_{\text{First
Order}}+\underbrace{\eta^{2}\frac{L_{0}+L_{1}\|\bm{G}_{t}\|}{2}\frac{\|\bm{m}_{t}\|^{2}}{(\lambda+\sqrt{\bm{\nu}_{t}})^{2}}}_{\text{Second
Order}}.$

To begin with, as for the ”First Order” term, acording to
$\bm{m}_{t}=\beta_{1}\bm{m}_{t-1}+(1-\beta_{1})\bm{G}_{t}$ we have that

$\displaystyle-\eta\left\langle\bm{G}_{t},\frac{\bm{m}_{t}}{\lambda+\sqrt{\bm{\nu}_{t}}}\right\rangle=$
$\displaystyle-\eta\frac{1}{1-\beta_{1}}\left\langle\bm{m}_{t},\frac{\bm{m}_{t}}{\lambda+\sqrt{\bm{\nu}_{t}}}\right\rangle+\eta\frac{\beta_{1}}{1-\beta_{1}}\left\langle\bm{m}_{t-1},\frac{\bm{m}_{t}}{\lambda+\sqrt{\bm{\nu}_{t}}}\right\rangle$
$\displaystyle\overset{(\star)}{\leq}$
$\displaystyle-\eta\frac{1}{1-\beta_{1}}\frac{\|\bm{m}_{t}\|^{2}}{\lambda+\sqrt{\bm{\nu}_{t}}}+\eta\frac{\beta_{1}}{(1-\beta_{1})\sqrt[4]{\beta_{2}}}\left\langle\bm{m}_{t-1},\frac{\bm{m}_{t}}{\sqrt{\lambda+\sqrt{\bm{\nu}_{t}}}\sqrt{\lambda+\sqrt{\bm{\nu}_{t-1}}}}\right\rangle$
$\displaystyle\overset{(\ast)}{\leq}$
$\displaystyle-\eta\frac{1}{1-\beta_{1}}\frac{\|\bm{m}_{t}\|^{2}}{\lambda+\sqrt{\bm{\nu}_{t}}}+{\frac{\beta_{1}}{2(1-\beta_{1})\sqrt[4]{\beta_{2}}}}\eta\frac{\|\bm{m}_{t}\|^{2}}{\lambda+\sqrt{\bm{\nu}_{t}}}+{\frac{\beta_{1}}{2(1-\beta_{1})\sqrt[4]{\beta_{2}}}}\eta\frac{\|\bm{m}_{t-1}\|^{2}}{\lambda+\sqrt{\bm{\nu}_{t-1}}}$
$\displaystyle=$
$\displaystyle-\eta\frac{1-\frac{\beta_{1}}{\sqrt[4]{\beta_{2}}}}{1-\beta_{1}}\frac{\|\bm{m}_{t}\|^{2}}{\lambda+\sqrt{\bm{\nu}_{t}}}-{\frac{\beta_{1}}{2(1-\beta_{1})\sqrt[4]{\beta_{2}}}}\eta\frac{\|\bm{m}_{t}\|^{2}}{\lambda+\sqrt{\bm{\nu}_{t}}}+{\frac{\beta_{1}}{2(1-\beta_{1})\sqrt[4]{\beta_{2}}}}\eta\frac{\|\bm{m}_{t-1}\|^{2}}{\lambda+\sqrt{\bm{\nu}_{t-1}}}.$

where inequality $(\star)$ is due to that
$\sqrt{\bm{\nu}_{t}}\geq\sqrt{\beta_{2}\bm{\nu}_{t-1}}$ and inequality
$(\ast)$ is due to Young’s inequality.

Meanwhile, as for the ”Second Order” term, we have

$\displaystyle\eta^{2}\frac{L_{0}+L_{1}\|\bm{G}_{t}\|}{2}\frac{\|\bm{m}_{t}\|^{2}}{(\lambda+\sqrt{\bm{\nu}_{t}})^{2}}\overset{(\bullet)}{\leq}$
$\displaystyle
L_{0}\eta^{2}\frac{(1-\beta_{1})^{2}}{(1-\beta_{2})(1-\frac{\beta_{1}^{2}}{\beta_{2}})}+\frac{L_{1}\eta^{2}}{\sqrt{1-\beta_{2}}}\frac{\|\bm{m}_{t}\|^{2}}{\lambda+\sqrt{\bm{\nu}_{t}}}$
$\displaystyle\overset{(\circ)}{\leq}$ $\displaystyle
L_{0}\eta^{2}\frac{(1-\beta_{1})^{2}}{(1-\beta_{2})(1-\frac{\beta_{1}^{2}}{\beta_{2}})}+\frac{\eta}{2}\frac{1-\frac{\beta_{1}}{\sqrt[4]{\beta_{2}}}}{1-\beta_{1}}\frac{\|\bm{m}_{t}\|^{2}}{\lambda+\sqrt{\bm{\nu}_{t}}}.$

Here inequality $(\bullet)$ is due to Lemma 1 and

$\bm{\nu}_{t}\geq(1-\beta_{2})\|\bm{G}_{t}\|^{2},$

and inequality $(\circ)$ is due to the requirement over $T$.

Applying the estimations of both the ”First Order” and the ”Second Order”
terms, we obtain that

$\displaystyle f(\bm{w}_{t+1})-f(\bm{w}_{t})\leq$
$\displaystyle-\frac{\eta}{2}\frac{1-\frac{\beta_{1}}{\sqrt[4]{\beta_{2}}}}{1-\beta_{1}}\frac{\|\bm{m}_{t}\|^{2}}{\lambda+\sqrt{\bm{\nu}_{t}}}-{\frac{\beta_{1}}{2(1-\beta_{1})\sqrt[4]{\beta_{2}}}}\eta\frac{\|\bm{m}_{t}\|^{2}}{\lambda+\sqrt{\bm{\nu}_{t}}}+{\frac{\beta_{1}}{2(1-\beta_{1})\sqrt[4]{\beta_{2}}}}\eta\frac{\|\bm{m}_{t-1}\|^{2}}{\lambda+\sqrt{\bm{\nu}_{t-1}}}$
$\displaystyle+L_{0}\eta^{2}\frac{(1-\beta_{1})^{2}}{(1-\beta_{2})(1-\frac{\beta_{1}^{2}}{\beta_{2}})}.$

Summing the above inequality over $t\in\\{1,\cdots,T\\}$ then gives

$\displaystyle\sum_{t=1}^{T}\frac{\eta}{2}\frac{1-\frac{\beta_{1}}{\sqrt[4]{\beta_{2}}}}{1-\beta_{1}}\frac{\|\bm{m}_{t}\|^{2}}{\lambda+\sqrt{\bm{\nu}_{t}}}$
(2) $\displaystyle\leq$ $\displaystyle
f(\bm{w}_{1})-f(\bm{w}_{T+1})-{\frac{\beta_{1}}{2(1-\beta_{1})\sqrt[4]{\beta_{2}}}}\eta\frac{\|\bm{m}_{T}\|^{2}}{\lambda+\sqrt{\bm{\nu}_{T}}}+TL_{0}\eta^{2}\frac{(1-\beta_{1})^{2}}{(1-\beta_{2})(1-\frac{\beta_{1}^{2}}{\beta_{2}})}$
$\displaystyle\leq$ $\displaystyle
f(\bm{w}_{1})-f(\bm{w}_{T+1})+TL_{0}\eta^{2}\frac{(1-\beta_{1})^{2}}{(1-\beta_{2})(1-\frac{\beta_{1}^{2}}{\beta_{2}})}.$

Furthermore, as $(1-\beta_{1})\bm{G}_{t}=\bm{m}_{t}-\beta_{1}\bm{m}_{t-1}$, we
have that

$\|\bm{G}_{t}\|^{2}\leq\frac{1}{(1-\beta_{1})^{2}}\|\bm{m}_{t}\|^{2}+\frac{1}{(1-\beta_{1})^{2}}\|\bm{m}_{t-1}\|^{2}.$

Applying the above inequality and $\lambda=0$ to Eq. (2), we obtain that

$\sum_{t=1}^{T}\frac{\eta}{4}\left(1-\frac{\beta_{1}}{\sqrt[4]{\beta_{2}}}\right)(1-\beta_{1})\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\bm{\nu}_{t}}}\leq
f(\bm{w}_{1})-f(\bm{w}_{T+1})+TL_{0}\eta^{2}\frac{(1-\beta_{1})^{2}}{(1-\beta_{2})(1-\frac{\beta_{1}^{2}}{\beta_{2}})}.$

Meanwhile, we have

$\sqrt{\bm{\nu}_{t}}-\sqrt{\beta_{2}\bm{\nu}_{t-1}}=\frac{(1-\beta_{2})\|\bm{G}_{t}\|^{2}}{\sqrt{\bm{\nu}_{t}}+\sqrt{\beta_{2}\bm{\nu}_{t-1}}}\leq(1-\beta_{2})\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\bm{\nu}_{t}}}.$

Therefore, applying the above inequality and dividing both sides by $\eta$, we
have

$\frac{1}{4}\left(1-\frac{\beta_{1}}{\sqrt[4]{\beta_{2}}}\right)(1-\beta_{1})\sum_{t=1}^{T}(\sqrt{\bm{\nu}_{t}}-\sqrt{\beta_{2}\bm{\nu}_{t-1}})\leq\frac{f(\bm{w}_{1})-f(\bm{w}_{T+1})}{\eta}+TL_{0}\eta\frac{(1-\beta_{1})^{2}}{(1-\beta_{2})(1-\frac{\beta_{1}^{2}}{\beta_{2}})},$

which by telescoping further leads to

$\frac{1}{4}\left(1-\frac{\beta_{1}}{\sqrt[4]{\beta_{2}}}\right)(1-\beta_{1})\sum_{t=1}^{T}(1-\beta_{2})\sqrt{\bm{\nu}_{t}}\leq\frac{f(\bm{w}_{1})-f(\bm{w}_{T+1})}{\eta}+TL_{0}\eta\frac{(1-\beta_{1})^{2}}{(1-\beta_{2})(1-\frac{\beta_{1}^{2}}{\beta_{2}})}.$

According to Cauchy-Schwartz’s inequality, we then obtain

$\displaystyle\left(\sum_{t=1}^{T}\|\bm{G}_{t}\|\right)^{2}\leq$
$\displaystyle\left(\sum_{t=1}^{T}\sqrt{\bm{\nu}_{t}}\right)\left(\sum_{t=1}^{T}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\bm{\nu}_{t}}}\right)$
$\displaystyle\leq$
$\displaystyle\frac{1}{1-\beta_{2}}\left(\frac{4(f(\bm{w}_{1})-f(\bm{w}_{T+1}))}{\eta\left(1-\frac{\beta_{1}}{\sqrt[4]{\beta_{2}}}\right)(1-\beta_{1})}+TL_{0}\eta\frac{(1-\beta_{1})}{(1-\beta_{2})\left(1-\frac{\beta_{1}}{\sqrt[4]{\beta_{2}}}\right)(1-\frac{\beta_{1}^{2}}{\beta_{2}})}\right)^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{1-\beta_{2}}\left(\frac{4(f(\bm{w}_{1})-f(\bm{w}_{T+1}))}{\eta\left(1-\frac{\beta_{1}}{\sqrt[4]{\beta_{2}}}\right)(1-\beta_{1})}+4TL_{0}\eta\frac{(1-\beta_{1})}{(1-\beta_{2})\left(1-\frac{\beta_{1}}{\sqrt[4]{\beta_{2}}}\right)(1-\frac{\beta_{1}^{2}}{\beta_{2}})}\right)^{2}.$

The proof is completed by applying the value of $\eta$. ∎

###  B.2 Proof for GDM

This section collects the proof of Theorem 2. To begin with, given problem
hyperparameters $\Delta_{1}$, $\varepsilon$, $L_{0}$, and $L_{1}$. We first
construct three 1D functions as follows:

$f_{1}(x)=\left\\{\begin{aligned}
&\frac{L_{0}e^{L_{1}x-1}}{L_{1}^{2}}&,x\in\left[\frac{1}{L_{1}},\infty\right),\\\
&\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}e^{-L_{1}x-1}}{L_{1}^{2}}&,x\in\left(-\infty,-\frac{1}{L_{1}}\right].\end{aligned}\right.$
(3) $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.$
(4) $f_{3}(z)=\left\\{\begin{aligned}
&\varepsilon(z-1)+\frac{\varepsilon}{2L_{1}}+\frac{L_{0}}{2L_{1}^{2}}&,z\in[1,\infty),\\\
&\frac{\varepsilon
L_{1}}{2}z^{2}+\frac{L_{0}}{2L_{1}^{2}}&,z\in[0,\frac{1}{L_{1}}],\\\
&\frac{L_{0}z^{2}}{2}+\frac{L_{0}}{2L_{1}^{2}}&,z\in[-\frac{1}{L_{1}},0],\\\
&\frac{L_{0}e^{-L_{1}z-1}}{L_{1}^{2}}&,z\in\left(-\infty,-\frac{1}{L_{1}}\right].\end{aligned}\right.$
(5)

It is easy to verify that these functions satisfy $(L_{0},L_{1})$-smooth
condition as long as $\varepsilon\leq L_{0}$. We then respectively the
convergence of GDM over these three examples with different learning rate and
momentum coefficient.

######  Lemma 6 (Convergence over $f_{1}$).

Assume $\Delta_{1}\geq\frac{L_{0}}{L_{1}^{2}}(e-\frac{1}{2})$,
$\varepsilon\leq 1$ ,and let
$x_{1}=\frac{1+\log(\frac{1}{2}+\frac{L_{1}^{2}}{L_{0}}\Delta_{1})}{L_{1}}$.
Then, we have $f_{1}(x_{1})-f_{1}^{*}=\Delta_{1}$, and if
$\eta\geq\frac{(5+8\log\frac{1}{\varepsilon})(1+\log(\frac{1}{2}+\frac{L_{1}^{2}}{L_{0}}\Delta_{1}))}{L_{1}^{2}(\Delta_{1}+\frac{L_{0}}{2L_{1}^{2}})}$
and $\beta\leq
1-2\left(\frac{L_{1}^{2}}{L_{0}}e\right)^{-4\log\frac{1}{\varepsilon}-2}(\Delta_{1}+\frac{L_{0}}{2L_{1}^{2}})^{-4\log\frac{1}{\varepsilon}-2}$,
we have that GDM satisfies that $\forall t\in[1,\infty)$,
$|f_{1}^{\prime}(x_{t})|\geq L_{1}\Delta_{1}$.

###### Proof.

We prove this lemma by proving that $\forall k\geq 1$,
$|x_{k+1}|\geq(4+8\log\frac{1}{\varepsilon})|x_{k}|$ and
$\operatorname{Sign}(x_{k+1})=(-1)^{k+1}$ by induction. When $k=1$, according
to the update rule of GDM, we have

$x_{2}=x_{1}-\eta f_{1}^{\prime}(x_{1}).$

As
$\eta\geq\frac{(5+8\log\frac{1}{\varepsilon})(1+\log(\frac{1}{2}+\frac{L_{1}^{2}}{L_{0}}\Delta_{1}))}{\Delta_{1}+\frac{L_{0}}{2L_{1}^{2}}}=-\frac{(5+8\log\frac{1}{\varepsilon})x_{1}}{f_{1}^{\prime}(x_{1})}$,
we have

$x_{2}\leq-(4+8\log\frac{1}{\varepsilon})x_{1},$

which leads to the claim.

Now assuming that the claim has been proved for $k\leq t-1$ ($t\geq 2$). Then,
for $k=t$, with induction hypothesis we have

$x_{t+1}=x_{t}-\eta\bm{m}_{t}=x_{t}-\eta\left(\beta^{t}f_{1}^{\prime}(x_{1})+(1-\beta)\sum_{s=1}^{t-1}\beta^{t-s}f_{1}^{\prime}(x_{s})+(1-\beta)f_{1}^{\prime}(x_{t})\right).$

Without the loss of generality, we assume $t$ is even. By the induction
hypothesis, we obtain that $f_{1}^{\prime}(x_{t})<0$ and
$f_{1}^{\prime}(x_{t-1})<0$, and

$|f_{1}^{\prime}(x_{1})|\leq|f_{1}^{\prime}(x_{2})|\leq\cdots\leq|f_{1}^{\prime}(x_{t-1})|.$

Therefore, we have

$\displaystyle x_{t+1}\geq$ $\displaystyle x_{t}-\eta\left(\beta
f_{1}^{\prime}(x_{t-1})+(1-\beta)f_{1}^{\prime}(x_{t})\right)$
$\displaystyle=$ $\displaystyle x_{t}-\frac{L_{0}}{L_{1}}\eta\left(\beta
e^{L_{1}x_{t-1}-1}-(1-\beta)e^{-L_{1}x_{t}-1}\right)$ $\displaystyle\geq$
$\displaystyle x_{t}-\frac{L_{0}}{L_{1}}\eta\left(\beta
e^{-\frac{L_{1}x_{t}}{8\log\frac{1}{\varepsilon}+4}-1}-(1-\beta)e^{-L_{1}x_{t}-1}\right).$

Furthermore, according to the definition of $x_{1}$, we have

$1-\beta\geq 2e^{-L_{1}(4\log\frac{1}{\varepsilon}+2)x_{1}}\geq
2e^{\frac{L_{1}x_{t}}{2}},$

which leads to

$\displaystyle x_{t+1}\geq x_{t}+\frac{L_{0}}{L_{1}}\eta
e^{-\frac{L_{1}x_{t}}{2}-1}\geq
x_{t}+\frac{(5+8\log\frac{1}{\varepsilon})x_{1}}{e^{L_{1}x_{1}}}e^{-\frac{L_{1}x_{t}}{2}}\geq
x_{t}+\frac{(5+8\log\frac{1}{\varepsilon})x_{1}}{e^{L_{1}x_{1}}}e^{L_{1}x_{t}(2+4\log\frac{1}{\varepsilon})}.$

Then, as $\frac{e^{\frac{L_{1}x}{2}}}{x}$ is monotonously increasing for
$x\in[\frac{2}{L_{1}},\infty)$, and $x_{1}\geq\frac{2}{L_{1}}$, we have

$x_{t+1}\geq
x_{t}+\frac{(5+8\log\frac{1}{\varepsilon})x_{1}}{e^{L_{1}x_{1}}}e^{L_{1}x_{t}(1+2\log\frac{1}{\varepsilon})}\geq
x_{t}-(5+8\log\frac{1}{\varepsilon})x_{t}\geq-(4+8\log\frac{1}{\varepsilon})x_{t}.$

The proof is completed. ∎

######  Lemma 7 (Convergence over $f_{2}$).

Assume that $\Delta_{1}\geq\frac{\varepsilon}{2}+\frac{L_{1}}{L_{0}}$, and let
$y_{1}\triangleq\frac{\Delta_{1}}{\varepsilon}+\frac{1}{2}$. Then, if
$\eta\leq\frac{(5+8\log\frac{1}{\varepsilon})(1+\log(\frac{1}{2}+\frac{L_{1}^{2}}{L_{0}}\Delta_{1}))}{L_{1}^{2}(\Delta_{1}+\frac{L_{0}}{2L_{1}^{2}})}$,
we have that GDM satisfies that $\|\nabla f_{2}(y_{t})\|\geq\varepsilon$ if
$T\leq\tilde{\Theta}(\frac{L_{1}^{2}\Delta_{1}^{2}+L_{0}\Delta_{1}}{\varepsilon^{2}})$.

###### Proof.

We have that $\bm{m}_{t}=\varepsilon$ before $y_{t}$ enters the region
$(-\infty,1]$. As the movement of each step before $y_{t}$ enters the region
$(-\infty,1]$ is $\eta\varepsilon$ and the total length to enter $(-\infty,1]$
is $y_{1}-1$, the proof is completed. ∎

######  Lemma 8 (Convergence over $f_{3}$).

Assume
$\Delta_{1}\geq\frac{L_{0}}{L_{1}^{2}}e+4e+\frac{L_{0}^{2}}{e^{2}L_{1}^{2}}$,
$L_{1}\geq 1$, $\varepsilon\leq\frac{1}{2}$, and let
$z_{1}=-\frac{1+\log(\frac{1}{2}+\frac{L_{1}^{2}}{L_{0}}\Delta_{1})}{L_{1}}$.
Then, we have $f_{3}(z_{1})-f_{3}^{*}=\Delta_{1}$, and if
$\eta\geq\frac{(5+8\log\frac{1}{\varepsilon})(1+\log(\frac{1}{2}+\frac{L_{1}^{2}}{L_{0}}\Delta_{1}))}{L_{1}^{2}(\Delta_{1}+\frac{L_{0}}{2L_{1}^{2}})}$
and $\beta\geq
1-2\left(\frac{L_{1}^{2}}{L_{0}}e\right)^{-4\log\frac{1}{\varepsilon}-2}(\Delta_{1}+\frac{L_{0}}{2L_{1}^{2}})^{-4\log\frac{1}{\varepsilon}-2}$,
we have that GDM satisfies that $\forall
t\in[1,\Theta(\frac{L_{1}^{2}\Delta_{1}^{2}}{\varepsilon^{3}}))$,
$|f_{3}^{\prime}(x_{t})|\geq\varepsilon$.

###### Proof.

To begin with, according to the definition of $z_{1}$, we have
$\eta\geq-\frac{(5+8\log\frac{1}{\varepsilon})z_{1}}{f_{3}^{\prime}(x_{1})}$
and $1-\beta\geq
2e^{L_{1}(4\log\frac{1}{\varepsilon}+2)z_{1}}\geq\frac{1}{2}$. Also. as
$\Delta_{1}\geq\frac{L_{0}}{L_{1}^{2}}(e-\frac{1}{2})$, we have
$z_{1}\leq-\frac{2}{L_{1}}$, and thus

$f^{\prime}_{3}(z_{1})=-\frac{L_{0}}{L_{1}}e^{-L_{1}z_{1}-1}\leq-
L_{1}\left(\Delta_{1}+\frac{L_{0}}{2L_{1}^{2}}\right)\leq-4.$

We will first prove the following claim by induction: for
$k\in[2,\lfloor\frac{1}{1-\beta}\rfloor]$, we have $z_{k}\geq\frac{1}{L_{1}}$,
and $\bm{m}_{k}\leq\frac{\beta^{k-1}f_{3}^{\prime}(z_{1})}{2}.$

As for $k=2$, we have

$z_{2}=z_{1}-\eta
f_{3}^{\prime}(z_{1})\geq-\left(4+8\log\frac{1}{\varepsilon}\right)z_{1}.$

According to $\Delta_{1}\geq\frac{L_{0}}{L_{1}^{2}}(e-\frac{1}{2})$, we have
$z_{1}\leq-\frac{2}{L_{1}}$, and thus $z_{2}\geq\frac{1}{L_{1}}$. Since
$\bm{m}_{2}=\beta
f^{\prime}(z_{1})+(1-\beta)\varepsilon<\frac{f_{3}^{\prime}(z_{1})}{2}$, the
claim is proved for $k=2$.

Now assuming that we have prove the claim for $k\leq t-1$. According to the
induction hypothesis, we have

$f_{3}^{\prime}(z_{2})=\cdots=f_{3}^{\prime}(z_{t-1})=\varepsilon,$

and thus

$\bm{m}_{t}=\beta^{t-1}f_{3}^{\prime}(z_{1})+(1-\beta^{t-1})\varepsilon\overset{(\star)}{\leq}\beta^{t-1}f_{3}^{\prime}(z_{1})-\frac{\beta^{t-1}f_{3}^{\prime}(z_{1})}{2}\leq\frac{\beta^{t-1}f_{3}^{\prime}(z_{1})}{2}.$

Here inequality $(\star)$ is due to
$\beta^{\lfloor\frac{1}{1-\beta}\rfloor}\geq\frac{1}{4}$ as
$\beta\geq\frac{1}{2}$. Therefore, as $z_{t}=z_{t-1}-\eta\bm{m}_{t}\geq
z_{t-1}\geq\frac{1}{L_{1}}$, we prove the claim.

It should be noticed that $\forall t\in[1,\lfloor\frac{1}{1-\beta}\rfloor]$,
$\|f_{3}^{\prime}(z_{t})|\geq\varepsilon$. Furthermore, according to the
claim, $z_{\lfloor\frac{1}{1-\beta}\rfloor+1}$ can now be bounded as

$\displaystyle z_{\lfloor\frac{1}{1-\beta}\rfloor+1}=$ $\displaystyle
z_{1}-\eta\sum_{k=1}^{\lfloor\frac{1}{1-\beta}\rfloor}\bm{m}_{t}\geq\frac{\eta}{5+8\log\frac{1}{\varepsilon}}f_{3}^{\prime}(z_{1})-\eta\sum_{k=1}^{\lfloor\frac{1}{1-\beta}\rfloor}\frac{\beta^{k-1}f_{3}^{\prime}(z_{1})}{2}\geq\frac{\eta}{5+8\log\frac{1}{\varepsilon}}f_{3}^{\prime}(z_{1})-\eta\frac{1-\frac{1}{e}}{(1-\beta)}\frac{f_{3}^{\prime}(z_{1})}{2}$
$\displaystyle\geq$
$\displaystyle\frac{1}{L_{1}}-\eta\frac{1-\frac{1}{e}}{(1-\beta)}\frac{f_{3}^{\prime}(z_{1})}{4}\geq\frac{1}{L_{1}}-\eta\left(1-\frac{1}{e}\right)\frac{f_{3}^{\prime}(z_{1})}{8}\left(\frac{L_{1}^{2}}{L_{0}}e\right)^{4\log\frac{1}{\varepsilon}+2}\left(\Delta_{1}+\frac{L_{0}}{2L_{1}^{2}}\right)^{4\log\frac{1}{\varepsilon}+2}$
$\displaystyle\geq$
$\displaystyle\frac{1}{L_{1}}+\frac{\eta}{16}\frac{L_{1}^{2}\Delta_{1}^{2}+L_{0}\Delta_{1}}{\varepsilon^{2}}.$

As $f_{3}^{\prime}(z)=\varepsilon$ for all $z\geq\frac{1}{L_{1}}$, the
iterates needs additional
$\frac{\frac{\eta}{16}\frac{L_{1}^{2}\Delta_{1}^{2}}{\varepsilon^{2}}}{\eta\varepsilon}=\frac{1}{16}\frac{L_{1}^{2}\Delta_{1}^{2}}{\varepsilon^{3}}$
steps to make $f_{3}^{\prime}(z_{t})<\varepsilon$. The proof is completed. ∎

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

Assume that $\Delta_{1}\geq
4\frac{L_{0}}{L_{1}}e+16e+4\frac{L_{0}^{2}}{e^{2}L_{1}^{2}}$, $L_{1}\geq 1$
and $\varepsilon\leq 1$, then there exists objective function $f$ satisfying
$(L_{0},L_{1})$-smooth condition and $f(\bm{w}_{1})-f^{*}=\Delta_{1}$, such
that for any learning rate $\eta>0$ and $\beta\in[0,1]$, the minimum step $T$
of GDM to achieve final error $\varepsilon$ satisfies

$T=\tilde{\Omega}\left(\frac{L_{1}^{2}\Delta_{1}^{2}+L_{0}\Delta_{1}}{\varepsilon^{2}}\right).$

###### Proof.

Construct the objective function as
$f(x,y,z,u)=f_{1}(x)+f_{2}(y)+f_{3}(z)+f_{4}(u)$. Then, let $x_{1}$, $y_{1}$,
$z_{1}$, $u_{1}$ be chosen as
$f_{1}(x_{1})-f_{1}^{*}=f_{2}(y_{1})-f_{2}^{*}=f_{3}(z_{1})-f_{3}^{*}=\frac{\Delta_{1}}{3}$
and $z_{1}\leq 0$. Then, for each learning rate and momentum coefficient, they
will always be cover by one of the above lemmas, and applying the
corresponding lemma gives the desired result.

The proof is completed. ∎

###  B.3 Proof for Deterministic AdaGrad

To begin with, we recall the following result from Wang et al. (2023b):

######  Proposition 2.

For every learning rate $\eta\geq\Theta(\frac{1}{L_{1}})$ and $\Delta_{1}$,
there exist a lower-bounded objective function $g_{1}$ obeying Assumption 1
and a corresponding initialization point $\bm{w}_{0}$ with
$g_{1}(\bm{w}_{1})-g_{1}^{*}=\Delta_{1}$, such that AdaGrad with learning rate
$\eta$ and initialized at $\bm{w}_{0}$ diverges over $g_{1}$.

We then define $g_{2}$ as the $f_{2}$ in the proof of Theorem 2, i.e.,

$g_{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.$
(6)

We then have the following lemma characterizing the convergence of AdaGrad
over $g_{2}$.

######  Lemma 9 (Convergence over $g_{2}$).

Assume that $\Delta_{1}\geq\frac{\varepsilon}{2}+\frac{L_{1}}{L_{0}}$, and let
$y_{1}\triangleq\frac{\Delta_{1}}{\varepsilon}+\frac{1}{2}$. Then, if
$\eta\leq\Theta(\frac{1}{L_{1}})$, we have that AdaGrad satisfies that
$\|\nabla g_{2}(y_{t})\|\geq\varepsilon$ if
$T\leq\tilde{\Theta}(\frac{L_{1}^{2}\Delta_{1}^{2}}{\varepsilon^{2}})$.

###### Proof.

We have that $\bm{g}_{t}=\varepsilon$ before $y_{t}$ enters the region
$(-\infty,1]$. Therefore, the sum of movement of each step before $y_{t}$
enters the region $(-\infty,1]$ is

$\eta\sum_{s=1}^{t}\frac{\varepsilon}{\sqrt{s}\varepsilon}=\eta\Theta(\sqrt{t}).$

Solving $\eta\Theta(\sqrt{t})=\frac{\Delta_{1}}{\varepsilon}+\frac{1}{2}-1$
gives $t=\frac{L_{1}^{2}\Delta_{1}^{2}}{\varepsilon^{2}}$, and the proof is
completed. ∎

We then have the following lower bound for deterministic AdaGrad.

######  Theorem 9.

Assume that $\Delta_{1}\geq\frac{\varepsilon}{2}+\frac{L_{1}}{L_{0}}$. Then,
there exists objective function $f$ satisfying $(L_{0},L_{1})$-smooth
condition and $f(\bm{w}_{1})-f^{*}=\Delta_{1}$, such that for any learning
rate $\eta>0$ and $\beta\in[0,1]$, the minimum step $T$ of AdaGrad to achieve
final error $\varepsilon$ satisfies

$T=\Omega(\frac{L_{1}^{2}\Delta_{1}^{2}}{\varepsilon^{2}}).$

###### Proof.

The proof is completed by letting $f(x,y)=g_{1}(x)+g_{2}(y)$ following the
same routine as Theorem 8. ∎

##  Appendix C Proof for stochastic algorithms

###  C.1 Proof for Adam

To begin with, we restate the theorem as follows:

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

Let Assumptions 1 and 2 hold. Then, $\forall\beta_{1}\geq 0$ and $\lambda=0$,
if
$\varepsilon\leq\frac{1}{\operatorname{poly}(f(\bm{w}_{1})-f^{*},L_{0},L_{1},\sigma_{0},\sigma_{1})}$,
with
$\eta=\frac{\sqrt{f(\bm{w}_{1})-f^{*}}}{\sqrt{L_{0}+L_{1}}\sqrt{T\sigma_{0}\sigma_{1}^{2}}}$
and momentum hyperparameter
$\beta_{2}=1-\eta^{2}\left(\frac{1024\sigma_{1}^{2}(L_{1}+L_{0})(1-\beta_{1})}{\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}}}(1-\frac{\beta_{1}}{\sqrt{\beta_{2}}})}\right)^{2}$,
we have if
$T\geq\Theta\left(\frac{(L_{0}+L_{1})\sigma_{0}^{3}\sigma_{1}^{2}(f(\bm{w}_{1})-f^{*})}{\varepsilon^{4}}\right)$,
then Algorithm 1 satisfies

$\frac{1}{T}\mathbb{E}\sum_{t=1}^{T}\|\nabla f(\bm{w}_{t})\|\leq\varepsilon.$

###### Proof.

Let the approximate iterative sequence be defined as
$\bm{u}_{t}\triangleq\frac{\bm{w}_{t}-\frac{\beta_{1}}{\sqrt{\beta_{2}}}\bm{w}_{t-1}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}$
and the surrogate second-order momentum be defined as
$\widetilde{\bm{\nu}}_{t}\triangleq\beta_{2}\bm{\nu}_{t-1}+(1-\beta_{2})\sigma_{0}^{2}$.
Then, as
$\frac{\eta}{\sqrt{1-\beta_{2}}}=\frac{\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}}}(1-\frac{\beta_{1}}{\sqrt{\beta_{2}}})}{1024\sigma_{1}^{2}(L_{1}+L_{0})(1-\beta_{1})}$,
we have

$\|\bm{u}_{t}-\bm{w}_{t}\|=\frac{\frac{\beta_{1}}{\sqrt{\beta_{2}}}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\|\bm{w}_{t}-\bm{w}_{t-1}\|\overset{(*)}{\leq}\eta\frac{\frac{\beta_{1}}{\sqrt{\beta_{2}}}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\frac{1-\beta_{1}}{\sqrt{1-\beta_{2}}\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}}}}\leq\frac{1}{4L_{1}},$

and

$\|\bm{u}_{t+1}-\bm{w}_{t}\|=\frac{1}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\|\bm{w}_{t+1}-\bm{w}_{t}\|\overset{(*)}{\leq}\eta\frac{1}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\frac{1-\beta_{1}}{\sqrt{1-\beta_{2}}\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}}}}\leq\frac{1}{4L_{1}}.$

Therefore, if choosing $\bm{w}^{1}=\bm{w}_{t}$, $\bm{w}^{2}=\bm{u}_{t+1}$, and
$\bm{w}^{3}=\bm{u}_{t}$ in Lemma 2, we see the conditions of Lemma 2 is
satisfied, which after taking expectation gives

$\displaystyle\mathbb{E}^{|{\mathcal{F}}_{t}}f(\bm{u}_{t+1})\leq
f(\bm{u}_{t})+\mathbb{E}^{|{\mathcal{F}}_{t}}\langle\nabla
f(\bm{w}_{t}),\bm{u}_{t+1}-\bm{u}_{t}\rangle+\frac{1}{2}(L_{0}+L_{1}\|\nabla
f(\bm{w}_{t})\|)\mathbb{E}^{|{\mathcal{F}}_{t}}(\|\bm{u}_{t+1}-\bm{w}_{t}\|+\|\bm{u}_{t}-\bm{w}_{t}\|)\|\bm{u}_{t+1}-\bm{u}_{t}\|.$

We call $\langle\nabla f(\bm{w}_{t}),\bm{u}_{t+1}-\bm{u}_{t}\rangle$ the
first-order term and $\frac{1}{2}(L_{0}+L_{1}\|\nabla
f(\bm{w}_{t})\|)(\|\bm{u}_{t+1}-\bm{w}_{t}\|+\|\bm{u}_{t}-\bm{w}_{t}\|)\|\bm{u}_{t+1}-\bm{u}_{t}\|$
the second-order term, as they respectively correspond to the first-order and
second-order Taylor’s expansion. We then respectively bound these two terms as
follows.

Analysis for the first-order term. Before we start, denote
$\widetilde{\bm{\nu}}_{t}\triangleq\beta_{2}\bm{\nu}_{t-1}+(1-\beta_{2})\sigma_{0}^{2}$

$\displaystyle\bm{u}_{t+1}-\bm{u}_{t}=$
$\displaystyle\frac{\bm{w}_{t+1}-\bm{w}_{t}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}-\frac{\beta_{1}}{\sqrt{\beta_{2}}}\frac{\bm{w}_{t}-\bm{w}_{t-1}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}$
$\displaystyle=$
$\displaystyle-\frac{\eta}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\frac{1}{\sqrt{\bm{\nu}_{t}}}\bm{m}_{t}+\beta_{1}\frac{\eta}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}\bm{m}_{t-1}$
$\displaystyle=$
$\displaystyle-\frac{\eta}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\frac{1}{\sqrt{\tilde{\bm{\nu}}_{t}}}\bm{m}_{t}+\beta_{1}\frac{\eta}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\frac{1}{\sqrt{\widetilde{\bm{\nu}}_{t}}}\bm{m}_{t-1}-\frac{\eta}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\left(\frac{1}{\sqrt{\bm{\nu}_{t}}}-\frac{1}{\sqrt{\tilde{\bm{\nu}}_{t}}}\right)\bm{m}_{t}$
$\displaystyle+\beta_{1}\frac{\eta}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\left(\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}-\frac{1}{\sqrt{\widetilde{\bm{\nu}}_{t}}}\right)\bm{m}_{t-1}$
$\displaystyle=$
$\displaystyle-\eta\frac{1-\beta_{1}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\frac{1}{\sqrt{\tilde{\bm{\nu}}_{t}}}\bm{g}_{t}-\frac{\eta}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\left(\frac{1}{\sqrt{\bm{\nu}_{t}}}-\frac{1}{\sqrt{\tilde{\bm{\nu}}_{t}}}\right)\bm{m}_{t}+\beta_{1}\frac{\eta}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\left(\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}-\frac{1}{\sqrt{\widetilde{\bm{\nu}}_{t}}}\right)\bm{m}_{t-1}.$

According to the above decomposition, we have the first-order term can also be
decomposed into

$\displaystyle\mathbb{E}^{|{\mathcal{F}}_{t}}\left[\left\langle\nabla
f(\bm{w}_{t}),\bm{u}_{t+1}-\bm{u}_{t}\right\rangle\right]$ $\displaystyle=$
$\displaystyle\frac{1-\beta_{1}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\mathbb{E}^{|{\mathcal{F}}_{t}}\left[\left\langle\bm{G}_{t},-\eta\frac{1}{\sqrt{\tilde{\bm{\nu}}_{t}}}\bm{g}_{t}\right\rangle\right]+\mathbb{E}^{|{\mathcal{F}}_{t}}\left[\left\langle\bm{G}_{t},-\frac{\eta}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\left(\frac{1}{\sqrt{\bm{\nu}_{t}}}-\frac{1}{\sqrt{\tilde{\bm{\nu}}_{t}}}\right)\bm{m}_{t}\right\rangle\right]$
$\displaystyle+\mathbb{E}^{|{\mathcal{F}}_{t}}\left[\left\langle\bm{G}_{t},\beta_{1}\frac{\eta}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\left(\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}-\frac{1}{\sqrt{\widetilde{\bm{\nu}}_{t}}}\right)\bm{m}_{t-1}\right\rangle\right].$
(7)

As
$\mathbb{E}^{|{\mathcal{F}}_{t}}\left[\left\langle\bm{G}_{t},-\eta\frac{1}{\sqrt{\tilde{\bm{\nu}}_{t}}}\bm{g}_{t}\right\rangle\right]=-\eta\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t}}}$,
we have

$\frac{1-\beta_{1}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\mathbb{E}^{|{\mathcal{F}}_{t}}\left[\left\langle\bm{G}_{t},-\eta\frac{1}{\sqrt{\tilde{\bm{\nu}}_{t}}}\bm{g}_{t}\right\rangle\right]\leq-\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t}}}.$

We then respectively bound the rest of the two terms in Eq. (7). To begin
with,

$\displaystyle\mathbb{E}^{|\mathcal{F}_{t}}\left[\left\langle\bm{G}_{t},-\frac{\eta}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\left(\frac{1}{\sqrt{\bm{\nu}_{t}}}-\frac{1}{\sqrt{\tilde{\bm{\nu}}_{t}}}\right)\bm{m}_{t}\right\rangle\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}^{|\mathcal{F}_{t}}\left[\left\langle\bm{G}_{t},-\frac{\eta}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\left(\frac{(1-\beta_{2})(\sigma_{0}^{2}-\|\bm{g}_{t}\|^{2})}{\sqrt{\bm{\nu}_{t}}\sqrt{\tilde{\bm{\nu}}_{t}}(\sqrt{\bm{\nu}_{t}}+\sqrt{\tilde{\bm{\nu}}_{t}})}\right)\bm{m}_{t}\right\rangle\right]$
$\displaystyle\leq$
$\displaystyle\frac{\eta}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\mathbb{E}^{|\mathcal{F}_{t}}\left[\|\bm{G}_{t}\|\left(\frac{(1-\beta_{2})(\sigma_{0}^{2}+\|\bm{g}_{t}\|^{2})}{\sqrt{\bm{\nu}_{t}}\sqrt{\tilde{\bm{\nu}}_{t}}(\sqrt{\bm{\nu}_{t}}+\sqrt{\tilde{\bm{\nu}}_{t}})}\right)\|\bm{m}_{t}\|\right]$
$\displaystyle=$
$\displaystyle{\frac{\eta}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\mathbb{E}^{|\mathcal{F}_{t}}\left[\|\bm{G}_{t}\|\left(\frac{(1-\beta_{2})\|\bm{g}_{t}\|^{2}}{\sqrt{\bm{\nu}_{t}}\sqrt{\tilde{\bm{\nu}}_{t}}(\sqrt{\bm{\nu}_{t}}+\sqrt{\tilde{\bm{\nu}}_{t}})}\right)\|\bm{m}_{t}\|\right]}+{\frac{\eta}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\mathbb{E}^{|\mathcal{F}_{t}}\left[\|\bm{G}_{t}\|\left(\frac{(1-\beta_{2})\sigma_{0}^{2}}{\sqrt{\bm{\nu}_{t}}\sqrt{\tilde{\bm{\nu}}_{t}}(\sqrt{\bm{\nu}_{t}}+\sqrt{\tilde{\bm{\nu}}_{t}})}\right)\|\bm{m}_{t}\|\right]}.$
(8)

The first term in the right-hand-side of Eq. (8) can be bounded as

$\displaystyle\frac{\eta}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\mathbb{E}^{|\mathcal{F}_{t}}\left[\|\bm{G}_{t}\|\left(\frac{(1-\beta_{2})\|\bm{g}_{t}\|^{2}}{\sqrt{\bm{\nu}_{t}}\sqrt{\tilde{\bm{\nu}}_{t}}(\sqrt{\bm{\nu}_{t}}+\sqrt{\tilde{\bm{\nu}}_{t}})}\right)\|\bm{m}_{t}\|\right]\overset{(*)}{\leq}\frac{\eta(1-\beta_{1})}{\left(\sqrt{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\right)^{3}}\mathbb{E}^{|\mathcal{F}_{t}}\left[\|\bm{G}_{t}\|\left(\frac{\sqrt{1-\beta_{2}}\|\bm{g}_{t}\|^{2}}{\sqrt{\tilde{\bm{\nu}}_{t}}(\sqrt{\bm{\nu}_{t}}+\sqrt{\tilde{\bm{\nu}}_{t}})}\right)\right]$
$\displaystyle\overset{(\circ)}{\leq}$
$\displaystyle\frac{\eta(1-\beta_{1})}{\left(\sqrt{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\right)^{3}}\frac{\|\bm{G}_{t}\|}{\sqrt{\tilde{\bm{\nu}}_{t}}}\sqrt{\mathbb{E}^{|\mathcal{F}_{t}}\|\bm{g}_{t}\|^{2}}\sqrt{\mathbb{E}^{|\mathcal{F}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{(\sqrt{\bm{\nu}_{t}}+\sqrt{\tilde{\bm{\nu}}_{t}})^{2}}}\overset{(\bullet)}{\leq}\frac{\eta(1-\beta_{1})\sqrt{1-\beta_{2}}}{\left(\sqrt{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\right)^{3}}\frac{\|\bm{G}_{t}\|}{\sqrt{\tilde{\bm{\nu}}_{t}}}\sqrt{\sigma_{0}^{2}+\sigma_{1}^{2}\|\bm{G}_{t}\|^{2}}\sqrt{\mathbb{E}^{|\mathcal{F}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{(\sqrt{\bm{\nu}_{t}}+\sqrt{\tilde{\bm{\nu}}_{t}})^{2}}}$
$\displaystyle\leq$
$\displaystyle\frac{\eta(1-\beta_{1})\sqrt{1-\beta_{2}}}{\left(\sqrt{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\right)^{3}}\frac{\|\bm{G}_{t}\|}{\sqrt{\tilde{\bm{\nu}}_{t}}}(\sigma_{0}+\sigma_{1}\|\bm{G}_{t}\|)\sqrt{\mathbb{E}^{|\mathcal{F}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{(\sqrt{\bm{\nu}_{t}}+\sqrt{\tilde{\bm{\nu}}_{t}})^{2}}},$

where inequality $(*)$ uses Lemma 1, inequality $(\circ)$ is due to Holder’s
inequality, and inequality $(\bullet)$ is due to Assumption 2. Applying mean-
value inequality respectively to
$\frac{\eta(1-\beta_{1})\sqrt{1-\beta_{2}}}{\left(\sqrt{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\right)^{3}}\mathbb{E}^{|\mathcal{F}_{t}}\frac{\|\bm{G}_{t}\|}{\sqrt{\tilde{\bm{\nu}}_{t}}}\sigma_{0}\sqrt{\mathbb{E}^{|\mathcal{F}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{(\sqrt{\bm{\nu}_{t}}+\sqrt{\tilde{\bm{\nu}}_{t}})^{2}}}$
and
$\frac{\eta(1-\beta_{1})\sqrt{1-\beta_{2}}}{\left(\sqrt{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\right)^{3}}\mathbb{E}^{|\mathcal{F}_{t}}\frac{\|\bm{G}_{t}\|}{\sqrt{\tilde{\bm{\nu}}_{t}}}\sigma_{1}\|\bm{G}_{t}\|\sqrt{\mathbb{E}^{|\mathcal{F}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{(\sqrt{\bm{\nu}_{t}}+\sqrt{\tilde{\bm{\nu}}_{t}})^{2}}}$
and due to $\beta_{1}\leq\beta_{2}$, we obtain that the right-hand-side of the
above inequality can be bounded by

$\displaystyle\frac{1}{16}\eta\frac{1-\beta_{1}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\sqrt{1-\beta_{2}}\sigma_{0}\frac{\|\bm{G}_{t}\|^{2}}{\tilde{\bm{\nu}}_{t}}+\frac{4\eta\sqrt{1-\beta_{2}}\sigma_{0}}{\left(1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}\right)^{2}}\mathbb{E}^{|\mathcal{F}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{(\sqrt{\bm{\nu}_{t}}+\sqrt{\tilde{\bm{\nu}}_{t}})^{2}}$
$\displaystyle+\frac{1}{16}\eta\frac{1-\beta_{1}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\tilde{\bm{\nu}}_{t}}}+4\eta\frac{(1-\beta_{2})(1-\beta_{1})}{(1-\frac{\beta_{1}}{\sqrt{\beta_{2}}})^{2}}\sigma_{1}^{2}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\tilde{\bm{\nu}}_{t}}}\mathbb{E}^{|\mathcal{F}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{(\sqrt{\bm{\nu}_{t}}+\sqrt{\tilde{\bm{\nu}}_{t}})^{2}}$
$\displaystyle\leq$
$\displaystyle\frac{1}{8}\eta\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\tilde{\bm{\nu}}_{t}}}+\frac{4\eta\sqrt{1-\beta_{2}}\sigma_{0}}{\left(1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}\right)^{2}}\mathbb{E}^{|\mathcal{F}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{\bm{\nu}_{t}}+\frac{1}{8}\eta\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\tilde{\bm{\nu}}_{t}}}+16\eta\frac{(1-\beta_{2})}{(1-\beta_{1})}\sigma_{1}^{2}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\tilde{\bm{\nu}}_{t}}}\mathbb{E}^{|\mathcal{F}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{(\sqrt{\bm{\nu}_{t}}+\sqrt{\tilde{\bm{\nu}}_{t}})^{2}}.$
(9)

Here the inequality is due to
$\widetilde{\bm{\nu}}_{t}=(1-\beta_{2})\sigma_{0}^{2}+\beta_{2}\bm{\nu}_{t-1}\geq(1-\beta_{2})\sigma_{0}^{2}$.
Meanwhile, we have

$\displaystyle\left(\frac{1}{\sqrt{\beta_{2}\widetilde{\bm{\nu}}_{t}}}-\frac{1}{\sqrt{\widetilde{\bm{\nu}}_{t+1}}}\right)\|\bm{G}_{t}\|^{2}$
$\displaystyle=$
$\displaystyle\frac{\|\bm{G}_{t}\|^{2}((1-\beta_{2})^{2}\sigma_{0}^{2}+\beta_{2}(1-\beta_{2})\|\bm{g}_{t}\|^{2})}{\sqrt{\beta_{2}\widetilde{\bm{\nu}}_{t}}\sqrt{\widetilde{\bm{\nu}}_{t+1}}(\sqrt{\beta_{2}\widetilde{\bm{\nu}}_{t}}+\sqrt{\widetilde{\bm{\nu}}_{t+1}})}\geq\frac{\|\bm{G}_{t}\|^{2}\beta_{2}(1-\beta_{2})\|\bm{g}_{t}\|^{2}}{\sqrt{\beta_{2}\widetilde{\bm{\nu}}_{t}}\sqrt{\widetilde{\bm{\nu}}_{t+1}}(\sqrt{\beta_{2}\widetilde{\bm{\nu}}_{t}}+\sqrt{\widetilde{\bm{\nu}}_{t+1}})}$
$\displaystyle\geq$
$\displaystyle\frac{1}{4}\frac{\|\bm{G}_{t}\|^{2}(1-\beta_{2})\|\bm{g}_{t}\|^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t}}(\sqrt{\bm{\nu}_{t}}+\sqrt{\widetilde{\bm{\nu}}_{t}})^{2}},$

where in the last inequality, we use $\sqrt{\beta_{2}}\geq\frac{1}{2}$.
Applying the above inequality back to Eq. (9), we obtain that

$\displaystyle\frac{\eta}{1-\beta_{1}}\mathbb{E}^{|\mathcal{F}_{t}}\left[\|\bm{G}_{t}\|\left(\frac{(1-\beta_{2})\bm{g}_{t}^{2}}{\sqrt{\bm{\nu}_{t}}\sqrt{\tilde{\bm{\nu}}_{t}}(\sqrt{\bm{\nu}_{t}}+\sqrt{\tilde{\bm{\nu}}_{t}})}\right)\|\bm{m}_{t}\|\right]$
$\displaystyle\leq$
$\displaystyle\frac{1}{4}\eta\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\tilde{\bm{\nu}}_{t}}}+\frac{4\eta\sqrt{1-\beta_{2}}\sigma_{0}}{\left(1-\frac{\beta_{1}^{2}}{\beta_{2}}\right)^{2}}\mathbb{E}^{|\mathcal{F}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{\bm{\nu}_{t}}+\eta\frac{64}{(1-\beta_{1})}\sigma_{1}^{2}\mathbb{E}^{|\mathcal{F}_{t}}\left(\frac{1}{\sqrt{\beta_{2}\widetilde{\bm{\nu}}_{t}}}-\frac{1}{\sqrt{\widetilde{\bm{\nu}}_{t+1}}}\right)\|\bm{G}_{t}\|^{2}.$
(10)

Furthermore, due to Assumption 1, we have (we define $G_{0}\triangleq G_{1}$)

$\displaystyle\|\bm{G}_{t+1}\|^{2}\leq$
$\displaystyle\|\bm{G}_{t}\|^{2}+2\|\bm{G}_{t}\|\|\bm{G}_{t+1}-\bm{G}_{t}\|+\|\bm{G}_{t+1}-\bm{G}_{t}\|^{2}$
$\displaystyle\leq$
$\displaystyle\|\bm{G}_{t}\|^{2}+2(L_{0}+L_{1}\|\bm{G}_{t}\|)\|\bm{G}_{t}\|\|\bm{w}_{t+1}-\bm{w}_{t}\|+2(L_{0}^{2}+L_{1}^{2}\|\bm{G}_{t}\|^{2})\|\bm{w}_{t+1}-\bm{w}_{t}\|^{2},$

which by
$\frac{\eta}{\sqrt{1-\beta_{2}}}=\frac{\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}}}(1-\frac{\beta_{1}}{\sqrt{\beta_{2}}})^{2}}{1024\sigma_{1}^{2}(L_{1}+L_{0})(1-\beta_{1})}$
further leads to

$\displaystyle\frac{1}{\sqrt{\beta_{2}\widetilde{\bm{\nu}}_{t+1}}}\|\bm{G}_{t}\|^{2}$
$\displaystyle\geq$
$\displaystyle\frac{1}{\sqrt{\beta_{2}\widetilde{\bm{\nu}}_{t+1}}}\left(\|\bm{G}_{t+1}\|^{2}-2(L_{0}+L_{1}\|\bm{G}_{t}\|)\|\bm{G}_{t}\|\|\bm{w}_{t+1}-\bm{w}_{t}\|-2(L_{0}^{2}+L_{1}^{2}\|\bm{G}_{t}\|^{2})\|\bm{w}_{t+1}-\bm{w}_{t}\|^{2}\right)$
$\displaystyle\geq$
$\displaystyle\left(\frac{1}{\sqrt{\beta_{2}\widetilde{\bm{\nu}}_{t+1}}}\|\bm{G}_{t+1}\|^{2}-\frac{2L_{0}}{\sigma_{0}}\frac{(1-\beta_{1})}{64\sigma_{1}^{2}}\|\bm{w}_{t+1}-\bm{w}_{t}\|^{2}-\frac{3}{8}\frac{(1-\beta_{1})}{64\sigma_{1}^{2}}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t}}}\right).$

Applying the above inequality back to Eq. (10) leads to that

$\displaystyle\frac{\eta}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\mathbb{E}^{|\mathcal{F}_{t}}\left[\|\bm{G}_{t}\|\left(\frac{(1-\beta_{2})\bm{g}_{t}^{2}}{\sqrt{\bm{\nu}_{t}}\sqrt{\tilde{\bm{\nu}}_{t}}(\sqrt{\bm{\nu}_{t}}+\sqrt{\tilde{\bm{\nu}}_{t}})}\right)\|\bm{m}_{t}\|\right]$
$\displaystyle\leq$
$\displaystyle\frac{5}{8}\eta\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\tilde{\bm{\nu}}_{t}}}+\frac{4\eta\sqrt{1-\beta_{2}}\sigma_{0}}{\left(1-{\beta_{1}}\right)^{2}}\mathbb{E}^{|\mathcal{F}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{\bm{\nu}_{t}}+\eta\frac{64}{(1-\beta_{1})}\sigma_{1}^{2}\mathbb{E}^{|\mathcal{F}_{t}}\left(\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\widetilde{\bm{\nu}}_{t}}}-\frac{\|\bm{G}_{t+1}\|^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t+1}}}\right)$
$\displaystyle+2\frac{L_{0}}{\sigma_{0}}\mathbb{E}^{|{\mathcal{F}}_{t}}\|\bm{w}_{t+1}-\bm{w}_{t}\|^{2}.$
(11)

As for the second term in the right-hand-side of Eq. (8), we have

$\displaystyle\frac{\eta}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\mathbb{E}^{|\mathcal{F}_{t}}\left[\|\bm{G}_{t}\|\left(\frac{(1-\beta_{2})\sigma_{0}^{2}}{\sqrt{\bm{\nu}_{t}}\sqrt{\tilde{\bm{\nu}}_{t}}(\sqrt{\bm{\nu}_{t}}+\sqrt{\tilde{\bm{\nu}}_{t}})}\right)\|\bm{m}_{t}\|\right]$
$\displaystyle\leq$
$\displaystyle\frac{\eta}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\mathbb{E}^{|\mathcal{F}_{t}}\left[\|\bm{G}_{t}\|\left(\frac{\sqrt[4]{1-\beta_{2}}\sqrt{\sigma_{0}}}{\sqrt[4]{\tilde{\bm{\nu}}_{t}}\sqrt{\bm{\nu}_{t}}}\right)\|\bm{m}_{t}\|\right]$
$\displaystyle\leq$
$\displaystyle\frac{1}{8}\eta\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\tilde{\bm{\nu}}_{t}}}+\frac{8\eta\sqrt{1-\beta_{2}}\sigma_{0}}{(1-\beta_{1})^{2}}\mathbb{E}^{|\mathcal{F}_{t}}\left[\left(\frac{\|\bm{m}_{t}\|^{2}}{\bm{\nu}_{t}}\right)\right].$
(12)

In the last inequality we use again $\beta_{2}\geq\beta_{1}$. With
Inequalities (11) and (12), we conclude that the first-order term can be
bounded by

$\displaystyle\mathbb{E}^{|{\mathcal{F}}_{t}}\left[\left\langle\nabla
f(\bm{w}_{t}),\bm{u}_{t+1}-\bm{u}_{t}\right\rangle\right]\leq$
$\displaystyle-\frac{1}{4}\eta\mathbb{E}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\tilde{\bm{\nu}}_{t}}}+\frac{4\eta\sqrt{1-\beta_{2}}\sigma_{0}}{\left(1-\beta_{1}\right)^{2}}\mathbb{E}^{|\mathcal{F}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{\bm{\nu}_{t}}+\eta\frac{64}{(1-{\beta_{1}})}\sigma_{1}^{2}\mathbb{E}^{|\mathcal{F}_{t}}\left(\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\widetilde{\bm{\nu}}_{t}}}-\frac{\|\bm{G}_{t+1}\|^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t+1}}}\right)$
$\displaystyle+2\frac{L_{0}}{\sigma_{0}}\mathbb{E}^{|{\mathcal{F}}_{t}}\|\bm{w}_{t+1}-\bm{w}_{t}\|^{2}+\frac{8\eta\sqrt{1-\beta_{2}}\sigma_{0}}{(1-\beta_{1})^{2}}\mathbb{E}^{|\mathcal{F}_{t}}\left[\left(\frac{\|\bm{m}_{t}\|^{2}}{\bm{\nu}_{t}}\right)\right].$
(13)

Analysis for the second-order term. To recall, the second order term is
$\frac{1}{2}(L_{0}+L_{1}\|\nabla
f(\bm{w}_{t})\|)(\|\bm{u}_{t+1}-\bm{w}_{t}\|+\|\bm{u}_{t}-\bm{w}_{t}\|)\|\bm{u}_{t+1}-\bm{u}_{t}\|$.
Before we start, we have the following expansion for
$\bm{u}_{t+1}-\bm{u}_{t}$: (here the operations are all coordinate-wisely)

$\displaystyle\bm{u}_{t+1}-\bm{u}_{t}=$
$\displaystyle\frac{\bm{w}_{t+1}-\bm{w}_{t}-\frac{\beta_{1}}{\sqrt{\beta_{2}}}(\bm{w}_{t}-\bm{w}_{t-1})}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}$
$\displaystyle=$
$\displaystyle\frac{-\eta\frac{\bm{m}_{t}}{\sqrt{\bm{\nu}_{t}}}+\eta\frac{\beta_{1}}{\sqrt{\beta_{2}}}\frac{\bm{m}_{t-1}}{\sqrt{\bm{\nu}_{t-1}}}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}=\frac{-\eta\frac{\bm{m}_{t}}{\sqrt{\bm{\nu}_{t}}}+\eta\beta_{1}\frac{\bm{m}_{t-1}}{\sqrt{\bm{\nu}_{t}}}-\eta\beta_{1}\frac{\bm{m}_{t-1}}{\sqrt{\bm{\nu}_{t}}}+\eta\frac{\beta_{1}}{\sqrt{\beta_{2}}}\frac{\bm{m}_{t-1}}{\sqrt{\bm{\nu}_{t-1}}}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}$
$\displaystyle=$
$\displaystyle\frac{-\eta\frac{(1-\beta_{1})\bm{g}_{t}}{\sqrt{\bm{\nu}_{t}}}+\eta\frac{\beta_{1}(1-\beta_{2})\|\bm{g}_{t}\|^{2}}{\sqrt{\beta_{2}}}\frac{\bm{m}_{t-1}}{\sqrt{\bm{\nu}_{t-1}}\sqrt{\bm{\nu}_{t}}(\sqrt{\bm{\nu}_{t}}+\sqrt{\beta_{2}\bm{\nu}_{t-1}})}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}$
(14)

Then firstly, we have

$\displaystyle\frac{1}{2}L_{0}(\|\bm{u}_{t+1}-\bm{w}_{t}\|+\|\bm{u}_{t}-\bm{w}_{t}\|)\|\bm{u}_{t+1}-\bm{u}_{t}\|$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}L_{0}\left(\|\bm{u}_{t+1}-\bm{u}_{t}\|^{2}+\frac{1}{2}\|\bm{u}_{t+1}-\bm{w}_{t}\|^{2}+\frac{1}{2}\|\bm{u}_{t}-\bm{w}_{t}\|^{2}\right)$
$\displaystyle=$
$\displaystyle\frac{1}{2}L_{0}\left(\left\|\frac{-\eta\frac{(1-\beta_{1})\bm{g}_{t}}{\sqrt{\bm{\nu}_{t}}}+\eta\frac{\beta_{1}(1-\beta_{2})\|\bm{g}_{t}\|^{2}}{\sqrt{\beta_{2}}}\frac{\bm{m}_{t-1}}{\sqrt{\bm{\nu}_{t-1}}\sqrt{\bm{\nu}_{t}}(\sqrt{\bm{\nu}_{t}}+\sqrt{\beta_{2}\bm{\nu}_{t-1}})}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\right\|^{2}+\frac{1}{2}\left\|\frac{\frac{\beta_{1}}{\sqrt{\beta_{2}}}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}(\bm{w}_{t}-\bm{w}_{t-1})\right\|^{2}+\frac{1}{2}\left\|\frac{1}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}(\bm{w}_{t+1}-\bm{w}_{t})\right\|^{2}\right)$
$\displaystyle\leq$
$\displaystyle\frac{L_{0}\eta^{2}}{2}\left(\left(\frac{1-\beta_{1}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}+\frac{\beta_{1}(1-\beta_{1})}{(\sqrt{\beta_{2}}-\beta_{1})\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}}}}\right)^{2}\left\|\frac{\bm{g}_{t}}{\sqrt{\bm{\nu}_{t}}}\right\|^{2}+\frac{1}{2}\left(\frac{\frac{\beta_{1}}{\sqrt{\beta_{2}}}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\right)^{2}\left\|\frac{\bm{m}_{t-1}}{\sqrt{\bm{\nu}_{t-1}}}\right\|^{2}+\frac{1}{2}\left(\frac{1}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\right)^{2}\left\|\frac{\bm{m}_{t}}{\sqrt{\bm{\nu}_{t}}}\right\|^{2}\right)$
$\displaystyle\overset{(\bullet)}{\leq}$
$\displaystyle\frac{L_{0}\eta^{2}}{2}\left(2\left(\frac{1-\beta_{1}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}+\frac{\beta_{1}(1-\beta_{1})}{(\sqrt{\beta_{2}}-\beta_{1})\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}}}}\right)^{2}\left\|\frac{\bm{g}_{t}}{\sqrt{\bm{\nu}_{t}}}\right\|^{2}+\left(\frac{\frac{\beta_{1}}{\sqrt{\beta_{2}}}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\right)^{2}\left\|\frac{\bm{m}_{t-1}}{\sqrt{\bm{\nu}_{t-1}}}\right\|^{2}\right).$

Secondly, we have

$\displaystyle\frac{1}{2}L_{1}\|\nabla
f(\bm{w}_{t})\|(\|\bm{u}_{t+1}-\bm{w}_{t}\|+\|\bm{u}_{t}-\bm{w}_{t}\|)\|\bm{u}_{t+1}-\bm{u}_{t}\|$
$\displaystyle\leq$ $\displaystyle\frac{1}{2}L_{1}\|\nabla
f(\bm{w}_{t})\|(2\|\bm{u}_{t+1}-\bm{w}_{t}\|+\|\bm{u}_{t+1}-\bm{u}_{t}\|)\left(\frac{\left\|\eta\frac{(1-\beta_{1})\bm{g}_{t}}{\sqrt{\bm{\nu}_{t}}}\right\|}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}+\frac{\eta\frac{\beta_{1}(1-\beta_{2})\|\bm{g}_{t}\|^{2}}{\sqrt{\beta_{2}}}\frac{\|\bm{m}_{t-1}\|}{\sqrt{\bm{\nu}_{t-1}}\sqrt{\bm{\nu}_{t}}(\sqrt{\bm{\nu}_{t}}+\sqrt{\beta_{2}\bm{\nu}_{t-1}})}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\right)$
$\displaystyle\overset{(*)}{\leq}$ $\displaystyle\frac{1}{2}L_{1}\|\nabla
f(\bm{w}_{t})\|(2\|\bm{u}_{t+1}-\bm{w}_{t}\|+\|\bm{u}_{t+1}-\bm{u}_{t}\|)\left(\frac{\left\|\eta\frac{(1-\beta_{1})\bm{g}_{t}}{\sqrt{\bm{\nu}_{t}}}\right\|}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}+\frac{\eta\frac{\beta_{1}(1-\beta_{1})}{\sqrt{\beta_{2}}}\frac{\|\bm{g}_{t}\|}{\sqrt{\bm{\nu}_{t}}}}{(1-\frac{\beta_{1}}{\sqrt{\beta_{2}}})\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}}}}\right)$
$\displaystyle=$
$\displaystyle\frac{L_{1}}{2}\eta\left(\frac{1-\beta_{1}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}+\frac{\beta_{1}(1-\beta_{1})}{(\sqrt{\beta_{2}}-\beta_{1})\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}}}}\right)\|\nabla
f(\bm{w}_{t})\|(2\|\bm{u}_{t+1}-\bm{w}_{t}\|+\|\bm{u}_{t}-\bm{u}_{t+1}\|)\frac{\|\bm{g}_{t}\|}{\sqrt{\bm{\nu}_{t}}}$
$\displaystyle\overset{(\circ)}{=}$
$\displaystyle\frac{L_{1}}{2}\eta\left(\frac{1-\beta_{1}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}+\frac{\beta_{1}(1-\beta_{1})}{(\sqrt{\beta_{2}}-\beta_{1})\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}}}}\right)\|\bm{G}_{t}\|\left(\|\bm{u}_{t+1}-\bm{u}_{t}\|+2\frac{1}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\eta\left\|\frac{\bm{m}_{t}}{\sqrt{\bm{\nu}_{t}}}\right\|\right)\frac{\|\bm{g}_{t}\|}{\sqrt{\bm{\nu}_{t}}}.$

where inequality $(*)$ is due to that
$\frac{\|\bm{m}_{t-1}\|}{\sqrt{\bm{\nu}_{t-1}}}\leq\frac{1-\beta_{1}}{\sqrt{1-\beta_{2}}\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}}}}$,
$\frac{\|\bm{g}_{t}\|}{\sqrt{\bm{\nu}_{t}}}\leq\frac{1}{\sqrt{1-\beta_{2}}}$,
and equation $(\circ)$ is due to
$\bm{u}_{t}-\bm{w}_{t}=\frac{\frac{\beta_{1}}{\sqrt{\beta_{2}}}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}(\bm{w}_{t}-\bm{w}_{t-1})$
and
$\bm{u}_{t+1}-\bm{w}_{t}=\frac{1}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}(\bm{w}_{t+1}-\bm{w}_{t})$.
As for the term
$\|\bm{G}_{t}\|\frac{\|\bm{m}_{t}\|}{\sqrt{\bm{\nu}_{t}}}\frac{\|\bm{g}_{t}\|}{\sqrt{\bm{\nu}_{t}}}$,
we first add additional denominator for it. Specifically, we have

$\displaystyle\|\bm{G}_{t}\|\frac{\|\bm{m}_{t}\|}{\sqrt{\bm{\nu}_{t}}}\frac{\|\bm{g}_{t}\|}{\sqrt{\bm{\nu}_{t}}}=$
$\displaystyle\frac{\|\bm{G}_{t}\|\|\bm{m}_{t}\|\|\bm{g}_{t}\|}{\bm{\nu}_{t}+(1-\beta_{2})\sigma_{0}^{2}}+\frac{\|\bm{G}_{t}\|\|\bm{m}_{t}\|\|\bm{g}_{t}\|(1-\beta_{2})\sigma_{0}^{2}}{(\bm{\nu}_{t}+(1-\beta_{2})\sigma_{0}^{2})\bm{\nu}_{t}}$
$\displaystyle\leq$
$\displaystyle\frac{\|\bm{G}_{t}\|\|\bm{m}_{t}\|\|\bm{g}_{t}\|}{\bm{\nu}_{t}+(1-\beta_{2})\sigma_{0}^{2}}+\frac{\|\bm{G}_{t}\|\|\bm{m}_{t}\|\sigma_{0}}{\sqrt{\bm{\nu}_{t}+(1-\beta_{2})\sigma_{0}^{2}}\sqrt{\bm{\nu}_{t}}}$
$\displaystyle\leq$
$\displaystyle\frac{\|\bm{G}_{t}\|\|\bm{m}_{t}\|\|\bm{g}_{t}\|}{\bm{\nu}_{t}+(1-\beta_{2})\sigma_{0}^{2}}+\frac{1}{2}\frac{\|\bm{G}_{t}\|^{2}\sigma_{0}}{\bm{\nu}_{t}+(1-\beta_{2})\sigma_{0}^{2}}+\frac{1}{2}\sigma_{0}\frac{\|\bm{m}_{t}\|^{2}}{\bm{\nu}_{t}}$
$\displaystyle\leq$
$\displaystyle\frac{\|\bm{G}_{t}\|\|\bm{m}_{t}\|\|\bm{g}_{t}\|}{\bm{\nu}_{t}+(1-\beta_{2})\sigma_{0}^{2}}+\frac{1}{2\sqrt{1-\beta_{2}}}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\bm{\nu}_{t}+(1-\beta_{2})\sigma_{0}^{2}}}+\frac{1}{2}\sigma_{0}\frac{\|\bm{m}_{t}\|^{2}}{\bm{\nu}_{t}}.$

We analyze the first term in the right-hand-side of above inequality more
carefully. Specifically, this term with expectation can be bounded as

$\displaystyle\mathbb{E}^{|{\mathcal{F}}_{t}}\frac{\|\bm{G}_{t}\|\|\bm{m}_{t}\|\|\bm{g}_{t}\|}{\bm{\nu}_{t}+(1-\beta_{2})\sigma_{0}^{2}}$
$\displaystyle\leq$
$\displaystyle\mathbb{E}^{|{\mathcal{F}}_{t}}\frac{\|\bm{G}_{t}\|\|\bm{m}_{t}\|\|\bm{g}_{t}\|}{\sqrt{\bm{\nu}_{t}+(1-\beta_{2})\sigma_{0}^{2}}\sqrt{\beta_{2}\bm{\nu}_{t-1}+(1-\beta_{2})\sigma_{0}^{2}}}$
$\displaystyle\leq$
$\displaystyle\frac{\|\bm{G}_{t}\|}{\sqrt{\beta_{2}\bm{\nu}_{t-1}+(1-\beta_{2})\sigma_{0}^{2}}}\sqrt{\|\bm{g}_{t}\|^{2}}\sqrt{\mathbb{E}^{|{\mathcal{F}}_{t}}\frac{\|\bm{m}_{t}\|^{2}}{\bm{\nu}_{t}+(1-\beta_{2})\sigma_{0}^{2}}}$
$\displaystyle\overset{(\star)}{\leq}$
$\displaystyle\frac{\|\bm{G}_{t}\|}{\sqrt{\beta_{2}\bm{\nu}_{t-1}+(1-\beta_{2})\sigma_{0}^{2}}}\sqrt{\sigma_{1}^{2}\|\bm{G}_{t}\|^{2}+\sigma_{0}^{2}}\sqrt{\mathbb{E}^{|{\mathcal{F}}_{t}}\frac{\|\bm{m}_{t}\|^{2}}{\bm{\nu}_{t}+(1-\beta_{2})\sigma_{0}^{2}}}$
$\displaystyle\leq$
$\displaystyle\frac{\|\bm{G}_{t}\|}{\sqrt{\beta_{2}\bm{\nu}_{t-1}+(1-\beta_{2})\sigma_{0}^{2}}}(\sigma_{1}\|\bm{G}_{t}\|+\sigma_{0})\sqrt{\mathbb{E}^{|{\mathcal{F}}_{t}}\frac{\|\bm{m}_{t}\|^{2}}{\bm{\nu}_{t}+(1-\beta_{2})\sigma_{0}^{2}}}$
$\displaystyle\leq$
$\displaystyle\frac{1-\beta_{1}}{\sqrt{1-\beta_{2}}\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}}}}\sigma_{1}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}+(1-\beta_{2})\sigma_{0}^{2}}}+\frac{1}{2\sqrt{1-\beta_{2}}}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}+(1-\beta_{2})\sigma_{0}^{2}}}+\frac{\sigma_{0}}{2}\mathbb{E}^{|{\mathcal{F}}_{t}}\frac{\|\bm{m}_{t}\|^{2}}{\bm{\nu}_{t}+(1-\beta_{2})\sigma_{0}^{2}},$

where Eq. ($\star$) is due to Holder’s inequality.

Meanwhile, due to Eq. (14), we have that the term
$|\bm{G}_{t}\|\|\bm{u}_{t+1}-\bm{u}_{t}\|\frac{\|\bm{g}_{t}\|}{\sqrt{\bm{\nu}_{t}}}$
can be be bounded as

$\displaystyle|\bm{G}_{t}\|\|\bm{u}_{t+1}-\bm{u}_{t}\|\frac{\|\bm{g}_{t}\|}{\sqrt{\bm{\nu}_{t}}}\leq\eta\left(\frac{1-\beta_{1}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}+\frac{\beta_{1}(1-\beta_{1})}{(\sqrt{\beta_{2}}-\beta_{1})\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}}}}\right)\|\bm{G}_{t}\|\frac{\|\bm{g}_{t}\|}{\sqrt{\bm{\nu}_{t}}}\frac{\|\bm{g}_{t}\|}{\sqrt{\bm{\nu}_{t}}}.$

Then, following the similar reasoning above, we have
$|\bm{G}_{t}\|\|\bm{u}_{t+1}-\bm{u}_{t}\|\frac{\|\bm{g}_{t}\|}{\sqrt{\bm{\nu}_{t}}}$
can be bounded as

$\displaystyle\mathbb{E}^{|{\mathcal{F}}_{t}}\|\bm{G}_{t}\|\frac{\|\bm{g}_{t}\|}{\sqrt{\bm{\nu}_{t}}}\frac{\|\bm{g}_{t}\|}{\sqrt{\bm{\nu}_{t}}}$
$\displaystyle\leq$
$\displaystyle\frac{1}{\sqrt{1-\beta_{2}}}\sigma_{1}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}+(1-\beta_{2})\sigma_{0}^{2}}}+\frac{1}{2\sqrt{1-\beta_{2}}}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}+(1-\beta_{2})\sigma_{0}^{2}}}+\sigma_{0}\mathbb{E}^{|{\mathcal{F}}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{\bm{\nu}_{t}+(1-\beta_{2})\sigma_{0}^{2}}$
$\displaystyle+\frac{1}{2\sqrt{1-\beta_{2}}}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\bm{\nu}_{t}+(1-\beta_{2})\sigma_{0}^{2}}}+\frac{1}{2}\sigma_{0}\mathbb{E}^{|{\mathcal{F}}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{\bm{\nu}_{t}}.$

Putting all the estimations together, we have that the second-order term can
be bounded by

$\displaystyle\mathbb{E}^{|{\mathcal{F}}_{t}}\frac{1}{2}(L_{0}+L_{1}\|\nabla
f(\bm{w}_{t})\|)(\|\bm{u}_{t+1}-\bm{w}_{t}\|+\|\bm{u}_{t}-\bm{w}_{t}\|)\|\bm{u}_{t+1}-\bm{u}_{t}\|$
$\displaystyle\leq$
$\displaystyle\frac{L_{1}\eta^{2}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\left(\frac{1-\beta_{1}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}+\frac{\beta_{1}(1-\beta_{1})}{(\sqrt{\beta_{2}}-\beta_{1})\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}}}}\right)\left(\frac{2}{\sqrt{1-\beta_{2}}}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}+(1-\beta_{2})\sigma_{0}^{2}}}+\frac{\sigma_{0}}{2}\mathbb{E}^{|{\mathcal{F}}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{\bm{\nu}_{t}}\right)$
$\displaystyle+\frac{L_{0}\eta^{2}}{2}\left(2\left(\frac{1-\beta_{1}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}+\frac{\beta_{1}(1-\beta_{1})}{(\sqrt{\beta_{2}}-\beta_{1})\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}}}}\right)^{2}\mathbb{E}^{|{\mathcal{F}}_{t}}\left\|\frac{\bm{g}_{t}}{\sqrt{\bm{\nu}_{t}}}\right\|^{2}+\left(\frac{\frac{\beta_{1}}{\sqrt{\beta_{2}}}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\right)^{2}\left\|\frac{\bm{m}_{t-1}}{\sqrt{\bm{\nu}_{t-1}}}\right\|^{2}\right)$
$\displaystyle\leq$ $\displaystyle
4\frac{L_{1}\eta^{2}}{1-\beta_{1}}\left(1+\frac{1}{\sqrt{1-\beta_{1}}}\right)\left(\frac{2}{\sqrt{1-\beta_{2}}}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}+(1-\beta_{2})\sigma_{0}^{2}}}+\frac{\sigma_{0}}{2}\mathbb{E}^{|{\mathcal{F}}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{\bm{\nu}_{t}}\right)$
$\displaystyle+2L_{0}\eta^{2}\left(2\left(1+\frac{1}{\sqrt{1-\beta_{1}}}\right)^{2}\mathbb{E}^{|{\mathcal{F}}_{t}}\left\|\frac{\bm{g}_{t}}{\sqrt{\bm{\nu}_{t}}}\right\|^{2}+\left(\frac{1}{1-\beta_{1}}\right)^{2}\left\|\frac{\bm{m}_{t-1}}{\sqrt{\bm{\nu}_{t-1}}}\right\|^{2}\right)$
$\displaystyle\leq$
$\displaystyle\frac{1}{8}\eta\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t}}}+4\frac{L_{1}\eta^{2}\sigma_{0}}{(1-\beta_{1})^{\frac{3}{2}}}\mathbb{E}^{|{\mathcal{F}}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{\bm{\nu}_{t}}+2L_{0}\eta^{2}\left(8\frac{1}{1-\beta_{1}}\mathbb{E}^{|{\mathcal{F}}_{t}}\left\|\frac{\bm{g}_{t}}{\sqrt{\bm{\nu}_{t}}}\right\|^{2}+\left(\frac{1}{1-\beta_{1}}\right)^{2}\left\|\frac{\bm{m}_{t-1}}{\sqrt{\bm{\nu}_{t-1}}}\right\|^{2}\right).$
(15)

Here in the second inequality we use $\beta_{2}\geq\beta_{1}$, and in the last
inequality we use
$\frac{\eta}{\sqrt{1-\beta_{2}}}=\frac{\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}}}(1-\frac{\beta_{1}}{\sqrt{\beta_{2}}})^{2}}{1024\sigma_{1}^{2}(L_{1}+L_{0})(1-\beta_{1})}$.

Applying the estimations of the first-order term (Eq. (13)) and the second-
order term (Eq. (15)) back into the descent lemma, we derive that

$\displaystyle\mathbb{E}^{|{\mathcal{F}}_{t}}f(\bm{u}_{t+1})\leq$
$\displaystyle
f(\bm{u}_{t})-\frac{1}{8}\eta\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\tilde{\bm{\nu}}_{t}}}+\frac{4\eta\sqrt{1-\beta_{2}}\sigma_{0}}{\left(1-\beta_{1}\right)^{2}}\mathbb{E}^{|\mathcal{F}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{\bm{\nu}_{t}}+\eta\frac{64}{(1-{\beta_{1}})}\sigma_{1}^{2}\mathbb{E}^{|\mathcal{F}_{t}}\left(\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\widetilde{\bm{\nu}}_{t}}}-\frac{\|\bm{G}_{t+1}\|^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t+1}}}\right)$
$\displaystyle+2\frac{L_{0}}{\sigma_{0}}\mathbb{E}^{|{\mathcal{F}}_{t}}\|\bm{w}_{t+1}-\bm{w}_{t}\|^{2}+\frac{8\eta\sqrt{1-\beta_{2}}\sigma_{0}}{(1-\beta_{1})^{2}}\mathbb{E}^{|\mathcal{F}_{t}}\left[\left(\frac{\|\bm{m}_{t}\|^{2}}{\bm{\nu}_{t}}\right)\right]$
$\displaystyle+4\frac{L_{1}\eta^{2}\sigma_{0}}{(1-\beta_{1})^{\frac{3}{2}}}\mathbb{E}^{|{\mathcal{F}}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{\bm{\nu}_{t}}+2L_{0}\eta^{2}\left(8\frac{1}{1-\beta_{1}}\mathbb{E}^{|{\mathcal{F}}_{t}}\left\|\frac{\bm{g}_{t}}{\sqrt{\bm{\nu}_{t}}}\right\|^{2}+\left(\frac{1}{1-\beta_{1}}\right)^{2}\left\|\frac{\bm{m}_{t-1}}{\sqrt{\bm{\nu}_{t-1}}}\right\|^{2}\right).$

Taking expectation to the above inequality and summing it over $t\in[1,T]$
then gives

$\displaystyle\frac{1}{8}\eta\sum_{t=1}^{T}\mathbb{E}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t}}}\leq$
$\displaystyle
f(\bm{u}_{1})-f^{*}+\eta\frac{64}{(1-{\beta_{1}})}\sigma_{1}^{2}\frac{\|\bm{G}_{1}\|^{2}}{\sqrt{\beta_{2}\widetilde{\bm{\nu}}_{1}}}+\eta\frac{64}{(1-{\beta_{1}})}\sigma_{1}^{2}\left(\frac{1}{\sqrt{\beta_{2}}}-1\right)\sum_{t=1}^{T}\mathbb{E}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t}}}$
$\displaystyle+\left(\frac{4\eta\sqrt{1-\beta_{2}}\sigma_{0}}{\left(1-\beta_{1}\right)^{2}}+4\frac{L_{1}\eta^{2}\sigma_{0}}{(1-\beta_{1})^{\frac{3}{2}}}+\frac{16L_{0}\eta^{2}}{1-\beta_{1}}\right)\sum_{t=1}^{T}\mathbb{E}\frac{\|\bm{g}_{t}\|^{2}}{\bm{\nu}_{t}}$
$\displaystyle+\left(2\frac{L_{0}}{\sigma_{0}}\eta^{2}+\frac{8\eta\sqrt{1-\beta_{2}}\sigma_{0}}{(1-\beta_{1})^{2}}+\frac{2L_{0}\eta^{2}}{(1-\beta_{1})^{2}}\right)\sum_{t=1}^{T}\mathbb{E}\left\|\frac{\bm{m}_{t}}{\sqrt{\bm{\nu}_{t}}}\right\|^{2}.$

Since $\beta_{2}\geq\frac{1}{2}$ and
$1-\beta_{2}\leq\frac{1-\beta_{1}}{1024\sigma_{1}^{2}}$, we have

$\eta\frac{64}{(1-{\beta_{1}})}\sigma_{1}^{2}\left(\frac{1}{\sqrt{\beta_{2}}}-1\right)\sum_{t=1}^{T}\mathbb{E}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t}}}\leq\frac{1}{16}\eta\sum_{t=1}^{T}\mathbb{E}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t}}}.$

By further applying Lemma 3 and $\beta_{2}\geq\beta_{1}$, we obtain

$\displaystyle\frac{1}{16}\eta\sum_{t=1}^{T}\mathbb{E}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t}}}$
$\displaystyle\leq$ $\displaystyle
f(\bm{u}_{1})-f^{*}+\eta\frac{64}{(1-{\beta_{1}})}\sigma_{1}^{2}\frac{\|\bm{G}_{1}\|^{2}}{\sqrt{\beta_{2}\widetilde{\bm{\nu}}_{1}}}$
(16)
$\displaystyle+\frac{1}{1-\beta_{2}}\left(\frac{36\eta\sqrt{1-\beta_{2}}\sigma_{0}}{\left(1-\beta_{1}\right)^{2}}+4\frac{L_{1}\eta^{2}\sigma_{0}}{(1-\beta_{1})^{\frac{3}{2}}}+\frac{24L_{0}\eta^{2}}{1-\beta_{1}}+8\frac{L_{0}}{\sigma_{0}}\eta^{2}\right)\left(\mathbb{E}\ln\bm{\nu}_{T}-T\ln\beta_{2}\right)$
$\displaystyle\leq$ $\displaystyle
f(\bm{w}_{1})-f^{*}+\eta\frac{64}{(1-{\beta_{1}})}\sigma_{1}^{2}\frac{\|\bm{G}_{1}\|^{2}}{\sqrt{\beta_{2}\widetilde{\bm{\nu}}_{1}}}$
$\displaystyle+\frac{1}{1-\beta_{2}}\left(\frac{147456\eta^{2}(L_{0}+L_{1})\sigma_{1}^{2}\sigma_{0}}{\left(1-\beta_{1}\right)^{\frac{5}{2}}}+4\frac{L_{1}\eta^{2}\sigma_{0}}{(1-\beta_{1})^{\frac{3}{2}}}+\frac{24L_{0}\eta^{2}}{1-\beta_{1}}+8\frac{L_{0}}{\sigma_{0}}\eta^{2}\right)\left(\mathbb{E}\ln\bm{\nu}_{T}-T\ln\beta_{2}\right).$
(17)

Here last inequality we apply
$\frac{\eta}{\sqrt{1-\beta_{2}}}=\frac{\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}}}(1-\frac{\beta_{1}}{\sqrt{\beta_{2}}})^{2}}{1024\sigma_{1}^{2}(L_{1}+L_{0})(1-\beta_{1})}$.

Below we transfer the above bound to the bound of
$\sum_{t=1}^{T}\|\bm{G}_{t}\|$ by two rounds of divide-and-conquer. In the
first round, we will bound $\mathbb{E}\ln\bm{\nu}_{T}$. To start with, we have
that

$\displaystyle\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t}}}\mathds{1}_{\|G_{t}\|\geq\frac{\sigma_{0}}{\sigma_{1}}}\geq\frac{\frac{1}{2\sigma_{1}^{2}}\mathbb{E}^{|{\mathcal{F}}_{t}}\|\bm{g}_{t}\|^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t}}}\mathds{1}_{\|G_{t}\|\geq\frac{\sigma_{0}}{\sigma_{1}}}$
$\displaystyle=$
$\displaystyle\frac{\frac{1}{2\sigma_{1}^{2}}\mathbb{E}^{|{\mathcal{F}}_{t}}\|\bm{g}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}+(1-\beta_{2})\sigma_{0}^{2}}}\mathds{1}_{\|G_{t}\|\geq\frac{\sigma_{0}}{\sigma_{1}}}$
$\displaystyle\geq$
$\displaystyle\frac{1}{2\sigma_{1}^{2}}\mathbb{E}^{|{\mathcal{F}}_{t}}\frac{\beta_{2}^{T-t}\|\bm{g}_{t}\|^{2}}{\sqrt{\bm{\nu}_{T}+(1-\beta_{2})\sigma_{0}^{2}}}\mathds{1}_{\|G_{t}\|\geq\frac{\sigma_{0}}{\sigma_{1}}},$

where the last inequality is due to that

$\displaystyle\beta_{2}\bm{\nu}_{t-1}+(1-\beta_{2})\sigma_{0}^{2}\leq\beta_{2}^{t-T}\bm{\nu}_{T}+(1-\beta_{2})\sigma_{0}^{2}\leq(\bm{\nu}_{T}+(1-\beta_{2})\sigma_{0}^{2})\beta_{2}^{2(t-T)}.$
(18)

Furthermore, we have

$\displaystyle\frac{\sigma_{0}^{2}+\frac{\beta_{2}^{T}\bm{\nu}_{0}}{1-\beta_{2}}}{\sqrt{\bm{\nu}_{T}+(1-\beta_{2})\sigma_{0}^{2}}}+\sum_{t=1}^{T}\mathbb{E}\frac{\beta_{2}^{T-t}\|\bm{g}_{t}\|^{2}}{\sqrt{\bm{\nu}_{T}+(1-\beta_{2})\sigma_{0}^{2}}}\mathds{1}_{\|\bm{G}_{t}\|<\frac{\sigma_{0}}{\sigma_{1}}}$
$\displaystyle\leq$
$\displaystyle\frac{\sigma_{0}^{2}+\frac{\beta_{2}^{T}\bm{\nu}_{0}}{1-\beta_{2}}}{\sqrt{\bm{\nu}_{0}\beta_{2}^{T}+\sum_{s=1}^{T}\beta_{2}^{T-s}\|g_{s}\|^{2}\mathds{1}_{\|\bm{G}_{s}\|<\frac{\sigma_{0}}{\sigma_{1}}}+(1-\beta_{2})\sigma_{0}^{2}}}+\sum_{t=1}^{T}\mathbb{E}\frac{\beta_{2}^{T-s}\|\bm{g}_{t}\|^{2}}{\sqrt{\bm{\nu}_{0}\beta_{2}^{T}+\sum_{s=1}^{T}\beta_{2}^{T-s}\|g_{s}\|^{2}\mathds{1}_{\|\bm{G}_{s}\|<\frac{\sigma_{0}}{\sigma_{1}}}+(1-\beta_{2})\sigma_{0}^{2}}}\mathds{1}_{\|\bm{G}_{t}\|<\frac{\sigma_{0}}{\sigma_{1}}}$
$\displaystyle=$
$\displaystyle\frac{1}{1-\beta_{2}}\mathbb{E}\sqrt{\bm{\nu}_{0}\beta_{2}^{T}+\sum_{s=1}^{T}\beta_{2}^{T-s}\|g_{s}\|^{2}\mathds{1}_{\|\bm{G}_{s}\|<\frac{\sigma_{0}}{\sigma_{1}}}+(1-\beta_{2})\sigma_{0}^{2}}\leq\frac{1}{1-\beta_{2}}\sqrt{\beta_{2}^{T}\bm{\nu}_{0}+2\sigma_{0}^{2}}.$
(19)

Conclusively, we obtain

$\displaystyle\mathbb{E}\sqrt{\bm{\nu}_{T}+(1-\beta_{2})\sigma_{0}^{2}}$
$\displaystyle=$
$\displaystyle(1-\beta_{2})\left(\frac{\sigma_{0}^{2}+\frac{\beta_{2}^{T}\bm{\nu}_{0}}{1-\beta_{2}}}{\sqrt{\bm{\nu}_{T}+(1-\beta_{2})\sigma_{0}^{2}}}+\sum_{t=1}^{T}\mathbb{E}\frac{\beta_{2}^{T-t}\|\bm{g}_{t}\|^{2}}{\sqrt{\bm{\nu}_{T}+(1-\beta_{2})\sigma_{0}^{2}}}\mathds{1}_{\|\bm{G}_{t}\|<\frac{\sigma_{0}}{\sigma_{1}}}\right.$
$\displaystyle+\left.\sum_{t=1}^{T}\mathbb{E}\frac{\beta_{2}^{T-t}\|\bm{g}_{t}\|^{2}}{\sqrt{\bm{\nu}_{T}+(1-\beta_{2})\sigma_{0}^{2}}}\mathds{1}_{\|\bm{G}_{t}\|\geq\frac{\sigma_{0}}{\sigma_{1}}}\right)$
$\displaystyle\leq$
$\displaystyle\sqrt{\beta_{2}^{T}\bm{\nu}_{0}+2\sigma_{0}^{2}}+2(1-\beta_{2})\sigma_{1}^{2}\mathbb{E}\sum_{t=1}^{T}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t}}}\mathds{1}_{\|\bm{G}_{t}\|\geq\frac{\sigma_{0}}{\sigma_{1}}}$
$\displaystyle\leq$
$\displaystyle\sqrt{\beta_{2}^{T}\bm{\nu}_{0}+2\sigma_{0}^{2}}+2(1-\beta_{2})\sigma_{1}^{2}\mathbb{E}\sum_{t=1}^{T}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t}}}.$

Substituting
$\mathbb{E}\sum_{t=1}^{T}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t}}}$
according to Eq. (17), we obtain that

$\displaystyle\mathbb{E}\sqrt{\bm{\nu}_{T}+(1-\beta_{2})\sigma_{0}^{2}}$
$\displaystyle\leq$
$\displaystyle\sqrt{\beta_{2}^{T}\bm{\nu}_{0}+2\sigma_{0}^{2}}+\frac{2(1-\beta_{2})\sigma_{1}^{2}}{\eta}\eta\mathbb{E}\sum_{t=1}^{T}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t}}}$
$\displaystyle\leq$
$\displaystyle\sqrt{\beta_{2}^{T}\bm{\nu}_{0}+2\sigma_{0}^{2}}+\frac{2(1-\beta_{2})\sigma_{1}^{2}}{\eta}\left(f(\bm{w}_{1})-f^{*}+\eta\frac{64}{(1-{\beta_{1}})}\sigma_{1}^{2}\frac{\|\bm{G}_{1}\|^{2}}{\sqrt{\beta_{2}\widetilde{\bm{\nu}}_{1}}}\right.$
$\displaystyle+\left.\frac{1}{1-\beta_{2}}\left(\frac{147456\eta^{2}(L_{0}+L_{1})\sigma_{1}^{2}\sigma_{0}}{\left(1-\beta_{1}\right)^{\frac{5}{2}}}+4\frac{L_{1}\eta^{2}\sigma_{0}}{(1-\beta_{1})^{\frac{3}{2}}}+\frac{24L_{0}\eta^{2}}{1-\beta_{1}}+8\frac{L_{0}}{\sigma_{0}}\eta^{2}\right)\left(\mathbb{E}\ln\bm{\nu}_{T}-T\ln\beta_{2}\right)\right)$
$\displaystyle\leq$
$\displaystyle\sqrt{\beta_{2}^{T}\bm{\nu}_{0}+2\sigma_{0}^{2}}+\sigma_{0}+\frac{1}{4}\mathbb{E}\ln\bm{\nu}_{T}$
$\displaystyle\leq$
$\displaystyle\sqrt{\beta_{2}^{T}\bm{\nu}_{0}+2\sigma_{0}^{2}}+\sigma_{0}+\frac{1}{2}\mathbb{E}\sqrt{\bm{\nu}_{T}+(1-\beta_{2})\sigma_{0}^{2}}.$

where the third inequality is due to

$\displaystyle T\geq$
$\displaystyle\frac{36*2048^{4}(L_{0}+L_{1})^{3}\sigma_{1}^{12}(f(\bm{w}_{1})-f^{*})}{(1-\beta_{1})^{6}\sigma_{0}^{2}}+\frac{768*2048^{2}(f(\bm{w}_{1})-f^{*})\sigma_{1}^{8}(8L_{1}^{2}(f(\bm{w}_{1})-f^{*})^{2}+4L_{0}(f(\bm{w}_{1})-f^{*}))}{(1-\beta_{1})^{4}\sigma_{0}^{2}}$
$\displaystyle+\frac{24^{2}*147456(L_{0}+L_{1})\sigma_{1}^{8}(f(\bm{w}_{1})-f^{*})\sigma_{0}^{2}}{(1-\beta_{2})^{5}}+\frac{128^{2}(L_{0}+L_{1})(f(\bm{w}_{1})-f^{*})\sigma_{1}^{4}}{\sigma_{0}^{2}}$
$\displaystyle+\frac{24^{2}*147456*2048^{2}(L_{0}+L_{1})^{3}\sigma_{1}^{16}(f(\bm{w}_{1})-f^{*})^{3}}{(1-\beta_{2})^{11}}+\frac{128^{2}*2048^{2}(L_{0}+L_{1})^{3}(f(\bm{w}_{1})-f^{*})^{3}\sigma^{12}}{\sigma_{0}^{4}(1-\beta_{1})^{6}},$

and the last inequality is due to $\ln x\leq x$. Solving the above inequality
with respect to $\mathbb{E}\sqrt{\bm{\nu}_{T}+(1-\beta_{2})\sigma_{0}^{2}}$
and applying $\bm{\nu}_{0}=\sigma_{0}^{2}$ then gives

$\displaystyle\mathbb{E}\sqrt{\bm{\nu}_{T}}\leq\mathbb{E}\sqrt{\bm{\nu}_{T}+(1-\beta_{2})\sigma_{0}^{2}}\leq$
$\displaystyle 6\sigma_{0}.$ (20)

Therefore, Eq. (17) can be rewritten as

$\displaystyle\frac{1}{16}\eta\sum_{t=1}^{T}\mathbb{E}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t}}}$
$\displaystyle\leq$ $\displaystyle
f(\bm{w}_{1})-f^{*}+\eta\frac{64}{(1-{\beta_{1}})}\sigma_{1}^{2}\frac{\|\bm{G}_{1}\|^{2}}{\sqrt{\beta_{2}\widetilde{\bm{\nu}}_{1}}}$
$\displaystyle+\frac{1}{1-\beta_{2}}\left(\frac{147456\eta^{2}(L_{0}+L_{1})\sigma_{1}^{2}\sigma_{0}}{\left(1-\beta_{1}\right)^{\frac{5}{2}}}+4\frac{L_{1}\eta^{2}\sigma_{0}}{(1-\beta_{1})^{\frac{3}{2}}}+\frac{24L_{0}\eta^{2}}{1-\beta_{1}}+8\frac{L_{0}}{\sigma_{0}}\eta^{2}\right)\left(2\ln
6\sigma_{0}-T\ln\beta_{2}\right).$ (21)

We then execute the second round of divide-and-conquer. To begin with, we have
that

$\sum_{t=1}^{T}\mathbb{E}\left[\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t}}}\mathds{1}_{\|G_{t}\|\geq\frac{\sigma_{0}}{\sigma_{1}}}\right]\leq\sum_{t=1}^{T}\mathbb{E}\left[\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t}}}\right].$
(22)

On the other hand, we have that

$\displaystyle\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t}}}\mathds{1}_{\|G_{t}\|\geq\frac{\sigma_{0}}{\sigma_{1}}}\geq\frac{\frac{2}{3}\|\bm{G}_{t}\|^{2}+\frac{1}{3}\frac{\sigma^{2}_{0}}{\sigma_{1}^{2}}}{\sqrt{\widetilde{\bm{\nu}}_{t}}}\mathds{1}_{\|G_{t}\|\geq\frac{\sigma_{0}}{\sigma_{1}}}\geq\frac{\frac{\beta_{2}}{3\sigma_{1}^{2}}\mathbb{E}^{|{\mathcal{F}}_{t}}\|\bm{g}_{t}\|^{2}+\frac{1-\beta_{2}}{3}\frac{\sigma^{2}_{0}}{\sigma_{1}^{2}}}{\sqrt{\widetilde{\bm{\nu}}_{t}}}\mathds{1}_{\|G_{t}\|\geq\frac{\sigma_{0}}{\sigma_{1}}}$
$\displaystyle=$