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

## Abstract

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.

## 1 Introduction

Among various optimization techniques, the Adam optimizer (Kingma & Ba, ; Loshchilov & Hutter, ) 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., ; Brown et al., ; Zhang et al., ; Rae et al., ; Chowdhery et al., ; Du et al., ). 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., ). 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., ). 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. () 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](#Thmassumption1)), 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., ; Crawshaw et al., ). 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, ; Carmon et al., ; Arjevani et al., ), 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., ; Li et al., ). However, even under these constraints, the convergence rates obtained for Adam are weaker than those of algorithms like clipped SGDM (Zhang et al., ).

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. () 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., ; Li et al., ), or to more general functions (Mei et al., ).
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., ), sign-based optimizers (Jin et al., ; Hübler et al., ; Sun et al., ), AdaGrad (Faw et al., ; Wang et al., ), variance-reduction methods (Reisizadeh et al., ; Chen et al., ), and trust-region methods (Xie et al., ). 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, ), subsequent analysis by Reddi et al. () pointed out flaws in this initial analysis and provided counterexamples claiming that Adam could fail to converge. Only recently, Shi et al. () and Zhang et al. () have shown that the counterexamples in Reddi et al. () 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. () proved that Adam without momentum can converge to the neighborhood of stationary points by additionally assuming that $\lambda$ is large. De et al. () 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. (), Défossez et al. (), and Guo et al. () derived the convergence of Adam by assuming the stochastic gradient is bounded. Shi et al. () and Zhang et al. () characterized the convergence of random-reshuffling Adam but suffer from sub-optimal rates. He et al. () studied the non-ergodic convergence of Adam under a bounded gradient assumption, while Hong & Lin () provided high-probability guarantees for Adam under a deterministically bounded noise assumption. A concurrent work by Wang et al. () 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., ; Li et al., ), both with restricted assumptions and results. We will provide a detailed discussion in Section [4](#S4).

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., ). However, this can be rectified by combining the GD with the Backtracking Line Search technique (Armijo, ).
In the stochastic offline setting, under the $L$-smooth condition, multiple algorithms have been shown to be parameter-agnostic (Yang et al., ; Ward et al., ; Faw et al., ; Wang et al., ; Cutkosky & Mehta, ). More recently, Hübler et al. () 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 (); Orabona & Tommasi () 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.

Figure: Algorithm 1 Adam Optimizer

In our paper, we present a slightly altered version of the Adam optimizer as delineated in Algorithm [1](#alg1), diverging from the canonical form described by (Kingma & Ba, ). 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., ; Faw et al., , ; Wang et al., ). Our proof is readily adaptable to the per-coordinate version by entailing a separate analysis for each dimension (^1^11It 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., ; Guo et al., )) 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](#Thmassumption1) is a more general form of $(L_{0},L_{1})$-smooth condition and is equivalent to the Hessian-bound form (Zhang et al., ) when Hessian exists. Assumption [2](#Thmassumption2) is one of the weakest assumptions on the noise in existing literature, and generalizes bounded variance assumption (Li et al., ), bounded gradient assumption (Défossez et al., ), bounded noise assumption (Li et al., ).

###### Assumption 1 ( ( L 0 , L 1 ) subscript 𝐿 0 subscript 𝐿 1 (L_{0},L_{1}) -smooth condition) .

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

## 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](#Thmassumption1) and [2](#Thmassumption2), 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., ), 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., , ) regarding both final error $\varepsilon$ and the initial function value gap $(f(\bm{w}_{1})-f^{*})$. The second study, (Li et al., ), 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](#Thmassumption1) 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](#alg1) satisfies

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

###### Proof.

Please see Appendix [B.1](#A2.SS1) for the formal statement of theorem and the proof.
∎

Our result offers a tighter bound than those presented in prior studies (Wang et al., ; Li et al., ). 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., ; Carmon et al., ; Faw et al., ))—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., ) 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., ). 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., ), is $\frac{(f(\bm{w}_{1})-f^{*})^{2}}{\varepsilon^{2}}$. This rate is outperformed by that of Adam(^2^22The 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](#Thmtheorem3).). In Appendix [B.3](#A2.SS3), we show that the rate in (Wang et al., ) 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., ; Crawshaw et al., ), 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., ; Arjevani et al., ) 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](#A2.SS2) 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](#Thmproposition1). Moreover, as shown in Zhang et al. (), 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](#Thmproposition1) 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](#Thmproposition1) 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](#Thmtheorem1) and Theorem [2](#Thmtheorem2), 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.

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

###### Proof.

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

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

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

###### Proof.

### 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](#S4.SS1), i.e., (Wang et al., ; Li et al., ).
However, these results pertaining to Adam are contingent upon rather stringent assumptions. Wang et al. () 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. () 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](#S4.SS1). 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. () 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., )(^3^33While Zhang et al. () also assumes an a.s. bounded gap between stochastic gradients and true gradients.).
Furthermore, Li et al. () 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](#Thmassumption1) and [2](#Thmassumption2) 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](#A3.SS1) for the formal statement of
theorem and the proof.
∎

Below we include several discussions regarding Theorem [3](#Thmtheorem3). To begin with, one can immediately observe that Theorem [3](#Thmtheorem3) only requires Assumptions [1](#Thmassumption1) and [2](#Thmassumption2), 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., ) 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](#Thmassumption1) and [2](#Thmassumption2), 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., ), 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., ), 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. () 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](#Thmtheorem3) addresses certain deficiencies identified in prior studies (Wang et al., ; Li et al., ), it is not without its limitations. As noted by Arjevani et al. (), 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](#Thmassumption2)) 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](#Thmassumption1) and [2](#Thmassumption2). The upper bound of Adam’s convergence rate as presented in Theorem [3](#Thmtheorem3) 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., ; Crawshaw et al., ) 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](#Thmassumption2), 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](#A3.SS2) for the formal statement of theorem and the proof.
∎

Theorem [4](#Thmtheorem4) provides concrete evidence for the challenges inherent in the convergence of SGDM. It shows that there are instances that comply with Assumption [1](#Thmassumption1) and Assumption [2](#Thmassumption2) 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](#Thmassumption1) and [2](#Thmassumption2), while SGD cannot, the superiority of Adam over SGDM becomes evident. It is important to note, however, a recent study by (Li et al., ), 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](#Thmtheorem4), 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., ; Drori & Shamir, ; Arjevani et al., ). 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. () 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.

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

###### Proof.

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

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

###### Proof.

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

As we mentioned in Remark [2](#Thmremark2), although Theorem [3](#Thmtheorem3) matches the lower bound established by Arjevani et al. () 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](#A3.E8)). 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, ), 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](#Thmassumption1) and [2](#Thmassumption2) 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](#A4.SS1) for the formal statement of theorem and the proof.
∎

One can easily see that the convergence rate of Theorem [5](#Thmtheorem5) matches the lower bound in Arjevani et al. () 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](#Thmassumption1) and [2](#Thmassumption2) 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](#alg1) 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., ) that Normed-SGDM is parameter-agnostic. Here we show that Adam with a specific scheduler can achieve the same goal.

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

###### Proof.

###### Theorem 6 .

## 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.

## 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](#Thmassumption1) 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](#Thmlemma4), 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](#Thmassumption1), 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](#A1.E1)) 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](#Thmlemma5).

The proof is completed.
∎

###### Lemma 1 .

###### Proof.

###### Lemma 2 .

###### Proof.

###### Lemma 3 .

###### Lemma 4 .

###### Proof.

###### Lemma 5 .

###### Proof.

## Appendix B Proofs for deterministic algorithms

### B.1 Proof for deterministic Adam

We will first provide the formal statement of Theorem [1](#Thmtheorem1), and then show the corresponding proof.

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

Let Assumption [1](#Thmassumption1) 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](#Thmlemma1) 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](#Thmlemma1) 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](#A2.E2)), 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$.
∎

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

###### Proof.

### B.2 Proof for GDM

This section collects the proof of Theorem [2](#Thmtheorem2). 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.
∎

###### Lemma 6 (Convergence over f 1 subscript 𝑓 1 f_{1} ) .

###### Proof.

###### Lemma 7 (Convergence over f 2 subscript 𝑓 2 f_{2} ) .

###### Proof.

###### Lemma 8 (Convergence over f 3 subscript 𝑓 3 f_{3} ) .

###### Proof.

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

###### Proof.

### B.3 Proof for Deterministic AdaGrad

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

###### 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](#Thmassumption1) 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](#Thmtheorem2), 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](#Thmtheorem8).
∎

###### Proposition 2 .

###### Lemma 9 (Convergence over g 2 subscript 𝑔 2 g_{2} ) .

###### Proof.

###### Theorem 9 .

###### Proof.

## 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](#Thmassumption1) and [2](#Thmassumption2) 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](#alg1) 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](#Thmlemma2), we see the conditions of Lemma [2](#Thmlemma2) 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](#A3.E7)). 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](#A3.E8)) 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](#Thmlemma1), inequality $(\circ)$ is due to Holder’s inequality, and inequality $(\bullet)$ is due to Assumption [2](#Thmassumption2). 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](#A3.E9)), 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](#Thmassumption1), 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](#A3.E10)) 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](#A3.E8)), 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](#A3.E11)) and ([12](#A3.E12)), 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](#A3.E14)), 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](#A3.E13))) and the second-order term (Eq. ([15](#A3.E15))) 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](#Thmlemma3) 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](#A3.E17)), 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](#A3.E17)) 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=$ $\displaystyle\mathbb{E}^{|\mathcal{F}_{t}}\frac{\frac{\beta_{2}}{3\sigma_{1}^{2}}\|\bm{g}_{t}\|^{2}+\frac{1-\beta_{2}}{3\sigma_{1}^{2}}\sigma_{0}^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t}}}\mathds{1}_{\|G_{t}\|\geq\frac{\sigma_{0}}{\sigma_{1}}}\geq\frac{1}{2}\mathbb{E}^{|\mathcal{F}_{t}}\frac{\frac{\beta_{2}}{3\sigma_{1}^{2}}\|\bm{g}_{t}\|^{2}+\frac{1-\beta_{2}}{3\sigma_{1}^{2}}\sigma_{0}^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t+1}}+\sqrt{\beta_{2}\widetilde{\bm{\nu}}_{t}}}\mathds{1}_{\|G_{t}\|\geq\frac{\sigma_{0}}{\sigma_{1}}}.$ $$

As a conclusion,

$$ $\displaystyle\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]\geq\frac{1}{2}\sum_{t=1}^{T}\mathbb{E}\left[\frac{\frac{\beta_{2}}{3\sigma_{1}^{2}}\|\bm{g}_{t}\|^{2}+\frac{1-\beta_{2}}{3\sigma_{1}^{2}}\sigma_{0}^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t+1}}+\sqrt{\beta_{2}\widetilde{\bm{\nu}}_{t}}}\mathds{1}_{\|G_{t}\|\geq\frac{\sigma_{0}}{\sigma_{1}}}\right]$ $\displaystyle\geq$ $\displaystyle\frac{1}{6(1-\beta_{2})\sigma_{1}^{2}}\sum_{t=1}^{T}\mathbb{E}\left[\left(\sqrt{\widetilde{\bm{\nu}}_{t+1}}-\sqrt{\beta_{2}\widetilde{\bm{\nu}}_{t}}\right)\mathds{1}_{\|G_{t}\|\geq\frac{\sigma_{0}}{\sigma_{1}}}\right].$ $$

Meanwhile, for convenience, we define $\{\bar{\bm{\nu}}_{t}\}_{t=0}^{\infty}$ as $\bar{\bm{\nu}}_{0}=\bm{\nu}_{0}$, $\bar{\bm{\nu}}_{t}=\beta_{2}\bar{\bm{\nu}}_{t-1}+(1-\beta_{2})|g_{t}|^{2}\mathds{1}_{\|\bm{G}_{t}\|<\frac{\sigma_{0}^{2}}{\sigma_{1}^{2}}}$. One can easily observe that $\bar{\bm{\nu}}_{t}\leq\bm{\nu}_{t}$, and thus

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

All in all, summing the above two inequalities together, we obtain that

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

Since $\forall t\geq 1$,

$$ $\displaystyle\mathbb{E}\sqrt{\beta_{2}\bar{\bm{\nu}}_{t}+(1-\beta_{2})\sigma_{0}^{2}}\leq\sqrt{\beta_{2}\mathbb{E}\bar{\bm{\nu}}_{t}+(1-\beta_{2})\sigma_{0}^{2}}\leq\sqrt{\sigma_{0}^{2}+\bm{\nu}_{0}}\leq\sqrt{2}\sigma_{0},$ $$

combining with $\sqrt{\beta_{2}{\widetilde{\bm{\nu}}}_{1}}=\sqrt{\beta_{2}(\beta_{2}\bar{\bm{\nu}}_{0}+(1-\beta_{2})\sigma_{0}^{2})}$ and $\mathbb{E}\sqrt{\widetilde{\bm{\nu}}_{t+1}}=\mathbb{E}\sqrt{\beta_{2}{\bm{\nu}}_{t}+(1-\beta_{2})\sigma_{0}^{2}}\geq\mathbb{E}\sqrt{\beta_{2}\bar{\bm{\nu}}_{t}+(1-\beta_{2})\sigma_{0}^{2}}$, we obtain

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

Dividing both sides of the above equation by $1-\sqrt{\beta_{2}}$ then gives

$$ $\displaystyle\sum_{t=1}^{T}\mathbb{E}\sqrt{\widetilde{\bm{\nu}}_{t}}\leq$ $\displaystyle\frac{3(1-\beta_{2})\sigma_{1}^{2}}{\sqrt{\beta_{2}}}\sum_{t=2}^{T}\mathbb{E}\left[\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t}}}\right]+(1-\sqrt{\beta_{2}})\sum_{t=1}^{T}\mathbb{E}\sqrt{\beta_{2}\bar{\bm{\nu}}_{t}+(1-\beta_{2})\sigma_{0}^{2}}$ $\displaystyle\leq$ $\displaystyle 12\sigma_{1}^{2}\sum_{t=1}^{T}\mathbb{E}\left[\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t}}}\right]+\sqrt{2}T\sigma_{0}.$ (23) $$

By applying Eq. ([21](#A3.E21)) and the constraint of $T$, we obtain that

$$ $\displaystyle\sum_{t=1}^{T}\mathbb{E}\sqrt{\widetilde{\bm{\nu}}_{t}}\leq$ $\displaystyle\sqrt{2}T\sigma_{0}+12\frac{\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(2\ln 6\sigma_{0}-T\ln\beta_{2}\right)\right)$ $\displaystyle\leq$ $\displaystyle 4T\sigma_{0}.$ $$

Combining the above inequality and Eq. ([21](#A3.E21)) and applying Cauchy’s inequality, we obtain that

$$ $\displaystyle\left(\mathbb{E}\sum_{t=1}^{T}\|\nabla f(\bm{w}_{t})\|\right)^{2}\leq$ $\displaystyle\left(\sum_{t=1}^{T}\mathbb{E}\sqrt{\widetilde{\bm{\nu}}_{t}}\right)\left(\sum_{t=1}^{T}\mathbb{E}\left[\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\widetilde{\bm{\nu}}_{t}}}\right]\right)$ $\displaystyle\leq$ $\displaystyle 4T\sigma_{0}\times\frac{1}{\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(2\ln 6\sigma_{0}-T\ln\beta_{2}\right)\right).$ $$

By $\eta=\frac{\sqrt{f(\bm{w}_{1})-f^{*}}}{\sqrt{L_{0}+L_{1}}\sqrt{T\sigma_{0}\sigma_{1}^{2}}}$ and the constraint of $T$, the proof is completed.
∎

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

###### Proof.

### C.2 Proof for SGDM

###### Theorem 11 (Informal) .

Fix $L_{0}\geq 0,L_{1}>0$, and $\Delta_{1}\geq 0$, there exists objective function $f$ satisfying $(L_{0},L_{1})$-smooth condition and $f(\bm{w}_{1})-f^{*}=\Delta_{1}$, and a noise oracle $\mathcal{O}(\bm{w},z)$ generating stochastic gradient by $\bm{g}_{t}=\nabla f(\bm{w}_{t})+\mathcal{O}(\bm{w}_{t},z_{t})$ and satisfying Assumption [2](#Thmassumption2) ($z_{t}$ is i.i.d. sampled from some underlying distribution), 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.

Define the objective function $f$ as $f_{1}$ used in the the proof of Theorem [2](#Thmtheorem2) as

$$ $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.$ (24) $$

It is easy to verify that $f_{1}$ obeys Assumption [1](#Thmassumption1). Then, we set $w_{1}$ as the solution of $f_{1}(x)-\frac{L_{0}}{2L_{1}^{2}}=\Delta_{1}$, thus $f(\bm{w}_{1})-f^{*}=\Delta_{1}$ is satisfied. We then construct the noise oracle as $O_{f}(\bm{w},z)=z$, where $z\sim e^{-\frac{\sqrt{|z|}}{\sqrt[6]{\sigma_{0}^{2}/960}}}$. One can easily verify that $\operatorname{Var}(z)=\sigma_{0}^{2}$ and Assumption [2](#Thmassumption2) is meet.

Now, we prove the following claim: starting any point $w_{t}$ and with any previous momentum $\bm{m}_{t-1}$, one step of SGDM

$$ $\mathbb{E}[\|\nabla f(\bm{w}_{t+1})\||\bm{w}_{t}]=\infty.$ $$

Specifically, we have one step of SGDM gives

$$ $\displaystyle\bm{w}_{t+1}=\bm{w}_{t}-\eta(1-\beta)\nabla f(\bm{w}_{t})-\eta\beta\bm{m}_{t-1}-\eta(1-\beta)z_{t}.$ $$

Therefore, we have

$$ $\displaystyle\mathbb{E}[|\nabla f(w_{t+1})||\bm{w}_{t}]\geq$ $\displaystyle\mathbb{E}\left[|\nabla f(w_{t+1})|\mathds{1}_{w_{t+1}\geq\max\{\frac{1}{L_{1}},\bm{w}_{t}-\eta(1-\beta)\nabla f(\bm{w}_{t})-\eta\beta\bm{m}_{t-1}\}}\right]$ $\displaystyle\geq$ $\displaystyle\mathbb{E}\left[|\nabla f(w_{t+1})|\mathds{1}_{z_{t}\leq\min\{\frac{\bm{w}_{t}-\frac{1}{L_{1}}}{\eta(1-\beta)}-\nabla f(\bm{w}_{t})-\frac{\beta}{1-\beta}\bm{m}_{t-1},0\}}\right]$ $\displaystyle\geq$ $\displaystyle\frac{1}{2}\int^{\min\{\frac{\bm{w}_{t}-\frac{1}{L_{1}}}{\eta(1-\beta)}-\nabla f(\bm{w}_{t})-\frac{\beta}{1-\beta}\bm{m}_{t-1},0\}}_{-\infty}\frac{L_{0}}{L_{1}}e^{L_{1}(\bm{w}_{t}-\eta(1-\beta)\nabla f(\bm{w}_{t})-\eta\beta\bm{m}_{t-1}-\eta(1-\beta)z)-1}e^{-\frac{\sqrt{-z}}{\sqrt[6]{\sigma_{0}^{2}/960}}}\mathrm{d}z.$ $$

Since $\lim_{z\rightarrow-\infty}e^{L_{1}(\bm{w}_{t}-\eta(1-\beta)\nabla f(\bm{w}_{t})-\eta\beta\bm{m}_{t-1}-\eta(1-\beta)z)-1}e^{-\frac{\sqrt{-z}}{\sqrt[6]{\sigma_{0}^{2}/960}}}=\infty$ regardless of $\eta$, $\beta$, and $\bm{m}_{t-1}$, we have $\mathbb{E}[|\nabla f(w_{t+1})||\bm{w}_{t}]=\infty$ based on the above inequalities. This means that an update from any point over this example will always lead to the divergence on expected gradient norm, thus we have $\forall t>1$,

$$ $\min_{t\in[T]}\mathbb{E}|\nabla f(w_{t})|=|\nabla f(w_{1})|.$ $$

The proof is completed.
∎

###### Theorem 11 (Informal) .

###### Proof.

## Appendix D Proofs for Section 5

### D.1 Proof for Theorem 5

###### Theorem 12 (Theorem 5 , restated) .

Let Assumption [1](#Thmassumption1) hold. Then, $\forall\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 $\eta=(1-\beta_{1})\frac{\sqrt{L_{0}(f(\bm{w}_{1})-f^{*})}}{\sqrt{T}}$ and momentum hyperparameter $\beta_{2}=1-\eta^{2}\frac{(256\sigma_{1}^{2}L_{1})^{2}}{1-\beta_{1}}$, 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.

Recall that $\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}$. Due to $\frac{\eta}{\sqrt{1-\beta_{2}}}\leq\frac{\sqrt{1-\beta_{1}}}{8L_{1}}$ and following the similar routine as Theorem [3](#Thmtheorem3), one can easily verify that

$$ $\|\bm{u}_{t}-\bm{w}_{t}\|\leq\frac{1}{4L_{1}},\|\bm{u}_{t+1}-\bm{w}_{t}\|\leq\frac{1}{4L_{1}}.$ $$

Therefore, if Lemma [2](#Thmlemma2) can be applied with $\bm{w}^{1}=\bm{w}_{t}$, $\bm{w}^{2}=\bm{u}_{t+1}$, and $\bm{w}^{3}=\bm{u}_{t}$, we see the conditions of Lemma [2](#Thmlemma2) 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. Similar to bounding the first-order term in the proof of Theorem [3](#Thmtheorem3), we have the following decomposition :

$$ $\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-\eta\frac{1-\beta_{1}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}\bm{g}_{t}-\frac{\eta}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\left(\frac{1}{\sqrt{\bm{\nu}_{t}}}-\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}\right)\bm{m}_{t}.$ $$

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{\beta_{2}{\bm{\nu}}_{t-1}}}\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}{\bm{\nu}_{t}}-\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}\right)\bm{m}_{t}\right\rangle\right].$ $$

As $\mathbb{E}^{|{\mathcal{F}}_{t}}\left[\left\langle\bm{G}_{t},-\eta\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}\bm{g}_{t}\right\rangle\right]=-\eta\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}$, 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{\beta_{2}\bm{\nu}_{t-1}}}\bm{g}_{t}\right\rangle\right]\leq-\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}.$ $$

We then bound $\mathbb{E}^{|{\mathcal{F}}_{t}}\left[\left\langle\bm{G}_{t},-\frac{\eta}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\left(\frac{1}{\bm{\nu}_{t}}-\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}\right)\bm{m}_{t}\right\rangle\right]$ as follows

$$ $\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{\beta_{2}\bm{\nu}_{t-1}}}\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})\|\bm{g}_{t}\|^{2}}{\sqrt{\bm{\nu}_{t}}\sqrt{\beta_{2}\bm{\nu}_{t-1}}(\sqrt{\bm{\nu}_{t}}+\sqrt{\beta_{2}\bm{\nu}_{t-1}})}\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})\|\bm{g}_{t}\|^{2}}{\sqrt{\bm{\nu}_{t}}\sqrt{\beta_{2}\bm{\nu}_{t-1}}(\sqrt{\bm{\nu}_{t}}+\sqrt{\beta_{2}\bm{\nu}_{t-1}})}\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{\beta_{2}\bm{\nu}_{t-1}}(\sqrt{\bm{\nu}_{t}}+\sqrt{\beta_{2}\bm{\nu}_{t-1}})}\right)\|\bm{m}_{t}\|\right]}.$ $$

Due to Lemma [1](#Thmlemma1), the right-hand-side of the above inequality can be further 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{\beta_{2}\bm{\nu}_{t-1}}(\sqrt{\bm{\nu}_{t}}+\sqrt{\beta_{2}\bm{\nu}_{t-1}})}\right)\|\bm{m}_{t}\|\right]\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{\beta_{2}\bm{\nu}_{t-1}}(\sqrt{\bm{\nu}_{t}}+\sqrt{\beta_{2}\bm{\nu}_{t-1}})}\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{\beta_{2}\bm{\nu}_{t-1}}}\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{\beta_{2}\bm{\nu}_{t-1}})^{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{\beta_{2}\bm{\nu}_{t-1}}}\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{\beta_{2}\bm{\nu}_{t-1}})^{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{\beta_{2}\bm{\nu}_{t-1}}}(\sigma_{0}+\sigma_{1}\|\bm{G}_{t}\|)\sqrt{\mathbb{E}^{|\mathcal{F}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{(\sqrt{\bm{\nu}_{t}}+\sqrt{\beta_{2}\bm{\nu}_{t-1}})^{2}}},$ $$

where inequality $(\circ)$ is due to Holder’s inequality, and inequality $(\bullet)$ is due to Assumption [2](#Thmassumption2). 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{\beta_{2}\bm{\nu}_{t-1}}}\sigma_{0}\sqrt{\mathbb{E}^{|\mathcal{F}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{(\sqrt{\bm{\nu}_{t}}+\sqrt{\beta_{2}\bm{\nu}_{t-1}})^{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{\beta_{2}\bm{\nu}_{t-1}}}\sigma_{1}\|\bm{G}_{t}\|\sqrt{\mathbb{E}^{|\mathcal{F}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{(\sqrt{\bm{\nu}_{t}}+\sqrt{\beta_{2}\bm{\nu}_{t-1}})^{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}}}}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}+\frac{4\eta(1-\beta_{2})\sigma_{0}^{2}}{\left(1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}\right)^{2}\sqrt{\beta_{2}\bm{\nu}_{t-1}}}\mathbb{E}^{|\mathcal{F}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{(\sqrt{\bm{\nu}_{t}}+\sqrt{\beta_{2}\bm{\nu}_{t-1}})^{2}}$ $\displaystyle+\frac{1}{16}\eta\frac{1-\beta_{1}}{1-\frac{\beta_{1}}{\sqrt{\beta_{2}}}}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}+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{\beta_{2}\bm{\nu}_{t-1}}}\mathbb{E}^{|\mathcal{F}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{(\sqrt{\bm{\nu}_{t}}+\sqrt{\beta_{2}\bm{\nu}_{t-1}})^{2}}$ $\displaystyle\leq$ $\displaystyle\frac{1}{8}\eta\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}+\frac{8\eta(1-\beta_{2})\sigma_{0}^{2}}{\left(1-{\beta_{1}}\right)^{2}}\mathbb{E}^{|\mathcal{F}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}(\sqrt{\bm{\nu}_{t}}+\sqrt{\beta_{2}\bm{\nu}_{t-1}})^{2}}$ $\displaystyle+\frac{1}{8}\eta\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}+16\eta\frac{(1-\beta_{2})}{(1-\beta_{1})}\sigma_{1}^{2}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}\mathbb{E}^{|\mathcal{F}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{(\sqrt{\bm{\nu}_{t}}+\sqrt{\beta_{2}\bm{\nu}_{t-1}})^{2}}.$ $$

Meanwhile, we have

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

and

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

Combing the above two inequalities, we further obtain

$$ $\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{\beta_{2}\bm{\nu}_{t-1}}(\sqrt{\bm{\nu}_{t}}+\sqrt{\beta_{2}\bm{\nu}_{t-1}})}\right)\|\bm{m}_{t}\|\right]$ $\displaystyle\leq$ $\displaystyle\frac{1}{4}\eta\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}+\frac{8\eta\sigma_{0}^{2}}{\left(1-\beta_{1}\right)^{2}}\mathbb{E}^{|\mathcal{F}_{t}}\left(\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}-\frac{1}{\sqrt{\bm{\nu}_{t}}}\right)+\eta\frac{16}{(1-\beta_{1})}\sigma_{1}^{2}\mathbb{E}^{|\mathcal{F}_{t}}\left(\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}-\frac{1}{\sqrt{\bm{\nu}_{t}}}\right)\|\bm{G}_{t}\|^{2}.$ $$

Furthermore, due to Assumption [1](#Thmassumption1), 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 further leads to

$$ $\displaystyle\frac{1}{\sqrt{\bm{\nu}_{t}}}\|\bm{G}_{t}\|^{2}$ $\displaystyle\geq$ $\displaystyle\frac{1}{\sqrt{\bm{\nu}_{t}}}\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\frac{1}{\sqrt{\bm{\nu}_{t}}}\|\bm{G}_{t+1}\|^{2}-\frac{1-\beta_{1}}{128\sigma_{1}^{2}}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\bm{\nu}_{t}}}-\frac{128L_{0}^{2}\sigma_{1}^{2}}{(1-\beta_{1})\sqrt{\bm{\nu}_{t}}}\|\bm{w}_{t+1}-\bm{w}_{t}\|^{2}-2L_{1}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\bm{\nu}_{t}}}\|\bm{w}_{t+1}-\bm{w}_{t}\|-2\frac{L_{0}^{2}}{\sqrt{\bm{\nu}_{t}}}\|\bm{w}_{t+1}-\bm{w}_{t}\|^{2}$ $\displaystyle-\frac{2L_{1}^{2}\|\bm{G}_{t}\|^{2}\|\bm{w}_{t+1}-\bm{w}_{t}\|^{2}}{\sqrt{\bm{\nu}_{t}}}$ $\displaystyle\geq$ $\displaystyle\frac{1}{\sqrt{\bm{\nu}_{t}}}\|\bm{G}_{t+1}\|^{2}-\frac{1-\beta_{1}}{128\sigma_{1}^{2}}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\bm{\nu}_{t}}}-\frac{128L_{0}^{2}\sigma_{1}^{2}}{(1-\beta_{1})\sqrt{\bm{\nu}_{t}}}\|\bm{w}_{t+1}-\bm{w}_{t}\|^{2}-\frac{1-\beta_{1}}{128\sigma_{1}^{2}}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\bm{\nu}_{t}}}-2\frac{L_{0}^{2}}{\sqrt{\bm{\nu}_{t}}}\|\bm{w}_{t+1}-\bm{w}_{t}\|^{2}$ $\displaystyle-\frac{1-\beta_{1}}{128\sigma_{1}^{2}}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\bm{\nu}_{t}}},$ (25) $$

where the second inequality is due to Young’s inequality, and the last inequality is due to $\|\bm{w}_{t+1}-\bm{w}_{t}\|\leq\frac{\eta(1-\beta_{1})}{\sqrt{1-\beta_{2}}\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}}}}\leq\frac{\eta\sqrt{1-\beta_{1}}}{\sqrt{1-\beta_{2}}}\leq\frac{1-\beta_{1}}{256\sigma_{1}^{2}L_{1}}$.

Applying the above inequality back to the estimation of $\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{\beta_{2}\bm{\nu}_{t-1}}(\sqrt{\bm{\nu}_{t}}+\sqrt{\beta_{2}\bm{\nu}_{t-1}})}\right)\|\bm{m}_{t}\|\right]$ leads to 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{\beta_{2}\bm{\nu}_{t-1}}(\sqrt{\bm{\nu}_{t}}+\sqrt{\beta_{2}\bm{\nu}_{t-1}})}\right)\|\bm{m}_{t}\|\right]$ $\displaystyle\leq$ $\displaystyle\frac{5}{8}\eta\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}+\frac{8\eta\sigma_{0}^{2}}{\left(1-\beta_{1}\right)^{2}}\mathbb{E}^{|\mathcal{F}_{t}}\left(\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}-\frac{1}{\sqrt{\bm{\nu}_{t}}}\right)+\eta\frac{16}{(1-\beta_{1})}\sigma_{1}^{2}\mathbb{E}^{|\mathcal{F}_{t}}\left(\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}-\frac{\|\bm{G}_{t+1}\|^{2}}{\sqrt{\bm{\nu}_{t}}}\right)$ $\displaystyle+$ $\displaystyle\frac{32768L_{0}^{2}\sigma_{1}^{4}\eta^{3}}{(1-\beta_{1})(1-\beta_{2})}\mathbb{E}^{|{\mathcal{F}}_{t}}\left(\sum_{s=1}^{t}\frac{\beta_{1}^{t-s}}{\sqrt[4]{\beta_{2}^{3(t-s)}}}\left(\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{s-1}}}-\frac{1}{\sqrt{\bm{\nu}_{s}}}\right)\right).$ $$

All in all, 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{3}{8}\eta\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}+\frac{8\eta\sigma_{0}^{2}}{\left(1-\beta_{1}\right)^{2}}\mathbb{E}^{|\mathcal{F}_{t}}\left(\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}-\frac{1}{\sqrt{\bm{\nu}_{t}}}\right)+\eta\frac{16}{(1-\beta_{1})}\sigma_{1}^{2}\mathbb{E}^{|\mathcal{F}_{t}}\left(\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}-\frac{\|\bm{G}_{t+1}\|^{2}}{\sqrt{\bm{\nu}_{t}}}\right)$ $\displaystyle+$ $\displaystyle\frac{32768L_{0}^{2}\sigma_{1}^{4}\eta^{3}}{(1-\beta_{1})(1-\beta_{2})}\mathbb{E}^{|{\mathcal{F}}_{t}}\left(\sum_{s=1}^{t}\frac{\beta_{1}^{t-s}}{\sqrt[4]{\beta_{2}^{3(t-s)}}}\left(\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{s-1}}}-\frac{1}{\sqrt{\bm{\nu}_{s}}}\right)\right).$ $$

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}}}}$ $$

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\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)$ $\displaystyle\leq$ $\displaystyle\frac{L_{0}\eta^{2}}{2}\left(\frac{32}{(1-\beta_{1})^{2}}\left\|\frac{\bm{g}_{t}}{\sqrt{\bm{\nu}_{t}}}\right\|^{2}+\frac{4}{(1-\beta_{1})^{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}}}$ $\displaystyle\leq$ $\displaystyle\frac{2L_{1}\eta}{\sqrt{1-\beta_{1}}}\|\bm{G}_{t}\|\left(\|\bm{u}_{t+1}-\bm{u}_{t}\|+4\frac{1}{1-\beta_{1}}\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}}}$, 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})$, and the last inequality is due to $\beta_{1}\leq\beta_{2}$. As for the term $\|\bm{G}_{t}\|\frac{\|\bm{m}_{t}\|}{\sqrt{\bm{\nu}_{t}}}\frac{\|\bm{g}_{t}\|}{\sqrt{\bm{\nu}_{t}}}$, we have

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

By applying Lemma [5](#Thmlemma5), we further obtain

$$ $\displaystyle\mathbb{E}^{|{\mathcal{F}}_{t}}\frac{\|\bm{G}_{t}\|\|\bm{m}_{t}\|\|\bm{g}_{t}\|}{\bm{\nu}_{t}}$ $\displaystyle\leq$ $\displaystyle\frac{\sqrt{(1-\beta_{1})^{3}}}{256\eta L_{1}}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}+\frac{64\eta\sigma_{0}^{2}L_{1}}{\sqrt{(1-\beta_{1})^{3}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}}\mathbb{E}^{|{\mathcal{F}}_{t}}\frac{\|\bm{m}_{t}\|^{2}}{\bm{\nu}_{t}}+\frac{\sqrt{(1-\beta_{1})^{3}}}{256\eta L_{1}}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}$ $\displaystyle+\frac{64\eta\sigma_{1}^{2}L_{1}}{\sqrt{(1-\beta_{1})^{3}}}\mathbb{E}^{|{\mathcal{F}}_{t}}\left(4(1-\beta_{1})\left(\sum_{s=1}^{t}\frac{\sqrt[8]{\beta_{1}^{t-s}}\|\bm{g}_{s}\|^{2}\|\bm{G}_{s}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{s-1}}\sqrt{\bm{\nu}_{s}^{2}}}\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)\right),$ $$

which further indicates that

$$ $\displaystyle\frac{8L_{1}\eta^{2}}{(1-\beta_{1})^{\frac{3}{2}}}\mathbb{E}^{|{\mathcal{F}}_{t}}\|\bm{G}_{t}\|\frac{\|\bm{g}_{t}\|}{\sqrt{\bm{\nu}_{t}}}\frac{\|\bm{m}_{t}\|}{\sqrt{\bm{\nu}_{t}}}$ $\displaystyle\leq$ $\displaystyle\frac{1}{16}\eta\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}+\frac{8L_{1}\eta^{2}}{(1-\beta_{1})^{\frac{3}{2}}}\frac{64\eta\sigma_{0}^{2}L_{1}}{\sqrt{(1-\beta_{1})^{3}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}}\mathbb{E}^{|{\mathcal{F}}_{t}}\frac{\|\bm{m}_{t}\|^{2}}{\bm{\nu}_{t}}$ $\displaystyle+\frac{64\eta\sigma_{1}^{2}L_{1}}{\sqrt{(1-\beta_{1})^{3}}}\mathbb{E}^{|{\mathcal{F}}_{t}}\frac{32L_{1}\eta^{2}}{(1-\beta_{1})^{\frac{1}{2}}}\left(\sum_{s=1}^{t}\frac{\sqrt[8]{\beta_{1}^{t-s}}\|\bm{g}_{s}\|^{2}\|\bm{G}_{s}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{s-1}}\sqrt{\bm{\nu}_{s}^{2}}}\right)$ $\displaystyle+\frac{64L_{1}\eta^{2}}{(1-\beta_{1})^{\frac{3}{2}}}\frac{64\eta\sigma_{1}^{2}L_{1}}{\sqrt{(1-\beta_{1})^{3}}}\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)$ $\displaystyle\leq$ $\displaystyle\frac{1}{16}\eta\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}+\frac{8L_{1}\eta^{2}}{(1-\beta_{1})^{\frac{3}{2}}}\frac{64\eta\sigma_{0}^{2}L_{1}}{\sqrt{(1-\beta_{1})^{3}}}\mathbb{E}^{|{\mathcal{F}}_{t}}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)$ $\displaystyle+\frac{64\eta\sigma_{1}^{2}L_{1}}{\sqrt{(1-\beta_{1})^{3}}}\mathbb{E}^{|{\mathcal{F}}_{t}}\frac{32L_{1}\eta^{2}}{(1-\beta_{1})^{\frac{1}{2}}}\left(\sum_{s=1}^{t}\frac{\sqrt[8]{\beta_{1}^{t-s}}\|\bm{g}_{s}\|^{2}\|\bm{G}_{s}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{s-1}}\sqrt{\bm{\nu}_{s}^{2}}}\right)$ $\displaystyle+\frac{64L_{1}\eta^{2}}{(1-\beta_{1})^{\frac{3}{2}}}\frac{64\eta\sigma_{1}^{2}L_{1}}{\sqrt{(1-\beta_{1})^{3}}}\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 due to Lemma [4](#Thmlemma4).

Following similar reasoning, we have $\|\bm{u}_{t+1}-\bm{u}_{t}\|\leq\frac{4\eta}{\sqrt{1-\beta_{2}}}\frac{\|\bm{g}_{t}\|}{\sqrt{\bm{\nu}_{t}}}$, and

$$ $\displaystyle\mathbb{E}^{|{\mathcal{F}}_{t}}\frac{\|\bm{G}_{t}\|\|\bm{g}_{t}\|\|\bm{g}_{t}\|}{\bm{\nu}_{t}}$ $\displaystyle\leq$ $\displaystyle\frac{\sqrt{(1-\beta_{1})^{3}}}{256\eta L_{1}}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}+\frac{64\eta\sigma_{0}^{2}L_{1}}{\sqrt{(1-\beta_{1})^{3}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}}\mathbb{E}^{|{\mathcal{F}}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{\bm{\nu}_{t}}+\frac{\sqrt{(1-\beta_{1})^{3}}}{256\eta L_{1}}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}$ $\displaystyle+\frac{64\eta\sigma_{1}^{2}L_{1}\|\bm{G}_{t}\|^{2}}{\sqrt{(1-\beta_{1})^{3}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}}\mathbb{E}^{|{\mathcal{F}}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{\bm{\nu}_{t}}$ $\displaystyle\leq$ $\displaystyle\frac{\sqrt{(1-\beta_{1})^{3}}}{256\eta L_{1}}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}+\frac{128\eta\sigma_{1}^{2}L_{1}}{\sqrt{(1-\beta_{1})^{3}}(1-\beta_{2})}\mathbb{E}^{|{\mathcal{F}}_{t}}\left(\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}-\frac{1}{\sqrt{\bm{\nu}_{t}}}\right)+\frac{\sqrt{(1-\beta_{1})^{3}}}{256\eta L_{1}}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}$ $\displaystyle+\frac{128\eta\sigma_{1}^{2}L_{1}\|\bm{G}_{t}\|^{2}}{\sqrt{(1-\beta_{1})^{3}}(1-\beta_{2})}\mathbb{E}^{|{\mathcal{F}}_{t}}\left(\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}-\frac{1}{\sqrt{\bm{\nu}_{t}}}\right).$ $$

Then, following the similar routine as Eq. ([25](#A4.E25)) and due to $\frac{\eta}{\sqrt{1-\beta_{2}}}\leq\frac{1-\beta_{1}}{128L_{1}\sigma_{1}}$, we have

$$ $\displaystyle\frac{2L_{1}\eta}{(1-\beta_{1})^{\frac{1}{2}}}\mathbb{E}^{|{\mathcal{F}}_{t}}\|\bm{G}_{t}\|\|\bm{u}_{t+1}-\bm{u}_{t}\|\frac{\|\bm{g}_{t}\|}{\sqrt{\bm{\nu}_{t}}}\leq\frac{8L_{1}\eta^{2}}{(1-\beta_{1})}\mathbb{E}^{|{\mathcal{F}}_{t}}\|\bm{G}_{t}\|\frac{\|\bm{g}_{t}\|^{2}}{\bm{\nu}_{t}}$ $\displaystyle\leq$ $\displaystyle\frac{1}{16}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}+\frac{8L_{1}\eta^{2}}{(1-\beta_{1})^{\frac{3}{2}}}\frac{128\eta\sigma_{1}^{2}L_{1}}{\sqrt{(1-\beta_{1})^{3}}(1-\beta_{2})}\mathbb{E}^{|{\mathcal{F}}_{t}}\left(\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}-\frac{1}{\sqrt{\bm{\nu}_{t}}}\right)$ $\displaystyle+\frac{8L_{1}\eta^{2}}{(1-\beta_{1})^{\frac{3}{2}}}\frac{128\eta\sigma_{1}^{2}L_{1}}{\sqrt{(1-\beta_{1})^{3}}(1-\beta_{2})}\mathbb{E}^{|{\mathcal{F}}_{t}}\left(\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}-\frac{\|\bm{G}_{t+1}\|^{2}}{\sqrt{\bm{\nu}_{t}}}\right)$ $\displaystyle+\frac{1}{16}\eta\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}+\eta^{3}\frac{64L_{0}^{2}}{(1-\beta_{1})^{2}}\mathbb{E}^{|{\mathcal{F}}_{t}}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).$ $$

Putting all the estimations together, we have that the second-order term can be bounded by (note here due to the complexity of coefficients, we use $\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}})$ to denote the polynomial function of $L_{0},L_{1},\sigma_{0},\sigma_{1}$, $\frac{1}{1-\beta_{1}}$)

$$ $\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_{0}\eta^{2}}{2}\left(\frac{32}{(1-\beta_{1})^{2}}\left\|\frac{\bm{g}_{t}}{\sqrt{\bm{\nu}_{t}}}\right\|^{2}+\frac{4}{(1-\beta_{1})^{2}}\left\|\frac{\bm{m}_{t-1}}{\sqrt{\bm{\nu}_{t-1}}}\right\|^{2}\right)+\frac{3}{16}\eta\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}$ $\displaystyle+\frac{\eta^{3}}{1-\beta_{2}}\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\mathbb{E}^{|{\mathcal{F}}_{t}}\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)$ $\displaystyle+\frac{\eta^{3}}{1-\beta_{2}}\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\mathbb{E}^{|{\mathcal{F}}_{t}}\left(\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}-\frac{\|\bm{G}_{t+1}\|^{2}}{\sqrt{\bm{\nu}_{t}}}\right)$ $\displaystyle+\frac{64\eta\sigma_{1}^{2}L_{1}}{\sqrt{(1-\beta_{1})^{3}}}\mathbb{E}^{|{\mathcal{F}}_{t}}\frac{32L_{1}\eta^{2}}{(1-\beta_{1})^{\frac{1}{2}}}\left(\sum_{s=1}^{t}\frac{\sqrt[8]{\beta_{1}^{t-s}}\|\bm{g}_{s}\|^{2}\|\bm{G}_{s}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{s-1}}\sqrt{\bm{\nu}_{s}^{2}}}\right)$ $$

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 and the second-order term 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{3}{16}\eta\mathbb{E}^{|{\mathcal{F}}_{t}}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}+\frac{L_{0}\eta^{2}}{2}\left(\frac{32}{(1-\beta_{1})^{2}}\left\|\frac{\bm{g}_{t}}{\sqrt{\bm{\nu}_{t}}}\right\|^{2}+\frac{4}{(1-\beta_{1})^{2}}\left\|\frac{\bm{m}_{t-1}}{\sqrt{\bm{\nu}_{t-1}}}\right\|^{2}\right)$ $\displaystyle+\frac{\eta^{3}}{1-\beta_{2}}\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\mathbb{E}^{|{\mathcal{F}}_{t}}\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)$ $\displaystyle+\left(\frac{\eta^{3}}{1-\beta_{2}}+\eta\right)\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\mathbb{E}^{|{\mathcal{F}}_{t}}\left(\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}-\frac{\|\bm{G}_{t+1}\|^{2}}{\sqrt{\bm{\nu}_{t}}}\right)$ $\displaystyle+\eta\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\mathbb{E}^{|\mathcal{F}_{t}}\left(\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}-\frac{\|\bm{G}_{t+1}\|^{2}}{\sqrt{\bm{\nu}_{t}}}\right)$ $\displaystyle+\frac{64\eta\sigma_{1}^{2}L_{1}}{\sqrt{(1-\beta_{1})^{3}}}\mathbb{E}^{|{\mathcal{F}}_{t}}\frac{32L_{1}\eta^{2}}{(1-\beta_{1})^{\frac{1}{2}}}\left(\sum_{s=1}^{t}\frac{\sqrt[8]{\beta_{1}^{t-s}}\|\bm{g}_{s}\|^{2}\|\bm{G}_{s}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{s-1}}\sqrt{\bm{\nu}_{s}^{2}}}\right).$ (26) $$

Constructing stopping time as $\tau\triangleq\min\{t:\|\nabla f(\bm{w}_{t+1})\|\leq\frac{\sqrt[4]{L_{0}\sigma_{0}^{2}(f(\bm{w}_{1})-f^{*})}}{\sqrt[4]{T}}\}\wedge T$. Then, denote

$$ $\displaystyle x_{t}\triangleq$ $\displaystyle f(\bm{u}_{t})-f(\bm{u}_{t+1})-\frac{3}{16}\eta\mathbb{E}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}+\frac{L_{0}\eta^{2}}{2}\left(\frac{32}{(1-\beta_{1})^{2}}\left\|\frac{\bm{g}_{t}}{\sqrt{\bm{\nu}_{t}}}\right\|^{2}+\frac{4}{(1-\beta_{1})^{2}}\left\|\frac{\bm{m}_{t-1}}{\sqrt{\bm{\nu}_{t-1}}}\right\|^{2}\right)$ $\displaystyle+\frac{\eta^{3}}{1-\beta_{2}}\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\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)$ $\displaystyle+\left(\frac{\eta^{3}}{1-\beta_{2}}+\eta\right)\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\left(\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}-\frac{\|\bm{G}_{t+1}\|^{2}}{\sqrt{\bm{\nu}_{t}}}\right)$ $\displaystyle+\frac{64\eta\sigma_{1}^{2}L_{1}}{\sqrt{(1-\beta_{1})^{3}}}\frac{32L_{1}\eta^{2}}{(1-\beta_{1})^{\frac{1}{2}}}\left(\sum_{s=1}^{t}\frac{\sqrt[8]{\beta_{1}^{t-s}}\|\bm{g}_{s}\|^{2}\|\bm{G}_{s}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{s-1}}\sqrt{\bm{\nu}_{s}^{2}}}\right),$ $$

and due to Eq. ([26](#A4.E26)), we have $\mathbb{E}^{|{\mathcal{F}}_{t}}x_{t}\geq 0$, and thus $S_{t}\triangleq\sum_{s=1}^{t}x_{s}$ ($S_{0}=0$) is a submartingale with respect to $\{{\mathcal{F}}_{t}\}_{t}$. Also, as $\tau$ is a bounding stopping theorem, by optional stopping time, we obtain that $\mathbb{E}S_{\tau}\geq 0$, which gives

$$ $\displaystyle\frac{3}{16}\eta\mathbb{E}\sum_{t=1}^{\tau}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}\leq$ $\displaystyle f(\bm{u}_{1})-\mathbb{E}f(\bm{u}_{\tau+1})+\frac{L_{0}\eta^{2}}{2}\mathbb{E}\sum_{t=1}^{\tau}\left(\frac{32}{(1-\beta_{1})^{2}}\left\|\frac{\bm{g}_{t}}{\sqrt{\bm{\nu}_{t}}}\right\|^{2}+\frac{4}{(1-\beta_{1})^{2}}\left\|\frac{\bm{m}_{t-1}}{\sqrt{\bm{\nu}_{t-1}}}\right\|^{2}\right)$ $\displaystyle+\frac{\eta^{3}}{1-\beta_{2}}\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\mathbb{E}\sum_{t=1}^{\tau}\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)$ $\displaystyle+\mathbb{E}\sum_{t=1}^{\tau}\left(\frac{\eta^{3}}{1-\beta_{2}}+\eta\right)\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\left(\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}-\frac{\|\bm{G}_{t+1}\|^{2}}{\sqrt{\bm{\nu}_{t}}}\right)$ $\displaystyle+\mathbb{E}\sum_{t=1}^{\tau}\frac{64\eta\sigma_{1}^{2}L_{1}}{\sqrt{(1-\beta_{1})^{3}}}\frac{32L_{1}\eta^{2}}{(1-\beta_{1})^{\frac{1}{2}}}\left(\sum_{s=1}^{t}\frac{\sqrt[8]{\beta_{1}^{t-s}}\|\bm{g}_{s}\|^{2}\|\bm{G}_{s}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{s-1}}\sqrt{\bm{\nu}_{s}^{2}}}\right)$ $\displaystyle\leq$ $\displaystyle f(\bm{u}_{1})-\mathbb{E}f(\bm{u}_{\tau+1})+\frac{L_{0}\eta^{2}}{2}\mathbb{E}\sum_{t=1}^{\tau}\left(\frac{32}{(1-\beta_{1})^{2}}\left\|\frac{\bm{g}_{t}}{\sqrt{\bm{\nu}_{t}}}\right\|^{2}+\frac{4}{(1-\beta_{1})^{2}}\left\|\frac{\bm{m}_{t-1}}{\sqrt{\bm{\nu}_{t-1}}}\right\|^{2}\right)$ $\displaystyle+\frac{\eta^{3}}{1-\beta_{2}}\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\mathbb{E}\sum_{t=1}^{\tau}\left(\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}-\frac{1}{\sqrt{\bm{\nu}_{t}}}\right)$ $\displaystyle+\mathbb{E}\sum_{t=1}^{\tau}\left(\frac{\eta^{3}}{1-\beta_{2}}+\eta\right)\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\left(\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}-\frac{\|\bm{G}_{t+1}\|^{2}}{\sqrt{\bm{\nu}_{t}}}\right)$ $\displaystyle+\mathbb{E}\sum_{t=1}^{\tau}\frac{64\eta\sigma_{1}^{2}L_{1}}{\sqrt{(1-\beta_{1})^{3}}}\frac{256L_{1}\eta^{2}}{(1-\beta_{1})^{\frac{3}{2}}}\left(\frac{\|\bm{g}_{t}\|^{2}\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}\sqrt{\bm{\nu}_{t}^{2}}}\right)$ $\displaystyle\leq$ $\displaystyle f(\bm{u}_{1})-\mathbb{E}f(\bm{u}_{\tau+1})+\frac{L_{0}\eta^{2}}{2}\mathbb{E}\sum_{t=1}^{\tau}\left(\frac{32}{(1-\beta_{1})^{2}}\left\|\frac{\bm{g}_{t}}{\sqrt{\bm{\nu}_{t}}}\right\|^{2}+\frac{4}{(1-\beta_{1})^{2}}\left\|\frac{\bm{m}_{t-1}}{\sqrt{\bm{\nu}_{t-1}}}\right\|^{2}\right)$ $\displaystyle+\frac{\eta^{3}}{1-\beta_{2}}\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\mathbb{E}\sum_{t=1}^{\tau}\left(\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}-\frac{1}{\sqrt{\bm{\nu}_{t}}}\right)$ $\displaystyle+\mathbb{E}\sum_{t=1}^{\tau}\left(\frac{\eta^{3}}{1-\beta_{2}}+\eta\right)\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\left(\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}-\frac{\|\bm{G}_{t+1}\|^{2}}{\sqrt{\bm{\nu}_{t}}}\right)$ $\displaystyle+\frac{1}{16}\eta\mathbb{E}\sum_{t=1}^{\tau}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}},$ $$

where the last inequality is because due to $\frac{\eta}{\sqrt{1-\beta_{2}}}\leq\frac{1-\beta_{1}}{128L_{1}\sigma_{1}}$, following the similar reasoning of Eq. ([25](#A4.E25)), we have

$$ $\displaystyle\frac{64\eta\sigma_{1}^{2}L_{1}}{\sqrt{(1-\beta_{1})^{3}}}\frac{256L_{1}\eta^{2}}{(1-\beta_{1})^{\frac{3}{2}}}\left(\frac{\|\bm{g}_{t}\|^{2}\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}\sqrt{\bm{\nu}_{t}^{2}}}\right)\leq$ $\displaystyle\frac{128\eta\sigma_{1}^{2}L_{1}}{\sqrt{(1-\beta_{1})^{3}}}\frac{256L_{1}\eta^{2}}{(1-\beta_{2})(1-\beta_{1})^{\frac{3}{2}}}\left(\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}-\frac{\|\bm{G}_{t+1}\|^{2}}{\sqrt{\bm{\nu}_{t}}}\right)$ $\displaystyle+\frac{\eta^{3}}{1-\beta_{2}}\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\sum_{s=1}^{t}\sqrt[8]{\beta_{1}^{t-s}}\left(\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}-\frac{1}{\sqrt{\bm{\nu}_{t}}}\right)$ $\displaystyle+\frac{1}{16}\eta\mathbb{E}\sum_{t=1}^{\tau}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}.$ $$

By rearranging the inequality and due to Lemma [3](#Thmlemma3), we obtain

$$ $\displaystyle\frac{1}{8}\eta\mathbb{E}\sum_{t=1}^{\tau}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}$ $\displaystyle\leq$ $\displaystyle f(\bm{u}_{1})-\mathbb{E}f(\bm{u}_{\tau+1})+\frac{64L_{0}\eta^{2}}{(1-\beta_{2})(1-\beta_{1})^{2}}\mathbb{E}\left(\ln\frac{\bm{\nu}_{\tau}}{\bm{\nu}_{0}}-\tau\ln\beta_{2}\right)$ $\displaystyle+\frac{\eta^{3}}{1-\beta_{2}}\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{0}}}+\eta^{3}\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\mathbb{E}\sum_{t=1}^{\tau-1}\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{t}}}$ $\displaystyle+\left(\frac{\eta^{3}}{1-\beta_{2}}+\eta\right)\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\left(\frac{\|\bm{G}_{1}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{0}}}\right)$ $\displaystyle+\mathbb{E}\sum_{t=1}^{\tau}\left(\eta^{3}+\eta(1-\beta_{2})\right)\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\left(\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}\right),$ $$

Furthermore, as $T\geq\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})$, $\eta^{3}=\frac{\eta}{T}\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})$, $\eta(1-\beta_{2})=\frac{\eta}{T}\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})$, and $\|\bm{G}_{t}\|\geq\frac{\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})}{\sqrt[4]{T}}$, we have

$$ $\displaystyle\eta^{3}\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\mathbb{E}\sum_{t=1}^{\tau-1}\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{t}}}\leq\frac{1}{32}\eta\mathbb{E}\sum_{t=1}^{\tau}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}},$ $\displaystyle\mathbb{E}\sum_{t=1}^{\tau}\left(\eta^{3}+\eta(1-\beta_{2})\right)\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\left(\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}\right)\leq\frac{1}{32}\eta\mathbb{E}\sum_{t=1}^{\tau}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}},$ $$

which thus leads to

$$ $\displaystyle\frac{1}{16}\eta\mathbb{E}\sum_{t=1}^{\tau}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}\leq f(\bm{u}_{1})-\mathbb{E}f(\bm{u}_{\tau+1})+\frac{64L_{0}\eta^{2}}{(1-\beta_{2})(1-\beta_{1})^{2}}\mathbb{E}\left(\ln\frac{\bm{\nu}_{\tau}}{\bm{\nu}_{0}}-\tau\ln\beta_{2}\right)$ $\displaystyle+\frac{\eta^{3}}{1-\beta_{2}}\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{0}}}+\left(\frac{\eta^{3}}{1-\beta_{2}}+\eta\right)\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\left(\frac{\|\bm{G}_{1}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{0}}}\right).$ (27) $$

Similar to the proof of Theorem [3](#Thmtheorem3), we then transfer the above bound to the bound of $\sum_{t=1}^{\tau}\|\bm{G}_{t}\|$ by two rounds of divide-and-conquer. In the first round, we will bound $\mathbb{E}\ln\bm{\nu}_{\tau}$. To start with, we have that

$$ $\displaystyle\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}\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{\beta_{2}\bm{\nu}_{t-1}}}\mathds{1}_{\|G_{t}\|\geq\frac{\sigma_{0}}{\sigma_{1}}}$ $$

Furthermore, we have

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

where inequality $(\star)$ is due to $E^{|{\mathcal{F}}_{t}}\|\bm{g}_{t}\|^{2}\mathds{1}_{\|\bm{G}_{t}\|<\frac{\sigma_{0}}{\sigma_{1}}}\leq 2\sigma_{0}^{2}$ and optimal stopping theorem.

Conclusively, we obtain

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

where inequality $(\circ)$ is due to optimal stopping theorem.

Then by substituting $\mathbb{E}\sum_{t=1}^{\tau}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}$ we obtain that

$$ $\displaystyle\mathbb{E}{\sqrt{\sum_{t=1}^{\tau}\|\bm{g}_{t}\|^{2}+\frac{\bm{\nu}_{0}}{1-\beta_{2}}}}$ $\displaystyle\leq$ $\displaystyle\sqrt{\frac{\bm{\nu}_{0}}{1-\beta_{2}}+2\sigma_{0}^{2}T}+\frac{32\sigma_{1}^{2}\sqrt{1-\beta_{2}}}{\eta}\frac{1}{16}\eta\mathbb{E}\sum_{t=1}^{\tau}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}$ $\displaystyle\leq$ $\displaystyle\sqrt{\frac{\bm{\nu}_{0}}{1-\beta_{2}}+2\sigma_{0}^{2}T}+\frac{32\sqrt{1-\beta_{2}}\sigma_{1}^{2}}{\eta}\left(f(\bm{u}_{1})-f^{*}+\frac{64L_{0}\eta^{2}}{(1-\beta_{2})(1-\beta_{1})^{2}}\mathbb{E}\left(\ln\frac{\bm{\nu}_{\tau}}{\bm{\nu}_{0}}-T\ln\beta_{2}\right)\right.$ $\displaystyle+\left.+\frac{\eta^{3}}{1-\beta_{2}}\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{0}}}\left(\frac{\eta^{3}}{1-\beta_{2}}+\eta\right)\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\left(\frac{\|\bm{G}_{1}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{0}}}\right)\right)$ $\displaystyle\leq$ $\displaystyle\sqrt{\frac{\bm{\nu}_{0}}{1-\beta_{2}}+2\sigma_{0}^{2}T}+\frac{32\sqrt{1-\beta_{2}}\sigma_{1}^{2}}{\eta}\left(f(\bm{w}_{1})-f^{*}+\frac{128L_{0}\eta^{2}}{(1-\beta_{2})(1-\beta_{1})^{2}}\left(\ln\frac{\mathbb{E}\sqrt{1-\beta_{2}}\sqrt{\sum_{t=1}^{\tau}\|\bm{g}_{t}\|^{2}+\frac{\bm{\nu}_{0}}{1-\beta_{2}}}}{\sqrt{\bm{\nu}_{0}}}-T\ln\beta_{2}\right)\right.$ $\displaystyle\left.+\frac{\eta^{3}}{1-\beta_{2}}\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{0}}}+\left(\frac{\eta^{3}}{1-\beta_{2}}+\eta\right)\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\left(\frac{\|\bm{G}_{1}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{0}}}\right)\right).$ $$

Multiplying both sides of the above inequality by $\sqrt{1-\beta_{2}}$ then gives

$$ $\displaystyle\sqrt{1-\beta_{2}}\mathbb{E}{\sqrt{\sum_{t=1}^{\tau}\|\bm{g}_{t}\|^{2}+\frac{\bm{\nu}_{0}}{1-\beta_{2}}}}$ $\displaystyle\leq 3\sqrt{\bm{\nu}_{0}+2\sigma_{0}^{2}T(1-\beta_{2})}+\frac{1}{4}\ln\mathbb{E}\sqrt{1-\beta_{2}}\sqrt{\sum_{t=1}^{\tau}\|\bm{g}_{t}\|^{2}+\frac{\bm{\nu}_{0}}{1-\beta_{2}}},$ $$

where we use $\eta=\frac{\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})}{\sqrt{T}}$, $1-\beta_{2}=\frac{\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})}{T}$, and $T\geq\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})$. Therefore, we obtain $\sqrt{1-\beta_{2}}\mathbb{E}{\sqrt{\sum_{t=1}^{\tau}\|\bm{g}_{t}\|^{2}+\frac{\bm{\nu}_{0}}{1-\beta_{2}}}}\leq 6\sqrt{\bm{\nu}_{0}+2\sigma_{0}^{2}T(1-\beta_{2})}$.

Therefore, Eq. ([27](#A4.E27)) can be rewritten as

$$ $\displaystyle\frac{1}{16}\eta\mathbb{E}\sum_{t=1}^{\tau}\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}\leq f(\bm{u}_{1})-\mathbb{E}f(\bm{u}_{\tau+1})+\frac{128L_{0}\eta^{2}}{(1-\beta_{2})(1-\beta_{1})^{2}}\left(\ln\frac{6\sqrt{\bm{\nu}_{0}+2\sigma_{0}^{2}T(1-\beta_{2})}}{\sqrt{\bm{\nu}_{0}}}-T\ln\beta_{2}\right)$ $\displaystyle+\frac{\eta^{3}}{1-\beta_{2}}\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{0}}}$ $\displaystyle+\left(\frac{\eta^{3}}{1-\beta_{2}}+\eta\right)\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\left(\frac{\|\bm{G}_{1}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{0}}}\right).$ $$

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

$$ $\mathbb{E}\sum_{t=1}^{\tau}\left[\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}\mathds{1}_{\|G_{t}\|\geq\frac{\sigma_{0}}{\sigma_{1}}}\right]\leq\mathbb{E}\sum_{t=1}^{\tau}\left[\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}\right].$ $$

On the other hand, we have that

$$ $\displaystyle\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}\mathds{1}_{\|G_{t}\|\geq\frac{\sigma_{0}}{\sigma_{1}}}\geq\frac{1}{2\sigma_{1}^{2}}\mathbb{E}^{|\mathcal{F}_{t}}\frac{\|\bm{g}_{t}\|^{2}}{\sqrt{\bm{\nu}_{t}}+\sqrt{\beta_{2}\bm{\nu}_{t-1}}}\mathds{1}_{\|G_{t}\|\geq\frac{\sigma_{0}}{\sigma_{1}}}\geq\frac{1}{2(1-\beta_{2})\sigma_{1}^{2}}\mathbb{E}^{|{\mathcal{F}}_{t}}\left[\left(\sqrt{\bm{\nu}_{t}}-\sqrt{\beta_{2}\bm{\nu}_{t-1}}\right)\mathds{1}_{\|G_{t}\|\geq\frac{\sigma_{0}}{\sigma_{1}}}\right].$ $$

Meanwhile, recall $\{\bar{\bm{\nu}}_{t}\}_{t=0}^{\infty}$ as $\bar{\bm{\nu}}_{0}=\bm{\nu}_{0}$, $\bar{\bm{\nu}}_{t}=\beta_{2}\bar{\bm{\nu}}_{t-1}+(1-\beta_{2})|g_{t}|^{2}\mathds{1}_{\|\bm{G}_{t}\|<\frac{\sigma_{0}^{2}}{\sigma_{1}^{2}}}$ and $\bar{\bm{\nu}}_{t}\leq\bm{\nu}_{t}$. Therefore

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

All in all, summing the above two inequalities together, we obtain that

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

Since $\bm{\nu}_{0}=\bar{\bm{\nu}}_{0}$ and $\mathbb{E}\sqrt{\bm{\nu}_{\tau}}\geq\mathbb{E}\sqrt{\bar{\bm{\nu}}_{\tau}}$, we obtain

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

Dividing both sides of the above equation by $1-\sqrt{\beta_{2}}$ then gives

$$ $\displaystyle\mathbb{E}\sum_{t=0}^{\tau-1}\sqrt{\widetilde{\bm{\nu}}_{t}}\leq$ $\displaystyle{4\sigma_{1}^{2}}\mathbb{E}\sum_{t=1}^{\tau}\left[\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}\right]+T\sigma_{0}.$ $$

By applying Eq. ([21](#A3.E21)) and the constraint of $\tau$, we obtain that

$$ $\displaystyle\mathbb{E}\sum_{t=0}^{\tau-1}\sqrt{\bm{\nu}_{t}}\leq$ $\displaystyle T\sigma_{0}+64\frac{\sigma_{1}^{2}}{\eta}\left(f(\bm{u}_{1})-\mathbb{E}f(\bm{u}_{\tau+1})+\frac{64L_{0}\eta^{2}}{1-\beta_{2}}\left(\ln\frac{6\sqrt{\bm{\nu}_{0}+2\sigma_{0}^{2}T(1-\beta_{2})}}{\sqrt{\bm{\nu}_{0}}}-T\ln\beta_{2}\right)\right.$ $\displaystyle+\left.\frac{\eta^{3}}{1-\beta_{2}}\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{0}}}\right.$ $\displaystyle+\left.\left(\frac{\eta^{3}}{1-\beta_{2}}+\eta\right)\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\left(\frac{\|\bm{G}_{1}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{0}}}\right)\right)$ $\displaystyle\leq$ $\displaystyle 4T\sigma_{0}.$ $$

Here the last inequality is due to $\eta=\frac{\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})}{\sqrt{T}}$, $1-\beta_{2}=\frac{\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})}{T}$, and $T\geq\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})$.
Therefore, by Cauchy’s inequality, we obtain that

$$ $\displaystyle\left(\mathbb{E}\sum_{t=1}^{\tau}\|\nabla f(\bm{w}_{t})\|\right)^{2}\leq$ $\displaystyle\left(\mathbb{E}\sum_{t=0}^{\tau-1}\sqrt{\bm{\nu}_{t}}\right)\left(\mathbb{E}\sum_{t=1}^{\tau}\left[\frac{\|\bm{G}_{t}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{t-1}}}\right]\right)$ $\displaystyle\leq$ $\displaystyle 4T\sigma_{0}\times\frac{16}{\eta}\left(f(\bm{w}_{1})-f^{*}+\frac{64L_{0}\eta^{2}}{1-\beta_{2}}\left(\ln\frac{6\sqrt{\bm{\nu}_{0}+2\sigma_{0}^{2}T(1-\beta_{2})}}{\sqrt{\bm{\nu}_{0}}}-T\ln\beta_{2}\right)\right.$ $\displaystyle+\left.\frac{\eta^{3}}{1-\beta_{2}}\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\frac{1}{\sqrt{\beta_{2}\bm{\nu}_{0}}}\right.$ $\displaystyle+\left.\left(\frac{\eta^{3}}{1-\beta_{2}}+\eta\right)\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})\left(\frac{\|\bm{G}_{1}\|^{2}}{\sqrt{\beta_{2}\bm{\nu}_{0}}}\right)\right)$ $\displaystyle\overset{(*)}{\leq}$ $\displaystyle 4T\sigma_{0}\times\frac{16}{\eta}\left(3(f(\bm{w}_{1})-f^{*})+\frac{128L_{0}\eta^{2}}{(1-\beta_{2})(1-\beta_{1})^{2}}\left(\ln\frac{6\sqrt{\bm{\nu}_{0}+2\sigma_{0}^{2}T(1-\beta_{2})}}{\sqrt{\bm{\nu}_{0}}}-T\ln\beta_{2}\right)\right)$ $\displaystyle\overset{(\bullet)}{\leq}$ $\displaystyle 64T\sigma_{0}\left(3\sqrt{TL_{0}(f(\bm{w}_{1})-f^{*})}+\frac{128L_{0}\eta}{(1-\beta_{2})(1-\beta_{1})^{2}T}T\left(\ln\frac{6\sqrt{\bm{\nu}_{0}+2\sigma_{0}^{2}T(1-\beta_{2})}}{\sqrt{\bm{\nu}_{0}}}\right)\right)$ $\displaystyle\leq$ $\displaystyle 64T\sigma_{0}\left(387(1-\beta_{1})\sqrt{TL_{0}(f(\bm{w}_{1})-f^{*})}\right),$ $$

where inequality $(*)$ is due to $\eta=\frac{\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})}{\sqrt{T}}$, $1-\beta_{2}=\frac{\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})}{T}$, and $T\geq\operatorname{Poly}(L_{0},L_{1},\sigma_{0},\sigma_{1},\frac{1}{1-\beta_{1}},f(\bm{w}_{1})-f^{*})$, inequality $(\bullet)$ is due to that $\eta=\frac{\sqrt{f(\bm{w}_{1})-f^{*}}}{\sqrt{L_{0}}}$, and last inequality is due to $\frac{1}{(1-\beta_{2})T}\ln\frac{6\sqrt{\bm{\nu}_{0}+2\sigma_{0}^{2}T(1-\beta_{2})}}{\sqrt{\bm{\nu}_{0}}}\leq 6$.

We then consider two cases: $\tau<T$ and $\tau=T$: for the first case, we have that according to the definition of $\tau$

$$ $\mathbb{E}\min_{t\in[1,T]}\|\bm{G}_{t}\|\mathds{1}_{\tau<T}\leq\frac{\sqrt[4]{\sigma_{0}^{2}L_{0}(f(\bm{w}_{1})-f^{*})}}{\sqrt[4]{T}}.$ $$

For the latter case, we have

$$ $\displaystyle\mathbb{E}\min_{t\in[1,T]}\|\bm{G}_{t}\|\mathds{1}_{\tau=T}\leq\frac{1}{T}\left(\mathbb{E}\sum_{t=1}^{T}\|\nabla f(\bm{w}_{t})\|\mathds{1}_{\tau=T}\right)\leq\frac{1}{T}\left(\mathbb{E}\sum_{t=1}^{\tau}\|\nabla f(\bm{w}_{t})\|\right)\leq\frac{256\sqrt[4]{\sigma_{0}^{2}L_{0}(f(\bm{w}_{1})-f^{*})}}{\sqrt[4]{T}}.$ $$

Summing the two inequalities above complete the proof.
∎

###### Theorem 12 (Theorem 5 , restated) .

###### Proof.

### D.2 Proof of Theorem 6

###### Proof.

As described in Section [5](#S5), the proof immediately follows by several modifications of the proof of Theorem [12](#Thmtheorem12):

- •
We start our analysis for $t\geq\frac{L_{1}^{4}128^{4}\sigma_{1}^{4}}{(1-\beta_{1})^{4}}$. For $t\leq\frac{L_{1}^{4}128^{4}\sigma_{1}^{4}}{(1-\beta_{1})^{4}}$, the function value can be bounded by constant as $\frac{L_{1}^{4}128^{4}\sigma_{1}^{4}}{(1-\beta_{1})^{4}}$ is independent of $t$;
- •
For $t\geq\frac{L_{1}^{4}128^{4}\sigma_{1}^{4}}{(1-\beta_{1})^{4}}$, we have $\max\{\|\bm{u}_{t}-\bm{w}_{t}\|,\|\bm{u}_{t+1}-\bm{w}_{t}\|\}\leq\frac{1}{L_{1}}$ since $\|\bm{w}_{t+1}-\bm{w}_{t}\|\leq\frac{1}{\sqrt[4]{t}}$ which also can be used to prove Eq. ([25](#A4.E25)).

The proof is completed.
∎

###### Proof.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: see weaknesses
soundness: 2
strengths: The article establishes convergence theory for Stochastic Gradient Descent with Momentum (SGDM) and simplified Adam. 
The comparsion of the convergence theory between SGDM with simplified Adam could be interesting from some certain points of view.
summary: This paper provides a comparative analysis of Stochastic Gradient Descent with Momentum (SGDM) and simplified Adam (considering the same step-size for each coordinate and ignoring the corrective terms), focusing on their convergence rates under varying conditions. The authors argue that the variant of Adam converges faster than SGDM when dealing with non-uniformly bounded smoothness. 

In the deterministic environments, the authors claim that simplified Adam can reach the optimal convergence rate for deterministic first-order methods, while SGDM shows a higher dependence on the initial function value, suggesting a slower convergence rate.

In the stochastic setting: the authors claim that simplified Adam's convergence rate upper bound is shown to align with the theoretical lower bounds for stochastic first-order methods, considering both the initial function value and final error. The authors highlight that SGDM can sometimes fail to converge, regardless of the learning rate, under certain conditions.

The paper use a stopping-time-based technique, enabling analysis of the minimum gradient norm over iterations. This method demonstrates that simplified Adam’s convergence rate can match lower bounds.
weaknesses: The paper establishes convergence results only for a simplified version of Adam, where uniform step sizes are applied across coordinates, and corrective terms are ignored. This limitation leaves the convergence behavior of the full coordinate-wise Adam algorithm unaddressed.

Notation issues: Notation is inconsistently applied, leading to potential confusion. For instance, in the algorithm’s statement, $v_t$
is a vector, but in the appendix proof, 
$v_t$ is treated as a scalar.

It seems some of the cited references may already have derived optimal convergence rates for deterministic Adam (or provided results in the stochastic setting that could be applied to the deterministic setting). A thorough comparison with these existing results would strengthen the paper and clarify its contributions.

The stopping rule employed appears similar to those used in analyses of other stochastic gradient methods under generalized smoothness conditions. The paper may clarify what novelty this rule brings to the current analysis. Additionally, please clarify the dependence of 
$\tau$ on random variables. Since 
$\tau$ itself is a random variable, it’s unclear how the inequality in line 2019 follows directly from Equation (26). Similar clarifications may be needed for the statements in lines 2276 and 2280.

Is there any explicit expression for $\beta_2$ from Theorem 9?

The overall write-up would benefit from improvements in clarity. For example, several formulas in the appendix exceed the width and could be improved to improve readability.

---

confidence: 2
contribution: 3
initial_rating: 8
presentation: 3
questions: How does this paper relate to the following prior work which also analyzes Adam and SGD(M) under non-uniform smoothness:
```@inproceedings{wang2024provable,
  title={Provable adaptivity of adam under non-uniform smoothness},
  author={Wang, Bohan and Zhang, Yushun and Zhang, Huishuai and Meng, Qi and Sun, Ruoyu and Ma, Zhi-Ming and Liu, Tie-Yan and Luo, Zhi-Quan and Chen, Wei},
  booktitle={Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  pages={2960--2969},
  year={2024}
}
```
soundness: 3
strengths: * Paper is clearly structured, moving from motivations to assumptions, to the simpler determinstic setting to the more complex stochastic section.
* Paper provides clear exposition and arguments for the practical relevance of the non-uniform smoothness assumptions they use.
* Paper provides the intuition behind the different convergence behaviors e.g. explaining the behavior of the adaptive conditioner used in AdaGrad or GDM’s inability to manage varying degrees of sharpness in the loss function.
* Authors explain the limitations of a previous derivation of the lower bound of determinstic GD in the literature and use this to motivate their lower bound formulation that allows adjusted hyperparams (learning rate) after the objective function has been selected but arrives at the same bound and is taking into account momentum.
* For their Adam upper bound in the stochastic case they provide a high level summary of the additional challenges addressed compare to an analysis of Adam under L-smooth condition from the literature.
summary: The paper presents a convergence analysis of Adam and SGD with Momentum (SGDM) under the non-uniform (L_0, L_1)-smoothness assumption (where the gradient smoothness depends on the gradient norm itself) and an affine noise assumption on the gradient in the stochastic setting. The authors show that under these assumptions Adam has an upper bound that is better than the lower bound of (S)GDM in both the deterministic and stochastic settings.

In the deterministic setting the authors provide a tighter upper bound for Adam than two cited previous papers and for GDM they re-iterate on a prior known lower bound in more realistic setting (with choosing learning rate after the objective function is known). Based on these two bounds the authors are then able to separate the convergence rates of Adam and GDM showing that Adam is superior in the deterministic setting.

The authors then move on to extend their analysis to the stochastic setting where they claim that their new Adam upper bound extends prior convergence results of Adam and clipped SGDM with their new Adam bound giving the best upper bound achieved under the assumptions made in the paper so far. For the lower bound of SGDM the authors provide a bound that is tighter than the prior results from the literature to be able to separate the Adam and SGDM bounds.

In the final sections the authors discuss what happens when the “regularizing” constant lambda is used and introduce a stopping-time analysis under which they discuss how Adam can actually achieve the optimal lower bound rate.
weaknesses: * The paper could perhaps be improved with a more extensive overview/discussion of the attributes of optimizers that allow the type of analysis they provide for Adam (as an extension of e.g. their brief discussion on AdaGrad). The authors already provide the intuition behind why e.g. SGDM fails to converge under non-uniform smoothness etc. but perhaps these reasons could be summarized in a sort of "intuitions behind the results" paragraph earlier in the paper.

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 3
questions: The main concerns from my perspective for this paper have been listed in the **Weakness** part. Below are some more related questions that need to be addressed:

1. How to ensure that the choice of $\beta_2$ provided in Theorem 9 satisfies all the assumptions ($\beta_1 \leq \beta_2$, $0\leq \beta_1^2 < \beta_2 < 1$, $\beta_2 \geq \frac{1}{2}$ and $1-\beta_2\leq \frac{1-\beta_1}{1024\sigma_1^2}$) required in the derivation of this result? 

2.  How to ensure that the choice of $\beta_2$ provided in Theorem 11 satisfies all the assumptions ($\beta_1 \leq \beta_2$ and $0\leq \beta_1^2 < \beta_2 < 1$) required in the derivation of this result? If such a choice of $\beta_2$ exists, can we guarantee that inequality $\frac{\eta}{\sqrt{1-\beta_2}}\leq \frac{1-\beta_1}{128L_1\sigma_1}$ given on page 39 hold true? 

3. Could you please give more details on the choice of $\beta_2$ and the derivation of the inequality $\Vert w_{t+1} - w_t\Vert \leq \frac{1}{\sqrt[4]{t}}$ in the case where $t\geq \left(\frac{128\sigma_1 L_1}{1-\beta_1}\right)^4$?
soundness: 2
strengths: 1. This work analyzes Adam's convergence rate under mild assumptions. Specifically, the convergence results are established under the $(L_0,L_1)$-smooth condition and affine noise variance assumption, relaxing the commonly used $L$-smooth condition and bounded variance assumption in prior studies. 
   
2. The obtained upper bound on the convergence rate of Adam is tighter than those given in prior studies and matches the lower bound of first-order optimizers in both deterministic and stocahstic settings. 

3. A novel stopping time technique is developed. Based on this technique, it is demonstrated in Theorem 12 that Adam with some **specific parameter scheduler** is parameter-agnostic.
summary: This paper aims to theoretically compare the convergence rates of Adam and Stochastic Gradient Descent with Momentum (SGDM) to explore the superior empirical performance of Adam over SGDM. Specifically, it separates Adam and SGDM regarding the convergence rate under $(L_0,L_1)$-smooth condition in both deterministic and stochastic settings. One interesting point in this paper is that the authors used a novel stopping time technique to show Adam's convergence rate in terms of the minimum gradient norm matching the lower bound for first-order stochastic optimizers, considering all problem hyperparameters. With the aid of this technique, the authors show that Adam with a specific parameter scheduler is parameter-agnostic.
weaknesses: 1. The proof of Theorem 3 in Appendix C.1 appears to be **NOT complete**. Specifically, in deriving an upper bound for Adam in terms of the average gradient norm, the first-order term $\mathbb{E}^{\vert \mathcal{F}_t}[\langle\nabla f(w_t),u_{t+1}-u_t\rangle]$ is decomposed into three components as shown in equation (7). However, referring to equation (8), the combination of inequalities (11) and (12) provides an upper bound only for the second term on the RHS of equation (7). Then, the RHS of inequality (13) provides an upper bound only for the sum of the first two terms, neglecting the third term on the RHS of equation (7). Thus, the proof lacks justification for establishing an upper bound on the third term. 

2.  Some statements in the paper are not consistent. The consistency of the statements is critical for a theoretical paper. For example, the proof of Theorem 3 provided in Appendix C.1 relies on assumptions that $\beta_1 \leq \beta_2$ (line 1390 in page 26), $0\leq \beta_1^2 < \beta_2 < 1$ (requirement of Lemma 1), $\beta_2 \geq \frac{1}{2}$ and $1-\beta_2\leq \frac{1-\beta_1}{1024\sigma_1^2}$ (line 1416 in page 27), which are not captured in the corresponding formal statement. Similarly, the formal statement of Theorem 5 omits assumptions that $\beta_1 \leq \beta_2$ and $0\leq \beta_1^2 < \beta_2 < 1$ (see Theorem 11 in Appendix D.1). 

3. The convergence results for Adam presented in Theorem 3 and Theorem 5 stipulate "a proper choice of learning rate $\eta$ and momentum hyperparameter $\beta_2$". However, as shown in the corresponding formal statements in Appendix C.1 (Theorem 9) and Appendix D.1 (Theorem 11), deriving these results necessitates tuning $\eta$ and $\beta_2$ with prior knowledge of the non-uniformly bounded smoothness parameters $(L_0,L_1)$ and affine noise variance parameters $(\sigma_0,\sigma_1)$. Since these parameters may be unknown or difficult to estimate in realistic situations, the practical utility of the derived results is questionable as their conditions on hyperparameters would be challenging to satisfy. 

4. There is a lack of clarity around the focused version of Adam. Two different versions are assumed in this paper: the coordinate-wise version and the norm version. While Algorithm 1 introduced in the main text is the coordinate-wise Adam, it is not until Appendix B that the authors first state that all the subsequent theorems apply to the norm version of Adam. Although a footnote in the appendix mentions that an extension to the coordinate-wise version from the norm version is not difficult, more detailed discussions are necessary and helpful. 

5. There are some typos in this paper. Also, the citation format should be carefully checked.

Overall, I found this paper made some interesting theoretical comparisons between Adam and SGDM. But the rigorous proofs and statements are the key to a theoretical paper. **My current rating of this paper is under the assumption that the first point above can be fully addressed**.

---

confidence: 4
contribution: 1
initial_rating: 1
presentation: 1
questions: - Remove the blue color in theorems.
- Define the sequence $\( w_t \)$ in Theorems 3, 4, 5. Also, add a proper name for each theorem to understand which algorithm each result deals with.
- The appendix needs a thorough re-reading; for instance, look at line 2015: "Also, as  $\tau$  is a bounding stopping theorem, by optional stopping time, we obtain ..."
- Writing literature reviews in the appendix in the middle of the proof makes the reading inefficient.
- Line 465: the quantifier $\forall$ looks weird this way. I suggest writing "for all."
- Throughout the paper, rewrite the left quotation mark in the correct direction.
- Avoid cumbersome expressions such as "to the best of our knowledge," "for the first time" (used many times on page 7).
soundness: 2
strengths: L0,L1 smoothness assumptions are interesting to consider as they better coincide with deep learning situations.
summary: ADAM and momentum based stochastic gradient algorithms are popular optimization methods used in deep learning. Classical analyses of such methods rely on a globally Lipschitz gradient assumption (L-smoothness). Yet   this condition is not satisfied in practical situations. This paper studies stochastic gradient method with momentum and ADAM algorithm under "$L_0, L_1$ smoothness", where compared L-smoothness, the Lipschitz constant of the gradient depends on the gradient norm (hence allowing for non Lipschitz gradients). This follows many works dealing with relaxed smoothness conditions.

The authors provide convergence rates in (expected) best iterate, or averaged gradient norms. They also provide lower bounds by exhibiting one dimensional functions attaining the guarantees.
weaknesses: Overall, the paper brings no substantial contribution compared to the literature.


- The convergence rates use classical and elementary tools (smoothness inequalities, stopping time in the stochastic setting) that already exist in the literature. For instance, similar convergence rates were established in Li et al., 2023a. The authors highlight some differences (section 4.1) with the related works but the arguments seem wrong or irrelevant.

- Some mathematical parts are wrong. For instance, the authors consider the regularization parameter $\lambda$ to be zero but this leads to divisions by zero in the proofs (see for instance line 857) with no further assumption.

- The lower bounds are based on trivial and degenerate situations, especially in the stochastic setting. The lower bound function (Theorem 10 in Appendix) is based on a gradient noise which image by the gradient is not integrable, thus leading to a vacuous bound (all expectations become infinite). For instance, it does not depend on the smoothness parameters, which was the motivation stated in the introduction. Exhibiting the lower bounding function in the main text would make the presentation more honest and transparent. Lower bounds found in the literature are based on constructions that are much more sophisticated because they exhibit more restrictive properties (stability, gradient boundedness, etc.); see, for instance, Carmon et al., Arjevani et al.

Meta-review: The paper presents a convergence analysis comparing Adam and SGDM under non-uniform smoothness assumptions in both deterministic and stochastic settings. The study introduces stopping-time techniques to show that Adam achieves convergence rates that align with lower bounds for first-order methods, while SGDM struggles under specific conditions. 

There was a strong divergence of opinion in the initial reviews but the authors unfortunately did not reply to all the reviewers. Some concerns are important and regard the correctness of the analysis. I'm therefore not in a position to accept the paper and ask the authors to address the comments from the reviewers in a resubmission.

Decision: Reject