January 01, 1970
The Exponential Moving Average (EMA) is a cornerstone of widely used optimizers such as Adam. However, existing theoretical analyses of Adam-style methods have notable limitations: their guarantees can remain suboptimal in the zero-noise regime, rely on restrictive boundedness conditions (e.g., bounded gradients or objective gaps), use constant or open-loop stepsizes, or require prior knowledge of Lipschitz constants. To overcome these bottlenecks, we introduce OptEMA and analyze two novel variants: OptEMA-M, which applies an adaptive, decreasing EMA coefficient to the first-order moment with a fixed second-order decay, and OptEMA-V, which swaps these roles. At the heart of these variants is a novel Corrected AdaGrad-Norm stepsize. This formulation renders OptEMA closed-loop and Lipschitz-free, meaning its effective stepsizes are strictly trajectory-dependent and require no parameterization via the Lipschitz constant. Under standard stochastic gradient descent (SGD) assumptions, namely smoothness, a lower-bounded objective, and unbiased gradients with bounded variance, we establish rigorous convergence guarantees. Both variants achieve a noise-adaptive convergence rate of \(\widetilde{\mathcal{O}}(T^{-1/2}+\sigma^{1/2} T^{-1/4})\) for the average gradient norm, where \(\sigma\) is the noise level. Crucially, the Corrected AdaGrad-Norm stepsize plays a central role in enabling the noise-adaptive guarantees: in the zero-noise regime (\(\sigma=0\)), our bounds automatically reduce to the nearly optimal deterministic rate \(\widetilde{\mathcal{O}}(T^{-1/2})\) without any manual hyperparameter retuning.
Stochastic Optimization, Exponential Moving Average, Nonconvex Optimization, Adaptive Gradient Method, Convergence Analysis, Adam
We study mini-batch stochastic optimization for the nonconvex objective \[\label{eq:main} \min_{\mathbf{x}\in\mathbb{R}^{n}} f(\mathbf{x}):=\mathbb{E}_{\xi\sim\mathcal{D}}[f(\mathbf{x};\xi)] ,\tag{1}\] where \(f(\cdot)\) is differentiable and possibly nonconvex, and \(\xi\) denotes an i.i.d. sample from an unknown distribution \(\mathcal{D}\). Our goal is to find an \(\epsilon\)-approximate stationary point \(\mathbf{x}\) such that \(\mathbb{E}[\|\nabla f(\mathbf{x})\|]\le \epsilon\). We adopt only the basic assumptions standard in Stochastic Gradient Descent (SGD) theory [1]: lower-bounded objective, unbiased stochastic gradients, and smoothness of \(f(\cdot)\), together with bounded variance.
Adaptive gradient methods, such as RMSProp [2] and Adam [3], have become standard tools for training deep neural networks, often showing strong empirical performance compared to vanilla Stochastic Gradient Descent (SGD). A key ingredient behind their practical success is the Exponential Moving Average (EMA) mechanism, which provides a memory-efficient way to accumulate historical gradient information. In particular, EMA is used to form moving estimates of the first moment and the second raw moment of stochastic gradients, thereby inducing momentum-like averaging and coordinate-wise rescaling. Intuitively, EMA can be viewed as a temporal low-pass filter on the gradient sequence [4]: it suppresses rapid stochastic fluctuations while retaining more persistent directional information. By smoothing updates and damping oscillations, EMA often yields more stable optimization dynamics, which is particularly valuable in the highly nonconvex loss landscapes encountered in modern deep learning.
Despite their empirical success, the theoretical understanding of EMA-based optimizers still remains incomplete. First, existing analyses exhibit weak behavior in the zero-noise regime. Ideally, a noise-adaptive optimizer should recover the deterministic rate \(\mathcal{O}(T^{-1/2})\) when the stochastic variance vanishes (\(\sigma=0\)). In contrast, available guarantees for Adam-type methods often remain stuck at the suboptimal rate \(\mathcal{O}(T^{-1/4})\) in deterministic settings [5]–[9], suggesting that current proofs rely on worst-case arguments rather than genuine noise adaptivity. Second, these results are typically established under restrictive assumptions, most notably globally bounded gradients, an assumption that fails even for simple strongly convex objectives and is difficult to justify in modern deep learning models [10]. Third, conventional adaptive methods are inherently open-loop: their EMA decay coefficients and global learning rate are fixed or pre-scheduled, rather than coupled to the observed trajectory. Consequently, they cannot adapt their stepsize to the local geometry [11], and their performance remains sensitive to manual tuning and unknown smoothness parameters.
These theoretical limitations and practical tuning burdens motivate the search for a more principled stochastic optimizer. To better bridge optimization theory and deep learning practice, such a method should be Lipschitz-free and noise-adaptive. To this end, we propose the Adaptive Exponential Moving Average with zero-noise optimality, OptEMA. Our contributions are threefold.
Novel Algorithmic Design: We redesign the standard EMA mechanism as a closed-loop feedback controller rather than an open-loop scaling rule. This leads to two variants: OptEMA-M, which adapts the first-moment update while fixing the second moment, and OptEMA-V, which adapts the second-moment update while fixing the first. In both cases, the EMA coefficients are coupled to the observed optimization trajectory.
Rigorous Theoretical Guarantees: Under standard assumptions and without the bounded-gradient condition, we prove that OptEMA attains the noise-adaptive rate \(\widetilde{\mathcal{O}}(T^{-1/2} + \sigma^{1/2}T^{-1/4})\). Moreover, in the zero-noise regime, the guarantee automatically improves to the optimal deterministic rate, without requiring prior knowledge of the Lipschitz constant or manual retuning.
Corrected Adaptive Stepsize: As an independent structural contribution, we propose a novel data-dependent schedule termed the Corrected AdaGrad-Norm stepsize. This schedule is dimension-free and monotonically non-increasing. Crucially, it incorporates a historical averaging mechanism that renders the optimization process highly robust to gradient spikes, effectively mitigating the premature stepsize decay that inherently plagues standard AdaGrad-Norm.
The remainder of this paper is organized as follows. Section 2 reviews the related literature, and Section 3 introduces the assumptions and technical preliminaries. Section 4 presents the OptEMA framework and its variants, while Section 5 provides the iteration complexity analysis. Section 6 concludes the paper. Detailed proofs are deferred to the appendix.
This section reviews the literature most relevant to our work, including stochastic gradient methods, adaptive optimization, momentum-based variance reduction, and recent Lipschitz-free and noise-adaptive algorithms.
Stochastic first-order methods, including SGD and momentum-based variants, remain the foundation of large-scale learning. For smooth nonconvex objectives, their analyses typically assume unbiased stochastic gradients, bounded variance, lower-bounded objectives, and suitable smoothness conditions. The achievable convergence rate depends critically on the adopted smoothness model. Under average smoothness, the best known lower bound scales as \(\Omega(T^{-1/4})\), whereas stronger individual smoothness can support faster rates such as \(\Omega(T^{-1/3})\) [12]. These distinctions are central to understanding the gap between classical stochastic optimization theory and modern deep-learning optimizers.
Adaptive gradient methods were developed to better handle stochastic gradients with heterogeneous coordinate scales, especially in sparse-data regimes. AdaGrad [13] introduced data-dependent per-coordinate stepsizes through accumulated gradient statistics, which naturally amplify updates on infrequent coordinates and damp those on frequently active ones. RMSProp [2] replaced monotone accumulation with an EMA of squared gradients to avoid overly aggressive decay. Adam [3] then combined first-moment momentum with second-moment EMA scaling, and has since become the dominant adaptive optimizer in practice. Later variants refined this design in different ways: AdamW [14] decoupled weight decay from adaptive updates, while AMSGrad [15] introduced a running maximum of second moments to address known non-convergence phenomena in vanilla Adam.
STORM [16] was among the first methods to combine recursive gradient estimation with a momentum-style update in stochastic optimization. STORM\(^+\) [17] further demonstrated that, with appropriately designed adaptive stepsize strategies, such estimators can achieve both Lipschitz-free and noise-adaptive guarantees. META-STORM [18] relaxed the bounded-objective assumption, while AdaSTORM [19] further removed both the bounded-objective and bounded-gradient assumptions, although it relies on a hybrid stepsize scheme that combines a constant step size of order \(\mathcal{O}(T^{-1/3})\) with a momentum-adapted one. SuperAdam [7] offered a broader perspective by integrating momentum, adaptive scaling, and matrix preconditioning. MARS [20] revisited recursive momentum by introducing an additional variance-reduction correction term to improve the quality of the gradient estimator. Together, these works help bridge modern stochastic optimization theory and practical adaptive optimization.
Adam-type and STORM-type methods represent two complementary directions in stochastic optimization. STORM-type methods can achieve faster asymptotic rates, such as \(\mathcal{O}(T^{-1/3})\), but typically rely on individual smoothness, which is stronger than the average smoothness commonly used in analyses of Adam-type methods. They also incur additional computational overhead, since maintaining the recursive variance-reduced estimator requires evaluating both \(\nabla f(\mathbf{x}_t,\xi_t)\) and \(\nabla f(\mathbf{x}_{t-1},\xi_t)\) on the same mini-batch at each iteration. In large-scale deep learning, this extra cost can substantially reduce their practical appeal. As a result, STORM-type methods are used mainly as theoretical baselines, whereas Adam-type methods remain the dominant practical choice. OptEMA follows this Adam-style design: it preserves the standard one-gradient EMA update rule, operates under average smoothness, and achieves the noise-adaptive rate \(\widetilde{\mathcal{O}}(T^{-1/2} + \sigma^{1/2}T^{-1/4})\) (see Theorems 1, 2), compared with the STORM-type dependence \(\widetilde{\mathcal{O}}(T^{-1/2} + \sigma^{1/3}T^{-1/3})\) in [17]. Hence, ignoring differences in assumptions and logarithmic factors, OptEMA attains a strictly tighter bound when \(\sigma <T^{-1/2}\).
Representative methods in this regime, such as AdaGrad-Norm [21], STORM+ [17], and META-STORM [18], use the optimization trajectory as feedback to adapt the learning rate. These methods are both Lipschitz-free and noise-adaptive: they do not require prior knowledge of the Lipschitz smoothness constant and automatically adjust to the noise level \(\sigma\). In particular, when \(\sigma=0\), their bounds recover the deterministic convergence rate for smooth nonconvex optimization. However, these approaches remain structurally different from standard EMA-based optimizers used in deep learning. AdaGrad-Norm relies on cumulative averaging rather than exponential moving averages (EMA), while the analyses of STORM\(^+\) and META-STORM are tied to variance-reduction architectures. By contrast, OptEMA preserves the standard EMA structure of Adam-type methods and achieves the rate \(\widetilde{\mathcal{O}}(T^{-1/2} + \sigma^{1/2}T^{-1/4})\) through closed-loop stepsize adaptation.
OptEMA is analyzed under the standard assumptions used in stochastic gradient methods: a lower-bounded objective, unbiased stochastic gradients with bounded variance, and smoothness of \(f(\cdot)\). By contrast, several STORM-family analyses [17], [18] additionally impose not only the stronger individual smoothness condition, but also boundedness assumptions such as bounded gradients (BG), bounded objective values (BF), or Hessian-type boundedness (BH), which may be restrictive in large-scale learning. Similarly, under average smoothness, SuperAdam also relies on Hessian-type boundedness assumptions [7].
Recent work has also emphasized hardware efficiency and structural priors. Sign-based methods such as signSGD [22] and Lion [23] reduce memory and communication costs, while AdaFactor [24] compresses second-moment statistics through factorization. Matrix-structured optimizers, such as Muon [25], use orthogonalized gradient updates to improve conditioning. These efficiency- and structure-oriented approaches, however, are typically paired with open-loop stepsize rules and thus offer limited adaptivity to heterogeneous noise. In a different direction, methods such as D-Adaptation [26] and DoG [27] use the optimization trajectory itself as feedback to adapt the learning rate. This trajectory-aware perspective is closely related to the closed-loop EMA design of OptEMA.
Existing adaptive methods are frequently bottlenecked by weak zero-noise optimality, restrictive boundedness assumptions (e.g., bounded gradients or objective gaps), rigid open-loop step sizes, and the need for known Lipschitz constants. Our proposed OptEMA framework systematically eliminates these theoretical and practical hurdles, achieving noise-adaptive, closed-loop optimization under standard assumptions. A comprehensive comparison of existing stochastic gradient methods is detailed in Table ¿tbl:tab:main?.
| Algorithm | Smoothness Assum. | Lipschitz-Free | 1st Moment Coef. (\(\alpha_t\)) \(^a\) | 2nd Moment Coef. (\(\beta_t\))\(^a\) | Stepsize (\(\gamma_t\)) \(^a\) | Additional Assumptions \(^b\) | Convergence Rate |
|---|---|---|---|---|---|---|---|
| STORM [16] | Individual | \(^c\) | Ada | — | Ada | BG, BF | \(\widetilde{\mathcal{O}}(1/\sqrt{T} + \sigma^{1/3} T^{-1/3})\) |
| STORM\(^+\) [17] | Individual | Ada | — | Ada | BG, BF | \({\mathcal{O}}(1/\sqrt{T} + \sigma^{1/3} T^{-1/3})\) | |
| SuperADAM-I [7] | Individual | \(^c\) | Const | — | Open | BH | \(\widetilde{\mathcal{O}}(T^{-1/3})\) |
| MARS [20] | Individual | Open | — | Open | BG | \(\widetilde{\mathcal{O}}(1/\sqrt{T} + \sigma^{1/3} T^{-1/3})\) | |
| META-STORM [18] | Individual | Ada | — | Ada | BG | \(\widetilde{\mathcal{O}}(1/\sqrt{T} + \sigma^{1/3} T^{-1/3})\) | |
| AdaSTORM [19] | Individual | Const | — | Const + Ada \(^d\) | — | \(\mathcal{O}(T^{-1/3})\) | |
| AdaFom [5] | Average | Const | Open | Open | BG | \(\widetilde{\mathcal{O}}(T^{-1/4})\) | |
| Practical Adam [6] | Average | Open | Const | Open | BG, \(\alpha_t > \beta^2\) | \(\widetilde{\mathcal{O}}(T^{-1/4})\) | |
| SuperADAM-A [7] | Average | \(^b\) | Const | — | Open | BH | \(\widetilde{\mathcal{O}}(T^{-1/4})\) |
| Vanilla Adam [8] | Average | Open | Const | Open | BG, \(\alpha_t\leq \sqrt{\beta}\) | \(\widetilde{\mathcal{O}}(T^{-1/4})\) | |
| AdaGrad-Norm [21] | Average | — | — | Ada \(^e\) | BG | \(\widetilde{\mathcal{O}}(1/\sqrt{T} + \sigma^{1/2} T^{-1/4})\) | |
| OptEMA-M [ours] | Average | Ada | Const | Ada | — | \(\widetilde{\mathcal{O}}(1/\sqrt{T} + \sigma^{1/2} T^{-1/4})\) | |
| OptEMA-V [ours] | Average | Const | Ada | Ada | — | \(\widetilde{\mathcal{O}}(1/\sqrt{T} + \sigma^{1/2} T^{-1/4})\) |
| Note a: Const: fixed constant. Open: openloop stepsize. Ada: adaptive stepsize using local geometry. |
| Note b: BF: bounded objective; BG: bounded gradient; BH: lower-bounded Hessian eigenvalues. |
| Note c: STORM and SuperADAM are not Lipschitz-free, as they depend on the Lipschitz constant for parameterization. |
| Note d: AdaSTORM uses a hybrid step size (constant + momentum-adapted) and is therefore not fully adaptive. |
| Note e: AdaGrad-Norm exhibits limited adaptivity, as it lacks both an EMA mechanism and coordinate-wise scaling. |
We begin by stating the standard assumptions used throughout the paper.
Assumption 1 (Lower-Bounded Objective). There exists a constant \(f_* > -\infty\) such that \(f(\mathbf{x})\ge f_*\), \(\forall\,\mathbf{x}\in\mathbb{R}^n\).
Assumption 2 (Unbiased Stochastic Gradient with Bounded Variance). There exists a constant \(\sigma \geq 0\) such that, for all \(\mathbf{x}\in\mathbb{R}^n\), \(\mathbb{E}\!\left[\nabla f(\mathbf{x};\xi)\right]=\nabla f(\mathbf{x})\), \(\mathbb{E}\!\left[\|\nabla f(\mathbf{x};\xi)-\nabla f(\mathbf{x})\|_2^2\right]\le \sigma^2\).
Assumption 3 (Smoothness of the Objective). We assume that \(f\) is (average) \(L\)-smooth, namely, \(\|\nabla f(\mathbf{x})-\nabla f(\mathbf{y})\| \le L\|\mathbf{x}-\mathbf{y}\|,\,\forall\,\mathbf{x},\mathbf{y}\in\mathbb{R}^n\).
Assumptions 1–3 are standard in stochastic optimization; see, e.g., [16], [28]. Assumption 3 implies the classical descent lemma: \(f(\mathbf{x})\le f(\mathbf{y})+\langle\nabla f(\mathbf{y}),\,\mathbf{x}-\mathbf{y}\rangle+\frac{L}{2}\|\mathbf{x}-\mathbf{y}\|_2^2,\, \forall\,\mathbf{x},\mathbf{y}\in\mathbb{R}^n\), see, for example, Lemma 1.2.3 in [29]. Many STORM-type methods adopt the stronger individual smoothness condition \(\|\nabla f(\mathbf{x};\xi)-\nabla f(\mathbf{y};\xi)\| \le L\|\mathbf{x}-\mathbf{y}\|\), \(\forall\,\mathbf{x},\mathbf{y}\in\mathbb{R}^n\), which is strictly stronger than the average smoothness condition in Assumption 3. In this paper, Lipschitz-free means that the algorithm does not use the smoothness constant \(L\) for parameter tuning, although the analysis still assumes that \(f\) is \(L\)-smooth.
Unless otherwise specified, vector operations are understood element-wise. For any \(\mathbf{x},\mathbf{y}\in\mathbb{R}^n\), the expressions \(\mathbf{x}+\mathbf{y}\), \(\mathbf{x}-\mathbf{y}\), \(\mathbf{x}\odot\mathbf{y}\), and \(\tfrac{\mathbf{x}}{\mathbf{y}}\) denote element-wise addition, subtraction, multiplication, and division, respectively. Additional notation and auxiliary lemmas are collected in Appendix 7.
In this section, we present our unified algorithmic framework, termed OptEMA (Exponential Moving Average with zero-noise Optimality), summarized in Algorithm 1. The central idea of OptEMA is to equip the standard EMA-based update rule with a fully adaptive closed-loop stepsize mechanism driven by the observed optimization trajectory.
To disentangle the roles of the first- and second-moment estimators, we introduce two complementary variants. The first variant, OptEMA-M, assigns adaptivity to the first-moment EMA coefficient while keeping the second-moment decay fixed. The second variant, OptEMA-V, instead assigns adaptivity to the second-moment EMA coefficient while keeping the first-moment decay fixed. These two variants provide symmetric yet distinct realizations of the same design principle.
None
Figure 1: No caption.
The goal of OptEMA is to construct a closed-loop adaptive stepsize mechanism while preserving the canonical exponential moving average structure used in Adam-type methods.
At iteration \(t\), the algorithm computes a stochastic gradient \(\mathbf{g}_t := \nabla f(\mathbf{x}_t;\xi_t)\) and updates two trajectory-dependent statistics: \[\begin{align} \textstyle\rho_t = \sqrt{\frac{1 + \frac{\tau}{t}\sum_{i=1}^t \| \mathbf{g}_i \|^2}{1 + \sum_{i=1}^t \| \mathbf{g}_i \|^2}}, \qquad \hat{g}_t = \max_{1\le i\le t} \|\mathbf{g}_i\|, \end{align}\] where \(\tau \in [0,1]\). We refer to \(\rho_t\) using the default parameter \(\tau=1\) as the Corrected AdaGrad-Norm stepsize, which is novel in this paper.
This dynamic schedule seamlessly bridges the stochastic and deterministic optimization regimes. By introducing the average of the historical squared gradient norms in the numerator, \(\rho_t\) preserves the monotonically decreasing, adaptive nature of AdaGrad-Norm while mitigating its tendency for overly rapid decay caused by historical accumulation. Specifically, this corrected formulation yields three critical advantages: Noise-adaptive suppression: It guarantees noise-adaptive suppression in high-noise settings (where \(\rho_t = \mathcal{O}(1/\sqrt{t})\)), yet stabilizes to a constant near stationary points when gradients vanish, ensuring zero-noise optimality. Robustness to Gradient Spikes: In the presence of occasional gradient spikes, the numerator partially offsets the impact, preventing a single large gradient from permanently suppressing subsequent stepsizes. Dimensional Consistency: The construction maintains matching dimensions between the numerator and the denominator, providing a unified foundation for subsequent noise-adaptive and complexity analyses.
These desirable, dimension-free properties are rigorously formalized in the following lemma, which establishes the strict bounds and monotonic descent of \(\rho_t\).
Lemma 1. (Proof in Appendix 8.1) Let \(S_t:=\sum_{i=1}^t \|\mathbf{g}_i\|^2\) and \(\hat{g}_t = \max_{1\le i\le t} \|\mathbf{g}_i\|\). For all \(t\geq 2\), we have: (a) \(\sqrt{\frac{\tau}{t-1}}\le \rho_{t-1}\le 1\). (b) \(1\le \tfrac{\rho_{t-1}}{\rho_{t}} \leq \sqrt{ 1 + {\hat{g}_{t}^2}/(1 + S_{t-1})}\). (c) \(\rho_{t}^2 \le \tfrac{1 + \hat{g}_{t}^2}{1 + \sum_{i=1}^t \|\mathbf{g}_i\|^2}\). (d) \((\rho_{t-1}-\rho_t)^2/\rho_t \le \tfrac{\hat{g}_{t}^3}{1 + \sum_{i=1}^t \|\mathbf{g}_i\|^2}\).
In summary, \(\rho_t\) captures the cumulative gradient magnitude along the optimization path, whereas \(\hat{g}_t\) records the largest gradient norm observed so far. Together, these quantities provide purely data-dependent signals for robustly controlling both the exponential moving average (EMA) coefficients and the effective stepsize.
The algorithm then maintains the standard first- and second-moment EMA estimates \[\textstyle\mathbf{m}_t = (1-\alpha_t)\mathbf{m}_{t-1} + \alpha_t \mathbf{g}_t, \qquad \mathbf{v}_t = (1-\beta_t)\mathbf{v}_{t-1} + \beta_t \mathbf{g}_t^2,\] which retain exactly the same structural form as in Adam-style optimizers. The essential departure from standard Adam lies in the fact that the coefficients \((\alpha_t,\beta_t)\) and the effective stepsize \(\gamma_t\) are no longer preset in an open-loop manner; instead, they are determined adaptively from the observed trajectory.
Within this framework, we study two complementary designs. One places adaptivity on the first-moment coefficient \(\alpha_t\), and the other places adaptivity on the second-moment coefficient \(\beta_t\). Both variants share the same EMA backbone and the same closed-loop philosophy, but they emphasize different aspects of moment estimation and stability control.
The first variant, OptEMA-M, introduces adaptivity through the first-moment coefficient \(\alpha_t\). Specifically, we set \[\textstyle\alpha_t = \rho_t, \qquad \beta_t = \beta \in (0,1), \qquad \gamma_t = \min\!\left( \frac{\alpha_t}{1+\mu\hat{g}_t^4},\, \left( 1 + \sum_{j=1}^t \frac{\|\mathbf{m}_j\|^2}{\alpha_j} \right)^{-1/2} \right).\]
Under this construction, the first-moment EMA coefficient decreases automatically with the accumulated gradient magnitude, whereas the second-moment estimator remains a standard EMA with fixed decay. As a result, the influence of newly observed gradients is gradually attenuated as the trajectory evolves, which leads to a progressively more stable momentum estimate.
From a theoretical viewpoint, adapting \(\alpha_t\) creates a stronger coupling between the momentum tracking error and the stepsize dynamics. For this reason, the closed-loop stepsize \(\gamma_t\) contains two complementary components: a stability term involving \(\hat{g}_t\), and an energy-control term involving the cumulative quantity \(\sum_{j=1}^t \|\mathbf{m}_j\|^2/\alpha_j\). This design is crucial for closing the Lyapunov-based analysis without invoking bounded-gradient assumptions.
The second variant, OptEMA-V, instead introduces adaptivity through the second-moment coefficient. More precisely, we choose \[\textstyle\alpha_t = \alpha \in (0,1), \qquad \beta_t = \rho_t, \qquad \gamma_t = \frac{1}{1+\mu\hat{g}_t^4} \left(1+\sum_{j=1}^t \|\mathbf{m}_j\|^2\right)^{-1/2}.\]
Under this scheme, the first-moment coefficient remains fixed, while the second-moment estimator adapts to the observed trajectory through both the cumulative gradient scale \(\rho_t\) and the maximal gradient magnitude \(\hat{g}_t\). Consequently, OptEMA-V places greater emphasis on adaptive variance estimation within the EMA framework.
The corresponding closed-loop stepsize \(\gamma_t\) is again fully trajectory-dependent. The factor \(\big(1+\sum_{j=1}^t \|\mathbf{m}_j\|^2\big)^{-1/2}\) modulates the effective stepsize according to the cumulative momentum energy, while the prefactor \((1+\mu\hat{g}_t^4)^{-1}\) provides additional safeguarding against large gradients. Together, these two components yield a fully adaptive update rule that does not require prior knowledge of any Lipschitz constant.
In this section, we establish the convergence guarantees of the proposed OptEMA algorithms.
Throughout this section, we define \(\mathbf{s}_t \triangleq \mathbf{m}_t-\nabla f(\mathbf{x}_t)\), and \(\hat{g}_t = \max_{i=1}^t \| \mathbf{g}_i \|\). We let \(T\geq 0\) to denote the total number of iterations. Denote \(\mathbb{G}_t := \sum_{i=1}^t \|\mathbf{g}_i\|^2\) and \(\mathbb{M}_t := \sum_{i=1}^t \|\mathbf{m}_i\|^2\). For brevity, we drop the subscript when \(t=T\), denoting \(\mathbb{G}:= \mathbb{G}_T\) and \(\mathbb{M}:= \mathbb{M}_T\).
In this section, we establish the theoretical convergence rate of the OptEMA-M algorithm.
The proof proceeds in three steps. We begin by establishing basic bounds on the internal EMA sequences, then control the gradient tracking error, and finally combine these ingredients with a one-step descent inequality to derive the global convergence rate.
We start with two elementary estimates that relate the momentum sequence \(\mathbf{m}_t\) to the stochastic gradients \(\mathbf{g}_t\) and control the second-moment estimator together with the adaptive EMA coefficient.
Lemma 2. (Proof in Appendix 9.1) Define \(\hat{g}_T:=\max_{i=1}^T \|\mathbf{g}_i\|\). For all \(T\geq 1\), we have: \(\sum_{t=1}^T \|\mathbf{m}_t\|^2 \le (2 + 2 \sqrt{\tau}\hat{g}_T) \sum_{t=1}^T \|\mathbf{g}_t\|^2 \leq 3(1+\sum_{t=1}^T \|\mathbf{g}_t\|^2)^{3/2}\).
Lemma 3. (Proof in Appendix 9.2) For all \(t\geq 1\), we have: \(\|\mathbf{v}_t\| \le \hat{g}_t^2\).
A central quantity in the analysis is the gradient tracking error \(\mathbf{s}_t := \mathbf{m}_t - \nabla f(\mathbf{x}_t)\), which measures the deviation of the first-moment estimator from the true gradient. The next lemma gives a recursive bound on its expected squared norm.
Lemma 4. (Proof in Appendix 9.3) Let \(\lambda:=\tfrac{\theta^2 L^2}{\varepsilon^2}\). For all \(t\geq 1\), we have \[\begin{align} \mathbb{E}[\|\mathbf{s}_t\|^2] ~~\le~~\mathbb{E}[\big(1-\tfrac{\alpha_t}{4}\big)\|\mathbf{s}_{t-1}\|^2 + B_t], \label{eq:lemma:bound:eee:1:new} \end{align}\qquad{(1)}\] where \(B_t:=\tfrac{3}{\alpha_{t}} \lambda \gamma_{t-1}^2\| \mathbf{m}_{t-1}\|^2 + \tfrac{ 11 (1 + \hat{g}_t)^3\|\mathbf{g}_t\|^2 }{ 1 + \sum_{i=1}^t \|\mathbf{g}_i\|^2 }\).
We next derive the basic descent relation for a single iteration. This inequality isolates the contribution of the true gradient from the errors induced by momentum tracking and adaptive scaling.
Lemma 5 (One-Step Descent Inequality). (Proof in Appendix 9.4) Define \(c_0:= \tfrac{\theta}{2}\), \(c_1:=\tfrac{\theta}{ 2\varepsilon^2}\), and \(c_2:=\tfrac{L\theta^2}{2\varepsilon^2}\). For all \(t\geq 1\), we have: \[\begin{align} \label{eq:OptEMA:M:suff:dec} \mathbb{E}[ f(\mathbf{x}_{t+1}) - f(\mathbf{x}_{t}) + \tfrac{c_0 \gamma_t }{1+\hat{g}_t}\|\nabla f(\mathbf{x}_t)\|_2^2 ]\leq \mathbb{E}[c_1 \gamma_t (1+\hat{g}_t)\| \mathbf{s}_t \|^2 + c_2 \gamma_t^2 \|\mathbf{m}_{t}\|_2^2]. \end{align}\qquad{(2)}\]
To telescope ?? over \(t=1,\dots,T\), it remains to control the cumulative error terms on the right-hand side. We first bound the weighted tracking error, and then establish logarithmic growth bounds for the objective values and stochastic gradients.
Lemma 6. (Proof in Appendix 9.5) It holds that \(\mathbb{E}\left[\sum_{t=1}^T \gamma_t (1+\hat{g}_t) \|\mathbf{s}_t\|^2\right]\leq C_w \ln ( e + \sum_{t=1}^T \|\mathbf{g}_t\|^2 )\), where \(C_w := \tfrac{1}{\mu} ( 32\|\mathbf{s}_0\|^2 + 576 \lambda + 704)\) is a constant.
Lemma 7 (Boundedness of Objectives and Gradients). (Proof in Appendix 9.6) Let \(\chi:=4 L \big( \hat{f}_1 + c_1 C_w + \frac{48 c_2}{\mu} \big) + 4\sigma^2\), \(C_f:=\tfrac{(1+\chi)^3}{4L}\) and \(C_g:=4 \sigma^2 + 4 L C_f\). We have: \(\mathbb{E}[f(\mathbf{x}_{t})] - f_* \leq C_f \ln(e + t)\), and \(\mathbb{E}[\|\nabla f(\mathbf{x}_t;\xi_t)\|^2]\leq C_g \ln(e+t)\).
Using the above logarithmic bounds, we can further control the cumulative tracking error and the cumulative true gradient norm in terms of the path-dependent quantities \(\mathbb{G}:=\sum_{t=1}^T \|\mathbf{g}_t\|^2\) and \(\mathbb{M}:=\sum_{t=1}^T \|\mathbf{m}_t\|^2\).
Lemma 8. (Proof in Appendix 9.7) Let \(C_s:=88 \left( \lambda + \lambda C_g + 1 + C_g + C_f +\sigma^2 \right)\). We have \(\mathbb{E}[\sum_{t=1}^T \|\mathbf{s}_t\|^2 ]\leq C_s \sqrt{1 + \mathbb{G}} \cdot \ln^2(e+T)\).
Lemma 9. (Proof in Appendix 9.8) We define \(\iota := 1+C_g\) and \(C_o:= \tfrac{\iota^{5/2}}{c_0} (2 C_f + 2c_2 + c_1 C_s)\). We have: \[\begin{align} \textstyle\mathbb{E}[ \sum_{t=1}^T \|\nabla f(\mathbf{x}_t)\|_2^2 ] \leq C_o\cdot \mathbb{E}[ \ln^{7/2}(e+T) \sqrt{1 + \mathbb{G}} + \ln^{3/2}(e+T) \sqrt[4]{1+\mathbb{G}} \sqrt{\mathbb{M}} ]. \end{align}\]
We are now ready to state the main convergence guarantee for OptEMA-M, obtained by combining the preceding bounds and taking expectation over the full trajectory.
Theorem 1. (Proof in Appendix 9.9) We have the following results: \[\begin{align} \textstyle\mathbb{E}[\tfrac{1}{T}\sum_{t=1}^T \| \nabla f(\mathbf{x}_{t})\|] \leq \mathcal{O}\left( \tfrac{ \ln^{7/2}(e+T) }{T^{1/2}} + \sigma^{1/2} \cdot \tfrac{ \ln^{7/4}(e+T) }{T^{1/4}} \right). \end{align}\] Consequently, if \(R \sim \mathrm{Unif}\{1,2,\dots,T\}\) is independent of the algorithmic randomness and \(\mathbf{x}_{\rm out}:=\mathbf{x}_R\), then \(\textstyle \mathbb{E}\!\left[\|\nabla f(\mathbf{x}_{\rm out})\|\right] \le \mathcal{O}\!\left( \frac{\ln^{7/2}(e+T)}{T^{1/2}} + \sigma^{1/2}\frac{\ln^{7/4}(e+T)}{T^{1/4}} \right)\).
Theorem 1 shows that OptEMA-M attains the rate \(\widetilde{\mathcal{O}}(T^{-1/2}+\sigma^{1/2}T^{-1/4})\) for the averaged gradient norm. In particular, this yields the canonical \(\widetilde{\mathcal{O}}(T^{-1/4})\) stochastic rate and recovers the nearly optimal deterministic rate \(\widetilde{\mathcal{O}}(T^{-1/2})\) when \(\sigma=0\). The bound separates cleanly into a deterministic optimization term and a stochastic variance-dependent term. The additional polylogarithmic factors arise from the fully adaptive and horizon-free nature of the algorithm, which requires neither prior knowledge of the total iteration budget \(T\) nor the noise level \(\sigma^2\).
In this subsection, we establish the theoretical convergence guarantees for the OptEMA-V algorithm.
As in the analysis of OptEMA-M, we first control the internal algorithmic states, then decouple the historical terms induced by the EMA recursion, and finally derive the global convergence rate. We begin with two basic bounds on the momentum and second-moment sequences.
Lemma 10. (Proof in Appendix 10.1) For any integer \(T\ge 1\), assume that \(\alpha_t=\alpha \in (0,1)\), it holds that \(\sum_{t=1}^T \|\mathbf{m}_t\|_2^2 \le\sum_{t=1}^T \|\mathbf{g}_t\|_2^2\).
Lemma 11. (Proof in Appendix 10.2) For all \(t\geq 1\), we have: \(\|\mathbf{v}_t\| \le \hat{g}_t^2\).
We next establish a one-step descent inequality. Unlike OptEMA-M, the analysis here involves a nonlocal historical term generated by the EMA structure, so the descent at iteration \(t\) depends on the entire past trajectory.
Lemma 12 (One-Step Descent Inequality). (Proof in Appendix 10.3) Define \(c_1:=\tfrac{\theta^2 L}{\varepsilon^2}\), \(c_2:= \frac{2 \theta}{ \varepsilon^4 }\), \(c_3:=\tfrac{L\theta^2}{\varepsilon^2}\). For all \(t\geq 1\), we have: \[\begin{align} \label{eq:OptEMA:V:suff:dec} \textstyle\mathbb{E}[ f(\mathbf{x}_{t+1}) - f(\mathbf{x}_{t}) ] \leq \mathbb{E}[ c_3 \gamma_t^2 \|\mathbf{m}_t\|^2 + \gamma_t \sum_{j=1}^{t} \left( \prod_{k=j+1}^t (1-\alpha_k) \right) \left(E_j - D_j\right)]. \end{align}\qquad{(3)}\] Here, \(E_t:=c_1\gamma_{t-1} \|\mathbf{m}_{t-1}\|^2 + c_2 \frac{\rho_t }{ \alpha_t } \|\mathbf{m}_t\|^2 \cdot (1 + \hat{g}_t)^3\), and \(D_t = \tfrac{\theta \alpha_t}{2(\varepsilon + \hat{g}_t)} \|\nabla f(\mathbf{x}_t)\|^2\).
The historical summation in ?? couples the error term \(E_j\) and the descent term \(D_j\) across time. To telescope this inequality over all iterations, we need to decouple such temporal dependence. The next lemma provides precisely this mechanism by controlling accumulated EMA-weighted sums.
Lemma 13 (EMA Accumulation Bound). **(Proof in Appendix 10.4)* Assume \(A_j\geq 0\) for all \(j \geq 1\). If both \(\alpha_t\in(0,1)\) and \(\gamma_t\in(0,1]\) are decreasing sequences, we have: \[\begin{align} \sum_{t=1}^T \gamma_t A_t \leq \sum_{t=1}^T \gamma_t \sum_{j=1}^{t} \left( \prod_{k=j+1}^t (1-\alpha_k) \right) A_j \leq \frac{1}{\alpha_T} \sum_{t=1}^T \gamma_t A_t. \nonumber \end{align}\]*
Before concluding the proof, we also need pathwise logarithmic bounds on the objective values and stochastic gradients.
Lemma 14 (Boundedness of Objectives and Gradients). (Proof in Appendix 10.5) Let \(\chi:= 4 L \big( \hat{f}_1 + c_3 + \tfrac{c_1 + 8 c_2}{\alpha^2 \mu } \big) + 4\sigma^2\), \(C_f:= \frac{(1+\chi)^3 }{4 L}\), and \(C_g:=4\sigma^2 + 4LC_f\). For all \(t\geq 1\), we have \(\mathbb{E}[f(\mathbf{x}_{t}) - f_*] \leq C_f \ln(e + t)\), and \(\mathbb{E}[\|\mathbf{g}_t\|^2]\leq C_g \ln(e+t)\).
Combining Lemma 13 with the above pathwise bounds allows us to telescope the descent inequality and control the cumulative squared norm of the true gradients.
Lemma 15. (Proof in Appendix 10.6) Assume that \(\alpha_t = \alpha \in (0,1)\). We define \(\iota:=1+C_g\), and \(C_o:=\frac{2 \iota}{ \theta \alpha} \cdot \big( 2 \iota^2 \cdot \frac{c_1 + c_2}{\alpha^2} + C_f \iota^2 + 2c_3 \big)\). We have: \[\begin{align} \textstyle\mathbb{E}[\sum_{t=1}^T \|\nabla f(\mathbf{x}_t)\|^2] \leq C_o \ln^{5/2}(e+T) \sqrt{1 + \mathbb{G}} . \end{align}\]
Applying Jensen’s inequality to the preceding estimate yields the main convergence result for OptEMA-V.
Theorem 2. (Proof in Appendix 10.7) Assume that \(\alpha_t = \alpha \in (0,1)\). We have the following results: \[\begin{align} \textstyle\mathbb{E}[\tfrac{1}{T}\sum_{t=1}^T \| \nabla f(\mathbf{x}_{t})\|] \leq \mathcal{O}\left( \tfrac{ \ln^{5/2}(e+T) }{T^{1/2}} + \sigma^{1/2} \cdot \tfrac{ \ln^{5/4}(e+T) }{T^{1/4}} \right). \end{align}\] Consequently, if \(R \sim \mathrm{Unif}\{1,2,\dots,T\}\) is independent of the algorithmic randomness and \(\mathbf{x}_{\rm out}:=\mathbf{x}_R\), then \(\textstyle \mathbb{E}\!\left[\|\nabla f(\mathbf{x}_{\rm out})\|\right] \le \mathcal{O}\left( \tfrac{ \ln^{5/2}(e+T) }{T^{1/2}} + \sigma^{1/2} \cdot \tfrac{ \ln^{5/4}(e+T) }{T^{1/4}} \right)\).
Theorem 2 shows that OptEMA-V also attains the canonical noise-adaptive rate \(\widetilde{\mathcal{O}}(T^{-1/2}+\sigma^{1/2}T^{-1/4})\), and hence matches the standard stochastic nonconvex complexity up to polylogarithmic factors. Compared with OptEMA-M, the proof of OptEMA-V involves a more delicate treatment of the second-moment recursion, which is reflected in a different polylogarithmic dependence. Nevertheless, the resulting guarantee remains fully adaptive and horizon-free.
We proposed OptEMA, a family of adaptive exponential moving average methods for mini-batch stochastic nonconvex optimization. The proposed framework employs fully closed-loop and Lipschitz-free stepsize rules, and establishes noise-adaptive convergence guarantees for standard EMA-based updates without relying on bounded gradients, bounded objective gaps, or Hessian-type assumptions. Both variants achieve the rate \(\widetilde{\mathcal{O}}(T^{-1/2}+\sigma^{1/2}T^{-1/4})\) in terms of the averaged gradient norm, where \(\sigma\) denotes the noise level. In particular, in the zero-noise regime \(\sigma=0\), this reduces to the nearly optimal deterministic rate \(\widetilde{\mathcal{O}}(T^{-1/2})\). These results show that fully adaptive EMA-type methods can attain strong noise-adaptive guarantees under standard smooth stochastic assumptions without modifying the basic EMA update structure.
Appendix
The appendix is structured as follows:
introduces the notation and collects several supporting lemmas.
presents the proofs of the results in Section 4.
presents the proofs of the results in Section 5.1.
presents the proofs of the results in Section 5.2.
Throughout the paper, we use the following notation. Bold lowercase letters denote vectors, while uppercase letters denote real-valued matrices.
\([n]\): The set \(\{1,2,...,n\}\).
\(\|\mathbf{x}\|\): Euclidean norm, defined as \(\|\mathbf{x}\|=\|\mathbf{x}\|_2 = \sqrt{\langle\mathbf{x},\mathbf{x}\rangle}\).
\(\langle\mathbf{a},\mathbf{b}\rangle\) : Standard inner product, given by \(\langle\mathbf{a},\mathbf{b}\rangle=\sum_{i}{\mathbf{a}_{i}\mathbf{b}_{i}}\).
\(\mathbf{a}\leq \alpha\): For \(\mathbf{a}\in\mathbb{R}^n\) and scalar \(\alpha\in\mathbb{R}\), this means \(\mathbf{a}_i\leq \alpha\) for all \(i\in[n]\).
\(\mathbb{E}[v]\): Expectation of the random variable \(v\).
\(\{A_i\}_{i=1}^{\infty}\), \(\{B_i\}_{i=1}^{\infty}\): sequences indexed by non-negative integers.
We collect several useful lemmas that will be used in the subsequent analysis. These results are independent of the specific context of the paper.
Lemma 16. Let \(b_1,b_2,\ldots,b_T \ge 0\), and let \(p\in(0,1)\). Then the following inequalities hold:
\(\sum_{t=1}^T \frac{b_t}{ 1 + \sum_{i=1}^t b_i } \leq \ln\left(1+ \sum_{t=1}^T b_t \right)\).
\(\sum_{t=1}^T \frac{b_t}{\left( 1 + \sum_{i=1}^{t} b_i \right)^{p}} \leq \frac{1}{1-p} \cdot \left(1 + \sum_{t=1}^T b_t \right)^{1-p}\).
Lemma 17. Let \(\{A_t\}_{t=1}^{T}\) and \(\{B_t\}_{t=1}^{T+1}\) be two nonnegative sequences, with \(\{A_t\}_{t=1}^T\) being non-decreasing. Then we have: \[\textstyle\sum_{t=1}^T A_t (B_t - B_{t+1}) \leq A_T \Big(\max_{1 \leq t \leq T} B_t\Big).\nonumber\]
Proof. Using summation by parts and the nonnegativity of \(A_T\) and \(B_{T+1}\), we have: \[\begin{align} \textstyle\sum_{t=1}^T A_t (B_t - B_{t+1}) &=\textstyle A_1 B_1 - A_T B_{T+1} + \sum_{t=2}^T (A_t - A_{t-1}) B_t \\ &\leq \textstyle A_1 B_1 + \sum_{t=2}^T (A_t - A_{t-1}) B_t. \end{align}\] Since \(\{A_t\}_{t=1}^T\) is non-decreasing, we know \(A_t - A_{t-1} \geq 0\) for \(t \geq 2\). Bounding each \(B_t\) by its maximum yields: \[\begin{align} \textstyle\sum_{t=1}^T A_t (B_t - B_{t+1}) &\leq \textstyle A_1 \Big(\max_{1 \leq j \leq T} B_j\Big) + \Big(\max_{1 \leq j \leq T} B_j\Big) \sum_{t=2}^T (A_t - A_{t-1}) \\ &=\textstyle A_T \Big(\max_{1 \leq t \leq T} B_t\Big). \end{align}\] ◻
Lemma 18. Assume \(\chi>0\), and the non-negative sequence \(\{A_t\}_{t=1}^{\infty}\) satisfying \[A_{t}\leq \chi \ln\left( e + (\max_{i=1}^t A_i)\cdot t \right).\] Then, for all \(t\geq 1\), we have: \[\begin{align} A_t\leq (1+\chi)^3 \ln(e+t).\nonumber \end{align}\]
**Proof.* For all \(a,b\geq 0\) with \(x \le a+b\ln (1 + x )\), we derive the following results: \[\begin{align} \label{eq:abab} x&\le& a+b\ln (1 + x ) ~~\overset{\text{\ding{\numexpr 1+171\relax}}}{\leq }~~ a+b\left(\ln(1+b)+\frac{x - b}{1+b}\right) ~~\leq ~~ a+b\ln(1+b) +\frac{bx}{1+b} \nonumber\\ &\overset{}{\leq }& \left\{ a+b\ln(1+b)\right\} \cdot (1+b) ~~\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq }~~ \left( a+b^2\right) \left(1+b \right),~~~ \end{align}\tag{2}\] where step uses \(\ln(1+x)\le \ln(1+b)+\frac{x-b}{1+b}\) for all \(x,b\ge 0\), which can be derived by the concavity of the function \(\phi(t) \triangleq \ln(1+t)\); step uses \(\ln(1+x)\leq x\) for all \(x\geq 0\).*
For all \(t\geq 1\), we have: \[\begin{align} M_t &\triangleq& \textstyle\textstyle\max_{1\le i\le t}A_i~~\overset{\text{\ding{\numexpr 1+171\relax}}}{\leq }~~ \chi \ln\left( e + (\max_{i=1}^t A_i)\cdot t \right) \nonumber\\ &=& \textstyle\chi \ln\left( e + M_t t \right) ~~\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq }~~ \underbrace{\textstyle\chi \ln( e + t )}_{\triangleq a} + \underbrace{\chi}_{\triangleq b} \ln ( 1+ \underbrace{M_t}_{\triangleq x}) \nonumber\\ &\overset{\text{\ding{\numexpr 3+171\relax}}}{\leq }& \textstyle(a+b^2) (1+b) ~~\overset{}{=}~~ ( \chi \ln( e + t ) + \chi^2) (1+\chi) ~~\overset{\text{\ding{\numexpr 4+171\relax}}}{\leq }~~ (1+\chi)^3 \ln( e+ t ), \nonumber \end{align}\] where step uses the condition of this lemma; step uses \(\ln(e+M_t t) \leq \ln( (e+t) (1+M_t)) = \ln(e+t) + \ln(1+M_t)\); step uses Inequality (2 ); step uses \(\chi + \chi^2\leq (1+\chi)^2\). ◻
Lemma 19. For all \(\mu\in (0,1]\), \(x\geq 0\) and \(c\geq 1\), it holds that \(\tfrac{\mu (1+x)^c}{1 + \mu x^c} \leq 2^{c-1}\).
**Proof.* Let \(f(x) = \frac{\mu(1+x)^c}{1+\mu x^c}\). The derivative with respect to \(x\) is given by: \[\textstyle f'(x) = \frac{c\mu(1+x)^{c-1}(1-\mu x^{c-1})}{(1+\mu x^c)^2}.\] Setting \(f'(x) = 0\) yields a unique critical point at \(x^* = \mu^{-\frac{1}{c-1}}\) for \(x \geq 0\). Since \(f'(x) > 0\) for \(x \in [0, x^*)\) and \(f'(x) < 0\) for \(x > x^*\), the function \(f(x)\) achieves its global maximum at \(x^*\). Evaluating \(f(x)\) at this maximum, we obtain: \[\textstyle f(x^*) = \frac{\mu(1+\mu^{-\frac{1}{c-1}})^c}{1+\mu(\mu^{-\frac{1}{c-1}})^c} = \frac{\mu(1+\mu^{-\frac{1}{c-1}})^c}{1+\mu^{-\frac{1}{c-1}}} = \mu\left(1+\mu^{-\frac{1}{c-1}}\right)^{c-1} = \left(\mu^{\frac{1}{c-1}} + 1\right)^{c-1}.\]*
Given \(\mu \in (0, 1]\) and \(c \geq 1\), we have \(\mu^{\frac{1}{c-1}} \leq 1\), leading to: \(f(x) \leq f(x^*) \leq (1+1)^{c-1} = 2^{c-1}\). ◻
Lemma 20. For any \(L\)-smooth function \(f(\cdot)\), assume there exists a constant \(f_* > -\infty\) such that \(f(\mathbf{x}) \ge f_*\) for all \(\mathbf{x}\in \mathbb{R}^{n}\). Then, for any \(\mathbf{x}\), we have: \[\|\nabla f(\mathbf{x})\|^2 \leq 2L (f(\mathbf{x}) - f_*).\nonumber\]
**Proof.* By the standard descent lemma for an \(L\)-smooth function \(f(\cdot)\), we have \[\label{eq:smoothness} \textstyle f(\mathbf{y}) \le f(\mathbf{x}) + \langle \nabla f(\mathbf{x}), \mathbf{y}-\mathbf{x}\rangle + \frac{L}{2}\|\mathbf{x}-\mathbf{y}\|^2.\tag{3}\] Choosing \(\mathbf{y}= \mathbf{x}- \frac{1}{L}\nabla f(\mathbf{x})\) and substituting this into Inequality (3 ), we obtain: \[\begin{align} \textstyle f\big(\mathbf{x}- \frac{1}{L}\nabla f(\mathbf{x})\big) ~~\le~~ \textstyle f(\mathbf{x}) - \frac{1}{L}\|\nabla f(\mathbf{x})\|^2 + \frac{L}{2}\left\| \frac{1}{L}\nabla f(\mathbf{x}) \right\|^2 ~~=~~ f(\mathbf{x}) - \frac{1}{2L}\|\nabla f(\mathbf{x})\|^2.\nonumber \end{align}\] Rearranging the terms and using the assumption that \(f(\cdot) \ge f_*\), we have: \[\textstyle\frac{1}{2L}\|\nabla f(\mathbf{x})\|^2 \,\,\le\,\, f(\mathbf{x}) - f\left(\mathbf{x}- \frac{1}{L}\nabla f(\mathbf{x})\right) \,\,\le\,\, f(\mathbf{x}) - f_*.\nonumber\] Multiplying both sides by \(2L\) completes the proof. ◻*
Proof. Define \(S_t=\sum_{i=1}^t \|\mathbf{g}_i\|^2\) and \(\hat{g}_t = \max_{1\le i\le t} \|\mathbf{g}_i\|\).
Define \(\rho_t := \sqrt{\frac{1 + \frac{\tau}{t}\sum_{i=1}^t \| \mathbf{g}_i \|^2}{1 + \sum_{i=1}^t \| \mathbf{g}_i \|^2}}\), where \(\tau \in [0,1]\).
For any \(x\geq 0\), we let \(\phi_t(x):=\frac{1+\frac{\tau}{t}x}{1+x}\).
For all \(t\geq 1\), we derive: \[\begin{align} \textstyle\rho_t^2 - \frac{\tau}{t} \,\,= \,\,\frac{1 + \frac{\tau}{t} S_t }{1 + S_t } - \frac{\tau}{t} \,\,=\,\, \frac{1-\tau/t}{1+S_t} \ge 0.\nonumber \end{align}\] where the inequality uses \(t \ge 1\) and \(\tau \in [0,1]\). This leads to \(\rho_t \ge \sqrt{\frac{\tau}{t}}\). Additionally, we trivially have \(1+\frac{\tau}{t}S_t \le 1+S_t\), which yields \(\rho_t \le 1\). Shifting the index to \(t-1\) yields \(\sqrt{\frac{\tau}{t-1}} \le \rho_{t-1}\leq 1\).
We now show \(\rho_t \le \rho_{t-1}\) for \(t \ge 2\). We obtain \[\begin{align} \rho_t^2 \,\,\overset{\text{\ding{\numexpr 1+171\relax}}}{=} \,\, \phi_t(S_t) \,\,\overset{\text{\ding{\numexpr 2+171\relax}}}{\le} \,\,\phi_t(S_{t-1}) \,\,\overset{\text{\ding{\numexpr 3+171\relax}}}{\le}\,\, \phi_{t-1}(S_{t-1}) \,\,\overset{\text{\ding{\numexpr 4+171\relax}}}{=}\,\, \rho_{t-1}^2,\nonumber \end{align}\] where step and step use the definition of \(\phi_t(x)\); step uses \(S_t \ge S_{t-1}\), and the fact that \(\phi_t(\cdot)\) is a non-increasing function since \(\phi_t'(x) = \frac{\tau/t - 1}{(1+x)^2} \le 0\); step uses \(\frac{\tau}{t} \le \frac{\tau}{t-1}\). Thus, \(\rho_t \le \rho_{t-1}\).
For all \(t \ge 2\), we derive: \[\begin{align} \textstyle\rho_{t-1}^2 - \rho_t^2 &\overset{\text{\ding{\numexpr 1+171\relax}}}{=}& \textstyle\frac{1+\frac{\tau}{t-1}S_{t-1}}{1+S_{t-1}} - \frac{1+\frac{\tau}{t}S_t}{1+S_t} ~~\overset{}{=}~~ \textstyle\big( \frac{1+\frac{\tau}{t-1}S_{t-1}}{1+S_{t-1}} - \frac{1+\frac{\tau}{t}S_{t-1}}{1+S_{t-1}} \big) + \big( \frac{1+\frac{\tau}{t}S_{t-1}}{1+S_{t-1}} - \frac{1+\frac{\tau}{t}S_t}{1+S_t} \big) \nonumber\\ &\overset{\text{\ding{\numexpr 2+171\relax}}}{=}& \textstyle\frac{\tau S_{t-1}}{t(t-1)(1+S_{t-1})} + \frac{(t-\tau)\|\mathbf{g}_t\|^2}{t(1+S_{t-1})(1+S_t)}~~\overset{\text{\ding{\numexpr 3+171\relax}}}{\le}~~ \textstyle\frac{\tau \hat{g}_t^2}{t(1+S_{t-1})} + \frac{(t-\tau)\hat{g}_t^2}{t(1+S_{t-1})(1+S_t)} \nonumber\\ &\overset{}{=}& \textstyle\frac{\hat{g}_t^2}{1+S_{t-1}} \left( \frac{\tau}{t} + \frac{t-\tau}{t(1+S_t)} \right) ~~\overset{}{=} ~~\textstyle\frac{\hat{g}_t^2}{1+S_{t-1}} \left( \frac{\tau(1+S_t) + t-\tau}{t(1+S_t)} \right) ~~\overset{\text{\ding{\numexpr 4+171\relax}}}{=}~~ \textstyle\frac{\hat{g}_t^2}{1+S_{t-1}} \rho_t^2, \nonumber \end{align}\] where step uses the definition of \(\rho_t^2\); step uses \(\frac{\tau}{t-1} - \frac{\tau}{t} = \frac{\tau}{t(t-1)}\), and \(S_t = S_{t-1} + \|\mathbf{g}_t\|^2\); step uses the average gradient bound \(\frac{S_{t-1}}{t-1} \le \hat{g}_{t-1}^2 \le \hat{g}_t^2\), and the current gradient bound \(\|\mathbf{g}_t\|^2 \le \hat{g}_t^2\); step uses the definition of \(\rho_t\). Dividing both sides by \(\rho_t^2\) and rearranging the terms yields \(\tfrac{\rho_{t-1}^2}{\rho_t^2} \le 1 + \tfrac{\hat{g}_t^2}{1+S_{t-1}}\). Taking the square root gives \[\begin{align} \textstyle\tfrac{\rho_{t-1}}{\rho_t} \le \sqrt{1 + \tfrac{\hat{g}_t^2}{1+S_{t-1}}}. \label{eq:bound:ratio} \end{align}\tag{4}\]
We now prove \(\rho_t^2 \le \frac{1+\hat{g}_t^2}{1+S_t}\). For all \(t\ge 2\), we derive \[\begin{align} \textstyle\rho_t^2 ~~\overset{\text{\ding{\numexpr 1+171\relax}}}{=}~~ \tfrac{1+\frac{\tau}{t}S_t}{1+S_t} ~~\overset{\text{\ding{\numexpr 2+171\relax}}}{\le}~~ \tfrac{1+\frac{1}{t}S_t}{1+S_t} ~~\overset{\text{\ding{\numexpr 3+171\relax}}}{\le}~~ \tfrac{1+\hat{g}_t^2}{1+S_t},\nonumber \end{align}\] where step uses the definition of \(\rho_t\); step uses \(\tau\in[0,1]\); step uses \(\frac{S_t}{t}=\frac{1}{t}\sum_{i=1}^t \|g_i\|^2 \le \hat{g}_t^2\).
We now bound the variation term \(\frac{(\rho_{t-1}-\rho_t)^2}{\rho_t}\) using the following inequalities: \[\begin{align} \textstyle\frac{(\rho_{t-1}-\rho_t)^2}{\rho_t} &\overset{}{=}& \textstyle\rho_t ( \frac{\rho_{t-1}}{\rho_t} - 1 )^2 ~~\overset{\text{\ding{\numexpr 1+171\relax}}}{\le}~~ \textstyle\frac{ ( \frac{\rho_{t-1}}{\rho_t} - 1 )^2}{ \rho_{t-1}/\rho_t} ~~\overset{\text{\ding{\numexpr 2+171\relax}}}{\le}~~\frac{ ( \sqrt{1 + {\hat{g}_t^2}/{(1+S_{t-1})}} - 1 )^2}{ \sqrt{1 + {\hat{g}_t^2}/{(1+S_{t-1})}} } \nonumber\\ &\overset{\text{\ding{\numexpr 3+171\relax}}}{\leq}& \textstyle\frac{ ( {\hat{g}_t^2} / ({1+S_{t-1}} ))^{3/2}}{1 + {\hat{g}_t^2}/(1+S_{t-1})} ~~\overset{}{=}~~ \textstyle\frac{\hat{g}_t^3}{\sqrt{1+S_{t-1}} \left( 1+S_{t-1}+\hat{g}_t^2 \right)} ~~\overset{\text{\ding{\numexpr 4+171\relax}}}{\le}~~ \textstyle\frac{\hat{g}_t^3}{1+S_{t-1}+\|\mathbf{g}_t\|^2} ~~\overset{\text{\ding{\numexpr 5+171\relax}}}{=}~~ \textstyle\frac{\hat{g}_t^3}{1+S_t}, \nonumber \end{align}\] where step uses \(\rho_{t-1} \le 1\); step uses the fact that the function \(h(x)=\tfrac{(x-1)^2}{x}\) is an increasing function for all \(x\geq 1\) with \(x=\tfrac{\rho_{t-1}}{\rho_t}\), and the upper bound of \(\tfrac{\rho_{t-1}}{\rho_t}\) in Inequality (4 ); step uses \(\tfrac{(\sqrt{y+1}-1)^2}{\sqrt{1+y}} \leq \tfrac{y^2}{\sqrt{1+y} (\sqrt{1+y}+1)^2} \leq \tfrac{y^2}{\sqrt{1+y} \sqrt{ y(1+y) }} \leq \tfrac{y^{3/2}}{1+y}\) for all \(y=\frac{\hat{g}_t^2}{1+S_{t-1}}\); step uses \(\hat{g}_t^2 \ge \|\mathbf{g}_t\|^2\); step uses \(S_t = S_{t-1} + \|\mathbf{g}_t\|^2\). ◻
Proof. Let \(\mathbb{G}_t := \sum_{i=1}^t \|\mathbf{g}_i\|^2\), and \(M := \hat{g}_T^2\).
By the convexity of the squared norm \(\|\cdot\|^2\), the EMA update \(\mathbf{m}_t = (1-\alpha_t) \mathbf{m}_{t-1} + \alpha_t \mathbf{g}_t\) implies \(\|\mathbf{m}_t\|^2 \leq (1-\alpha_t) \|\mathbf{m}_{t-1}\|^2 + \alpha_t \|\mathbf{g}_t\|^2\). Summing this recursion over \(t=1,\dots,T\) with \(\mathbf{m}_0 = \mathbf{0}\) yields \[\begin{align} && \textstyle\sum_{t=1}^T \alpha_t \|\mathbf{g}_t\|^2 ~~\geq ~~ \textstyle\big(\sum_{t=1}^T \|\mathbf{m}_t\|^2\big) - \big( \sum_{t=1}^{T} (1-\alpha_{t}) \|\mathbf{m}_{t-1}\|^2 \big) \nonumber\\ &\overset{\text{\ding{\numexpr 1+171\relax}}}{=}&\textstyle\|\mathbf{m}_T\|^2 + \sum_{t=1}^{T-1} \alpha_{t+1} \|\mathbf{m}_{t}\|^2 ~~\overset{\text{\ding{\numexpr 2+171\relax}}}{\geq} ~~\textstyle\|\mathbf{m}_T\|^2 + \alpha_T \sum_{t=1}^{T-1} \|\mathbf{m}_{t}\|^2 ~~\geq ~~ \alpha_T \sum_{t=1}^T \|\mathbf{m}_t\|^2,\nonumber \end{align}\] where step uses \(\mathbf{m}_0=\mathbf{0}\); step uses the monotonic non-increasing property of \(\alpha_t\) (i.e., \(\alpha_{t+1} \le \alpha_t\)) and \(\alpha_T \in (0,1]\). This leads to: \(\sum_{t=1}^T \|\mathbf{m}_t\|^2 \le \frac{1}{\alpha_T} \sum_{t=1}^T \alpha_t \|\mathbf{g}_t\|^2\).
We further derive: \[\begin{align} &&\textstyle\sum_{t=1}^T \alpha_t \|\mathbf{g}_t\|^2 ~~\overset{\text{\ding{\numexpr 1+171\relax}}}{=}~~ \textstyle\sum_{t=1}^T \sqrt{\frac{1+\frac{\tau}{t}\mathbb{G}_t}{1+\mathbb{G}_t}} \|\mathbf{g}_t\|^2 ~~\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq}~~\sqrt{1+\tau M} \sum_{t=1}^T \frac{\|\mathbf{g}_t\|^2}{\sqrt{1+\mathbb{G}_t}} \nonumber\\ &\overset{\text{\ding{\numexpr 3+171\relax}}}{\leq}& \textstyle\sqrt{1+\tau M} \sum_{t=1}^T 2(\sqrt{1+\mathbb{G}_t}-\sqrt{1+\mathbb{G}_{t-1}}) ~~= ~~2\sqrt{1+\tau M} (\sqrt{1+\mathbb{G}_T}-1).\nonumber \end{align}\] where step uses the definition of \(\alpha_t\); step uses \(1+\frac{\tau}{t}\mathbb{G}_t \le 1+\tau M\); step uses the standard integral bound \(\frac{\|\mathbf{g}_t\|^2}{\sqrt{1+\mathbb{G}_t}} \le \int_{\mathbb{G}_{t-1}}^{\mathbb{G}_t} \frac{dx}{\sqrt{1+x}} = 2(\sqrt{1+\mathbb{G}_t}-\sqrt{1+\mathbb{G}_{t-1}})\).
Combining the above bounds, we obtain \[\begin{align} && \textstyle\sum_{t=1}^T \|\mathbf{m}_t\|^2 ~~\le~~ \frac{1}{\alpha_T} \sum_{t=1}^T \alpha_t \|\mathbf{g}_t\|^2 ~~\overset{\text{\ding{\numexpr 1+171\relax}}}{\leq}~~ 2\sqrt{1+\tau M} \sqrt{1+\mathbb{G}_T}(\sqrt{1+\mathbb{G}_T}-1) \nonumber\\ &=& 2\sqrt{1+\tau M} (1+\mathbb{G}_T - \sqrt{1+\mathbb{G}_T}) ~~\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq}~~ 2(1+\sqrt{\tau}\hat{g}_T) \mathbb{G}_T, \nonumber \end{align}\] where step uses \(\frac{1}{\alpha_T} = \sqrt{\frac{1+\mathbb{G}_T}{1+\frac{\tau}{T}\mathbb{G}_T}} \le \sqrt{1+\mathbb{G}_T}\) since \(1+\frac{\tau}{T}\mathbb{G}_T \ge 1\); step uses \(\sqrt{1+\mathbb{G}_T} \ge 1\) and \(\sqrt{1+\tau M} = \sqrt{1+\tau \hat{g}_T^2} \le 1 + \sqrt{\tau}\hat{g}_T\).
Furthermore, we derive: \[\begin{align} 2(1+\sqrt{\tau}\hat{g}_T) \mathbb{G}_T \overset{\text{\ding{\numexpr 2+171\relax}}}{\leq} 2(1+\sqrt{\mathbb{G}_T}) \mathbb{G}_T \leq 3 (1+\mathbb{G}_T)^{3/2},\nonumber \end{align}\] where step uses \(\tau\in[0,1]\) and \(\hat{g}_T\leq \sqrt{\mathbb{G}_T}\); step uses the fact that \(\tfrac{2 (1 + \sqrt{x}) x}{(1+x)^{3/2}}\leq 3\) for all \(x\geq 0\) with \(x=\mathbb{G}_T\). ◻
Proof. Define \(\hat{g}_t = \max_{i=1}^t \|\mathbf{g}_i\|\).
Since \(\mathbf{v}_{t} = (1-\beta_t) \mathbf{v}_{t-1} + \beta_t \mathbf{g}_t \odot \mathbf{g}_t\), and assuming \(\beta_t \in [0, 1]\), using the convexity of \(\lVert \cdot \rVert\) and the inequality \(\lVert \mathbf{x} \odot \mathbf{x} \rVert \leq \lVert \mathbf{x} \rVert^2\), we have: \[\begin{align} \lVert \mathbf{v}_t \rVert ~\leq~ (1-\beta_t) \lVert \mathbf{v}_{t-1} \rVert + \beta_t \lVert \mathbf{g}_t \odot \mathbf{g}_t \rVert ~\leq~ (1-\beta_t) \lVert \mathbf{v}_{t-1} \rVert + \beta_t \lVert \mathbf{g}_t \rVert^2 ~\leq~\max \left( \lVert \mathbf{v}_{t-1} \rVert, \lVert \mathbf{g}_t \rVert^2 \right). \end{align}\]
Using this inequality recursively, and assuming \(\mathbf{v}_0 = \mathbf{0}\), we obtain: \[\begin{align} \lVert \mathbf{v}_t \rVert ~\leq~ \max \left( \lVert \mathbf{v}_0 \rVert, \max_{i=1}^t \lVert \mathbf{g}_i \rVert^2 \right) ~=~ \max_{i=1}^t \lVert \mathbf{g}_i \rVert^2 ~\leq~ \hat{g}_t^2. \end{align}\] ◻
Proof. We consider OptEMA-M, where \(\beta_t=\beta\) is fixed and \(\alpha_t\) is decreasing.
Define \(\mathbf{s}_t \triangleq \mathbf{m}_t - \nabla f(\mathbf{x}_t)\), and \(\boldsymbol{\epsilon}_t \triangleq \nabla f(\mathbf{x}_t;\xi_t)-\nabla f(\mathbf{x}_t)\). Let \(\lambda:=\tfrac{\theta^2L^2}{\varepsilon^2}\).
Let \(\mathbf{z}_t := (1-\alpha_{t})\big(\mathbf{s}_{t-1}+\nabla f(\mathbf{x}_{t-1})-\nabla f(\mathbf{x}_t)\big)\) and \(\hat{\mathbf{z}}_t := (1-\alpha_{t-1})\big(\mathbf{s}_{t-1}+\nabla f(\mathbf{x}_{t-1})-\nabla f(\mathbf{x}_t)\big)\).
Recall the parameter update rule \(\mathbf{x}_{t} = \mathbf{x}_{t-1} - \theta \gamma_{t-1} \cdot \frac{\mathbf{m}_{t-1}}{\varepsilon+ \sqrt{\mathbf{v}_{t-1}}}\). Using the \(L\)-smoothness of the objective function \(f\), we can bound the difference in gradients as follows: \[\begin{align} \label{eq:bound:gradient:diff} \textstyle\|\nabla f(\mathbf{x}_{t}) - \nabla f(\mathbf{x}_{t-1})\|^2 &\leq& \textstyle L^2 \|\mathbf{x}_t - \mathbf{x}_{t-1}\|^2 ~~= ~~ L^2 \theta^2 \gamma_{t-1}^2 \left\| \frac{\mathbf{m}_{t-1}}{ \varepsilon + \sqrt{\mathbf{v}_{t-1}}} \right\|^2 \nonumber\\ &\leq& \textstyle\frac{L^2 \theta^2 \gamma_{t-1}^2}{\varepsilon^2} \|\mathbf{m}_{t-1}\|^2 ~~=~~\lambda \gamma_{t-1}^2 \|\mathbf{m}_{t-1}\|^2. \end{align}\tag{5}\]
We derive the following equalities for \(\mathbf{s}_t\): \[\begin{align} \label{eq:bound:s} \mathbf{s}_{t} &\overset{\text{\ding{\numexpr 1+171\relax}}}{=}& (1-\alpha_{t}) \mathbf{m}_{t-1} + \alpha_{t} \nabla f(\mathbf{x}_{t};\xi_{t}) - \nabla f(\mathbf{x}_{t}) \nonumber\\ &=& (1-\alpha_{t}) (\mathbf{m}_{t-1} - \nabla f(\mathbf{x}_{t-1}) ) + \alpha_{t} \nabla f(\mathbf{x}_{t};\xi_{t}) + (1-\alpha_{t})\nabla f(\mathbf{x}_{t-1}) - \nabla f(\mathbf{x}_{t}) \nonumber\\ &\overset{\text{\ding{\numexpr 2+171\relax}}}{=}& \textstyle\underbrace{ (1-\alpha_{t}) \big( \mathbf{s}_{t-1} + \nabla f(\mathbf{x}_{t-1}) - \nabla f(\mathbf{x}_{t}) \big) }_{:= \mathbf{z}_t } + \alpha_{t} \underbrace{ \big( \nabla f(\mathbf{x}_{t};\xi_{t}) - \nabla f(\mathbf{x}_{t})\big)}_{:=\boldsymbol{\epsilon}_t}, \end{align}\tag{6}\] where step uses \(\mathbf{m}_{t} = (1-\alpha_{t}) \mathbf{m}_{t-1} + \alpha_{t} \nabla f(\mathbf{x}_{t};\xi_t)\); and step uses \(\mathbf{s}_{t-1} \triangleq \mathbf{m}_{t-1} - \nabla f(\mathbf{x}_{t-1})\).
We derive the following results: \[\begin{align} \label{eq:z:squared} \|\mathbf{z}_{t}\|^2 &=& \| (1-\alpha_{t}) \mathbf{s}_{t-1} + (1 - \alpha_{t})(\nabla f(\mathbf{x}_{t-1}) - \nabla f(\mathbf{x}_{t})) \|_2^2 \nonumber\\ &\overset{\text{\ding{\numexpr 1+171\relax}}}{\leq}& (1+\alpha_{t})(1-\alpha_{t})^2 \| \mathbf{s}_{t-1}\|^2 + \left(1+\tfrac{1}{\alpha_{t}}\right)(1-\alpha_{t})^2 \| \nabla f(\mathbf{x}_{t-1}) - \nabla f(\mathbf{x}_{t}) \|^2 \nonumber\\ &\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq}& (1-\alpha_{t}) \|\mathbf{s}_{t-1}\|_2^2 + \tfrac{1}{\alpha_{t}} \| \nabla f(\mathbf{x}_{t-1}) - \nabla f(\mathbf{x}_{t}) \|^2 \nonumber\\ &\overset{\text{\ding{\numexpr 3+171\relax}}}{\leq}& (1-\alpha_{t}) \|\mathbf{s}_{t-1}\|_2^2 + \tfrac{\lambda}{\alpha_{t}} \gamma_{t-1}^2\| \mathbf{m}_{t-1}\|^2, \end{align}\tag{7}\] where step uses \(\|\mathbf{a}+\mathbf{b}\|_2^2 \leq (1+\gamma)\|\mathbf{a}\|_2^2 + (1+\tfrac{1}{\gamma})\|\mathbf{b}\|_2^2\) for all \(\gamma=\alpha_{t}\); step uses \((1+\alpha_{t})(1-\alpha_{t})\leq 1\), and the relation \((1+\tfrac{1}{\alpha_{t}})(1-\alpha_{t})^2 = \tfrac{1}{\alpha_{t}} (\alpha_{t}+1)(1-\alpha_{t})^2 \leq \tfrac{1}{\alpha_{t}}\); step uses the gradient difference bound derived in Inequality (5 ).
We derive: \[\begin{align} \tag{8} \|\mathbf{z}_t-\hat{\mathbf{z}}_t\|^2 &\le& 2(\alpha_{t-1}-\alpha_t)^2\|\mathbf{s}_{t-1}\|^2 + 2(\alpha_{t-1}-\alpha_t)^2 \|\nabla f(\mathbf{x}_{t-1})-\nabla f(\mathbf{x}_t)\|^2 \nonumber\\ &\le& 2(\alpha_{t-1}-\alpha_t)^2\|\mathbf{s}_{t-1}\|^2 + 2(\alpha_{t-1}-\alpha_t)^2 \lambda \|\mathbf{m}_{t-1}\|^2\gamma_{t-1}^2.\tag{9} \end{align}\]
Letting \(\zeta_t>0\) and \(\nu_t>0\) for all \(t\). Expanding the squared norm of Equality (6 ) gives \(\|\mathbf{s}_t\|^2 = \|\mathbf{z}_t\|^2 + \alpha_t^2\|\boldsymbol{\epsilon}_t\|^2 + 2\langle\mathbf{z}_t,\alpha_t\boldsymbol{\epsilon}_t\rangle\). Arranging terms and taking conditional expectation \(\mathbb{E}[\cdot]:=\mathbb{E}[\cdot\mid \mathcal{F}_{t-1}]\) of both sides yields: \[\begin{align} \label{eq:lemma:bound:eee:1:expand} \textstyle\mathbb{E}[\|\mathbf{s}_t\|^2 ] &= & \mathbb{E}[\|\mathbf{z}_t\|^2+\alpha_t^2\|\boldsymbol{\epsilon}_t\|^2 ]+\mathbb{E}[2\langle\mathbf{z}_t,\alpha_t\boldsymbol{\epsilon}_t\rangle] \nonumber\\ &= & \mathbb{E}[\|\mathbf{z}_t\|^2+\alpha_t^2\|\boldsymbol{\epsilon}_t\|^2 ]+ \mathbb{E}[ 2\langle\mathbf{z}_t-\hat{\mathbf{z}}_t,\alpha_{t-1}\boldsymbol{\epsilon}_t\rangle+ 2\langle\mathbf{z}_t,(\alpha_t-\alpha_{t-1})\boldsymbol{\epsilon}_t\rangle+ 2\langle\hat{\mathbf{z}}_t,\alpha_{t-1}\boldsymbol{\epsilon}_t\rangle] \nonumber\\ &\overset{\text{\ding{\numexpr 1+171\relax}}}{=}& \mathbb{E}[\|\mathbf{z}_t\|^2+\alpha_t^2\|\boldsymbol{\epsilon}_t\|^2 ]+ \mathbb{E}[2\langle\mathbf{z}_t-\hat{\mathbf{z}}_t,\alpha_{t-1}\boldsymbol{\epsilon}_t\rangle+ 2\langle\mathbf{z}_t,(\alpha_t-\alpha_{t-1})\boldsymbol{\epsilon}_t\rangle] + 0 \nonumber\\ &\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq}& \textstyle\mathbb{E}[\|\mathbf{z}_t\|^2+\alpha_t^2\|\boldsymbol{\epsilon}_t\|^2 ]+ \mathbb{E}[\frac{1}{\zeta_t} \|\mathbf{z}_t-\hat{\mathbf{z}}_t\|^2 + \zeta_t \| \alpha_{t-1} \boldsymbol{\epsilon}_t\|^2] \nonumber\\ && \textstyle+ \mathbb{E}[ \frac{\nu_t}{2} \|\mathbf{z}_t\|^2 + \frac{2}{\nu_t} (\alpha_t-\alpha_{t-1})^2\|\boldsymbol{\epsilon}_t\|^2],~\forall \zeta_t,\nu_t >0\nonumber\\ &\overset{\text{\ding{\numexpr 3+171\relax}}}{\leq}& \textstyle\mathbb{E}[ (1+ \tfrac{\nu_t}{2}) \|\mathbf{z}_t\|^2] + \big( \alpha_t^2 + \zeta_t \alpha_{t-1}^2 +\frac{2}{\nu_t} (\alpha_t-\alpha_{t-1})^2 \big) \|\boldsymbol{\epsilon}_t\|^2 \nonumber\\ && \textstyle+ \mathbb{E}[\frac{2(\alpha_{t-1}-\alpha_t)^2}{\zeta_t} \|\mathbf{s}_{t-1}\|^2 + \frac{2(\alpha_{t-1}-\alpha_t)^2}{\zeta_t} \lambda \|\mathbf{m}_{t-1}\|^2\gamma_{t-1}^2] \nonumber\\ &\overset{\text{\ding{\numexpr 4+171\relax}}}{\leq}& \textstyle\mathbb{E}[ (1+ \tfrac{\nu_t}{2}) (1-\alpha_{t}) \|\mathbf{s}_{t-1}\|_2^2 + (1+ \tfrac{\nu_t}{2}) \tfrac{\lambda}{\alpha_{t}} \gamma_{t-1}^2\| \mathbf{m}_{t-1}\|^2] \nonumber\\ && \textstyle+ \mathbb{E}[ \big( \alpha_{t}^2 + \zeta_t \alpha_{t-1}^2 +\frac{2}{\nu_t} (\alpha_t-\alpha_{t-1})^2 \big) \|\boldsymbol{\epsilon}_t\|^2 ] \nonumber\\ && \textstyle+ \mathbb{E}[\frac{2(\alpha_{t-1}-\alpha_t)^2}{\zeta_t} \|\mathbf{s}_{t-1}\|^2 + \frac{2(\alpha_{t-1}-\alpha_t)^2}{\zeta_t } \lambda \|\mathbf{m}_{t-1}\|^2\gamma_{t-1}^2] \nonumber\\ &\overset{}{\leq}& \textstyle\mathbb{E}[ (1 -\alpha_t + \tfrac{\nu_t}{2}- \tfrac{\alpha_t\nu_t }{2} + \frac{2(\alpha_{t-1}-\alpha_t)^2}{\zeta_t} ) \|\mathbf{s}_{t-1}\|_2^2 + ( \tfrac{1}{\alpha_{t}} + \tfrac{\nu_t}{2 \alpha_t} + \tfrac{2 (\alpha_{t-1}-\alpha_t)^2 }{\zeta_t} ) \lambda \gamma_{t-1}^2\| \mathbf{m}_{t-1}\|^2] \nonumber\\ && \textstyle+ \mathbb{E}[ \big( \alpha_t^2 + \zeta_t \alpha_{t-1}^2 +\frac{2}{\nu_t} (\alpha_t-\alpha_{t-1})^2 \big) \|\boldsymbol{\epsilon}_t\|^2 ] , \nonumber \end{align}\tag{10}\] where step uses \(\mathbb{E}[\langle\hat{\mathbf{z}}_t,\alpha_{t-1}\boldsymbol{\epsilon}_t\rangle]=0\); step uses the Young’s inequality that \(2\mathbb{E}[\langle\mathbf{z}_t-\hat{\mathbf{z}}_t,\alpha_{t-1}\boldsymbol{\epsilon}_t\rangle] \le \frac{1}{\zeta_t}\mathbb{E}_t[\|\mathbf{z}_t-\hat{\mathbf{z}}_t\|^2] + \zeta_t \alpha_{t-1}^2 \mathbb{E}[\|\boldsymbol{\epsilon}_t\|^2]\), and \(2\mathbb{E}[\langle\mathbf{z}_t,(\alpha_t-\alpha_{t-1})\boldsymbol{\epsilon}_t\rangle] \le \frac{\nu_t}{2}\mathbb{E}_t[\|\mathbf{z}_t\|^2] + \frac{2}{\nu_t}\mathbb{E}[(\alpha_t-\alpha_{t-1})^2\|\boldsymbol{\epsilon}_t\|^2]\); step uses Inequality (9 ); step uses Inequality (7 ).
Letting \(\nu_t = \alpha_t\) and \(\zeta_t= \tfrac{ 8 (\alpha_{t-1}-\alpha_t)^2 }{\alpha_t}\) yields: \[\begin{align} && \textstyle\mathbb{E}[\|\mathbf{s}_t\|^2 ] - \mathbb{E}[ (1-\tfrac{\alpha_t}{4}) \|\mathbf{s}_{t-1}\|_2^2 \nonumber\\ &\leq & \textstyle\mathbb{E}[ ( \tfrac{1}{\alpha_{t}} + \tfrac{1}{2 } + \tfrac{\alpha_t}{ 2} ) \lambda \gamma_{t-1}^2\| \mathbf{m}_{t-1}\|^2 + \big( \alpha_t^2 + \tfrac{ 8 (\alpha_{t-1}-\alpha_t)^2 }{\alpha_t} \alpha_{t-1}^2 +\frac{2}{\alpha_t} (\alpha_t-\alpha_{t-1})^2 \big) \|\boldsymbol{\epsilon}_t\|^2 ]\nonumber\\ &\overset{\text{\ding{\numexpr 1+171\relax}}}{\leq}& \textstyle\mathbb{E}[ \tfrac{3}{\alpha_{t}} \lambda \gamma_{t-1}^2\| \mathbf{m}_{t-1}\|^2 + \big( \alpha_t^2 + \frac{10}{\alpha_t} (\alpha_t-\alpha_{t-1})^2 \big) \|\boldsymbol{\epsilon}_t\|^2 ] \nonumber\\ &\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq}& \textstyle\mathbb{E}[ \tfrac{3}{\alpha_{t}} \lambda \gamma_{t-1}^2\| \mathbf{m}_{t-1}\|^2 + \big( \alpha_t^2 + \frac{10}{\alpha_t} (\alpha_t-\alpha_{t-1})^2 \big) \|\mathbf{g}_t\|^2 ] \nonumber\\ &\overset{\text{\ding{\numexpr 3+171\relax}}}{\leq}& \textstyle\mathbb{E}[ \tfrac{3}{\alpha_{t}} \lambda \gamma_{t-1}^2\| \mathbf{m}_{t-1}\|^2 + \tfrac{1 + \hat{g}_t^2 }{ 1 + \sum_{i=1}^t \|\mathbf{g}_i\|^2 } \|\mathbf{g}_t\|^2 + 10 \tfrac{\hat{g}_t^3 }{ 1 + \sum_{i=1}^t \|\mathbf{g}_i\|^2 } \|\mathbf{g}_t\|^2 ] \nonumber\\ &\overset{}{\leq }& \textstyle\mathbb{E}[ \tfrac{3}{\alpha_{t}} \lambda \gamma_{t-1}^2\| \mathbf{m}_{t-1}\|^2 + \tfrac{ 11 (1 + \hat{g}_t)^3\|\mathbf{g}_t\|^2 }{ 1 + \sum_{i=1}^t \|\mathbf{g}_i\|^2 } ] ,\nonumber \end{align}\] where step uses \(\alpha_t \in (0, 1]\); step uses \(\mathbb{E}[\|\boldsymbol{\epsilon}_t\|^2] \le \mathbb{E}[\|\mathbf{g}_t\|^2]\); step uses Lemma 1(c) that \(\rho_{t}^2 \le \tfrac{1 + \hat{g}_{t}^2}{1 + \sum_{i=1}^t \|\mathbf{g}_i\|^2}\), and Lemma 1(d) that \((\rho_{t-1}-\rho_t)^2/\rho_t \le \tfrac{\hat{g}_{t}^3}{1 + \sum_{i=1}^t \|\mathbf{g}_i\|^2}\). ◻
Proof. Define \(\hat{g}_t = \max_{i=1}^t \|\mathbf{g}_i\|_2\), \(\mathbf{s}_t := \mathbf{m}_{t} - \nabla f(\mathbf{x}_t)\), and \(\kappa_t := \varepsilon + \sqrt{\max(\mathbf{v}_t)}\).
Given \(f(\mathbf{x})\) is \(L\)-smooth, we have: \[\begin{align} \label{eq:L:smooth} &&\textstyle\mathbb{E}[ f(\mathbf{x}_{t+1}) - f(\mathbf{x}_t) ] \nonumber\\ &\leq & \textstyle\mathbb{E}[ \tfrac{L}{2}\|\mathbf{x}_{t+1}-\mathbf{x}_t\|_2^2 + \langle\nabla f(\mathbf{x}_t),\mathbf{x}_{t+1}-\mathbf{x}_t\rangle] \nonumber\\ &\overset{\text{\ding{\numexpr 1+171\relax}}}{=}& \mathbb{E}[ \tfrac{L}{2}\theta^2\gamma_t^2\|\tfrac{\mathbf{m}_{t}}{\varepsilon+ \sqrt{\mathbf{v}_{t}}}\|_2^2 + \theta \gamma_t \left( - \langle\nabla f(\mathbf{x}_t), \tfrac{\nabla f(\mathbf{x}_t)}{\varepsilon+ \sqrt{ \mathbf{v}_{t}}}\rangle+ \langle\nabla f(\mathbf{x}_t), \tfrac{\nabla f(\mathbf{x}_t) - \mathbf{m}_{t} }{\varepsilon+ \sqrt{\mathbf{v}_{t}}} \rangle\right) ] \nonumber\\ &\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq}& \mathbb{E}[ \tfrac{L\theta^2\gamma_t^2}{2 \varepsilon^2} \|\mathbf{m}_{t}\|_2^2 + \theta \gamma_t \left( -\tfrac{1}{ \kappa_t }\|\nabla f(\mathbf{x}_t)\|_2^2 + \tfrac{1}{\varepsilon}\| \nabla f(\mathbf{x}_t)\| \cdot \| \mathbf{m}_t - \nabla f(\mathbf{x}_t) \|\right)] \nonumber\\ &\overset{}{=}& \mathbb{E}[ \tfrac{L \theta^2\gamma_t^2}{2 \varepsilon^2} \|\mathbf{m}_{t}\|_2^2 + \theta \gamma_t \left( - \tfrac{ 1 }{ 2 \kappa_t }\|\nabla f(\mathbf{x}_t)\|_2^2 - \tfrac{ 1 }{ 2 \kappa_t }\|\nabla f(\mathbf{x}_t)\|_2^2 + \tfrac{1}{\varepsilon} \|\nabla f(\mathbf{x}_t)\|\cdot \|\mathbf{s}_t\| \right) ] \nonumber\\ &\overset{\text{\ding{\numexpr 3+171\relax}}}{\leq}& \mathbb{E}[\tfrac{L\theta^2\gamma_t^2}{2\varepsilon^2} \|\mathbf{m}_{t}\|_2^2 + \theta \gamma_t \left( - \tfrac{1 }{ 2 \kappa_t }\|\nabla f(\mathbf{x}_t)\|_2^2 + \tfrac{ \kappa_t }{ 2\varepsilon^2} \| \mathbf{s}_t \|^2 \right) ] \nonumber\\ &\overset{\text{\ding{\numexpr 4+171\relax}}}{\leq}& \mathbb{E}[ \tfrac{L\theta^2\gamma_t^2}{2\varepsilon^2} \|\mathbf{m}_{t}\|_2^2 + \theta \gamma_t \left( - \tfrac{ 1 }{ 2 (1+\hat{g}_t) }\|\nabla f(\mathbf{x}_t)\|_2^2 + \tfrac{ 1+\hat{g}_t }{ 2 \varepsilon^2} \| \mathbf{s}_t \|^2 \right) ] , \nonumber \end{align}\tag{11}\] where step uses \(\mathbf{x}_{t+1} = \mathbf{x}_t - \theta \gamma_t \cdot \tfrac{\mathbf{m}_{t}}{ \varepsilon + \sqrt{ \mathbf{v}_{t}}}\); step uses Cauchy-Schwarz inequality, \(\mathbf{v}_t \geq 0\), and the definition of \(\kappa_t\); step uses the inequality \(-\tau x^2 + ax \leq \tfrac{a^2}{4\tau}\) with \(\tau=\tfrac{1}{2\kappa_t}\), \(a=\tfrac{1}{\varepsilon}\|\mathbf{s}_t\|\) and \(x=\|\nabla f(\mathbf{x}_t)\|\); step uses the fact that \(\kappa_t:=\varepsilon + \sqrt{\max(\mathbf{v}_t)} \leq \varepsilon + \sqrt{ \|\mathbf{v}_t\|} \leq 1+\hat{g}_t\), which is implied by \(\varepsilon\in(0,1)\) and Lemma 3. ◻
Proof. Define \(\hat{g}_t = \max_{1\leq i\leq t} \|\mathbf{g}_i\|\) and \(\alpha_t= \sqrt{\frac{1 + \frac{\tau}{t}\sum_{i=1}^t \| \mathbf{g}_i \|^2}{1 + \sum_{i=1}^t \| \mathbf{g}_i \|^2}}\), where \(\tau\in[0,1]\).
Define \(\gamma_t = \min\left( \frac{\alpha_t}{ 1 + \mu \hat{g}_t^4} ,\, \left(1 + \sum_{j=1}^t \tfrac{\|\mathbf{m}_j\|^2}{\alpha_j} \right)^{-1/2}\right)\).
Define \(B_t:=\tfrac{3}{\alpha_{t}} \lambda \gamma_{t-1}^2\| \mathbf{m}_{t-1}\|^2 + \tfrac{ 11 (1 + \hat{g}_t)^3\|\mathbf{g}_t\|^2 }{ 1 + \sum_{i=1}^t \|\mathbf{g}_i\|^2 }\), and \(\hat{f}_t \triangleq \max_{t=1}^t f(\mathbf{x}_t) - f_*\).
We have: \[\begin{align} \label{eq:sum:alpha:m:gamma} \textstyle\sum_{t=1}^T \frac{1}{\alpha_{t}} \|\mathbf{m}_{t}\|^2 \gamma_{t}^2 &\overset{\text{\ding{\numexpr 1+171\relax}}}{\leq}& \textstyle\sum_{t=1}^T \frac{\|\mathbf{m}_{t}\|^2/\alpha_t}{ 1 + \sum_{j=1}^t \|\mathbf{m}_j\|^2/\alpha_j } \nonumber\\ &\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq}& \textstyle\ln \left( 1 + \sum_{t=1}^T \frac{\|\mathbf{m}_t\|^2}{\alpha_j}\right) \nonumber\\ &\overset{\text{\ding{\numexpr 3+171\relax}}}{\leq}& \textstyle\ln \left( 1 + \big (1 + \sum_{t=1}^T \|\mathbf{g}_t\|^2 \big)^{1/2} \big(\sum_{t=1}^T \|\mathbf{m}_t\|^2\big) \right) \nonumber\\ &\overset{\text{\ding{\numexpr 4+171\relax}}}{\leq}& \textstyle\ln \left( 1 + 3 \left(1 + \sum_{t=1}^T \|\mathbf{g}_t\|^2 \right)^{2} \right) \nonumber\\ &\overset{\text{\ding{\numexpr 5+171\relax}}}{\leq}& \textstyle 3 \ln \left( e +\sum_{t=1}^T \|\mathbf{g}_t\|^2 \right), \end{align}\tag{12}\] where step uses the definition of \(\gamma_t^2\), leading to \(\gamma_t^2\leq \tfrac{1}{1+\sum_{i=1}^t \|\mathbf{m}_i\|^2/\alpha_i}\); step uses the standard sum-to-integral inequality \(\sum_{t=1}^T \frac{\mathbf{x}_t}{1 + \sum_{i=1}^t \mathbf{x}_i} \leq \ln(1 + \sum_{t=1}^T \mathbf{x}_t)\) with \(\mathbf{x}_i=\|\mathbf{m}_i\|^2/\alpha_i\); step uses \(\tfrac{1}{\alpha_t} \leq \tfrac{1}{\alpha_T} = \sqrt{\frac{1 + \sum_{i=1}^t \| \mathbf{g}_i \|^2}{1 + \frac{\tau}{t}\sum_{i=1}^t \| \mathbf{g}_i \|^2}} \leq \big(1+\sum_{t=1}^T \|\mathbf{g}_t\|^2\big)^{1/2}\) for all \(t\leq T\); step uses \(\sum_{t=1}^T \|\mathbf{m}_i\|^2\leq 3 (1 + \sum_{t=1}^T \|\mathbf{g}_i\|^2)^{3/2}\); step uses the logarithmic inequality \(\ln( 1 + 3 (1+x)^{2}) \leq 3 \ln(e+x)\) for all \(x\geq 0\) with \(x=\sum_{t=1}^T \|\mathbf{g}_t\|^2\).
Using Lemma 4, we derive the following inequalities for all \(t\geq 1\): \[\begin{align} \mathbb{E}[ \|\mathbf{s}_t\|^2 ] &\leq& \mathbb{E}[ B_t + (1-\tfrac{\alpha_t}{4}) \|\mathbf{s}_{t-1}\|^2 ] \tag{13} \\ &\overset{\text{\ding{\numexpr 1+171\relax}}}{\leq}& \mathbb{E}[ B_t + \|\mathbf{s}_{t-1}\|^2 - \tfrac{1}{4} \gamma_t (1+\mu\hat{g}_t^4) \|\mathbf{s}_{t-1}\|^2 ] \nonumber\\ &\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq}& \mathbb{E}[ B_t + \|\mathbf{s}_{t-1}\|^2 - \tfrac{1}{4} \gamma_t (1+\mu\hat{g}_t^4) (\|\mathbf{s}_{t}\|^2 - B_t ) ] \nonumber\\ &\overset{\text{\ding{\numexpr 3+171\relax}}}{\leq}& \mathbb{E}[ (1+1) B_t + \|\mathbf{s}_{t-1}\|^2 - \tfrac{1}{4} \gamma_t (1+\mu\hat{g}_t^4) \|\mathbf{s}_{t}\|^2 ] \nonumber\\ &\overset{\text{\ding{\numexpr 4+171\relax}}}{\leq}& \mathbb{E}[ 2 B_t + \|\mathbf{s}_{t-1}\|^2 - \tfrac{\mu}{32} \gamma_t (1+\hat{g}_t)^4 \|\mathbf{s}_{t}\|^2 ], \tag{14} \end{align}\] where step uses the fact that \(\gamma_{t}\leq \frac{\alpha_t}{ 1+\mu\hat{g}_t^4}\); step uses the relation \(\mathbb{E}[\|\mathbf{s}_{t}\|^2] \leq \mathbb{E}[\|\mathbf{s}_{t-1}\|^2 + B_{t}]\) implied by neglecting the non-positive term \(-\tfrac{\alpha_t}{4}\|\mathbf{s}_{t-1}\|^2\) in Inequality (13 ); step uses \(\tfrac{1}{4}\gamma_t (1+\mu \hat{g}_t^4) B_t \leq \tfrac{1}{4} \alpha_t B_t \leq B_t\); step uses \(1+\mu x^4 \geq \tfrac{\mu}{8} (1+\mu x)^4\) for all \(x=\hat{g}_t\geq 0\), which is implied by Lemma 19.
Multiplying both sides of Inequality (14 ) by \(\tfrac{32}{\mu (1+\hat{g}_t)^2}\) and rearranging terms yields: \[\begin{align} \mathbb{E}[ \gamma_t (1+\hat{g}_t)\|\mathbf{s}_t\|^2] &\leq& \textstyle\mathbb{E}[ \frac{32}{\mu (1+\hat{g}_t)^3} (\|\mathbf{s}_{t-1}\|^2 - \|\mathbf{s}_t\|^2) + \frac{64}{\mu (1+\hat{g}_t)^3} B_t ] \nonumber\\ &\overset{\text{\ding{\numexpr 1+171\relax}}}{\leq}& \textstyle\mathbb{E}[ \frac{32}{ \mu (1+\hat{g}_{t-1})^3} \|\mathbf{s}_{t-1}\|^2 - \frac{32}{ \mu (1+\hat{g}_t^3)} \|\mathbf{s}_t\|^2 + \frac{64}{\mu (1+\hat{g}_t)^3} B_t], \nonumber \end{align}\] where step uses \(\hat{g}_t\geq \hat{g}_{t-1}\). Summing this inequality over \(t\) from \(1\) to \(T\) allows the sequence to telescope: \[\begin{align} \label{eq:to:log} && \textstyle\mathbb{E}[\sum_{t=1}^T \gamma_t (1+\hat{g}_t) \|\mathbf{s}_t\|^2] \nonumber\\ &\leq& \textstyle\mathbb{E}[ \tfrac{32}{\mu}\sum_{t=1}^T \left(\frac{\|\mathbf{s}_{t-1}\|^2}{ (1+\hat{g}_{t-1})^3} - \frac{\|\mathbf{s}_t\|^2}{ (1+\hat{g}_t)^3} \right) + \tfrac{64}{\mu} \sum_{t=1}^T \frac{B_t}{ (1+\hat{g}_t)^3} ] \nonumber\\ &\overset{\text{\ding{\numexpr 1+171\relax}}}{\leq}& \textstyle\mathbb{E}[ \tfrac{32 \|\mathbf{s}_0\|^2}{ \mu (1+\hat{g}_0)^3} + \tfrac{64}{\mu} \sum_{t=1}^T \frac{1}{ (1+\hat{g}_t)^3 } \left( \tfrac{3}{\alpha_{t}} \lambda \gamma_{t-1}^2\| \mathbf{m}_{t-1}\|^2 + \tfrac{ 11 (1 + \hat{g}_t)^3\|\mathbf{g}_t\|^2 }{ 1 + \sum_{i=1}^t \|\mathbf{g}_i\|^2 } \right) ] \nonumber\\ &\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq}& \textstyle\mathbb{E}[ \tfrac{32}{\mu} \|\mathbf{s}_0\|^2 + \frac{192\lambda}{\mu} \cdot \sum_{t=1}^T \tfrac{1}{(1+\hat{g}_t)^3} \frac{1+\hat{g}_t}{\alpha_{t-1}} \|\mathbf{m}_{t-1}\|^2 \gamma_{t-1}^2 + \tfrac{704}{\mu} \cdot \ln(e + \sum_{t=1}^T \|\mathbf{g}_t\|^2) ] \nonumber\\ &\overset{\text{\ding{\numexpr 3+171\relax}}}{\leq}& \textstyle\mathbb{E}[ \tfrac{32}{\mu} \|\mathbf{s}_0\|^2 + \frac{192 \lambda }{\mu} \sum_{t=1}^T \frac{1}{\alpha_{t}} \|\mathbf{m}_{t}\|^2 \gamma_{t}^2 + \tfrac{704}{\mu} \ln(e+ \sum_{i=1}^T \|\mathbf{g}_i\|^2) ]\nonumber\\ &\overset{\text{\ding{\numexpr 4+171\relax}}}{\leq}& \textstyle\mathbb{E}[ \underbrace{ \big( \tfrac{32}{\mu} \|\mathbf{s}_0\|^2 + \tfrac{192 \times 3 \lambda}{\mu} + \tfrac{704}{\mu} \big)}_{:=C_w} \cdot \ln\left(e + \sum_{t=1}^T \|\mathbf{g}_t\|^2\right)], \nonumber \end{align}\tag{15}\] where step uses the definition of \(B_t\); step uses \(\frac{\alpha_{t-1}}{\alpha_t} \leq 1+\hat{g}_t\) (which is implied by Lemma 1(b) since \(\alpha_t=\rho_t\), and Lemma 16(a) that \(\sum_{t=1}^T \frac{b_t}{ 1 + \sum_{i=1}^t b_i } \leq \ln\left(1+ \sum_{t=1}^T b_t \right)\) with \(b_t=\|\mathbf{g}\|^2\); step uses the results of shifting the summation index and \(\|\mathbf{m}_0\|^2 = 0\); step uses Inequality (12 ). ◻
Proof. Define \(\hat{g}_t = \max_{1\leq i\leq t} \|\mathbf{g}_i\|\) and \(\alpha_t= \sqrt{\frac{1 + \frac{\tau}{t}\sum_{i=1}^t \| \mathbf{g}_i \|^2}{1 + \sum_{i=1}^t \| \mathbf{g}_i \|^2}}\), where \(\tau\in[0,1]\).
Let \(\gamma_t = \min\left( \frac{\alpha_t}{ 1 + \mu \hat{g}_t^4 } ,\, \left(1 + \sum_{j=1}^t \frac{\|\mathbf{m}_j\|^2}{\alpha_j} \right)^{-1/2}\right)\), and \(\hat{f}_t \triangleq f(\mathbf{x}_t) - f_*\).
Let \(\mathbb{G}_t := \sum_{i=1}^t \|\mathbf{g}_i\|^2\) and \(\mathbb{M}_t := \sum_{i=1}^t \|\mathbf{m}_i\|^2\), with the shorthands \(\mathbb{G}:= \mathbb{G}_T\) and \(\mathbb{M}:= \mathbb{M}_T\).
Using the Cauchy-Schwarz inequality and a standard consequence of \(L\)-smoothness (Lemma 20), we derive: \[\label{eq:bound:g95t} \mathbb{E}[\|\mathbf{g}_t\|^2] ~\leq~ \mathbb{E}[2\|\mathbf{g}_t - \nabla f(\mathbf{x}_t)\|^2 + 2\|\nabla f(\mathbf{x}_t)\|^2] ~\leq~ 2\sigma^2 + \mathbb{E}[ 4 L( f(\mathbf{x}_t) - f_* )].\tag{16}\]
We derive: \[\begin{align} \label{eq:bound:sum:gamma:m} && \textstyle\sum_{t=1}^T \gamma_t^2 \|\mathbf{m}_{t}\|_2^2 ~~\overset{\text{\ding{\numexpr 1+171\relax}}}{\leq}~~ \textstyle\sum_{t=1}^T \tfrac{\|\mathbf{m}_{t}\|_2^2}{ 1 + \mu \hat{g}_t^4} \cdot \frac{1 + \tau \mathbb{G}_t/t }{1 + \mathbb{G}_t} ~~\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq}~~ \tfrac{8}{\mu} \sum_{t=1}^T \tfrac{\|\mathbf{m}_{t}\|_2^2}{ 1+\mathbb{G}_t } \cdot \frac{1 + \hat{g}_t^2 }{(1 + \hat{g}_t)^4 } \nonumber\\ &\overset{\text{\ding{\numexpr 3+171\relax}}}{\leq}& \textstyle\tfrac{8}{\mu} \sum_{t=1}^T \tfrac{\|\mathbf{m}_{t}\|_2^2}{1 + \mathbb{G}_t} \cdot \frac{ 1 }{ (1 + \hat{g}_t )^2 }~~\overset{\text{\ding{\numexpr 4+171\relax}}}{\leq} ~~\textstyle\tfrac{8}{\mu} \sum_{t=1}^T \tfrac{\|\mathbf{m}_{t}\|_2^2}{1 + \mathbb{M}_t/ (2+2 \hat{g}_t)} \cdot \frac{ 1 }{ (1 + \hat{g}_t )^2 }~~\leq~~\tfrac{8}{\mu} \sum_{t=1}^T \tfrac{\|\mathbf{m}_{t}\|_2^2}{ 1 + \mathbb{M}_t} \cdot \frac{ 2+2 \hat{g}_t }{ (1 + \hat{g}_t )^2 } \nonumber\\ &\overset{\text{\ding{\numexpr 5+171\relax}}}{\leq} & \textstyle\tfrac{16}{\mu} \sum_{t=1}^T \tfrac{\|\mathbf{m}_{t}\|_2^2}{ 1 + \mathbb{M}_t} ~~\overset{\text{\ding{\numexpr 6+171\relax}}}{\leq}~~ \textstyle\tfrac{16}{\mu}\ln(1 + \mathbb{M}) ~~\overset{\text{\ding{\numexpr 7+171\relax}}}{\leq}~~ \textstyle\tfrac{16}{\mu}\ln(1 + 3 (1 + \mathbb{G})^{3/2})~~\overset{\text{\ding{\numexpr 8+171\relax}}}{\leq}~~ \textstyle\tfrac{48}{\mu}\ln( e + \mathbb{G}),\nonumber \end{align}\tag{17}\] where step uses \(\gamma_t^2\leq \frac{\alpha_t^2}{ (1 + \mu\hat{g}_t^4)^2} \leq \frac{1}{1 + \mu\hat{g}_t^4}\cdot \tfrac{1+\tau \mathbb{G}_t /t}{1+\mathbb{G}_t}\); step uses Inequality \(\tfrac{\mu(1+x)^4}{1 + \mu x^4}\leq 8\) for all \(\mu\in(0,1)\) (see Lemma 19), and \(\mathbb{G}_t/t\leq \hat{g}_t^2\); step uses \(1+\hat{g}_t^2\leq (1+\hat{g}_t)^2\); step uses \(\mathbb{M}_T\leq (2+2\sqrt{\tau} \hat{g}_T) \mathbb{G}_T\leq (2+2\hat{g}_T) \mathbb{G}_T\); step uses \(\tfrac{1+x}{(1+x)^2}\leq 1\); step uses the standard logarithmic integral bound \(\sum_{t=1}^T \frac{\mathbf{x}_t}{1 + \sum_{i=1}^t \mathbf{x}_i} \leq \ln(1 + \sum_{t=1}^T \mathbf{x}_t)\) with \(\mathbf{x}_i=\|\mathbf{m}_i\|^2\); step uses \(\sum_{i=1}^T \|\mathbf{m}_i\|^2 \leq 3 (1+\sum_{i=1}^T \|\mathbf{g}_i\|^2)^{3/2}\), as shown in the second inequality in Lemma 2; step uses \(\ln(1 + 3(1+x)^{3/2}) \leq 3\ln(e+x)\) for all \(x\geq 0\).
Dropping the non-positive term in Inequality ?? yields: \[\textstyle\mathbb{E}[\hat{f}_{t+1} - \hat{f}_t] \leq \mathbb{E}[ c_1 \gamma_t (1+\hat{g}_t)\| \mathbf{s}_t \|^2 + c_2 \gamma_t^2 \|\mathbf{m}_t\|^2].\] Summing this recursion from \(t=1\) to \(T-1\) gives: \[\begin{align} \textstyle\mathbb{E}[ \hat{f}_T] &\leq& \textstyle\mathbb{E}[ \hat{f}_1 + c_1 \sum_{t=1}^{T-1} \gamma_t (1+\hat{g}_t) \| \mathbf{s}_t \|^2 + c_2 \sum_{t=1}^{T-1} \gamma_t^2 \|\mathbf{m}_{t}\|_2^2] \nonumber\\ &\overset{\text{\ding{\numexpr 1+171\relax}}}{\leq}& \textstyle\mathbb{E}[ \hat{f}_1 + c_1 C_w \ln ( e + \sum_{t=1}^T \|\mathbf{g}_t\|^2) + \tfrac{48}{\mu} c_2\ln(1 + \sum_{t=1}^T \|\mathbf{g}_t\|^2)] \nonumber\\ &\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq}& \textstyle\mathbb{E}[ \left( \hat{f}_1 + c_1 C_w + \tfrac{48 c_2}{\mu} \right) \cdot \ln (e + 4T(\sigma^2+L \big(\max_{t=1}^T \hat{f}_t \big)))] , \nonumber \end{align}\] where step uses \(\mathbb{E}\left[\sum_{t=1}^T \gamma_t (1+\hat{g}_t) \|\mathbf{s}_t\|^2\right]\leq C_w \ln (e + \sum_{t=1}^T \|\mathbf{g}_t\|^2)\) (which is established in Lemma 6) and Inequality (17 ); step uses Inequality (16 ).
Defining \(A_t \triangleq 4 \sigma^2 + 4 L \mathbb{E}[\hat{f}_t]\) and substituting this definition into the bound above yields: \[\frac{A_T - 4 \sigma^2}{4L} \leq \Big( \hat{f}_1 + c_1 C_w + \frac{48 c_2}{\mu} \Big) \ln \Big(e + T \max_{1 \leq t \leq T} A_t \Big).\] Since \(\ln \Big(e + T \max_{1 \leq t \leq T} A_t \Big)\geq 1\), we further obtain: \[\mathbb{E}[A_T] \leq \mathbb{E}[\underbrace{\big(4 L \big( \hat{f}_1 + c_1 C_w + \frac{48 c_2}{\mu} \big) + 4\sigma^2 \big)}_{:=\chi} \cdot \ln \Big(e + T \max_{1 \leq t \leq T} A_t \Big)].\] Invoking Lemma 18, this inequality directly implies: \[\mathbb{E}[A_T] \leq (1+\chi)^3 \ln(e+T).\] Translating this result back to the function suboptimality, we derive: \[\textstyle\mathbb{E}[f(\mathbf{x}_T) - f_*] ~=~ \mathbb{E}[\hat{f}_T]~=~ \mathbb{E}[\frac{A_T - 4 \sigma^2}{4L}] ~\leq~ \frac{(1+\chi)^3 }{4 L} \cdot \ln(e+T)~ \leq~ \underbrace{\textstyle\frac{(1+\chi)^3 }{4 L} }_{:=C_f} \ln(e+T).\]
Substituting this bound back into 16 , we have for all \(t \geq 1\): \[\mathbb{E}[\|\mathbf{g}_t\|^2] ~\leq~ \mathbb{E}[4 (\sigma^2 + L \hat{f}_t)] ~\leq ~4 \big(\sigma^2 + L C_f \ln(e+T)\big) ~\leq ~ \underbrace{\textstyle(4 \sigma^2 + 4 L C_f )}_{:=C_g} \ln(e+T).\] ◻
Proof. Define \(\hat{g}_t = \max_{1\leq i\leq t} \|\mathbf{g}_i\|\) and \(\alpha_t= \sqrt{\frac{1 + \frac{\tau}{t}\sum_{i=1}^t \| \mathbf{g}_i \|^2}{1 + \sum_{i=1}^t \| \mathbf{g}_i \|^2}}\), where \(\tau\in[0,1]\).
Define \(\gamma_t = \min\left( \frac{\alpha_t}{ 1 + \mu\hat{g}_t^4 } ,\, \left(1 + \sum_{j=1}^t \tfrac{\|\mathbf{m}_j\|^2}{\alpha_j} \right)^{-1/2}\right)\).
Define \(B_t:=\tfrac{3}{\alpha_{t}} \lambda \gamma_{t-1}^2\| \mathbf{m}_{t-1}\|^2 + \tfrac{ 11 (1 + \hat{g}_t)^3\|\mathbf{g}_t\|^2 }{ 1 + \sum_{i=1}^t \|\mathbf{g}_i\|^2 }\), and \(\hat{f}_t \triangleq \max_{i=1}^t f(\mathbf{x}_i) - f_*\).
Let \(\mathbb{G}_t := \sum_{i=1}^t \|\mathbf{g}_i\|^2\) and \(\mathbb{M}_t := \sum_{i=1}^t \|\mathbf{m}_i\|^2\), with the shorthands \(\mathbb{G}:= \mathbb{G}_T\) and \(\mathbb{M}:= \mathbb{M}_T\).
Using the Cauchy-Schwarz Inequality and Lemma 20, we derive: \[\begin{align} \label{eq:bound:g95t:app} \mathbb{E}[\|\mathbf{g}_t\|^2] ~\leq~ \textstyle\mathbb{E}[2\|\mathbf{g}_t - \nabla f(\mathbf{x}_t)\|^2+ 2\|\nabla f(\mathbf{x}_t)\|^2] ~\leq~ \textstyle 2\sigma^2 + 4 L \mathbb{E}[ f(\mathbf{x}_t) - f_* ]. \end{align}\tag{18}\]
Using the update rule for the stochastic gradient estimator \(\mathbf{m}_t = (1-\alpha_t)\mathbf{m}_{t-1}+\alpha_t\nabla f(\mathbf{x}_t;\xi_t)\), we derive the following result: \[\begin{align} \|\mathbf{m}_t\|^2 ~~ \leq~~ \max\left( \|\mathbf{m}_{t-1}\|^2,\, \|\nabla f(\mathbf{x}_t;\xi_t)\|^2 \right) ~~\leq ~~ \max_{i=1}^t \|\nabla f(\mathbf{x}_i;\xi_i)\|^2 ~~\leq ~~ C_g \ln(e+t). \nonumber \end{align}\] We further derive: \[\begin{align} \label{eq:bound:sss} \mathbb{E}[\|\mathbf{s}_t\|^2] &=& \mathbb{E}[\|\mathbf{m}_t - \nabla f(\mathbf{x}_t) + \nabla f(\mathbf{x}_t;\xi_t) - \nabla f(\mathbf{x}_t;\xi_t)\|^2] \nonumber\\ & \leq & 3 \mathbb{E}[\|\mathbf{m}_t\|^2] + 3 \mathbb{E}[\| \nabla f(\mathbf{x}_t;\xi_t)- \nabla f(\mathbf{x}_t) \|^2] + 3 \mathbb{E}[\|\nabla f(\mathbf{x}_t;\xi_t)\|^2] \nonumber\\ & \leq & 3 C_g \ln(e+t) + 3 \sigma^2 + 3 C_f \ln(e+t) \nonumber\\ & \leq & 3 \left(C_g + C_f +\sigma^2 \right) \ln(e+t). \end{align}\tag{19}\]
We derive the following results: \[\begin{align} \label{eq:bound:sum:B} && \textstyle\sum_{t=1}^T \frac{1}{\alpha_{t-1}} \|\mathbf{m}_{t-1}\|^2 \gamma_{t-1}^2 ~~\overset{\text{\ding{\numexpr 1+171\relax}}}{\leq}~~ \textstyle\sum_{t=1}^T \frac{1}{\alpha_{t}} \|\mathbf{m}_{t}\|^2 \gamma_{t}^2 ~~\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq}~~ \textstyle\sum_{t=1}^T \tfrac{ \|\mathbf{m}_{t}\|^2/\alpha_t }{ 1 + \sum_{j=1}^t \|\mathbf{m}_j\|^2/\alpha_j } \nonumber\\ &\leq& \ln(1 + \sum_{t=1}^T \|\mathbf{m}_t\|^2/\alpha_t ) ~~\overset{\text{\ding{\numexpr 3+171\relax}}}{\leq}~~ \textstyle\ln \left( 1 + \mathbb{M}_T \cdot \big( 1 + \mathbb{G}_T \big)^{1/2} \right) ~~\overset{\text{\ding{\numexpr 4+171\relax}}}{\leq}~~ \textstyle\ln \left( 1 + 3 \big( 1 + \mathbb{G}_T \big)^{2} \right)\nonumber\\ &\overset{\text{\ding{\numexpr 5+171\relax}}}{\leq}& \textstyle 3 \ln \left( e + \mathbb{G}_T \right) ~~\overset{}{\leq}~~ \textstyle 3\ln \left( e + T C_g\ln( e + T) \right) ~~\overset{\text{\ding{\numexpr 6+171\relax}}}{\leq}~~ \textstyle 3 (1+C_g) \ln(e+T) , \end{align}\tag{20}\] where step uses the results of shifting the summation since \(\|\mathbf{m}_0\|^2=0\); step uses \(\gamma_t^2 \leq \tfrac{1}{ 1 + \sum_{j=1}^t \|\mathbf{m}_j\|^2/\alpha_j }\); step uses \(\tfrac{1}{\alpha_t}\leq \tfrac{1}{\alpha_T} \leq \sqrt{1+\sum_{t=1}^T \|\mathbf{g}_t\|^2}\); step uses the second inequality of Lemma 2 that \(\sum_{t=1}^T \|\mathbf{m}_t\|^2\leq 3(1+\sum_{t=1}^T \|\mathbf{g}_t\|^2)^{3/2}\); step uses \(\ln(1 + 3 (1+x)^2) \leq 3\ln(e+x)\); step uses \(\ln( 1 + T C_g\ln(e+T) ) \leq (1+C_g) \ln(e+T)\) for all \(T\geq 1\).
We have: \[\begin{align} \label{eq:bound:sum:BB} \textstyle\sum_{t=1}^T \tfrac{\|\mathbf{g}_t\|^2}{1+\sum_{i=1}^t \|\mathbf{g}_i\|^2} ~~\leq ~~ \ln(1 + \sum_{t=1}^T \|\mathbf{g}_t\|^2) ~~\leq ~~ \ln(e + T C_g \ln(e+T) ) \leq (1+C_g) \ln(e+T).~ \end{align}\tag{21}\]
For all \(t\geq 1\), we have from Lemma 4: \(\mathbb{E}[ \|\mathbf{s}_t\|^2 ] \leq \mathbb{E}[ (1-\tfrac{\alpha_{t}}{4}) \|\mathbf{s}_{t-1}\|^2 + B_{t}]\), leading to: \[\begin{align} \label{eq:alpha:s} && \textstyle\mathbb{E}[ \tfrac{\alpha_t}{4} \|\mathbf{s}_t\|^2 ] \leq \mathbb{E}[ (1-\tfrac{\alpha_t}{4}) (\|\mathbf{s}_{t-1}\|^2 - \|\mathbf{s}_{t}\|^2) + B_{t}] \nonumber\\ &\Rightarrow&\mathbb{E}[ \alpha_t \|\mathbf{s}_t\|^2 ] \leq \mathbb{E}[ 4 (1-\tfrac{\alpha_t}{4}) (\|\mathbf{s}_{t-1}\|^2 - \|\mathbf{s}_{t}\|^2) + 4 B_{t}]. \nonumber \end{align}\tag{22}\] Summing this inequality over \(t\) from \(1\) to \(T\) yields: \[\begin{align} && \textstyle\mathbb{E}[\sum_{t=1}^T \alpha_t \|\mathbf{s}_t\|^2] \nonumber\\ &\leq& \textstyle\mathbb{E}[ (4 \sum_{t=1}^T B_t ) + \left( 4 \sum_{t=1}^T (1-\tfrac{\alpha_{t}}{4}) (\|\mathbf{s}_{t-1}\|^2 - \|\mathbf{s}_{t}\|^2 ) \right)] \nonumber\\ &\overset{\text{\ding{\numexpr 1+171\relax}}}{\leq}& \textstyle\mathbb{E}[ \left(\sum_{t=1}^T \tfrac{12\lambda\gamma_{t-1}^2}{\alpha_{t}} \| \mathbf{m}_{t-1}\|^2 + \tfrac{ 44 (1 + \hat{g}_t)^3\|\mathbf{g}_t\|^2 }{ 1 + \sum_{i=1}^t \|\mathbf{g}_i\|^2 } \right) + 4 \left(\max_{t=1}^T (1-\alpha_{t}) \right)\cdot \left( \max_{t=1}^{T-1} \|\mathbf{s}_t\|^2 \right) ] \nonumber\\ &\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq}& \textstyle\mathbb{E}[ (1+\hat{g}_T)\cdot \sum_{t=1}^T \tfrac{12\lambda \gamma_{t-1}^2}{\alpha_{t-1}} \| \mathbf{m}_{t-1}\|^2 ] + 44 (1 + \hat{g}_T)^3 \ln(1 + \sum_{t=1}^T \|\mathbf{g}_t\|^2) \nonumber\\ && \textstyle+ 12 \left(C_g + C_f +\sigma^2 \right) \ln(e+T) \nonumber\\ &\overset{\text{\ding{\numexpr 3+171\relax}}}{\leq}& \textstyle(1+\hat{g}_T)\cdot 12\lambda \cdot 2 (1+C_g)\ln(e+T) + 44 (1 + \hat{g}_T)^3 \cdot (1+C_g) \ln(e+T) \nonumber\\ && \textstyle+ 12 \left(C_g + C_f +\sigma^2 \right) \ln(e+T) \nonumber\\ &\overset{\text{\ding{\numexpr 4+171\relax}}}{\leq}& \textstyle(1+\hat{g}_T)^3 \cdot \ln(e+T) \cdot \left( 24 \lambda (1+C_g) + 44 \cdot (1+C_g) + 12 (C_g + C_f +\sigma^2 ) \right) \nonumber\\ &\overset{\text{\ding{\numexpr 5+171\relax}}}{\leq}& \textstyle\ln^{5/2}(e+T) \cdot (1+\sqrt{C_g})^{3} \cdot \left( 24\lambda (1+C_g) + 44 \cdot (1+C_g) + 12 (C_g + C_f +\sigma^2 ) \right) \nonumber\\ &\overset{}{\leq}& \textstyle\ln^{5/2}(e+T) \cdot (1+\sqrt{C_g})^{3} \cdot \underbrace{\textstyle 88 \left( \lambda (1+C_g) + 1 + C_g + C_f +\sigma^2 \right)}_{:=C_s} , \nonumber \end{align}\] where step uses Lemma 17; step uses \(\tfrac{\alpha_{t-1}}{\alpha_t}\leq \sqrt{1+ \hat{g}_t^2} \leq 1 + \hat{g}_t\), and the standard logarithmic integral bound \(\sum_{t=1}^T \frac{\mathbf{x}_t}{1 + \sum_{i=1}^t \mathbf{x}_i} \leq \ln(1 + \sum_{t=1}^T \mathbf{x}_t)\) with \(\mathbf{x}_i=\|\mathbf{g}_i\|^2\); step uses Inequalities (20 ) and (21 ); step uses \(1+ \hat{g}_T \leq (1+ \hat{g}_T)^3\); step uses \((1+\hat{g}_T)^3 \leq (1 + \sqrt{C_g \ln (e+T)} )^3 \leq (1 + \sqrt{C_g})^3 \ln^{3/2}(e+T)\).
Using the fact that \(\tfrac{1}{\alpha_T}\leq \sqrt{1 + \sum_{t=1}^T \|\mathbf{g}_t\|^2}\), we further derive: \[\begin{align} \textstyle\mathbb{E}[ \sum_{t=1}^T \|\mathbf{s}_t\|^2] \leq \mathbb{E}[\tfrac{C_s (\ln(e+T))^{2}}{\alpha_T}] = \mathbb{E}[C_s (\ln(e+T))^{2} \sqrt{ 1 + \sum_{t=1}^T \|\mathbf{g}_t\|^2 }].\nonumber \end{align}\] ◻
Proof. Define \(c_0:= \tfrac{\theta \mu }{4}\), \(c_1:=\tfrac{\theta }{ \mu \varepsilon}\), \(c_2:=\tfrac{L\theta^2}{2 \varepsilon^2}\).
Define \(\hat{g}_t = \max_{1\leq i\leq t} \|\mathbf{g}_i\|\) and \(\alpha_t= \sqrt{\frac{1 + \frac{\tau}{t}\sum_{i=1}^t \| \mathbf{g}_i \|^2}{1 + \sum_{i=1}^t \| \mathbf{g}_i \|^2}}\), where \(\tau\in[0,1]\).
Let \(\mathbb{G}_t := \sum_{i=1}^t \|\mathbf{g}_i\|^2\) and \(\mathbb{M}_t := \sum_{i=1}^t \|\mathbf{m}_i\|^2\), with the shorthands \(\mathbb{G}:= \mathbb{G}_T\) and \(\mathbb{M}:= \mathbb{M}_T\).
Define \(\gamma_t = \min\left( \frac{\alpha_t}{ 1 + \mu \hat{g}_t^4} ,\, \left(1 + \sum_{j=1}^t \tfrac{\|\mathbf{m}_j\|^2}{\alpha_j} \right)^{-1/2}\right)\).
We define \(\iota:=1+C_g\).
We derive: \[\begin{align} \label{eq:iota} 1 + \hat{g}_T~~\overset{\text{\ding{\numexpr 1+171\relax}}}{\leq}~~\textstyle 1 + \sqrt{C_g \ln (e+T)} ~~\leq~~ \sqrt{1+C_g} \sqrt{\ln(e+T)} ~~= ~~ \sqrt{\iota} \sqrt{\ln(e+T)}, \end{align}\tag{23}\] where step uses \(\hat{g}_t:=\max_{i=1}^t \|\mathbf{g}_i\|\), and \(\|\mathbf{g}_t\|^2 \leq C_g \ln(e+t)\) for all \(t\).
We derive: \[\begin{align} \label{eq:bound:gamma:fxfxt1} \textstyle\tfrac{1}{\gamma_T}&\overset{\text{\ding{\numexpr 1+171\relax}}}{\leq}& \textstyle\max \left( \tfrac{1+\mu\hat{g}_T^4}{\alpha_T}, \big(1 + \sum_{t=1}^T \tfrac{\|\mathbf{m}_t\|^2}{\alpha_t} \big)^{1/2} \right) \nonumber\\ &\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq}& \textstyle\max \left( \iota^2 \ln^2 (e+T) \sqrt{ 1 + \mathbb{G}} , \big(1 + \mathbb{M}\sqrt{ 1+ \mathbb{G}} \big)^{1/2} \right) \nonumber\\ &\overset{\text{\ding{\numexpr 3+171\relax}}}{\leq}& \textstyle\iota^2 \ln^2(e+T)\sqrt{ 1 + \mathbb{G}} + 1 + \mathbb{M}^{1/2} (1+ \mathbb{G})^{1/4} \nonumber\\ &\overset{}{\leq}& \textstyle 2 \iota^2 \ln^2(e+T) \sqrt{ 1 + \mathbb{G}} + \mathbb{M}^{1/2} (1+ \mathbb{G})^{1/4}, \end{align}\tag{24}\] where step uses the definition of \(\gamma_T\); step uses \(1+\mu \hat{g}_T^4\leq 1+ \hat{g}_T^4 \leq (1+\hat{g}_T)^4\), and Inequality (23 ); step uses \(\sqrt{a+b}\leq \sqrt{a}+\sqrt{b}\) for all \(a,b\geq 0\).
We derive: \[\begin{align} \label{eq:sum:gamma:m2} \textstyle\sum_{t=1}^T \gamma_t \|\mathbf{m}_t\|^2 ~\overset{\text{\ding{\numexpr 1+171\relax}}}{\leq}~\textstyle\sum_{t=1}^T \tfrac{\|\mathbf{m}_t\|^2}{ \sqrt{ 1 + \sum_{j=1}^t \|\mathbf{m}_j\|^2/\alpha_j }} ~\leq~ \textstyle\sum_{t=1}^T \tfrac{\|\mathbf{m}_t\|^2}{ \sqrt{ 1 + \sum_{j=1}^t \|\mathbf{m}_j\|^2 }}~\leq ~ 2 \sqrt{ 1 + \mathbb{M}} , \end{align}\tag{25}\] where step uses \(\gamma_t\leq\left(1 + \sum_{j=1}^t \tfrac{\|\mathbf{m}_j\|^2}{\alpha_j} \right)^{-1/2}\); step uses \(\alpha_j\in(0,1)\); step uses Lemma 16(b).
Multiplying both sides of Inequality (?? ) by \(\tfrac{1+\hat{g}_t}{\gamma_t}\) yields: \[\begin{align} c_0 \mathbb{E}[\|\nabla f(\mathbf{x}_t)\|_2^2] &\leq& \mathbb{E}[ \tfrac{1+\hat{g}_t}{\gamma_t} \cdot \big( f(\mathbf{x}_{t}) - f(\mathbf{x}_{t+1}) \big) + c_1 (1+\hat{g}_t)^2 \|\mathbf{s}_t\|^2 + c_2 (1+\hat{g}_t) \gamma_t \|\mathbf{m}_t\|_2^2]. \nonumber \end{align}\] Summing this inequality over \(t\) from \(t=1\) to \(T\) yields: \[\begin{align} && \textstyle\mathbb{E}[ c_0 \sum_{t=1}^T \|\nabla f(\mathbf{x}_t)\|_2^2 ]\nonumber\\ & \leq & \textstyle\sum_{t=1}^T \tfrac{1+\hat{g}_t}{\gamma_t} \cdot \big( f(\mathbf{x}_{t}) - f(\mathbf{x}_{t+1}) \big) + c_1 \sum_{t=1}^T (1+\hat{g}_t)^2 \|\mathbf{s}_t\|^2 + c_2 \sum_{t=1}^T (1+\hat{g}_t) \gamma_t \|\mathbf{m}_t\|_2^2 \nonumber\\ & \overset{\text{\ding{\numexpr 1+171\relax}}}{\leq} & \mathbb{E}[ \textstyle\big(1+\hat{g}_T\big)\cdot \tfrac{\max_{t=1}^T f(\mathbf{x}_{t}) - f_*}{\gamma_T} + c_1 (1+\hat{g}_T)^2 \cdot \big(\sum_{t=1}^T\|\mathbf{s}_t\|^2\big) + c_2 (1+\hat{g}_T) \cdot \big(\sum_{t=1}^T \gamma_t \|\mathbf{m}_t\|_2^2 \big) ] \nonumber\\ & \overset{\text{\ding{\numexpr 2+171\relax}}}{\leq} & \textstyle\mathbb{E}[ \sqrt{\iota} \ln^{1/2}(e+T) \cdot C_f \ln (e+T) \cdot \left( 2 \iota^2 \ln^2(e+T) (1 + \mathbb{G})^{1/2} + \mathbb{M}^{1/2} (1+\mathbb{G})^{1/4} \right) \nonumber\\ && \textstyle+ c_1 \iota \ln (e+T)\cdot C_s \sqrt{1 + \mathbb{G}_T} \ln^2(e+T) + 2 c_2 \sqrt{\iota} \sqrt{\ln (e+T)} \sqrt{1+\mathbb{M}} ] \nonumber\\ & \overset{}{\leq} & \textstyle\mathbb{E}[ (2 C_f + c_1 C_s + 2 c_2) \cdot\iota^{5/2} \cdot \ln^{7/2} (e+T) \cdot (1 + \mathbb{G})^{1/2} \nonumber\\ && \textstyle+ (C_f + 2 c_2) \cdot \iota^{1/2} \cdot \ln^{3/2}(e+T) \cdot \mathbb{M}^{1/2} (1+\mathbb{G})^{1/4} ],\nonumber \end{align}\] where step uses uses Lemma 17; uses Inequality (23 ), Inequality (24 ), \(f(\mathbf{x}_t) - f_*\leq C_f \ln(e+t)\), Lemma 8 that \(\mathbb{E}\left[\sum_{t=1}^T \|\mathbf{s}_t\|^2\right]\leq C_s \sqrt{1 + \mathbb{G}_T} \ln^2(e+T)\), and Inequality (25 ).
Defining \(C_o:= \tfrac{\iota^{5/2}}{c_0} (2 C_f + 2c_2 + c_1 C_s)\), we derive: \[\begin{align} \textstyle\mathbb{E}[ \sum_{t=1}^T \|\nabla f(\mathbf{x}_t)\|_2^2 ] \leq C_o\cdot \mathbb{E}[ \ln^{7/2}(e+T) \sqrt{1 + \mathbb{G}} + \ln^{3/2}(e+T) \sqrt[4]{1+\mathbb{G}} \sqrt{\mathbb{M}} ].\nonumber \end{align}\] ◻
Proof. Define \(\mathbf{s}_t:=\mathbf{m}_t-\nabla f(\mathbf{x}_t)\).
Let \(\mathbb{G}_t := \sum_{i=1}^t \|\mathbf{g}_i\|^2\) and \(\mathbb{M}_t := \sum_{i=1}^t \|\mathbf{m}_i\|^2\), with the shorthands \(\mathbb{G}:= \mathbb{G}_T\) and \(\mathbb{M}:= \mathbb{M}_T\).
Let \(\delta:= 1 + 2 C_s + 4C_o\).
Recall that we have established the bounds for \(\sum_{t=1}^T \|\nabla f(\mathbf{x}_t)\|_2^2\) and \(\sum_{t=1}^T \|\mathbf{m}_t-\nabla f(\mathbf{x}_t)\|^2\) in Lemma 9 and Lemma 8 respectively, such that: \[\begin{align} \textstyle\mathbb{E}[\sum_{t=1}^T \|\nabla f(\mathbf{x}_t) - \mathbf{m}_t\|^2] &\leq& \textstyle C_s \ln^{2}(e+T) \sqrt{1+\mathbb{G}} , \tag{26}\\ \textstyle\mathbb{E}[\sum_{t=1}^T \|\nabla f(\mathbf{x}_t)\|_2^2] &\leq& \textstyle C_o \mathbb{E}[ \ln^{7/2}(e+T) \sqrt{1+\mathbb{G}} + \ln^{3/2}(e+T) \sqrt[4]{1+\mathbb{G}}\sqrt{\mathbb{M}} ].\tag{27} ~~~~~~~~~ \end{align}\] We derive the following results: \[\begin{align} \label{eq:sum:MMM} && \textstyle\mathbb{E}[\sum_{t=1}^T \|\mathbf{m}_t \|^2 ] \nonumber\\ &\leq& \textstyle\mathbb{E}[ 2 \sum_{t=1}^T \|\nabla f(\mathbf{x}_t) \|^2 + 2 \sum_{t=1}^T \|\nabla f(\mathbf{x}_t) - \mathbf{m}_t \|^2 ] \nonumber\\ &\overset{\text{\ding{\numexpr 1+171\relax}}}{\leq}& \textstyle\mathbb{E}[ 2 C_o \ln^{7/2}(e+T) \sqrt{1+\mathbb{G}} + 2 C_o \ln^{3/2}(e+T) \sqrt[4]{1+\mathbb{G}} \sqrt{\mathbb{M}} + 2 C_s \ln^{2}(e+T) \sqrt{1+\mathbb{G}} ] \nonumber\\ &\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq}& \textstyle\mathbb{E}[ (2C_o+2C_s) \ln^{7/2}(e+T) \sqrt{1+\mathbb{G}} + 2 C_o \ln^{3/2}(e+T) \sqrt[4]{1+\mathbb{G}}\mathbb{M}^{1/2} ] \nonumber\\ &\leq& \textstyle(2C_s+4C_o) \max\left( \ln^{7/2}(e+T) \sqrt{1+\mathbb{G}},\, \ln^{3/2}(e+T) \sqrt[4]{1+\mathbb{G}}\sqrt{\mathbb{M}} \right)\nonumber\\ &\overset{\text{\ding{\numexpr 3+171\relax}}}{\leq}& \textstyle\max\left( \delta \ln^{7/2}(e+T) \sqrt{1+\mathbb{G}},\, \delta \ln^{3/2}(e+T) \sqrt[4]{1+\mathbb{G}}\sqrt{\mathbb{M}} \right)\nonumber\\ &\overset{\text{\ding{\numexpr 4+171\relax}}}{\leq}&\textstyle\max\left( \delta \ln^{7/2}(e+T) \sqrt{1+\mathbb{G}},\, \delta^2 \ln^3(e+T) \sqrt{1+\mathbb{G}} \right)\nonumber\\ &\leq& \textstyle 2 \delta^2 \ln^{7/2}(e+T) \sqrt{1+\mathbb{G}}, \end{align}\tag{28}\] where step uses Inequalities (27 ) and (26 ); step uses \(\ln(e+T)\geq 1\) for all \(T\geq 0\); step uses \(2C_s+4C_o\leq \delta\); step uses the property that \(x \leq a\sqrt{x}\) implies \(x \leq a^2\) for all \(a,x\geq 0\).
Using Inequality (27 ), we further derive: \[\begin{align} \textstyle\mathbb{E}[\sum_{t=1}^T \|\nabla f(\mathbf{x}_t)\|_2^2 ] &\leq& \textstyle C_o\cdot \mathbb{E}[ \ln^{7/2}(e+T) \sqrt{1+\mathbb{G}} + \ln^{3/2}(e+T) \sqrt[4]{1+\mathbb{G}} \mathbb{M}^{1/2} ] \nonumber\\ &\overset{\text{\ding{\numexpr 1+171\relax}}}{\leq}& \textstyle\mathbb{E}[ C_o \ln^{7/2}(e+T) \sqrt{1+\mathbb{G}} + C_o \ln^3(e+T) \sqrt{1+\mathbb{G}} \cdot \sqrt{2} \delta ] \nonumber\\ &\leq& \textstyle(1+2) \delta^2 \ln^{7/2}(e+T) \mathbb{E}[\sqrt{1+\mathbb{G}} ] \nonumber\\ &\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq}& \textstyle\underbrace{\textstyle 3 \delta^2 \ln^{7/2}(e+T) }_{:=\Gamma}\cdot \mathbb{E}\left[ \sqrt{ 1 + 2\sum_{t=1}^T \|\mathbf{g}_t - \nabla f(\mathbf{x}_t)\|^2 + 2\sum_{t=1}^T \|\nabla f(\mathbf{x}_t)\|^2 }\right], \nonumber \end{align}\] where step uses Inequality (28 ); step uses the definition of \(\mathbb{G}:=\mathbb{G}_T\).
Taking the expectation and utilizing Jensen’s inequality, we derive: \[\begin{align} \textstyle\mathbb{E}\Big[\sum_{t=1}^T \|\nabla f(\mathbf{x}_t)\|_2^2\Big] &\overset{\text{\ding{\numexpr 1+171\relax}}}{\leq}& \textstyle\Gamma \cdot \mathbb{E}\left[ 1 + \sqrt{2\sum_{t=1}^T \|\mathbf{g}_t - \nabla f(\mathbf{x}_t)\|^2} + \sqrt{2 \sum_{t=1}^T \|\nabla f(\mathbf{x}_t)\|^2 }\right]\nonumber\\ &\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq}& \textstyle\Gamma \cdot \left( 1 + \sqrt{ 2 \sum_{t=1}^T \mathbb{E}[\|\mathbf{g}_t - \nabla f(\mathbf{x}_t)\|^2] } + \sqrt{ 2 \mathbb{E}\Big[\sum_{t=1}^T \|\nabla f(\mathbf{x}_t)\|^2\Big] } \right)\nonumber\\ &\overset{\text{\ding{\numexpr 3+171\relax}}}{\leq}& \textstyle\Gamma \cdot \left( 1 + \sqrt{ 2 T \sigma^2 } \right) + \Gamma \sqrt{ 2 \mathbb{E}\Big[\sum_{t=1}^T \|\nabla f(\mathbf{x}_t)\|^2\Big] } \nonumber\\ &\overset{\text{\ding{\numexpr 4+171\relax}}}{\leq}& \textstyle\Gamma \left( 1 + \sqrt{ 2 T \sigma^2 } \right) + \frac{1}{2} \mathbb{E}\Big[\sum_{t=1}^T \|\nabla f(\mathbf{x}_t)\|^2\Big] + \Gamma^2, \nonumber \end{align}\] where step uses \(\|\mathbf{g}_t\|^2 \leq 2\| \mathbf{g}_t - \nabla f(\mathbf{x}_t)\|^2 + 2\|\nabla f(\mathbf{x}_t)\|^2\); step uses Jensen’s inequality (\(\mathbb{E}[\sqrt{X}]\leq\sqrt{\mathbb{E}[X]}\)); step uses \(\mathbb{E}[\|\mathbf{g}_t-\nabla f(\mathbf{x}_t)\|^2]\leq \sigma^2\); step uses the Young’s Inequality (\(ab \leq \frac{1}{2}a^2 + \frac{1}{2}b^2\) with \(a=\sqrt{2}\Gamma\) and \(b=\sqrt{\mathbb{E}[\sum\|\nabla f(\mathbf{x}_t)\|^2]}\)). Rearranging the terms, we obtain: \[\begin{align} \label{eq:EEE:sum:nabla} \textstyle\mathbb{E}\Big[\sum_{t=1}^T \|\nabla f(\mathbf{x}_t)\|_2^2\Big] \leq 2\Gamma \left( 1 + \sqrt{ 2 T \sigma^2 } \right) + 2\Gamma^2. \end{align}\tag{29}\]
Using the fact that \(\frac{1}{T}\|\mathbf{a}\|_1\leq\frac{1}{\sqrt{T}}\|\mathbf{a}\|_2\) for all \(\mathbf{a}\in\mathbb{R}^T\), we evaluate the expected average gradient norm: \[\begin{align} \textstyle\mathbb{E}\Big[ \frac{1}{T}\sum_{t=1}^T \| \nabla f(\mathbf{x}_{t})\| \Big] &\leq& \textstyle\mathbb{E}\Big[ \frac{1}{\sqrt{T}} \sqrt{ \sum_{t=1}^T \| \nabla f(\mathbf{x}_{t}) \|^2 } \Big] \nonumber\\ &\overset{\text{\ding{\numexpr 1+171\relax}}}{\leq}& \textstyle\frac{1}{\sqrt{T}} \sqrt{ \mathbb{E}\Big[ \sum_{t=1}^T \| \nabla f(\mathbf{x}_{t}) \|^2 \Big] } \nonumber\\ &\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq}& \textstyle\frac{1}{\sqrt{T}} \sqrt{ 2\Gamma \left( 1 + \sqrt{ 2 T \sigma^2 } \right) + 2\Gamma^2 }\nonumber\\ &\overset{\text{\ding{\numexpr 3+171\relax}}}{=}& \textstyle\mathcal{O}\left( \frac{ \ln^{7/2}(e+T) }{T^{1/2}} + \frac{\sigma^{1/2} \ln^{7/4}(e+T) }{T^{1/4}} \right), \nonumber \end{align}\] where step uses Jensen’s inequality; step uses Inequality (29 ); step uses \(\Gamma = \mathcal{O}(\ln^{7/2}(e+T))\). ◻
Proof. Since \(\mathbf{m}_{t} = (1-\alpha) \mathbf{m}_{t-1} + \alpha \mathbf{g}_t\), using the convexity of \(\|\cdot\|^2\), we have: \[\|\mathbf{m}_t\|^2 \leq (1-\alpha) \|\mathbf{m}_{t-1}\|^2 + \alpha \|\mathbf{g}_t\|^2.\] Subtracting \((1-\alpha) \|\mathbf{m}_t\|^2\) from both sides and dividing by \(\alpha > 0\) yields: \[\textstyle\|\mathbf{m}_t\|^2 \leq \frac{1-\alpha}{\alpha} (\|\mathbf{m}_{t-1}\|^2 - \|\mathbf{m}_t\|^2) + \|\mathbf{g}_t\|^2.\] Summing this inequality over \(t=1, \dots, T\) and telescoping the differences, we obtain: \[\textstyle\sum_{t=1}^T (\|\mathbf{m}_t\|^2 - \|\mathbf{g}_t\|^2) \leq \frac{1-\alpha}{\alpha} (\|\mathbf{m}_0\|^2 - \|\mathbf{m}_T\|^2) \leq 0 ,\] where the last inequality follows from the standard initialization \(\mathbf{m}_0 = \mathbf{0}\) and \(-\|\mathbf{m}_T\|^2 \leq 0\). ◻
Proof. Define \(\hat{g}_t := \max_{i=1}^t \lVert \mathbf{g}_i \rVert\).
Since \(\mathbf{v}_{t} = (1-\beta_t) \mathbf{v}_{t-1} + \beta_t \mathbf{g}_t \odot \mathbf{g}_t\), and assuming \(\beta_t \in [0, 1]\), using the convexity of \(\lVert \cdot \rVert\) and the inequality \(\lVert \mathbf{x} \odot \mathbf{x} \rVert \leq \lVert \mathbf{x} \rVert^2\), we have: \[\begin{align} \lVert \mathbf{v}_t \rVert ~\leq~ (1-\beta_t) \lVert \mathbf{v}_{t-1} \rVert + \beta_t \lVert \mathbf{g}_t \odot \mathbf{g}_t \rVert ~\leq ~\max \left( \lVert \mathbf{v}_{t-1} \rVert, \lVert \mathbf{g}_t \rVert^2 \right). \end{align}\]
Using this inequality recursively, and assuming \(\mathbf{v}_0 = \mathbf{0}\), we obtain: \[\begin{align} \textstyle\lVert \mathbf{v}_t \rVert ~\leq~ \max \left( \lVert \mathbf{v}_0 \rVert, \max_{i=1}^t \lVert \mathbf{g}_i \rVert^2 \right) ~= ~\max_{i=1}^t \lVert \mathbf{g}_i \rVert^2 ~\leq~ \hat{g}_t^2. \end{align}\] ◻
Proof. Define \(\Theta_t := - \langle \nabla f(\mathbf{x}_t), \tfrac{\theta \mathbf{m}_t}{\varepsilon + \sqrt{\mathbf{v}_t}} \rangle\), and \(\boldsymbol{\Delta}_t:=\tfrac{ \theta\mathbf{m}_t}{\varepsilon + \sqrt{\mathbf{v}_{t-1}}} - \tfrac{\theta \mathbf{m}_t}{\varepsilon + \sqrt{\mathbf{v}_t}}\).
Let \(\varpi_t=\tfrac{ {\theta \alpha_t}/{2}}{\varepsilon + \sqrt{ \max(\mathbf{v}_{t-1}) } }>0\). Define \(\hat{g}_t:= \max_{i=1}^t \| \mathbf{g}_i \|\). We rewrite \(\Theta_t\) as: \[\begin{align} \label{eq:ema:2:Theta} \Theta_t = \underbrace{ \langle \nabla f(\mathbf{x}_t), \boldsymbol{\Delta}_t \rangle }_{:=\Gamma_1} ~+~ \underbrace{ \langle \nabla f(\mathbf{x}_t), \tfrac{- \theta\mathbf{m}_t}{\varepsilon + \sqrt{\mathbf{v}_{t-1}}} \rangle}_{:=\Gamma_2} . \end{align}\tag{30}\]
We derive: \[\begin{align} \label{eq:ema:2:Gamma:1} \Gamma_1 &\leq&\|\nabla f(\mathbf{x}_t)\| \cdot \|\boldsymbol{\Delta}_t\| \nonumber\\ &\overset{\text{\ding{\numexpr 1+171\relax}}}{\leq}& \varpi_t \|\nabla f(\mathbf{x}_t)\|^2 + \tfrac{1}{4 \varpi_t } \|\boldsymbol{\Delta}_t\|^2 \nonumber\\ &\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq}& \textstyle\varpi_t \|\nabla f(\mathbf{x}_t)\|^2 +\frac{\theta^2}{4 \varpi_t } \|\mathbf{m}_t\|^2 \cdot \left\| \tfrac{1}{\varepsilon + \sqrt{\mathbf{v}_t}} - \tfrac{1}{\varepsilon + \sqrt{\mathbf{v}_{t-1}}} \right\|_\infty^2 \nonumber\\ &\overset{\text{\ding{\numexpr 3+171\relax}}}{\leq}& \textstyle\varpi_t \|\nabla f(\mathbf{x}_t)\|^2 +\frac{\theta^2}{4 \varpi_t } \|\mathbf{m}_t\|^2 \cdot \frac{\| \mathbf{v}_t - \mathbf{v}_{t-1} \|_\infty}{\varepsilon^4} \nonumber\\ &\overset{\text{\ding{\numexpr 4+171\relax}}}{\leq }& \textstyle\varpi_t \|\nabla f(\mathbf{x}_t)\|^2 + \frac{\theta^2}{4 \varpi_t } \|\mathbf{m}_t\|^2 \cdot \frac{\beta_t \| \mathbf{g}_t^2 - \mathbf{v}_{t-1} \|_\infty}{\varepsilon^4} \nonumber\\ &\overset{\text{\ding{\numexpr 5+171\relax}}}{\leq }& \textstyle\varpi_t \|\nabla f(\mathbf{x}_t)\|^2 +\frac{\theta^2}{4 \varpi_t } \|\mathbf{m}_t\|^2 \cdot \frac{2 \beta_t \hat{g}_t^2}{\varepsilon^4} \nonumber\\ &\overset{\text{\ding{\numexpr 6+171\relax}}}{\leq }& \textstyle\varpi_t \|\nabla f(\mathbf{x}_t)\|^2 +\frac{\theta^2}{2 \varpi_t \varepsilon^4} \|\mathbf{m}_t\|^2 \cdot { \rho_t \hat{g}_t^2}, \nonumber \end{align}\tag{31}\] where step uses the Young’s Inequality; step uses \(\|\frac{\mathbf{a}}{\mathbf{b}}-\frac{\mathbf{a}}{\mathbf{c}}\|^2 =\sum_i \mathbf{a}_i^2\big(\frac{1}{\mathbf{b}_i}-\frac{1}{\mathbf{c}_i}\big)^2 \le \|\frac{1}{\mathbf{b}}-\frac{1}{\mathbf{c}}\|_\infty^2\sum_i \mathbf{a}_i^2 = \|\mathbf{a}\|^2\|\frac{1}{\mathbf{b}}-\frac{1}{\mathbf{c}}\|_\infty^2\) for all \(\mathbf{a},\mathbf{b},\mathbf{c}\in \mathbb{R}^n\); step uses the inequality \((\tfrac{1}{\varepsilon+\sqrt{a}} - \tfrac{1}{\varepsilon+\sqrt{b}})^2 \leq \tfrac{|a-b|}{\varepsilon^4}\) for all \(a,b \geq 0\); step uses \(\mathbf{v}_t - \mathbf{v}_{t-1} = \beta_t (\mathbf{g}_t^2 - \mathbf{v}_{t-1})\); step uses \(\| \mathbf{g}_t^2 - \mathbf{v}_{t-1}\|_\infty \leq \|\mathbf{g}_t^2\|_\infty + \|\mathbf{v}_{t-1}\|_\infty \leq 2 \hat{g}_t^2\); step uses \(\beta_t = \rho_t\).
We have: \[\begin{align} \label{eq:ema:2:Gamma:2} \Gamma_2 &\overset{\text{\ding{\numexpr 1+171\relax}}}{=}& \textstyle\mathbb{E}[ - \langle \nabla f(\mathbf{x}_t), \frac{ (1-\alpha_t) \theta \mathbf{m}_{t-1}}{\varepsilon+\sqrt{\mathbf{v}_{t-1}}} \rangle - \langle \nabla f(\mathbf{x}_t), \frac{ \alpha_t \theta \mathbf{g}_t}{\varepsilon + \sqrt{\mathbf{v}_{t-1}}} \rangle ] \notag \\ &\overset{\text{\ding{\numexpr 2+171\relax}}}{=}& \textstyle\mathbb{E}[ (1-\alpha_t) \Theta_{t-1} + (1-\alpha_t) \langle \nabla f(\mathbf{x}_{t-1}) - \nabla f(\mathbf{x}_{t}), \tfrac{\theta \mathbf{m}_{t-1}}{\varepsilon + \sqrt{\mathbf{v}_{t-1}}} \rangle - \alpha_t \theta \langle \nabla f(\mathbf{x}_t), \frac{ \mathbf{g}_t}{\varepsilon + \sqrt{\mathbf{v}_{t-1}}} \rangle ] \notag \\ &\overset{\text{\ding{\numexpr 3+171\relax}}}{=}& \textstyle\mathbb{E}[ (1-\alpha_t) \Theta_{t-1} + (1-\alpha_t) \langle \nabla f(\mathbf{x}_{t-1}) - \nabla f(\mathbf{x}_{t}), \tfrac{\theta \mathbf{m}_{t-1}}{\varepsilon + \sqrt{\mathbf{v}_{t-1}}} \rangle - \alpha_t \theta \langle \nabla f(\mathbf{x}_t), \frac{ \nabla f(\mathbf{x}_t) }{\varepsilon + \sqrt{\mathbf{v}_{t-1}}} \rangle] \notag \\ &\overset{\text{\ding{\numexpr 4+171\relax}}}{\leq}& \textstyle- \frac{\alpha_t \theta\|\nabla f(\mathbf{x}_t)\|^2 }{\varepsilon + \sqrt{ \max(\mathbf{v}_{t-1})}} + (1-\alpha_t) \Theta_{t-1} + \frac{ \theta (1-\alpha_t)L}{\varepsilon} \cdot \|\mathbf{m}_{t-1}\| \cdot \|\mathbf{x}_t-\mathbf{x}_{t-1}\| \notag \\ &\overset{\text{\ding{\numexpr 5+171\relax}}}{=}& \textstyle- \frac{\alpha_t \theta \|\nabla f(\mathbf{x}_t)\|^2 }{\varepsilon + \sqrt{\max(\mathbf{v}_{t-1})}} + (1-\alpha_t)\Theta_{t-1} + \frac{\theta L}{\varepsilon} \cdot \|\mathbf{m}_{t-1}\| \cdot \theta \gamma_{t-1} \cdot \|\frac{ \mathbf{m}_{t-1}}{\varepsilon+\sqrt{\mathbf{v}_{t-1}}} \| \nonumber\\ & \leq& \textstyle-\frac{\alpha_t \theta \|\nabla f(\mathbf{x}_t)\|^2 }{\varepsilon + \sqrt{\max(\mathbf{v}_{t-1})}} + (1-\alpha_t)\Theta_{t-1} + \tfrac{\theta^2 L}{\varepsilon^2} \cdot \gamma_{t-1} \|\mathbf{m}_{t-1}\|^2, \end{align}\tag{32}\] where step uses \(\mathbf{m}_t = (1-\alpha_t)\mathbf{m}_{t-1}+\alpha_t \mathbf{g}_t\); step uses the definition of \(\Theta_t := -\langle \nabla f(\mathbf{x}_t), \tfrac{\mathbf{m}_t}{\varepsilon + \sqrt{\mathbf{v}_t}} \rangle\); step uses the fact that \(\mathbb{E}[\mathbf{g}_t] = \nabla f(\mathbf{x}_t)\); step uses the \(L\)-smoothness of \(f(\cdot)\); step uses \(\mathbf{x}_{t+1} = \mathbf{x}_t - \theta \gamma_t \cdot \tfrac{\mathbf{m}_{t}}{\varepsilon+ \sqrt{\mathbf{v}_{t}}}\).
We choose \(\varpi_t=\tfrac{ {\theta \alpha_t}/{2}}{\varepsilon + \sqrt{ \max(\mathbf{v}_{t-1}) } }\). Combining Inequalities (30 ), (31 ), and (32 ) yields: \[\begin{align} && \textstyle\Theta_t - (1-\alpha_t)\Theta_{t-1}\nonumber\\ &\leq& \textstyle-\varpi_t \|\nabla f(\mathbf{x}_t)\|^2 + \tfrac{\theta^2 L}{\varepsilon^2} \gamma_{t-1} \|\mathbf{m}_{t-1}\|^2 + \frac{\theta^2}{2 \varpi_t \varepsilon^4} \|\mathbf{m}_t\|^2 \cdot { \rho_t \hat{g}_t^2} \nonumber\\ &\overset{\text{\ding{\numexpr 1+171\relax}}}{=}& \textstyle-\varpi_t \|\nabla f(\mathbf{x}_t)\|^2 + \tfrac{\theta^2 L}{\varepsilon^2} \gamma_{t-1} \|\mathbf{m}_{t-1}\|^2 + \tfrac{\theta}{\varepsilon^4} \frac{ \varepsilon + \sqrt{ \max(\mathbf{v}_{t-1}) } }{ \alpha_t } \|\mathbf{m}_t\|^2 \cdot { \rho_t \hat{g}_t^2} \nonumber\\ &\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq}& \textstyle-\varpi_t \|\nabla f(\mathbf{x}_t)\|^2 + \tfrac{\theta^2 L}{\varepsilon^2} \gamma_{t-1} \|\mathbf{m}_{t-1}\|^2 + \tfrac{\theta}{\varepsilon^4} \frac{1 }{ \alpha_t } \|\mathbf{m}_t\|^2 \cdot \rho_t (1 + \hat{g}_t) \hat{g}_t^2 \nonumber\\ &\overset{\text{\ding{\numexpr 3+171\relax}}}{\leq}& \textstyle- \underbrace{\textstyle\tfrac{\theta \alpha_t}{2(\varepsilon + \hat{g}_{t}) } \|\nabla f(\mathbf{x}_t)\|^2}_{:=D_t} + \underbrace{\textstyle\tfrac{\theta^2 L}{\varepsilon^2} \gamma_{t-1} \|\mathbf{m}_{t-1}\|^2 + \tfrac{ \theta}{\varepsilon^4 } \frac{1 }{ \alpha_t } \|\mathbf{m}_t\|^2 \cdot \rho_t (1 + \hat{g}_t)^3 }_{:=E_t}.\nonumber \end{align}\] where step uses the choice \(\varpi_t\); step uses \(\varepsilon\leq 1\) and \(\sqrt{\max(\mathbf{v}_{t-1})} \leq \hat{g}_{t-1}\leq \hat{g}_{t}\); step uses \((1+x)x^2\leq (1+x)^3\) for all \(x\geq 0\).
Using \(\Theta_{0}=0\) (since \(\mathbf{m}_0=\mathbf{0}\)) and unrolling this recurrence yields: \[\begin{align} \label{eq:LemTheta951} \Theta_t \leq \sum_{j=1}^{t} \left( \prod_{k=j+1}^t (1-\alpha_k) \right) (-D_j +E_j).\nonumber \end{align}\tag{33}\]
By the \(L\)-smoothness of \(f\), we have: \[\begin{align} \mathbb{E}[ f(\mathbf{x}_{t+1}) - f(\mathbf{x}_t)] &\leq& \mathbb{E}[ \frac{L}{2}\|\mathbf{x}_{t+1}-\mathbf{x}_t\|^2 + \langle \nabla f(\mathbf{x}_t), \mathbf{x}_{t+1}-\mathbf{x}_t\rangle ] \notag \\ &=& \mathbb{E}[ \frac{L}{2} \theta^2\gamma_t^2 \left\|\frac{\mathbf{m}_t}{\varepsilon + \sqrt{\mathbf{v}_t}}\right\|^2 - \theta \gamma_t \langle \nabla f(\mathbf{x}_t), \frac{\mathbf{m}_t}{\varepsilon + \sqrt{\mathbf{v}_t}} \rangle] \notag \\ &=& \mathbb{E}[ \frac{L}{2} \theta^2\gamma_t^2 \left\|\frac{\mathbf{m}_t}{\varepsilon + \sqrt{\mathbf{v}_t}}\right\|^2 + \theta \gamma_t \Theta_t] \notag \\ &\leq& \mathbb{E}[\frac{L}{2} \frac{\theta^2}{\varepsilon^2} \gamma_t^2\left\| \mathbf{m}_t \right\|^2 + \theta \gamma_t \sum_{j=1}^{t} \left( \prod_{k=j+1}^t (1-\alpha_k) \right) (E_j -D_j)]. \nonumber \end{align}\] ◻
Proof. Let \(S\) denote the middle term of the inequality: \(S := \sum_{t=1}^T \gamma_t \sum_{j=1}^{t} \left( \prod_{k=j+1}^t (1-\alpha_k) \right) A_j\).
By standard mathematical convention, when \(j=t\), the empty product is defined as \(\prod_{k=t+1}^t (1-\alpha_k) = 1\). Since \(\alpha_k \in (0,1)\), it holds that \((1-\alpha_k) > 0\). Given that \(A_j \geq 0\) and \(\gamma_t > 0\), all terms in the inner summation are strictly non-negative. By retaining only the final term of the inner sum (i.e., where \(j=t\)), we establish the lower bound: \[\begin{align} \textstyle S \geq \sum_{t=1}^T \gamma_t \left( \prod_{k=t+1}^t (1-\alpha_k) \right) A_t = \sum_{t=1}^T \gamma_t \cdot 1 \cdot A_t = \sum_{t=1}^T \gamma_t A_t. \end{align}\]
To establish the upper bound, we first exchange the order of summation in \(S\): \[\begin{align} \label{eq:S95swapped} S = \sum_{j=1}^T A_j \sum_{t=j}^T \gamma_t \prod_{k=j+1}^t (1-\alpha_k). \end{align}\tag{34}\] Let us define the inner summation as \(C_j := \sum_{t=j}^T \gamma_t \prod_{k=j+1}^t (1-\alpha_k)\). Since \(\gamma_t\) is a decreasing sequence, we have \(\gamma_t \leq \gamma_j\) for all \(t \geq j\). Furthermore, since \(\alpha_k\) is a decreasing sequence, we have \(\alpha_k \geq \alpha_T\) for all \(k \leq T\), which implies \(1-\alpha_k \leq 1-\alpha_T < 1\).
Using these monotonic properties, we can upper bound \(C_j\) by factoring out \(\gamma_j\) and replacing the product with a geometric progression: \[\begin{align} C_j \leq \gamma_j \sum_{t=j}^T \prod_{k=j+1}^t (1-\alpha_T) = \gamma_j \sum_{t=j}^T (1-\alpha_T)^{t-j}. \nonumber \end{align}\] By applying a change of variables \(i = t-j\), we can upper bound this finite sum by an infinite geometric series: \[\begin{align} C_j \leq \gamma_j \sum_{i=0}^{T-j} (1-\alpha_T)^i \leq \gamma_j \sum_{i=0}^{\infty} (1-\alpha_T)^i = \gamma_j \frac{1}{1 - (1-\alpha_T)} = \frac{\gamma_j}{\alpha_T}. \nonumber \end{align}\] Finally, substituting this upper bound \(C_j \leq \frac{\gamma_j}{\alpha_T}\) back into Equation (34 ), we obtain: \[S = \sum_{j=1}^T A_j C_j \leq \sum_{j=1}^T A_j \left(\frac{\gamma_j}{\alpha_T}\right) = \frac{1}{\alpha_T} \sum_{t=1}^T \gamma_t A_t.\] This completes the proof. ◻
Proof. Define \(\beta_t= \rho_t\), and \(\gamma_t = \frac{1}{1 + \mu \hat{g}_t^4} \cdot \big(1 + \sum_{j=1}^t \|\mathbf{m}_j\|^2 \big)^{-1/2}\). Let \(\hat{f}_t \triangleq f(\mathbf{x}_t) - f_*\).
Define \(E_t:=c_1 \gamma_{t-1} \|\mathbf{m}_{t-1}\|^2 + \frac{c_2}{ \alpha_t } \rho_t \|\mathbf{m}_t\|^2 (1+\hat{g}_t)^3\), and \(D_t = \tfrac{\theta \alpha_t}{2(\varepsilon + \hat{g}_t)} \|\nabla f(\mathbf{x}_t)\|^2\).
Let \(\mathbb{G}_t := \sum_{i=1}^t \|\mathbf{g}_i\|^2\) and \(\mathbb{M}_t := \sum_{i=1}^t \|\mathbf{m}_i\|^2\), with the shorthands \(\mathbb{G}:= \mathbb{G}_T\) and \(\mathbb{M}:= \mathbb{M}_T\).
Using the Cauchy-Schwarz inequality and a standard consequence of \(L\)-smoothness (Lemma 20) that: \[\mathbb{E}[\|\mathbf{g}_t\|^2] ~\leq~ \mathbb{E}[2\|\mathbf{g}_t - \nabla f(\mathbf{x}_t)\|^2 + 2\|\nabla f(\mathbf{x}_t)\|^2] ~\leq~ 2\sigma^2 + \mathbb{E}[ 4 L( f(\mathbf{x}_t) - f_* )]. \label{eq:gggg}\tag{35}\]
We derive: \[\begin{align} \label{eq:bound:f:11} \textstyle\sum_{t=1}^T \gamma_t^2\left\| \mathbf{m}_t \right\|^2 ~~\leq~~ \textstyle\sum_{t=1}^T \tfrac{\left\| \mathbf{m}_t \right\|^2}{ 1 + \sum_{j=1}^t \|\mathbf{m}_j\|^2} ~~\leq ~~\textstyle\ln(1 + \sum_{t=1}^T \|\mathbf{m}_t\|^2). \end{align}\tag{36}\]
We derive: \[\begin{align} \label{eq:ratio:ba} \tfrac{\sqrt{1 + \tfrac{\tau}{t}\mathbb{G}_t} \cdot (1+\hat{g}_t)^3 }{ 1+\mu\hat{g}_t^4} ~~\leq~~ \tfrac{ (1 + \hat{g}_t) (1+\hat{g}_t )^3}{1+\mu\hat{g}_t^4}~~=~~ \tfrac{ (1+\hat{g}_t)^4}{1+\mu\hat{g}_t^4} ~~\leq~~ \tfrac{8}{\mu}. \end{align}\tag{37}\]
We derive: \[\begin{align} \label{eq:bound:f:22} && \textstyle\sum_{t=1}^T \gamma_t \sum_{j=1}^{t} \left( \prod_{k=j+1}^t (1-\alpha_k) \right) E_j \nonumber\\ &\overset{\text{\ding{\numexpr 1+171\relax}}}{=}& \textstyle\sum_{t=1}^T \gamma_t \sum_{j=1}^{t} \left( \prod_{k=j+1}^t (1-\alpha_k) \right) \left( c_1 \gamma_{j-1} \|\mathbf{m}_{j-1}\|^2 + \frac{c_2}{ \alpha_j } \rho_j \|\mathbf{m}_j\|^2 (1+ \hat{g}_j)^3 \right) \nonumber\\ &\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq}&\textstyle\tfrac{1}{\alpha_T} \sum_{t=1}^T \gamma_t \left( c_1 \gamma_{t-1} \|\mathbf{m}_{t-1}\|^2 + \frac{c_2}{ \alpha_t } \rho_{t} \|\mathbf{m}_t\|^2 (1+\hat{g}_t)^3 \right) \nonumber\\ &\overset{\text{\ding{\numexpr 3+171\relax}}}{\leq}& \textstyle\left( \tfrac{c_1}{\alpha_T} \sum_{t=1}^T \gamma_{t-1}^2 \|\mathbf{m}_{t-1}\|^2 \right) + \left(\tfrac{c_2}{\alpha_T^2} \sum_{t=1}^T \gamma_t \rho_{t} \|\mathbf{m}_t\|^2 (1+\hat{g}_t)^3 \right) \nonumber\\ &\overset{\text{\ding{\numexpr 4+171\relax}}}{\leq}& \textstyle\left( \tfrac{c_1}{\alpha_T} \sum_{t=1}^T \gamma_{t-1}^2 \|\mathbf{m}_{t-1}\|^2 \right) + \left(\tfrac{c_2}{\alpha_T^2} \sum_{t=1}^T \tfrac{( 1 + \mathbb{M}_t )^{-1/2}}{1 + \mu \hat{g}_t^4} \cdot \sqrt{\tfrac{ 1 + \tfrac{\tau}{t} \mathbb{G}_t}{ 1 + \mathbb{G}_t } } \cdot \|\mathbf{m}_t\|^2 (1+\hat{g}_t)^3 \right) \nonumber\\ &\overset{\text{\ding{\numexpr 5+171\relax}}}{\leq}& \textstyle\left( \tfrac{c_1}{\alpha_T} \sum_{t=1}^T \gamma_{t-1}^2 \|\mathbf{m}_{t-1}\|^2 \right) + \left(\tfrac{c_2}{\alpha_T^2} \tfrac{8}{\mu} \sum_{t=1}^T \tfrac{1}{ \sqrt{1 + \mathbb{M}_t} } \tfrac{ 1 }{\sqrt{ 1 + \mathbb{G}_t } } \cdot \|\mathbf{m}_t\|^2 \right) \nonumber\\ &\overset{\text{\ding{\numexpr 6+171\relax}}}{\leq}& \textstyle\left( \tfrac{c_1}{\alpha_T} \sum_{t=1}^T \gamma_{t}^2 \|\mathbf{m}_{t}\|^2 \right) + \left(\tfrac{c_2}{\alpha_T^2} \tfrac{8}{\mu} \sum_{t=1}^T \tfrac{\|\mathbf{m}_t\|^2 }{ 1 + \mathbb{M}_t } \right) \nonumber\\ &\overset{\text{\ding{\numexpr 7+171\relax}}}{\leq}& \textstyle\left( \tfrac{c_1}{\alpha_T} \sum_{t=1}^T \gamma_{t}^2 \|\mathbf{m}_{t}\|^2 \right) + \tfrac{c_2}{\alpha_T^2} \tfrac{8}{\mu} \ln( 1 + \mathbb{M}) \nonumber\\ &\overset{\text{\ding{\numexpr 8+171\relax}}}{\leq}& \textstyle\left( \tfrac{c_1}{\alpha_T} + \tfrac{8 c_2}{\alpha_T^2 \mu} \right) \ln( 1 + \mathbb{M}) ~~\leq~~ \textstyle\left( \tfrac{ c_1 + 8 c_2}{\alpha^2 \mu} \right) \ln( 1 + \mathbb{M}), \end{align}\tag{38}\] where step uses the definition of \(E_j\); step uses the second inequality in Lemma 13; step uses \(\gamma_t\leq \gamma_{t-1}\) and \(\alpha_t\leq \alpha_{t-1}\) for all \(t\); step uses \(\mathbf{m}_0=\mathbf{0}\) and \(\gamma_t=\frac{1}{1 + \mu \hat{g}_t^2} \cdot \big(1 + \mathbb{M}_t \big)^{-1/2}\); step uses Inequality (37 ); step uses Lemma 10 that \(\sum_{t=1}^T \|\mathbf{m}_t\|_2^2 \le\sum_{t=1}^T \|\mathbf{g}_t\|_2^2\), and results of shifting the summation since \(\|\mathbf{m}_0\|^2=0\); step uses Lemma 16(a) that \(\sum_{t=1}^T \frac{b_t}{ 1 + \sum_{i=1}^t b_i } \leq \ln\left(1+ \sum_{t=1}^T b_t \right)\); step uses \(\alpha_t=\alpha\in(0,1)\).
Dropping the non-positive term \(D_j\) in Inequality ?? yields: \[\textstyle\mathbb{E}[\hat{f}_{t+1} - \hat{f}_t] \leq \mathbb{E}[c_3 \gamma_t^2 \| \mathbf{m}_t \|^2 + \gamma_t \sum_{j=1}^{t} \left( \prod_{k=j+1}^t (1-\alpha_k) \right) E_j].\]
Summing this recursion from \(t=1\) to \(T-1\) gives: \[\begin{align} \textstyle\mathbb{E}[\hat{f}_T] &\leq& \textstyle\mathbb{E}[\hat{f}_1 + c_3 \sum_{t=1}^{T-1} \gamma_t^2 \| \mathbf{m}_t \|^2 + \sum_{t=1}^{T-1} \gamma_t \sum_{j=1}^{t} \left( \prod_{k=j+1}^t (1-\alpha_k) \right) E_j ] \nonumber\\ &\leq& \textstyle\mathbb{E}[ \hat{f}_1 + c_3 \sum_{t=1}^{T} \gamma_t^2 \| \mathbf{m}_t \|^2 + \sum_{t=1}^{T} \gamma_t \sum_{j=1}^{t} \left( \prod_{k=j+1}^t (1-\alpha_k) \right) E_j ] \nonumber\\ &\overset{\text{\ding{\numexpr 1+171\relax}}}{\leq}& \mathbb{E}[\textstyle\hat{f}_1 + \left( c_3 + \tfrac{c_1 + 8 c_2}{\alpha^2 \mu} \right) \ln(1 + \sum_{t=1}^T \|\mathbf{g}_t\|^2) ]\nonumber\\ &\overset{}{\leq}& \textstyle\mathbb{E}[ \big( \hat{f}_1 + c_3 + \tfrac{c_1 + 8 c_2}{\alpha^2 \mu } \big) \cdot \ln(e + \sum_{t=1}^T \|\mathbf{g}_t\|^2) ]\nonumber\\ &\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq}& \textstyle\mathbb{E}[\big( \hat{f}_1 + c_3 + \tfrac{c_1 + 8 c_2}{\alpha^2 \mu} \big) \cdot \ln (e + 4T(\sigma^2+L \big(\max_{t=1}^T \hat{f}_t \big)))] , \nonumber \end{align}\] where step uses Inequalities (36 ) and (38 ); step uses Inequality (35 ).
Defining \(A_t \triangleq 4 \sigma^2 + 4 L \mathbb{E}[\hat{f}_t]\) and substituting this definition into the bound above yields: \[\frac{A_T - 4 \sigma^2}{4L} \leq \Big( \hat{f}_1 + c_3 + \tfrac{c_1 + 8 c_2}{\alpha^2 \mu} \Big) \ln \Big(e + T \max_{1 \leq t \leq T} A_t \Big).\] Since \(\ln \Big(e + T \max_{1 \leq t \leq T} A_t \Big)\geq 1\), we further obtain: \[\mathbb{E}[A_T] \leq \underbrace{\textstyle\big( 4 L \big( \hat{f}_1 + c_3 + \tfrac{c_1 + 8 c_2}{\alpha^2 \mu } \big) + 4\sigma^2\big)}_{:=\chi}\cdot \ln \Big(e + T \max_{1 \leq t \leq T} A_t \Big).\] Invoking Lemma 18, this inequality directly implies: \[\mathbb{E}[A_T] \leq (1+\chi)^3 \ln(e+T).\] Translating this result back to the function suboptimality, we derive: \[\textstyle\mathbb{E}[f(\mathbf{x}_T) - f_*] ~=~ \mathbb{E}[\hat{f}_T]~=~ \mathbb{E}[\frac{A_T - 4 \sigma^2}{4L}] ~\leq~ \underbrace{\textstyle\frac{(1+\chi)^3 }{4 L} }_{:=C_f} \cdot \ln(e+T).\]
Substituting this bound back into (35 ), we have for all \(t \geq 1\): \[\mathbb{E}[\|\mathbf{g}_t\|^2] \leq 4 \mathbb{E}[\sigma^2 + L \hat{f}_t] ~\leq ~\textstyle 4 \big(\sigma^2 + L C_f \ln(e+T)\big) ~\leq ~ \underbrace{ (4 \sigma^2 + 4 L C_f ) }_{:=C_g} \ln(e+T).\] ◻
Proof. Define \(D_t = \tfrac{\theta \alpha_t}{2(\varepsilon + \hat{g}_t)} \|\nabla f(\mathbf{x}_t)\|^2\) and \(E_t:=c_1\gamma_{t-1} \|\mathbf{m}_{t-1}\|^2 + c_2 \frac{\rho_t }{ \alpha_t } \|\mathbf{m}_t\|^2 \cdot (1 + \hat{g}_t)^3\).
Define \(\iota:=1 + C_g\), and \(C_o:=\frac{2 \iota}{ \theta \alpha} \cdot \big( 2 \iota^2 \cdot \frac{c_1 + c_2}{\alpha^2} + C_f \iota^2 + 2c_3 \big)\).
Let \(\mathbb{G}_t := \sum_{i=1}^t \|\mathbf{g}_i\|^2\) and \(\mathbb{M}_t := \sum_{i=1}^t \|\mathbf{m}_i\|^2\), with the shorthands \(\mathbb{G}:= \mathbb{G}_T\) and \(\mathbb{M}:= \mathbb{M}_T\).
We derive: \[\begin{align} \label{eq:iota:2} 1 + \hat{g}_T~\overset{\text{\ding{\numexpr 1+171\relax}}}{\leq}~\textstyle 1 + \sqrt{C_g \ln (e+T)} \leq \sqrt{\iota} \sqrt{\ln(e+T)}, \end{align}\tag{39}\] where step uses \(\hat{g}_t:=\max_{i=1}^t \|\mathbf{g}_i\|\), and \(\|\mathbf{g}_t\|^2 \leq C_g \ln(e+t)\) for all \(t\).
Dividing both sides of Inequality (?? ) by \(\gamma_t\), we have: \[\begin{align} &&\textstyle\mathbb{E}[ \sum_{j=1}^{t} \left( \prod_{k=j+1}^t (1-\alpha_k) \right) D_j ]\nonumber\\ &\leq& \textstyle\mathbb{E}[ \frac{f(\mathbf{x}_{t}) - f(\mathbf{x}_{t+1})}{\gamma_t} + c_3 \gamma_t \|\mathbf{m}_t\|^2 + \sum_{j=1}^{t} \left( \prod_{k=j+1}^t (1-\alpha_k) \right) E_j]. \nonumber \end{align}\] Telescoping this inequality over \(t\) from \(1\) to \(T\) yields our core global bounding inequality: \[\begin{align} \label{eq:core:telescoping} && \textstyle\underbrace{ \textstyle\mathbb{E}[ \sum_{t=1}^T \sum_{j=1}^{t} \left( \prod_{k=j+1}^t (1-\alpha_k) \right) D_j] }_{\text{Term I (Descent)}} \nonumber\\ &\leq& \textstyle\underbrace{ \textstyle\mathbb{E}[ \sum_{t=1}^T \sum_{j=1}^{t} \left( \prod_{k=j+1}^t (1-\alpha_k) \right) E_j] }_{\text{Term II (Penalties)}} + \textstyle\underbrace{ \mathbb{E}[\textstyle\sum_{t=1}^T (\frac{f(\mathbf{x}_{t}) - f(\mathbf{x}_{t+1})}{\gamma_t} + c_3 \gamma_t \|\mathbf{m}_t\|^2 )]}_{\text{Term III (Objective \& Momentum)}}. \end{align}\tag{40}\] The remainder of the proof bounds these three terms separately.
By applying the lower bound from the EMA Accumulation Bound in Lemma 13, we derive: \[\begin{align} \label{eq:bound:TermI} \text{Term I} &\overset{}{\geq}& \textstyle\mathbb{E}[\sum_{t=1}^T D_t] = \mathbb{E}[\sum_{t=1}^T \frac{\theta \alpha_t}{2(\varepsilon + \hat{g}_t)} \|\nabla f(\mathbf{x}_t)\|^2] \nonumber\\ &\overset{\text{\ding{\numexpr 1+171\relax}}}{\geq}& \mathbb{E}[ \textstyle\frac{\theta\alpha_T}{2 (\varepsilon+\hat{g}_T)} \sum_{t=1}^T \|\nabla f(\mathbf{x}_t)\|^2] \nonumber\\ &\overset{\text{\ding{\numexpr 2+171\relax}}}{\geq}& \mathbb{E}[\textstyle\frac{\theta\alpha_T}{2 \iota \sqrt{ \ln (e+T)} } \sum_{t=1}^T \|\nabla f(\mathbf{x}_t)\|^2], \end{align}\tag{41}\] where step uses the fact that \(\alpha_t\) in non-increasing, and \(\hat{g}_t\) is increasing; step applies Inequality (39 ).
Applying the upper bound from Lemma 13, assuming \(\mathbf{m}_0 = \mathbf{0}\) and \(\beta_t \leq 1\), we derive: \[\begin{align} \label{eq:bound:TermIII} \textstyle\text{Term II} &\overset{}{\leq}& \textstyle\mathbb{E}[\frac{1}{\alpha_T} \sum_{t=1}^T E_t ] = \mathbb{E}[ \frac{1}{\alpha_T} \sum_{t=1}^T \left( c_1 \gamma_{t-1} \|\mathbf{m}_{t-1}\|^2 + \frac{c_2}{ \alpha_t } \rho_t \|\mathbf{m}_t\|^2 (1+\hat{g}_t)^3 \right) ] \nonumber\\ &\overset{\text{\ding{\numexpr 1+171\relax}}}{\leq}& \textstyle\mathbb{E}[ \frac{c_1}{\alpha_T} \sum_{t=1}^T \frac{(1+\hat{g}_t)^3}{1 + \mu \hat{g}_t^4} \cdot \big(1 + \sum_{j=1}^t \|\mathbf{m}_j\|^2 \big)^{-1/2} \|\mathbf{m}_{t}\|^2 + \frac{c_2}{\alpha_T^2} (1+\hat{g}_T)^3 \sum_{t=1}^T \rho_t \|\mathbf{m}_t\|^2 ] \nonumber\\ &\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq}&\textstyle\mathbb{E}[ \left( \frac{c_1}{\alpha_T}\cdot (1+\hat{g}_T)^3 + \frac{c_2}{\alpha_T^2} (1+\hat{g}_T)^4 \right) \sum_{t=1}^T \frac{\|\mathbf{m}_t\|^2}{ \sqrt{ 1 + \sum_{i=1}^t \|\mathbf{m}_i\|^2} }] \nonumber\\ &\overset{}{\leq}&\textstyle\mathbb{E}[ 2\left( \frac{c_1}{\alpha_T}+ \frac{c_2}{\alpha_T^2} \right) (1+\hat{g}_T)^4 \sqrt{1 + \sum_{t=1}^T \|\mathbf{m}_t\|^2}] \nonumber\\ &\overset{\text{\ding{\numexpr 3+171\relax}}}{\leq}& \textstyle\mathbb{E}[ 2\left( \frac{c_1+c_2}{\alpha^2} \right) \cdot \iota^2 \cdot \ln^2(e+T) \sqrt{1 + \mathbb{M}}], \end{align}\tag{42}\] where step uses the results of shifting the index for the first sum (since \(\mathbf{m}_0=\mathbf{0}\)) and the monotonic properties of \(\alpha_t\) and \(\hat{g}_t\), and the definition of \(\gamma_t\); step uses \(\rho_t \leq \sqrt{\tfrac{1 + \hat{g}_t^2}{1 + \mathbb{G}_t}} \leq \sqrt{\tfrac{1}{1 + \mathbb{M}_t}} \cdot (1+\hat{g}_t)\),and the standard integral bound \(\sum_{t=1}^T \frac{x_t}{\sqrt{1+\sum_{i=1}^t x_i}} \leq 2\sqrt{1+\sum_{t=1}^T x_t}\); step uses Inequality (39 ), and \(\alpha_T=\alpha\).
We derive the following results: \[\begin{align} \label{eq:bound:TermII} \text{Term III} &\overset{\text{\ding{\numexpr 1+171\relax}}}{\leq}& \textstyle\frac{\max_{t=1}^T f(\mathbf{x}_{t}) - f_*}{\gamma_T} + c_3 \sum_{t=1}^T \frac{\|\mathbf{m}_t\|^2}{ \sqrt{ 1 + \sum_{i=1}^t \|\mathbf{m}_i\|^2}} \nonumber\\ &\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq}& \textstyle C_f \ln(e+T) \cdot (1+\mu\hat{g}_T^4) \sqrt{1+\mathbb{M}} + 2 c_3 \sqrt{1+\mathbb{M}} \nonumber\\ &\overset{\text{\ding{\numexpr 3+171\relax}}}{\leq}& \textstyle C_f \ln(e+T) \cdot \iota^2 \ln^2(e+T) \sqrt{1+\mathbb{M}} + 2 c_3 \sqrt{1+\mathbb{M}} \nonumber\\ &\overset{}{\leq} & \left( C_f \iota^2 + 2c_3 \right) \ln^{2}(e+T) \sqrt{1+\mathbb{M}}, \end{align}\tag{43}\] where step uses Lemma 17 and the fact that \(\gamma_t\leq \big(1 + \sum_{j=1}^t \|\mathbf{m}_j\|^2 \big)^{-1/2}\); step uses Lemma 14, the fact that \(\frac{1}{\gamma_T} = (1+\mu\hat{g}_T^4) \sqrt{1+\mathbb{M}}\) with \(\mathbb{M}:=\sum_{t=1}^T\|\mathbf{m}_t\|^2\), and Lemma 16(b); step uses \(1+\hat{g}_T^4\leq (1+\hat{g}_T)^4\leq \iota^2\ln^2(e+T)\), as shown in Inequality (39 ).
Substituting the bounds from (41 ), (42 ), and (43 ) back into the core inequality (40 ) and rearranging for \(\sum_{t=1}^T \|\nabla f(\mathbf{x}_t)\|^2\), we have: \[\begin{align} && \textstyle\frac{\theta \alpha}{2 \iota \sqrt{ \ln (e+T)} } \sum_{t=1}^T \|\nabla f(\mathbf{x}_t)\|^2 \nonumber\\ &\leq &\textstyle 2 \iota^2 \cdot \frac{c_1 + c_2}{\alpha^2} \ln^2(e+T) \sqrt{1 + \mathbb{M}} + \left( C_f \iota^2 + 2c_3 \right) \ln^2(e+T) \sqrt{1+\mathbb{M}} \nonumber\\ &\leq &\textstyle\big( 2 \iota^2 \cdot \frac{c_1 + c_2}{\alpha^2} + C_f \iota^2 + 2c_3 \big) \ln^{2}(e+T) \sqrt{1+\mathbb{M}} \nonumber\\ \end{align}\] Multiplying both sides by \(\frac{2 \iota \sqrt{\ln(e+T)}}{ \theta \alpha}\) yields: \[\begin{align} \textstyle\mathbb{E}[\sum_{t=1}^T \|\nabla f(\mathbf{x}_t)\|^2] &\leq & \textstyle\mathbb{E}[ \frac{2 \iota}{ \theta \alpha} \cdot \big( 2 \iota^2 \cdot \frac{c_1 + c_2}{\alpha^2} + C_f \iota^2 + 2c_3 \big) \ln^{5/2}(e+T) \sqrt{1+\mathbb{M}} ]\nonumber\\ &\overset{\text{\ding{\numexpr 1+171\relax}}}{=}& \textstyle\mathbb{E}[ C_o \ln^{5/2}(e+T) \sqrt{1+\sum_{t=1}^T \|\mathbf{m}_t\|^2 } ]\nonumber\\ &\overset{\text{\ding{\numexpr 2+171\relax}}}{\leq}& \textstyle\mathbb{E}[ C_o \ln^{5/2}(e+T) \sqrt{1+\sum_{t=1}^T \|\mathbf{g}_t\|^2 } ], \nonumber \end{align}\] where step uses the definition of \(C_o\); step uses Lemma 10 that \(\sum_{t=1}^T \|\mathbf{m}_t\|_2^2 \le\sum_{t=1}^T \|\mathbf{g}_t\|_2^2\). ◻
Proof. We derive: \[\begin{align} \textstyle\mathbb{E}[\sum_{t=1}^T \|\nabla f(\mathbf{x}_t)\|^2] &\leq& \textstyle C_o \ln^{5/2}(e+T) \sqrt{1+\sum_{t=1}^T \|\mathbf{g}_t\|^2} \nonumber\\ & \leq & \textstyle\underbrace{C_o \ln^{5/2}(e+T)}_{:=\Gamma} \sqrt{1+2 \sum_{t=1}^T \|\mathbf{g}_t - \nabla f(\mathbf{x}_t)\|^2 + 2\sum_{t=1}^T \|\nabla f(\mathbf{x}_t)\|^2}. \nonumber \end{align}\] Using the same strategy as in Theorem 1, we have: \[\begin{align} \textstyle\mathbb{E}\Big[ \frac{1}{T}\sum_{t=1}^T \| \nabla f(\mathbf{x}_{t})\| \Big] &\leq& \textstyle\frac{1}{\sqrt{T}} \sqrt{ 2\Gamma \left( 1 + \sqrt{ 2 T \sigma^2 } \right) + 2\Gamma^2 }\nonumber\\ &\overset{\text{\ding{\numexpr 1+171\relax}}}{=}& \textstyle\mathcal{O}\left( \frac{ \ln^{5/2}(e+T) }{T^{1/2}} + \frac{\sigma^{1/2} \ln^{5/4}(e+T) }{T^{1/4}} \right), \nonumber \end{align}\] where step uses \(\Gamma = \mathcal{O}(\ln^{5/2}(e+T))\). ◻