A Comprehensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
Authors: Ruinan Jin
Xiao Li
Yaoliang Yu
Baoxiang Wang
Venue: ICML 2025 poster (2025)
Keywords: Adam
ABC Inequality
Sample Complexity
Almost Sure Convergence
L_1 Convergence
Primary area: optimization->stochastic
TL;DR: A theoretical paper on the convergence of Adam

Abstract: Adaptive moment estimation (Adam) is a cornerstone optimization algorithm in deep learning, widely recognized for its flexibility with adaptive learning rates and efficiency in handling large-scale data. However, despite its practical success, the theoretical understanding of Adam's convergence has been constrained by stringent assumptions, such as almost surely bounded stochastic gradients or uniformly bounded gradients, which are more restrictive than those typically required for analyzing stochastic gradient descent (SGD).

In this paper, we introduce a novel and comprehensive framework for analyzing the convergence properties of Adam. This framework offers a versatile approach to establishing Adam's convergence. Specifically, we prove that Adam achieves asymptotic (last iterate sense) convergence in both the almost sure sense and the \(L_1\) sense under the relaxed assumptions typically used for SGD, namely \(L\)-smoothness and the ABC inequality. Meanwhile, under the same assumptions, we show that Adam attains non-asymptotic sample complexity bounds similar to those of SGD.

A Comprehensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
Ruinan Jin
Xiao Li
Yaoliang Yu 34 Baoxiang Wang" 24
Abstract
widespread use, the theoretical understanding of Adam's convergence is not as advanced as its practical success. Pre- vious studies have often imposed stringent assumptions on the loss function and stochastic gradients, such as uniformly bounded loss functions and almost surely bounded gradi- ents (Reddi al., 2018; Zou Shen, 2019), which are more restrictive than those required for analyzing classical stochastic gradient descent (SGD).
Adaptive moment estimation (Adam) is corner- stone optimization algorithm in deep learning. widely recognized for its flexibility with adaptive learning rates and efficiency in handling large- scale data. However, despite its practical success, the theoretical understanding of Adam's 's conver- gence has been constrained by stringent assump- tions, such almost surely bounded stochastic gradients or uniformly bounded gradients, which are more restrictive than those typically required for analyzing stochastic gradient descent (SGD).
In this paper. we introduce a novel and comprehensive framework for analyzing the convergence properties of Adam. Our framework unifies various aspects of conver- gence analysis, including non-asymptotic (average iterate sense) sample complexity, asymptotic (last iterate sense) almost sure convergence, and asymptotic L1 convergence. Crucially, we demonstrate that under this framework, Adam can achieve convergence under the same assumptions typi- cally used for SGD SGD-namely, the L-smooth condition and the ABC inequality (Lg sense) (Khaled & Richtárik, 2023; Bottou, 2010; Ghadimi & Lan, 2013).
In this paper, we introduce a novel and compre- hensive framework for analyzing the convergence properties of Adam. This framework offers a versatile approach to establishing Adam's conver- gence. Specifically, we prove that Adam achieves asymptotic (last iterate sense) convergence in both the almost sure sense and the L1 sense un- der the relaxed assumptions typically used for SGD, namely [-smoothhess and the ABC inequal- ity. Meanwhile, under the same assumptions, we show that Adam attains non- non-asymptotic sample complexity bounds similar to those of SGD.
Several recent works have attempted to relax the stringent conditions required for Adam's 's convergence, each focusing on different aspects of the stochastic gradient assumptions and convergence guarantees. However, limitations still exist in terms of assumptions and the types of convergence results obtained. Table provides the references and a summary of the works and compares the assumptions on stochastic gradients, the resulting complexities, and the convergence properties achieved.
1. Introduction
Adaptive Moment Estimation (Adam) is one of the most widely used optimization algorithms in deep learning due to its adaptive learning rate properties and efficiency in han- dling large-scale data (Kingma & Ba, 2014). Despite its
Our approach builds upon these prior works and seeks to offer a more comprehensive and general framework for analysis. In contrast to these previous works, we study Adam under the ABC inequality, which is more general and less restrictive compared the assumptions made in the previous studies. Our analysis successfully establishes non-asymptotic sample complexity and achieves asymptotic almost sure convergence and L1 convergence under condi- tions that align with those required for SGD. This makes our framework theoretically sound and versatile for analyzing multiple convergence properties of Adam. Our framework might also be of independent interest in analyzing different variants of Adam. In summary, our work presents a novel and general theoretical framework for Adam, unifying vari-
'Centre for Artificial Intelligence and Robotics. Hong Kong Institute of Seience and Innovation, Chinese Academy of Sci- ences, New Territories, Hong Kong, China. Most of the work of Ruinan Jin was completed during he was with the Vector Insti- tute, Toronto, Canada, and The Chinese University of Hong Kong, Shenzhen, China. 'The Chinese University of Hong Kong, Shen- zhen, China Uniierssity of Waterloo, Waterloo, Canada VVector Institute, Toronto, Canada. Correspondence to: Xiao Li <lix- i cdhk.edu.en>.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
ous convergence properties. This framework demonstrates that Adam's ss convergence guarantees can be aligned with those of SGD, which justifies the applicability of Adam across a wide range of machine learning problems.
Wang et al. (2023) have highlighted that this assumption is unrealistic in many common machine learning frameworks, failing to hold even for simple quadratic functions, let alone for deep neural networks. While these works achieved al- most sure convergence and, in some cases, I1 convergence, the complexity result they obtained includes (11/p).
1.1. Related Works
In recent years, the convergence properties of Adam have been extensively studied, with various works focusing on different assumptions about stochastic gradients and the types of convergence guarantees provided. In the follow- ing discussion, we categorize and review key contributions based on the different types of stochastic gradient assump- tions they employ, as summarized in Table 1.
Ly Bounded Stochastic Gradients: Zou et al. (2019) ana- lyzed Adam under the assumption of L2 bounded stochastic gradients. Although this condition is milder than the almost surely bounded gradients assumption, it is still stronger than the traditional affine noise variance condition and the ABC inequality. In the standard analytical framework, this as- sumption can at best be weakened to the coordinate affine noise variance condition, which remains more restrictive than the assumptions typically considered for SGD. At the same time, this work focused on complexity analysis with- out addressing asymptotic convergence.
Bounded Variance and Coordinate Affine Noise Vari- Wang et al. (2024a) considered Adam's 's conver- gence under the assumption of bounded variance or co- ordinate affine noise variance. The coordinate affine noise variance condition (Eq. (10)) particularly stringent as it requires that each component of the stochastic gradient sat- isfies an affine noise variance inequality, which is stronger than the traditional affine noise variance condition (Eq. (9)) applied to the entire gradient. Under these assumptions, Wang et al. successfully achieved a complexity free of O11p)). However, their work did not focus on analyzing almost sure convergence or L1 convergence, as the primary emphasis was the sample complexity of the algorithm's behavior.
ance:
Randomly Reshuffled Stochastic Gradients: In other works, such as those by Zhang et al. (2022) and Wang et al. (2024b), the authors considered the case where the stochas- tic gradients are randomly reshuffled. Randomly reshuffled stochastic gradients represent a special case where the gra- dients are typically assumed to satisfy certain inequalities almost surely. This reliance on almost sure properties forms a much stronger and more restrictive analytical framework compared to those based traditional affine noise variance conditions the ABC incquality. Mcanwhile, they did not focus on analyzing the asymptotic convergence property.
Exponential-Taildt Affine Variance Noise Condition Hong & Lin (2024) explored the assumption of affine vari- ance noise with an exponential tail distribution (Fq. (11)), which closely approximates the almost-sure form of affine variance noise. The exponential-taile affine variance noise condition is stronger than the traditional affine variance noise assumption, which is based on the second moment of the stochastic gradient. Under these assumptions, they successfully derived a complexity that eliminates (1/p)). However, their work did not focus on analyzing almost sure convergence or L1 convergence, as their primary emphasis was on the sample complexity of the algorithm's 's perfor- mance.
2. Preliminaries
In this section, we introduce the necessary preliminaries and establish the foundational framework for our conver- gence analysis of Adam. We begin by recalling the Adam optimization algorithm. We then state the assumptions that will be used throughout our analysis. These assumptions are standard in stochastic optimization and are crucial for deriving our main results. By laying out these assumptions explicitly, we also facilitate a clear comparison with the conditions used in previous works, highlighting the less restrictive nature of our approach.
Almost Surely Bounded Stochastic Gradients: Several works, including He al. (2023) and Xiao et al. (2024), have explored Adam's convergence under the assumption that the stochastic gradients are almost surely bounded. This particularly strong assumption, as it implies several other commonly made assumptions about stochastic gradients, such as bounded variance, affine noise variance, coordinate affine noise variance, and sub- Gaussian properties. The as- sumption is often impractical in non-convex settings where gradients can become unbounded. Moreover, studies in
2.1. Adam
Adam is an extension of SGD that computes adaptive learn- ing rates for each parameter by utilizing estimates of the first and second moments of the gradients.
It combines the advantages of two other extensions of SGD: AdaGrad, which works well with sparse gradients, and RM- SProp, which works well in online and non- con-stationary set- tings.
2

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
Table 1. Comparison of Assumptions and Convergence Results. (+) The smoothing term is often set to small values like 10-a in practice. It is difficult and relevant avoid the O(poly()) (2)) dependence (Wang et al., 2024a), which our analysis achieves. The work Tocuses on learning rates and hyperparameters dependent on the total number of epochs T, leading to results without (In T') term, As our asymptotic analysis uses T -indeependent parameters, terms regarding (I) inevitably appear, though our method can easily extended to T 7-dependent settings. (+4) These works have weakened the classical --soooth condition, which is different from the focus of this paper.
Reference
Assumptions on Stochastic Gradient
Sample Complexity
A.S. Convergence
L Convergence
(Wang et al., 2024a)
Bounded Variance (or Coordinate Affine Noise Variance)
No
No
(Hong Lin, 2024)
Exponential-taile Affine Variance Noise
2
No
No
VT
(He et al., 2023)Φ
Almost Surely Bounded Stochastic Gradient
poly
luT
Yes
Yes
(Zou et al., 2019)
L Bounded Stochustic Gradient
0
I
No
No
vT
(Zhang et al., 2022)
Randomly Reshufiled Stochastic Gradient
I
No
No
vT
(Li ct al., 2024)0 Q
Almost Surely Bounded Stochastic Gradient
Sub- Gaussian Variance
O (poly
(1)
InT)
vT
No
No
(Wang et al., 2
Randomly Reshuffled Stochastic Gradient
No
No
v7
(Xian et al., 2024)<>$
Almost Surely Brunded Stochastic Gradient
No Result
Yes
No
Our Work
ABC Incquality
Yes
Yes
Algorithm 1 Adam
appears.
Input: Stochastic oracle O, initial learning rate 7n 2 0, initial iterate w1 E Rd. initial exponential moving averages mo = 0, 2o U. I with > 0, hyperparameters 31 E
When analyzing Adam, Vf(ww) refers to the true gradient of the loss function at epoch t. We define F, o agi,.... 9t) as the o-algebra generated by the stochastic gradients up to epoch t, with Fo = {Ω, 0} and 900 = a (U12) Throughout this paper. unless explicitly stated otherwise. the norm
[0, 1). 82.1 E 10. smoothing term μ > 0, number of
epochs T
Output: Final iterate WT
== to T Generate learning rate me: Generate condi- tioner parameter (2,5 Sample a random data point zt and compute the stochastic gradient 9: = O.Oyye 21) Update the estimate: V,- -2, 1 +
|| denotes the Euclidean norm.
2.2. Assumptions
(1-82, 0g 2 Up- date the estimate: m4 81m-11+ (1 (1-31)9c Compute the adaptive learning rate: Te, = 1):- Vertu* Update
To establish our convergence results, make the following standard assumptions. The assumption regarding smooth- ness is the classical L-smooth assumption. The assumption about stochastic gradient are less restrictive than those im- posed in some prior works, as highlighted in Table 1.
the iterate: W141 Wt M/, my;
Assumption 2.1. (Bounded from Below Loss Function) Let f : Rdd + R be loss function defined on Rd. We assume that there exists a constant f E R such that for all w E Rd, the following inequality holds: f(w) 2 f
In Adam, the random variables [zte2 are mutually inde- pendent. The stochastic gradient at epoch t is denoted by Jt- The quantities m, and it represent the exponential moving averages of the first and second moments of the gradients, respectively. The hyperparameters 31 and B2, control the exponential decay rates for the moment estimates. A small smoothing term is introduced to prevent division by zero, and Th, represents the adaptive learning rate for each param- eter.
This assumption ensures that the loss function f is bounded from below, preventing it from decreasing indefinitely dur- ing the optimization process.
Assumption 2.2. (L-Smoothness) Let f Rd - R be differentiable loss function. We assume that the gradient V is Lipschitz continuous. That is, there exists constant L3 2 O such that for all w, w' E IRd,, the following inequality holds: [[](() - V S Ly][w - w'll. The constant I. is known as the Lipschitz constant of the gradient.
Notations: The Hadamard product (element-wise multi- plication) is represented by 3 o y, and the element-wiss square root of vector 7 Rdd is written as /7. Operations such as B + vo, 7. and g82 are performed element wise. Additionally, for a vector with subscripts, such as 3r, we use 3,, to denote its i-th coordinate. However, for a scalar with subscripts, such as Le. the double subscript P,,, carries a specific meaning, which will be explicitly defined when it
Assumption 2.3. (ABC Inequality) We assume that the stochastic gradient 9e is an unbiased estimate of the true gradient. i.e. Eige | [ = ( and there exist constants A, B,C C 2 such that for all epochs i, we have:
3

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
Ellg || F.-1] s A(((w)) (*) + B(W + C.
means of ensuring that B2 asymptotically approaches 1, which is crucial for convergence.
The ABC inequality provides a bound on the second mo- ment of the stochastic gradients, which is crucial for an- alyzing the convergence of stochastic optimization algo- rithms. Notice identity E [[].e - [((=)]l FI-1] = E ||19:12 | - (wx,)) We can conclude that the above ABC inequality has the following equivalent form based on the variance of the stochastic gradients, i.c., there exist constants A 2 0. B 2 0, and C 2 0 such that: E [ll9: - Vf(w))]] r-1 I A(f(ur) - f*)
The hyperparameter settings adopted in this paper are rep- resentative and have been considered in previous studies (Zou et al., 2019; He et al., 2023). Our configuration in- cludes settings that can achieve near-optimal complexity of (InT/vT). The logarithmic factor in T arises because B2, is chosen independent of the total number of epochs T, which is an unavoidable consequence with this class of parameters.
(w;))( + C.
Our choice of hyperparameters simplifies the analysis while capturing the essential behavior of the Adam. Although the proof techniques can be extended to a broader range of parameter settings, this paper focuses primarily on the assumptions related the convergence of the algorithm rather than an exhaustive exploration of hyperparameter configurations.
2.3. Comparison with Prior Works on Stochastic Gradient Assumptions
Due to space limitations in the main text, these compar- isons have been moved to Appendix A.
Next, we introduce a property. We know that when the loss function is L-smooth, the true gradient of the loss function can be controlled by the loss function value f(w)) - f (as shown in Lemma C.2). Therefore, we can simplify the ABC inequality follows.
3. Theoretical Results
In this section, we establish both non-asymptotic and asymp- totic convergence guarantees for Adam within our smooth non-convex framework, as defined by Assumptions 2.1-2.3. For the non-asymptotic analysis, we derive sample com- plexity bound that is independent of O(1/p), providing an explicit bound on the number of epochs required to achieve a specified accuracy. In the asymptotic analysis, we consider two forms of convergence: almost sure convergence and convergence in the L1 norm. The almost sure convergence result demonstrates that, the gradient norm of almost every trajectory converges to zero. Meanwhile, the Li conver- gence result reveals that the convergence across different trajectories is uniform with respect to the L1 norm of the gradient, where the L1 norm is taken in the sense of the underlying random variable, meaning the expectation of the gradient norm.
Property 1. Under Assumptions 2.2 and 2.3, for all epochs I, we have: [| Fi-1) S (A+2I, (A) C.
This property demonstrates that the variance of the stochas- tic gradients can be bounded by the function value differ- ence, which is a key component in our convergence analysis.
2.4. Hyperparameter Settings
In this paper, to keep the proofs concise, we focus on a spe- cific set of representative parameter configurations, defined as follows:
B2 av.
ift= = 1,
Te B1 E 10,1,,
F ift 2,
+5+
3.1. Non-Asymptotic Sample Complexity
where ag E [0. 1),7 y [6. 26 1]. and 8 e (0.
Theorem 3.1 (Non-Asymptotic Sample Complexity). Con- sider the Adam algorithm as specified in Algorithm 2.1, and assume that Assumptions 2-1 are satisfied. Then, for any initial point, any T 2 and any (0, 1), the following bound holds with probability at least 1 8:
It is essential to impose certain constraints on Adam's 's pa- rameters, particularly on 82,,, to ensure the algorithm con- verges. Early studies (Reddi et al., 2018) have shown that without proper restrictions on 32,1. counterexamples exist where the algorithm fails to converge. Furthermore, for the gradient norm to converge to zero, it is necessary that 32,, approaches as noted in earlier works (Zou et al., 2019: He et al., 2023).
ifō E (0,
T
T2
1
( <
o
In
if > 1, 8 0
T
VT
Ina
if 6=0 0.
Some studies on complexity allow B2,, to be constant. How- ever, these studies typically focus on the algorithm's 's com- plexity over a finite number of epochs T. In such cases, the constant value of 1-82,, is inversely related to T, effectively causing B2,4 to approach as T increases. This is another
The constant implied by the O notation depends on the ini- tial point, the constants in Assumptions 2.1-2.3 (excluding 1/11), and the parameters 8 and on-
4

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
This theorem provides a non-asymptotic rate of convergence for the square of the gradient norm, highlighting how the choice of hyperparameters affects the convergence rate.
approach is built upon the insights provided by existing methods, while introducing new techniques to address the limitations of previous analyses and provide a more com- prehensive understanding of Adam's behavior under weaker assumptions. Our core innovations are detailed in Section 4.3.1, Section 4.4, and Section 4.5.
3.2. Asymptotic Convergence
We now present our main asymptotic convergence results, demonstrating that the gradients of the Adam converge to zero both almost surely and in the L1 sense under appropri- ate conditions.
4.1. Key Properties of Adaptive Learning Rates
We begin by characterizing the fundamental properties of the adaptive learning rate sequence 77, in Section 2.4. These properties are critical as they directly influence the behavior of the algorithm and are foundational to our subsequent analysis. By understanding how these properties interact with the algorithm's 's dynamics, we obtain more insights on the conditions under which Adam converges.
Theorem 3.2 (Asymptotic Almost Sure Convergence). Under Assumptions 2.1-2.3, consider the Adam with hy- perparameters specified in Subsection 2.4 with y and 5 > 0. Then, the gradients of the Adam converge zero almost surely, ie., lime- [[])]]] = 0 a.s.
This theorem shows that the gradients evaluated at the it- crates converge to zero almost surely, indicating that the algorithm approaches a critical point of the loss function along almost every trajectory.
Property 2. Each element Tous of the sequence (Ne, J121 [Me,,, 21.... Mo 3/21 is monotonically decreasing with respect to t.
Remark 1. (Almost sure vs L1 convergence) As stated in the introduction, it is important to note that the almost sure convergence does not imply L1 convergence. To illustrate this concept, let us consider a sequence of random variables {Gn J121, where IP(Gn 0) = 1/122² and P(Cn = n²) = 1 1/n2. Accordingg to the Borel- Cantelli lemma, it follows that fimn-+400 Gn= 0 almost surely. However, it can be shown that EE [IS = 1 for all n > 0 by simple calculations.
This property ensures that the learning rate becomes pro- gressively smaller as the algorithm progresses, which is a crucial factor in the stability and convergence of Adam.
Property 3. Each element no.5 of the sequence (11,,221 = [[Voe,, 2 (ee.dd Je21 satisfies the in- equality t ve,, 2 S1S,, where we define 0n == min Co ou): St, == -+ El for all t 2 1, and So,; == v.
Theorem 3.3 (Asymptotic L L.-Convergence), Under As- sumptions 2. 1-233, consider the Adam with hyperparame- ters specified in Subsection 2.4 with 7 > 1 and ō > O. Then, the gradients of the Adam converge to zero in the Lı sense, i.e., lim |1 ( 0.
This property highlights the relationship between the accu- mulated gradient information Sr, and the adaptive learning rate, ensuring that the latter appropriately scales with the former as epochs proceed.
Remark 4.1. For the purpose of simplifying the proofs of subsequent theorems, we define two auxiliary parameters:
This result establishes convergence in the mean sense, show- ing that the expected gradient norm approaches zero as the number of epochs increases. It indicates that the con- vergence of gradient norms across different trajectories is uniform in the L1 norm of the random variables.
De, Σi=1 Vt and S, := =E== St,i. Additionally, for convenience in the subsequent proofs. we define a new initial parameter based on Su,5 as Teg = So,s/a1 = =//01.
These definitions of auxiliary parameters help streamline the analysis, making the mathematical expressions more manageable and the proofs more concise.
In previous works (He et al., 2023; Xiao et al., 2024), the assumption that the stochastic gradients are uniformly bounded, i.e., ||9:1| < .M a.s. (V t 2 1). or that the gradi- ents themselves are uniformly bounded, i.e., f II M (A 2 1), allows almost sure convergence to directly imply L1 convergence via the Lebesgue's 's Dominated Con- vergence theorem. However, in our framework, which deals with potentially unbounded stochastic gradients or gradients, proving L convergence is much more challenging. We will elaborate on this in the next section.
With the key properties of the adaptive learning rates estab- lished, we now turn our attention to analyzing the momen- tum term, which plays crucial role in the Adam.
4.2. Handling the Momentum Term
To effectively analyze the momentum term in the Adam, we adopt a classical method introduced by Liu et al. (2020). The momentum term introduces additional complexity in the analysis due to its recursive nature, which can compli- cate the convergence proofs. To address this, we construct an auxiliary variable uy that simplifies the analysis by de- coupling the momentum term from the update process. This
4. Fr Framework for Analyzing Adam
In this section, we present the analytical framework that underpins our convergence analysis for the Adam. Our
5

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
auxiliary variable is defined follows:
Me (( ( (V)(w)) rc),
W/= 1 W/ + 1- B1
31
Martingale Difference Term
Ut
(we w1-1)
1 $1
where T) is the learning rate, is the Lipschitz constant, and yt. is the stochastic gradient.
31
Wt- 1- Bi 1 m
(1)
Motivated by the success of this approach in analyzing SGD, we aim to establish a similar approximate descent inequality for the Adam. The goal is to develop a descent inequality that captures the adaptive nature of Adam's 's learning rates while maintaining the essential structure seen in the analysis of SGD.
The introduction of u, allows us to handle the momentum term more effectively by transforming the recursive nature of the updates into a more tractable form. Specifically, we can express the relationship between successive epochs of Ur as follows:
0++11
U4 -100 o 9t.
To this end, we present the following key result, which forms the cornerstone of our convergence analysis for Adam.
31
+
Me-- Tus m
Lemma 4.1 (Approximate Descent Inequality). Consider the sequences (wrh21 fee and {urh12 generated by Algorithm 2.1 and Eq. (2). Under Assumptions 2.1-2.3 the following sufficient decrease inequality holds:
This recursive relation is instrumental in breaking down the complex dependencies introduced by the momentum term, which will facilitate the convergence analysis.
- (I..-1((u))
Then we establish two key properties that connect the origi- nal variable W, and the auxiliary variable uy These proper- ties are crucial for bounding the changes in the momentum term and connecting the function values different points in the epoch process.
d
-- Ma Σ 2
G(11) + Callmuu :ome-oom_ll om-
A V
Property 4. For any epoch f, the following inequality holds:
==1
mř,- - -m S (1 10-11(11mminn 31--mmmm--.. + B1
+ (L
2o Ii. + II
2
(4)
This property establishes a bound on the change in the mo- mentum term, which critical for ensuring that the momen- tum does not increase indefinitely during the optimization process. Controlling the momentum in this manner is an important step in proving the convergence.
Here,
f(u)) = f(ue) - -5" + E 7o--188
Property 5. For any epoch t, the following inequality holds:
(t)) Mo- (V:((w)(
(Ly 1) 2(1 - 3,) || o om-al
f(w)) S (L) 1))(m)))
Ia =
II
1
1 1- /3i
(
V3 + A
D1
A
(t2 1),
This property connects the function values at We and ut, which provides foundation for analyzing the convergence of (w.). By establishing this relationship, the behavior of the original variable w, to the more manage- able auxiliary variable ue thereby simplifying the overall convergence analysis.
k=1
11..0 = 1,
can relate
+oc
A VOT E
Σ
(v B1) 1 D LiB
where, D1, denotes the i-th component of De (defined in Eq. 2). M, == Mr.1 M1,2 + Mr,3-
(5)
4.3. Establishing the Approximate Descent Inequality
Constants C2 Dr is defined in Eq. (26) and Lemma E.2; Mr, is defined in Eq. (20); Ma. and Ma. are defined in Eq. (21).
In the convergence analysis of stochastic gradient descent (SGD), fundamental tool is the approximate descent in- equality, which quantifies the expected decrease in the ob- jective function at each epoch. Specifically, for SGD, the approximate descent inequality given by:
This lemma introduces Is, as a new Lyapumov function for Adam, which plays a crucial role in our analysis. In Eq. (4), the term - ITA Σn= (t) can be interpreted as the descent term, representing the expected decrease in the Lyapunov function. We collectively refer to the 2nd,
1 11
[w [wx) < (
Descent Term
Quodratic Error
6

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
3rd, and 4th terms on the right side of the inequality as the quadratic error terms. According to subsequent results (Lemma D.2), we can show that the expectation of the sum- mation from to T over t of these terms is of the same order The 5th term, a Mc, martingale difference sequence with respect to the fil- tration (F.) which, due to its zero expectation, can be considered to have no overall impact on the algorithm's epoch process.
discussed by (Wang et al., 2023; 2024a). This allows rewrite the first-order term as:
TTrm Σ R. [Mons V Vif((w))):
as O S i=1 E [mn.,.
Σ E [ive I. V. (1
Descent Term,
This structure closely resembles the approximate descent inequality commonly used in the analysis of SGD. For com- parison, the approximate descent inequality for SGD is given by Eq. (3).
[Meerad no x Vef
Term,,4
The presence of Term,, introduces an additional layer of complexity in the analysis, it reflects the difference be- tween successive adaptive learning rates. Addressing this extra error term is crucial for establishing robust conver- gence guarantees under the ABC inequality or affine noise variance conditions. Existing approaches to handling such terms, which often rely on the cancellation of errors through preceding descent terms, fall short in this context. This necessitates more innovative strategy, which we present in the following section.
We now proceed to provide the main idea of proving Lemma 4.1 and highlight the key steps and challenges involved in establishing this result for Adam.
To begin with, we calculate the difference in the loss func- tion values between two consecutive auxiliary variables turt21 that we introduced. We obtain the following ex- pression (informal):
f((++)) - f(we)
d
E M
Σ
2 Dii
4.3.1. ADDRESSING THE EXTRA ERROR TERM: OUR INNOVATIVE APPROACH
Terms.1
Terme
The term Term,,4 introduced by the difference between Moc-i. and Te. presents a significant challenge in the con- vergence analysis of Adam under the ABC inequality or affine noise variance conditions. In existing methods, it is common to attempt to cancel out such error terms by lever- aging the preceding descent term Descent-Term, However, this approach might not work within the ABC framework. Recent works such as Wang et al. (2023; 2024a) have shown that, under existing techniques, the best one can achieve is a weakened form of the stochastic gradient assumption, namely the coordinate affine noise variance condition. To overcome these limitations, we introduce novel approach to handle Term:,4. We scale it as follows:
E a V Vif(w))ge:
+-11]
Bor ViJ (w))e.
Temms,3
+ Re.
(6)
It can be observed that the above equation is simply second-order Taylor expansion of (u++1) - (ux) (since an L-smooth function is almost everywhere twice differ- entiable). Term,,, represents the first-order term, which in general serves as the descent term. Term, is the quadratic error, and Term is a martingale difference sequence. The remaining term R2 is negligible and can be ignored. In the informal explanation provided in the sketch, these were collectively referred to as remainder terms. For the exact formulation, refer to the detailed proof in Appendix D.3.2.
1
Termy,4
S
E [T 112 Vif(we))nt F(-1]
2
d
While handling the quadratic error term Term, is relatively straightforward using standard scaling techniques, address- ing the first-order term Term;,1 more challenging due to the adaptive nature of Adam's 's learning rates. Specifically, Nor.i and 9t.; are both F,- --eaasurrble, which necessitates the introduction of an auxiliary random variable T which is F mcasurbbee to facilitate the extraction of the leamn- ing rate from the conditional expectation. In this paper, we choose the auxiliary random variable 77 1.4 to approximate Me..i There are also other forms of this approximation, as
+ Cis(w:)
Σ
E E(A
[F,-]] + Ri.
+ E
D + C
Σ
ElAr, 1F-11l - -e.)).
1=1
1=1
Terms
where A == 17, 1on-1.--00,.k Mo C1 A+2L, B (Ly + and
R₁ represents a negligible remainder term, primarily stem- ming from the difference between f(w) and f(.)) The
7

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
critical term in this inequality is C1 E E|A Ft-1] which cannot be effectively canceled out using ex- isting methods.
Inequality. This term introduces a new layer of complexity not present in the standard SGD analysis. In particular, we are required to bound the p-th moment of the reciprocal of this term, i.e., E.l (p 2 1). Due to the unique struc- ture of I determining a bound for this y-th moment is a non-trivial task.
To handle this issue, assign A = Σー E(A,, F,-1]; and move the term (ue) to the left-hand side of inequality 6 and combine it with the existing f(w)) term. This leads to a new epoch inequality of the form:
To address this challenge, we leverage tools from discrete martingale theory, particularly the Burkholder's inequality, It allows us to establish recursive relationship between the p-th moment [ and the p/2-th moment TB( P2 This recursive structure is crucial as it enables us to itera- tively bound the higher moments of IT
f(441)) - (1+ (1
$ Descent-Term, + M-Term, + Terms,2
2 + R-Term:
(7)
Once the recursive relationship is established, we ap- ply fundamental theorems from measure theory, such as the Lebesgue's ' Monotone Convergence theorem or the Lebesgue's 's Dominated Convergence theorem, to obtain the final bound on the p-th moment. The detailed process for bounding E P and Lemma D.I.
In the incquality M- = Terms T is martin- gale difference sequence and R- R-Term, is the (neglectable) remainder term by combining all other terms from the in- equalities. To express this incquality in a form resembling a Lyapunov function, we introduce an auxiliary product vari- able: Ia.. := I (1+C 1 (Informal). Note that a here is merely a simplified ver- sion of the actual a used in the formal lemma; it is not the version we employ in practice. Multiplying both sides of the inequality by 1a we obtain the following reformu- lated inequality:
[ can be found in Lemma C.3, Lemma C.5
(Vt 2 2), II =
4.5. Establishing Asymptotic L1 Convergence
Since we have already proved almost sure convergence in Theorem 3.2, it is natural to attempt to prove Ln conver- gence via the Lebesgue's 's Dominated Convergence theorem. To achieve this, we need to find function h that is Fxc measurable and satisfies E//a < +oc, and such that for all 2 1, we have [[v )ll S [/s]_ Since for all t we natu- rally have || (w:)]] I supE21 || [V[(w))]], we only need to prove that E[sup:2] (wl))l < +00.
(l - 1A,.-1(())
< TAA Descent-Term, + Ia - M-Term, 2
+ IA, - 2 + A1 R- R-Term;
(8)
This reformulation introduces II as a scaling factor, which, along with the original Lyapunov function, captures the impact of Termy,4- The resulting inequality closely par- allels the approximate descent inequality for SGD, with additional terms accounting for Adam's 's adaptive nature.
This task presents significant challenge because, within our analytical framework, we cannot assume that the gra- dients are uniformly bounded, which means we cannot di- rectly apply the Lebesgue's 's Dominated Convergence theo- rem. Instead, we need to utilize advanced techniques from discrete martingale theory, specifically the first hitting time decomposition method, obtain a bound on this maximal expectation. The detailed process can be found in Appendix D.3.13.
The handling of Term,, in analysis framework is significant advancement over existing methods. It allows us to establish stronger convergence guarantees under more general conditions.
4.4. Deriving Sample Complexity and Almost Sure Convergence
5. Conclusion
We have introduced a novel and comprehensive framework for analyzing the convergence properties of Adam. Our frame starts with weak assumptions such as the ABC in- equality. By identifying the key properties of the learning rate, handling the momentum term, and establishing the ap- proximate descent inequality, the frame concludes the sam- ple complexity, almost surely convergence, and asymptotic L1 convergence results of Adam. Our techniques overcome existing limitations, aligning Adam's convergence guaran- tees with those of SGD, thereby justifying Adam's 's broad applicability in machine learning.
After establishing the Approximate Descent Inequality, the next step is to derive the sample complexity and almost sure convergence results for Adam. The methodology for obtain- ing these results largely mirrors the approaches traditionally used in the analysis of SGD. Specifically, the inequality provides a foundation for bounding the expected decrease in the loss function, which can then be used to establish both sample complexity and almost sure convergence.
However, key difference in our analysis lies in the intro- duction of the term Ta, within the Approximate Descent
8

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
Acknowledgements
KHOSHNEVISAN, D. Stochastic integration and stochastic partial differential equations: tutorial. 2006.
We thank the anonymous reviewers for their helpful feedback and suggestions. Xiao Li is supported in part by the National Natural Science Foundation of China (NSFC) under grant 12201534 and in part by the Shenzhen Science and Technology Program under grant Baoxiang Wang is partially supported by the National Natural Science Foundation of China (72394361, 62106213) and an extended support project from the Shenzhen Science and Technology Pro- gram.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint urXiv:1412.o00 2014.
Li, H., Rakhlin, A., and Jadbabaie, A. Convergence of
(CYX20221008093033000
Adam under relaxed assumptions. Advances in Neural Information Processing Systems, 36, 2024.
Liu, Y., Gao, Y., and Yin, W. An improved analysis of stochastic gradient descent with momentum, Advances in Neural Information Processing Systems, 33:18261- 18271, 2020.
Impact Statement
Nguyen, L., Nguyen, P. H., Dijk, M., Richtárik, P., Schein- berg, K., and Takác, M. SGD and hogwild! Convergence without the bounded gradients assumption. In Interna- tional Conference Machine Learming, pp. 3750-3758. PMLR, 2018.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences our work, none of which we feel must be specifically highlighted here.
References
Reddi, S. J., Kale, S., and Kumar, S. On the convergence Adam and beyond. In International Conference on Learning Representations (ICLR), 2018
Bottou, L. Large-scale machine learning with stochastic gradient descent. In Proceedings COMPSTAT'2010 19th International Conference Computational Statis- ticsParis France, August 22-27, 2010 Keynote, Invited and Contributed Papers, pp. 177-186. Springer, 2010.
Wang. B., Zhang, H., Ma, Z., and Chen, W. Convergence of AdaGrad for non-convex objectives: Simple proofs and relaxed assumptions. In The Thirty Sixth Annual Conference on Learning Theory, pp. 161-190. PMLR, 2023.
Bottou, I.,, Curtis, F. E., and Nocedal, J. Optimization methods for large-scale machine learning. SIAM review, (0(2))223-311,
2018. 2018.
Wang, B., Fu, J., Zhang, H., Zheng, N., and Chen, W. Clos- ing the gap between the upper bound and lower bound of Adam's iteration complexity. Advances Neural Infor- mation Processing Systems, 36, 2024a.
Ghadimi, S. and Lan, G. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2368 2013.
Wang. B., Zhang, Y., Zhang, H., Meng, Q., Sun, R., Ma, Z.-M., Liu, T.-Y., Luo, Z.-Q., and Chen, W. Provable adaptivity of Adam under non-uniform smoothness. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2960-2969, 2024b.
Guo, Z., Xu, Y., Yin, W., Jin, R., and Yang. T. A novel convergence analysis for algorithms of the Adam family and beyond. arXiv preprint arXiv:2104. 14840, 2021.
He, M., Liang, Y., Liu, J., and Xu, D. Convergence Adam for non-convex objectives: Relaxed hyperparameters and non-ergodic case. arXiv preprint arX1v 2023.
Xiao, N., Hu, X., Liu, X., and Toh, K.-C. Adam-family methods for nonsmooth optimization with convergence guarantees. Journal of Machine Learning Research, 25 (48):1-53, 2024.
Hong. Y. and Lin, J. On convergence of adam for stochastic optimization under relaxed assumptions. arXiv preprint arXiv:2402.03992, 2024.
Zhang, Y., Chen, C., Shi, N., Sun, R., and Luo, Z.-Q. Adam can converge without any modification on update rules. Advances in Neural Information Processing Systems, 35: 28386-28399, 2022.
Huang, F., Li, J., and Huang, H. Super-adam: faster and universal framework of adaptive gradients. Advances in Neural Information Processing Systems, 34:9074-9085, 2021.
Zou, D. and Shen, L. Improved convergence analysis of stochastic optimization algorithms for nonconvex opti- mization. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Khaled, A. and Richtárik, P. Better theory for SGD in the nonconvex world. Trans. Mach. Learn. Res., 2023, 2023.

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
Zou, F., Shen, Jie, Z.,, Zhang, W., and Liu, W. A sufficient condition for convergences of Adam and RMSprop. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11127-11135, 2019.
10

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
Contents
1. Introduction
1.1 Related Works
2. Prelininaries
2.1 Adam
2.2 Assumptions
2.3 Comparison with Prior Works on Stochastic Gradient Assumptions
2.4 Hyperparameter Settings
Theoretical Results
3.1 Non-Asymptotic Sample Complexity
3.2 Asymptotic Convergence
Framework for Analyzing Adam
4.1 Key Properties of Adaptive Learning Rates
4.2 Handling the Momentum Term
4.3 Establishing the Approximate Descent Inequality
4.3.1 Addressing the Extra Error Term: Our Innovative Approach
4.4 Deriving Sample Complexity and Almost Sure Convergence
4.5 Establishing Asymptotic LI Convergence
Conclusion
Impact Statement
A. Comparison with Prior Works on Stochastic Gradient Assumptions
12
B. Proofs of the Properties of Adaptive Learning Rates and Momentum Term
13
B.1 Proof Property 2
13
B.2 Proof of Property
13
B.3 Proof of Property 4
13
B.4 Proof of Property 5
14
C. Lemmas in Probability Theory and Real Analysis
14
C.I Proofs of These Lemmas
15
C.1.1 Proof of Lemma C.1
15
C.1.2 Proof of Lemma C.2
15
C.1.3 Proof of Lemma C.3
16
C.1.4 Proof of Lemma C.4
17
C.1.5 Proof of Lemma C.5
18
D. Supporting Lemmas
20
D.I Dependency Graph of Lemmas and Theorems
20

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
D.2 Statements of the Lemmas
21
D.3 Proofs of the Lemmas and the Theorems
23
D.3.1 Proof of Lemma D.I
23
D.3.2 Proofs of Lemma 4.1
24
D.3.3 Proof Lemma D.3
27
D.3.4 Proof Lemma D.4
28
D.3.5 Proof Lemma D.5
29
D.3.6 Proof Lemma D.7
29
D.3.7 Proof of Lemma D.8
31
D.3.8 Proof of Lemma D.9
31
D.3.9 Proof of Lemma D.10
33
D.3.10 Proof of Theorem 3.1
34
D.3.11 Proof of Lemma D.6
35
D.3.12 Proof of Theorem
35
D.3.13 Proof of Theorem 3.3
38
E. The Proof of Lemma D.2
E.1 Auxiliary Lemmas for Proving Lemma D.2
41
E.2 Proof of Lemma D.2
48
12

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
A. Comparison with Prior Works on Stochastic Gradient Assumptions
Our assumption on the stochastic gradient (Assumption 2.3) is relatively mild compared to those in prior works. Here, we focus on comparing with the traditional affine noise variance condition, coordinate affine noise variance assumption, and the almost surely bounded stochastic gradient assumption.
Traditional Affine Noise Variance Condition The traditional affine noise variance condition (Affine noise variance) (e.g.. (Bottou et al., 2018; Nguyen et al., 2018)) assumes that there exist constants B 2 0 and C' 2 0 such that:
Bilgg 1|2
--1
s B f +
This condition bounds the expected squared norm of the stochastic gradient by linear function of the squared norm of the true gradient plus constant. It is stronger than our ABC inequality because it does not include the term involving the function value difference f(w,) - f"
Some works adopt the following form of affine variance noise:
E [Ila - VS(w)) [
BI] C.
important to note that, due to the identity
11g - V](W:)]l | =B [1la [ - [V/[()))
is straightforward to see that these two forms are equivalent.
Even under this condition, current methods for analyzing Adam encounter significant difficulties. We will explain these challenges in the proof sketch of Lemma 4.1. Besides, both (Huang et al., 2021) and (Guo et al., 2021) provided convergence bounds under traditional affine noise variance condition. However, they relied on the assumption for step-size where G +
S C. (
Coordinate Affine Noise Variance Assumption Wang et al. (2024a) introduce the coordinate affine noise variance assumption, which requires that each component of the stochastic gradient satisfies an affine noise variance inequality, Specifically, for each coordinate i, there exist constants B, C 2 0 such that:
Elgi, F.11] S B
+
(10)
where gt,; and (ft( are the i-th components of gr and V fw:)) respectively.
This assumption is stronger than the traditional affine noise variance condition because it imposes the inequality on each coordinate individually, rather than on the overall gradient.
Exponential-tailed Affine Variance Noise Condition Certain works, such as (Hong & Lin, 2024), examine the assumption of affine variance noise with an exponential tail distribution, i.e.,
11ge B [1
[(()))1 1 C
\
IE
exp
F $,-1 Se.
(11)
This assumption is close to the almost sure form of affine variance noise, specifically 12 important emphasize that this assumption (exponential-tailed affine variance noise condition) is stronger than the traditional affine variance noise assumption based the second moment of the stochastic gradient. Furthermore, the methods developed under this stronger assumption are not applicable to affine variance noise models that rely the second moment.
((x) + C C.a.s.
Almost Surely Bounded Stochastic Gradient Assumption Some prior works, such as (He et al., 2023; Xiao et al., 2024), assume that the stochastic gradients are almost surely bounded. That is, there exists a constant M 2 0 such that for all epochs t: ||9e]| < M almost surely. This is a strong assumption, as it requires that the stochastic gradient norm is uniformly bounded almost surely all epochs. In practice, especially in non-convex optimization problems, this assumption
13

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
become unbounded due the complexity and non-linearity of the models. Moreover, this assumption implies that the true gradient is also bounded by M, because || f (wx)]] 2 < Blll9: l _--1] I M Our assumption is clearly weaker than the almost surely bounded stochastic gradient assumption, as we only require a bound on the expected squared norm of the stochastic gradient, which can depend on the current function value and gradient norm, rather than a uniform almost sure hound.
often violated (see Wang al. 2023). For instance, when optimizing deep neural networks, gradient
Moreover, assuming almost surely bounded stochastic gradients hard to satisfy in practice and may not reflect realistic scenarios. As discussed (Wang et al., 2023; Khaled & Richtárik, 2023), such assumptions can be unrealistic and limit the applicability of theoretical results.
B. Proofs of the Properties of Adaptive Learning Rates and Momentum Term
B.1. Proof of Property
Proof. Due to Algorithm 2.1, we observe that
= -(1- (1+ 157 11%) + (1+ 1). 1y Rit (41 1).
1
1 = 12, + 12222+4)906 =
which means
1)) (t + (1+1) = 117 oes + L. 2 ter.
(12)
This implies that (7 is monotonically non-decreasing. Subsequently, we have
V / + Vtlun, Vtn Vtuu, + Vtn
F)
no..
Because the numerator is monotonically decreasing and greater than O, while the denominator is monotonically non- increasing and greater than O, we deduce the monotonic non-increasing property of ne:-
B.2. Proof of Property
Proof. For U1 derive the following estimate
11 = Uo, + (1 - -2,1), -11 -aoj + aogi.
immediate to find that an S1, vı, S S1.; For k 2 2, by Eq. (12), we have 7 2 (k: 1) + g.. Then, by summing up the above iterative equations, obtain V 2 2,
tu 2 11
Σ Ik.t km2
Combining the estimate for 81 we have V 2:
Eer (1 - ao)e + aggi, +
Σ 2
Tk.s
k=
Then 1' 2 an St,s which completes the proof.
B.3. Proof of Property
Proof. According to Algorithm 2.1, we have the following iterative equations
me,i 31m4-1,1 (1 33 )gr.
We take the square of the 2-norm on both sides, which yields
m (8. (81m-111 + (1 - Br ))
14

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
- + + (1-3111-mmaa -.))m 92,) S 3/m + (1 +1--81)
In step (a), we used the AM-GM inequality, i.e.
23, (1 - 31)m--1,k 1,99,, 5: 31)m0 Bi - Bi)0k,
that is,
m mp-11 S -(1 31)m + (1- :2)
which completes the proof.
B.4. Proof of Property
Proof. Due to
Li
Li
Is(w)) s(we)] (u() (wo - uz) +
|0+ uz 12
-eel + [
we ue
2
1
(1x))) + 1,+11 +
|| 1
2
2
L.(w)) + +
|1 o m,-111
2(1 - B1)2
we have
11++1)89 2(1 B1)² | m4-1l12
f(w)) S f(u) + - s (L, +)f(um)
C. Lemmas in Probability Theory and Real Analysis
Lemma C.1. If0 < < and 0 < < (a < (J) are two constants, then for any positive sequence {Wa). there is
k
b. 11/(1 10ll-wo wo) Σ 4 i
6i
where wa = =/p.
Lemma C.2. Suppose that fxx is differentiable and lower bounded, i.e. f inf Ra f(x) > -0, and ff(x) is
Lipschitz continuous with parameter > 0, then V x. E Rd, we have
Lemma C.3. Let (Xn,,a)) be a non-negative adapted process such that t00 Xn = M < too almost surely,
where M is a finite constant. Define the partial sum of conditional expectations as AT == ΣT E[[,, Fn Then the following properties hold.
(i) The sequence (Arhry br21 converges almost surely, i.e., AT 9.8 A, where A +000 E[X,, F Fn-1]
(ii) For any p 2 1, the sequence (AT)T21 converges in Lp, i.e., limm E ||A AP = 0. Meanwhile, the p-th moment of the limit A is bounded by a constant Cx(p) > O, where Cx(p) 6(22M)
Lemma C.4. Lerl E (0. Then, for sufficiently large E N4, we have
[(v++1)
00.
(In !) vu+T
15

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
Lemma C.S. Let ((x, n21 be a non-negative adapted process such that En Xn M +00 almost surely, where
M is finite constant. For any k > 1, define the partial sum of conditional expectations as A&.T == En B[Xx F Fn-k] Then the following properties hold.
(i) The sequence (Ax,T Ir converges almost surely, i.e., AK,T _ (kk, where A E E[X,, Fn
(ii) For any p 2 1, the sequence {Aa,T hr converges in Lg. ie., limy E [ (1)) = Meanwhile, the p-th moment of the limit (8) is bounded by constant Cx (p) > O, where Ca(p) = ((22))()))))))
(iii) For any 0 < 1 1, the arbitrary p-th moment of the random variable ell exists, where
+o0
A(I) = Σ
Σ x
The upper bound of this p-th moment depends only on p. L, and M. We denote this upper bound by Cest (p, M).
C.1. Proofs of These Lemmas
C.1.1. PROOF OF LEMMA C.I
Proof. The proof of this lemma is through identities. We assume μ (the case μ < is the similar), and let wi log, 1. Then derive
11" tp..
k=1
1= i=1
im
Am
k-1
where wg o/u. Then combining <<
Ek=i
k=
wo
we get the result.
C.1.2. PROOF OF LEMMA C.2
Proof. For Vo E Rdd define the function
g(t) ff +t x' -x x =(
| x
where x' is a constant point such that x' - x is parallel to fxx) By taking the derivative, we obtain
x' x
x' x
g (1) V
x
(13)
1/ - x0||
|| - xe|
Through the Lipschitz condition of Vf(z), we get Vt,, to
( = ( V م'=
- x
x + 12 1| - æ1| )
- x
T
x' x
f x + t | - x1l
- x'= f
|| 1||
||
|| x1l
< V   f (a+t)
x'
(a+ba 1 x
x'
1 | x
x' x ||
S Clt - -z2.
||' æ|||
x+ع কল
This indicates that (t) satisfies the Lipschitz condition as well. Then infaen g(t) 2 inf f(x) > -00. Let g" = infaeR g(x). Subsequently, V to E R,
s(0) - 9" 2 20( g(to).
(14)
By using the Newton-Leibiiz formula,
g(0) - gtoo) = 1 g'(a)da = l ( + l d'(0)da.
10
16

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
Through the Lipschitz condition of g', get that
g(0) g(t))
{
1)
1 -Lla 0 [ d'(0)da
2C (0))
80
Then we take special value of to. Lo -0((0) L. We obtain
s(0) g((n) 2 - [n/ Llalda + [ g(0)dl = -
0
2 (0- -0)2 +
(15)
2C (g' (0))² + .z (o'(0)) 2C (d(
Substituting Eq. (15) into Eq. (14), have
9 g" 2 2C (g "
Due to g" 2 and ( follows that
[f(=)]| s 2c(((x) - f*).
C.1.3. PROOF OF LEMMA C.3
Proof. (i) Consider the non-negative adapted process (X,,, Fn)n21 and define the partial sum of conditional expectations
as Ar Ex= E F 11
First, we compute the expectation of Ar
T
E E[Ar]
E
Σ
n
E[X,] M. Σ
Since Xn are non-negative, we know that AT is a non-decreasing sequence. Because E(Ar) (A T 1) is also bounded by M. we apply the Lebesgue's 's Monotone Convergence theorem. Thus, Ar converges almost surely to limit A:
A := lim AT
E|x, Fn-1] a.s.
This concludes that the sequence of conditional expectation sums converges almost surely. (ii) We begin by normalizing Xn by considering the expression Ya Convergence theorem, we only need to prove that
X
According the Lebesgue's Monotone
2M
1, E Σ EYM = M(p) < +00.
Next, proceed with the calculation, and obtain that V p 2 there is (Strictly speaking, we should first consider finite N and compute Σn= and only then take the limit N - +00, applying the Lebesgue's monotone convergence theorem to obtain the result for D However, for the sake of simplicity in the proof, we have directly computed >)=
P
M(p) =
E
E Y
= E
ETY,
n
==1
==1
n=l
E
Y n
E
F n- - Yn)
2
1
+ E
Σ
(E\Y, I 1n- Km)
2
2
n=1
L==1
1/2
p/2
1
2 C
Σ
E|Y, 3 n- 1] Y,
+
2D
Σ
E.Y. F. Y
2
2
17

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
1/2
( 1 $ +
80
1-20-20 CG + + E
2
E|y
2
1=1
1 22 C, + 2228 C,M((22 2
(16)
In the above derivation, Inequality (a) requires noting that + Y, 2' Inequality (b) uses the AM-GM inequality, specifically,
a 11+b
a + b"
Incquality (c) involves using Burkholder's incquality, where Cp is constant depending only on p. and its order with respect to is (p) (see Theorem 5.27 in KHOSHNEVISAN (2006)). Inequality (d) requires noting that
E 1 Y, - 1 Yul-
By repeatedly using Equation (16) and using the fact that C, (p), we obtain the following estimate
M()) oppv"),
that is,
B|A"| = o((M)) pvP).
C.1.4. PROOF OF LEMMA C.4
Proof. Consider the function
f(x)= = 1
with its derivative
(' 1-vi- + vn).
We observe that / decreasing for
Va f
Therefore, we have the following estimate
0
Vn
+1
v 8
Σ 1k
1
Vn
+1) V
=0
Vn
v
In
1
1
1
In
In
OS
Vn in
+1
k=
On the other hand, we can bound the remainder as follows:
Σ
2
Σ
Fry" dx
k> VR In
<>
vv In
k+1
r+1
FT dx
Σ
FT dx
k=0"
0SKS mn
k+1
2
1a dr
+ 2
1"t dx
In
k=0
T(v]+1)
vn
+0
(In Vx+1
In
'Burkholder's inequality: For any martingale {(Mn: Fn) with Mo 0 almost surely, and for any 1 S there exist constants Cp and Cp > 0 depending only on p such that:
Cp ((((((M)))) S
where M supp20 [Ma]] and S(M) (Ezz (M. M, 1/2
18

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
Similarly, have the upper bound
Σ
Rvv
Σ
dx
k> in
+1
in
Fxva dx Σ
Pava dr
k-1
1--1
1sk5 ln +1
+(v=+1)
$
1x dr=
dr
(In v
Combining the estimates above, we have
T' (v
vu+I' [nn !)
000
K=
C.1.5. PROOF OF LEMMA C.5
Proof. (i) Consider the non-negative adapted process (Xn, Fnlnzi and define the partial sum of conditional expectations as A == Σm= E[x,, F k
First, we compute the expectation of AR.T
T
T
E[Ax,T] =
Σ Ln=k
x
Fn-1|
Σ n=
E X
B[X,] < M.
Since X, are non-negative, we know that Ag.T non-decreasing sequence, and considering that E(A,rr (VT 1) is also bounded by M, apply the Lebesgue's 's Monotone Convergence theorem. Thus, Ag,7 converges almost surely to limit A (d))
(k)
lim T-
ART
E[X,
F k a.s.
n=
This concludes that the sequence of conditional expectation sums converges almost surely.
(ii) We begin by normalizing Xn by considering the expression Yn Convergence theorem, we only need to prove that
Xa. 2M
According to the Lebesgue's Monotone
DC
p MM(pp) +00.
12 E
Σ
EY,
n- -k]
Next, we proceed with the calculation, and we obtain V p 2 2, there is:
M(p) = E
Σ
B F k k)
E
Y
(E n Fn - Yn)
R= mod k=
n=k
1=0 n=kin mod Ami
(a)
1
00
9 n 1) -v,) 1)
E
Σ
(E(Y, F n - Yn)
2
E
Σ
2
1=0 mod k=
(6)
1
k-1
2
G
E
Σ
(E\Y, F k] Vn)
km mad km
1/2
(4)
k
2F
E2
Σ
(E n [| - Yn)
1=0
n= mod k=
19

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
n/2
(e)
S + 20
10-
E
| -n
Ynl
1=0
n= mod k=i
P//2
( 1
80
S + 2 1 E
E n 1 n-
2
Ln=k
00
P/2
S 10-220-1 2p--1cp Cp + 28p-2k2 2 Cp E
Σ
2 Cp + 22r-2k" 2k- -
(17)
In the above derivation, Inequality (a) is by noting that Σns Yn Inequality (6) uses the AM-GM inequality, specifically,
a +++ P a + 6
2
Inequality (c) involves using the AM-GM inequality for l variables, specifically,
a1 + 02 + + ak P S
+ a + +
0%
k
Inequality (c) involves using Burkholder's inequality, where Cp is a constant depending only on p. and its order with respect to is (p). Inequality (d) is by noting that
Yal F., -
(r - Yvl--
By repeatedly using Equation (17) and using the fact that Cp = (p), we obtain the following estimate
M(p) =
that is,
(((2M) (kp)))
(iii) For any < 1 < 1, we obtain:
A(1) ΣE E
Σ 11 X₁
Fk-1
ΣE E
1' 1'Xxtt
|
1=1
1=1
+oo toc
to
E
1
Xx++
I k-1
(A())
Next, we apply Hölder's 's inequality, we obtain An n 2 2
A(1) = Σ
+000
(A
5
1-7
1
n-1
+00
1=
Then we have:
B[(eAA(1]
p ][
+00
p
+o0 ((((1)))
ΣΣ< 13)0 0=0==
400 4:00
P
n!!
n!
1 1-1
n!!
n=0
+00 400
L (2MM)"
vn
n!
n=0 t=
(2M) (p)vn
(1-))
0
n!
n
100
20

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
+00
(2M) (p)vi
Lemin C.4
o
Σ
r( T(vn+Il 1)
p
(In 7)
v
1-1
n!
0
By substituting the factorial the denominator with Stirling's approximation, it is evident that the series inside the notation converges and depends only on p, / and M. The lemma follows.
D. Supporting Lemmas
This section introduces key lemmas that are essential for the proofs. We start with a diagram illustrating their relationships with the theorems. Rigorous proofs for all lemmas and theorems follow in the subsequent subsections. Due to its isolated, lengthy proof, Lemma D.2 is addressed separately at the end of the paper (see Section E for details).
D.1. Dependency Graph of Lemmas and Theorems
Due to the large number of lemmas, we have combined these lemmas with those in the main text and theorems to create a Lemma-theorent dependency graph. We refer the audience to this graph for a whole picture of our proofs, while the reader may also find the lemmas needed for specific statement.
21

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
Lemma 4.1
Lemma C.3
Lemma D.2
Lemma D.1
Theorem 3.3
Lebesgue's 's Dominated Convergence theorem
Lemma D.3
Lemma D.6
Lemma D.4
Theorem
Lemma D.5
Lemma D.8
Theorem 3.2
Lemma D.7
Lemma D.10
Lemma D.9
D.2. Statements of the Lemmas
Lemma D.I. For IA defined in Equation (5), for any 2 0 and any p 2 the p-th moment of reciprocal is bounded, i.e.,
E
< Co.d.p +00,
where Cuddp is constant that depends only on d, and p.
Moreover, we have that 11_1 3,00 lim; 1 too a.s., and for any p 2 1, the p-th moment of 11 exists, with
II 00
< Co.d,p < 400.
22

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
Lemma D.2. Consider the Adam algorithm in Algorithm 2.1 and suppose that Assumption 2.1 2.3 hold. Then for any
initial point, and T 2 the following results hold
(f
Σ
E
o
gell?
+0(1,
T
T
E
(((()
=
Σ
E
10,0 o gell?
+ 011)
T
E MTA V.S(u))m O
Σ E l1m, sul? 0(1)
2m 1=
The specific form of the constants hidden behind the O() notation can be found in Equation (55) and Equation (56). All constants depend on the initial point and the constants in our required assumptions (excluding 1/p).
Lemma D.3. Consider the Adam algorithm defined in Algorithm 2.1 and suppose that Assumption 2.1-2.3 hold. Then for any initial point and vf & > O, have for any T 2 the following inequality holds
Il IT
S ddu
Σ Aott
(18)
(T + 1)0
where
11
A
(t+ (1+
and ST is defined in Remark 4.1.
Lemma D.4. Consider the Adam algorithm defined Algorithm 2.1 and suppose that Assumptions 2.1 2.3 hold. Then for any initial point and for all T 1, there exists a random variable & such that the following results hold
(a) O OSC C < +oo almost surely, and B(C) is uniformly bounded above by constant Cs, which depends on the initial point and the constants in the required assumptions (excluding 1/).. The explicit form of this upper bound is provided in Equation (29).
(b) VSr s (T 1)*II and In ( IT 1)(', where Ç' s 4 (1+ + 2/1m (max {e ee H
Lemma D.5. Consider the Adam algorithm defined in Algorithm 2.1 and suppose that Assumption any initial point and T 2 I, the following results hold
2.3 hold. Then for
T E
TAL
X 5.(0))
{
(c,+CC
C4.65
if (0,112).
=
where C3 and Cs are constants that depend on the initial point and the constants in our required assumptions (excluding 1/u), and C4.8 a constant that depends on the initial point, 8, and the constants in our required assumptions (excluding 1/p).
Lemma D.6 (Subsequence Convergence). Under Assumptions 2.1 - 2.3, consider the Adam algorithm (Algorithm 2.1)
with hyperparameters as specified in Subsection 2.4, where 8 > 0. Then, there exists subsequence (Wer 2re1 such that its gradients converge to zero almost surely, i.e., lim V f Il|
a.s.
Lemma D.7. Consider the Adam algorithm defined in Algorithm 2.1 and assume that Assumptions 2.1 2.3 hold. Then, for any initial point and for all T z 1, the following results hold
When 8 0, we have
II (J -1²)
(f - In2 (1+1)
sup
400 a.s. sup E
< <M -00
12
(n²(1+1)
T21
23

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
When 8 O, we have
sup (f f*) too a.s., supEma.(((u))- Ms +00.
T21
In the above equations, Mo and M8 are two constants that depend on the initial point and the constants in our assumptions (excluding 1/1),
Lemma D.8. Consider the Adam algorithm defined in Algorithum 2.1 and suppose that Assumption 2.1 2.3 hold. Then for any inilial point, for all 2 1, i E [1, dl, there is
B(S { ( (TT))
fō E 10, if = 0,
where constants hidden in O() depend the initial point and the constants in required assumptions (excluding 1/p). Lemma D.9. Under Assumptions 2.1 2.3, consider the Adam algorithmm (Algorithm 2.1) with the hyperparameters specified in Subsection 2.4. Then, for any & 2 1, the following inequality holds
BlIA, (A+ (A, CC B( + + bM) if = 0.
if E (0, 1/2),
sup sup SEpE,
Furthermore, if A > L, then
sup E[TT En, < [(A+21, C) Ei=l (141)) t21
ifō (0,1/2)
[(A+22, C) Ets hn'
=
< +00.
(141))
Additionally,
sup E., +00 12
Lemma D.10. Under Assumption 2.1 2.3, consider the Adam algorithm (Algorithm 2.1) with hyperparameters in Subsection 2.4 with 7 > 1, 8 > 0. Then for any initial point, the following results hold
toc
Σ mel Vf to0 a.s.
Σ
Mell TellVf(u))l2 < too a.s., and
Me mm/l 112 < too a.s.
D.3. Proofs of the Lemmas and the Theorems
D.3.1. PROOF OF LEMMA D.1
Proof. Consider the case where T is finite. For any T E (0, +o0), the ayoonemtial-logarthnii transformation can be applied to 2, resulting in
D
11 UR, = exp {
< In
1+
+1
A (BT.k)
VBT
In(1+z)<r VI
D
T
exp
p
1
VBi
+
Vank
k=1
d
+00
Fr-1 }
D1
exp
p
+1
E
B1 - De.
V
k=
t=
D
toc
exp
p
+1
Σ BBB) 1-k
((VB))
Σ Aes
F Kー
V
<
exp
p
D
+1
+oc
E
Σ (BB
Σ
A
F
V
Am
km
i=1
24

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
It can be readily verified that Σ A., in the inequality above satisfies all the properties of X, outlined in Lemma C.5. Consequently, by Lemma C.5, we deduce that for any 0 < T +00 and any p 2 1, the y-th moment of its reciprocal is bounded, i.e.,
R
< Co.d.p < +00,
where Co,.pp is constant depending only on d, and Letting T - +o and applying the Lebesgue's 's Monotone Convergence Theorem, we obtain
A S Coddp < +00.
D.3.2. PROOFS OF LEMMA 4.1
Proof. By the L-smoothness in Assumption 2.2, we have:
L1
f(uc+1) f(w)) ( ue) +
|ue+1 uell?
Then, by substituting the iterative formula for un from Equation (2) into the above inequality, we obtain
B1
d
[(u+1)) s(u)) S
Σ No Vif(u))
(u.))(( + Lg
1
31
31 2 d
+ Li
A
1
B1
1=1
Voe Vif(we)ge.
(V.f(v) - v.f(u))))(.)
i=1
e,,2
81
d
+
A (.f((u)) +hg
Fr,
31
L,,3
d
31
+ Ls
1
B1
2
m
1,
(19)
8
Step (a) employs the identity V.f(u,) = ves(wr) + V.S(u:) - Ves(we). Next, we handle Or,1, Or,2, O1,3 and e,,4 separately. First, for ,,,1, we use the following identity.
d D V, (1:)))))
11,1 = n Vef(weegrs =
no Vif(wi)ors Σ i=1
Tn 1i (w)))
A V=J(w))) +
no Ve V.l(e - gc.)),
(20)
(1())
1
where A in the above equality represents the i-th component of the vector A,, which defined in Equation (2). this way, we decompose θ into descent term -i i=1 ((t), error term 1r,1.1, and martingale difference term Mr We will further scale and control the error term 11111 Specifically, we have
1 = E [ v.f(w:) Fi-1
25

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
Aii Vif E Vi, (
M
M Vef(w:) E V A | Ft-1] + Me2
d
To M (v((())))
+
E2 [V V 8(-1] + M,
2
2 ==1
E
G(() +
Elgi, [8-1]] E|A,, F + Mr
2
2
i=1
E 4(1
Elghs ( -B|,,,1 | F M222
d
F--1) Σ ElAu. Bh-1l) + Mr
W
G(0) 2
Σ i=1
B
Blgg 2
2
G(() \
(A+ B)) +C):
Σ
BlAus 18--1) M,
2
i=1
1
Σ
4(1) + +/(A+ + 22,,, (w)
Σ ElA Fr-1l
2
d
Σ E|A.. | { + M,,
i=1
d + +
1
Σ
((t) + 2 (A + (l,
Σ
E ElA. / F--1l
D
2
1=1
i=1
A
E|Ar, [ - Ar:))
+M,
(21)
Mr.3
In the above derivation, in step (a), we utilized the property of conditional expectation, which states that for random variables
X E Fn-1 and Y E Fn. we have E[XY| [-= = X E[ Additionally, note that A.,; = V VA. < Mo Ar. (due to Property 2, we know Ae, 2 0, so taking the square root is well-defined). In step (b), we employed the AM-GM inequality, which states ab < 22 In step (c), we used the Cauchy-Schwarz inequality for conditional
expectations, namely B[X & B X &
Y p- For step (d), we used Property 1. Specifically, - E
have
Σ
13 =
|1 (A+2), +C.
Substituting the estimate of 0,,111 into Equation (21), we obtain
d
d A+ BLBBB A. (wx) + C
1,,1 = 2
Σ
(1(1
+
Σ
Ars + Ma, + M, + Mc
2
1=1
1=1
M.
26

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
Then, Property 5 to replace ((( with f(u) obtain
2 Σ (i(t) + (A+ (A+ BL, + +, f(u) + +C E D
1
11,1
2m
(Ly 1)
2(1 - 31)2 117 mm-1111 +M, M,.
(22)
Next, we handle the term ,, through the following derivation.
d
r,2
& (Ve((ue)) V=((u)))
(M
2 2m1
1 d
Σ
(
v.f(u)))
2
i=1
Σ Hh. 2
V f24))1
d
L2
No,,i
+
|lue uz
2
L3
2
+
11 mm-1112
(23)
2(1 31
Next, we handle the term 01,3- We have
1,33 A. S
(24)
For O1,4: because A S 7 we obtain that
1 =
2
No Σ
m = || 14-1
(25)
1=1
1=1
Finally, substituting the estimates of O.,1 from Equation (22), Or,2 from Equation (23), Or,3 from Equation (24), and e,,4 from Equation (25) back into Equation (19), we obtain
f(u(11) fr + Σ nors ) (f(u) f + Σ
Sitt) C, f(u))
2 1=1
flavts)
flm))
d
+ C2llmie. m + Σ V.fl + (L, +
Dt, + Mr.
2
2
1=1
where
G = (A
BL1 C2 = 2(1 31)2
L3
B1
)²
+ Ls
(26)
2
1 31
To the second term on the right side of the above inequality, we apply the inequality S(S(w)) < f(u+) f + C' CL The 1.4 = f(u) and then move the expanded term to the left side of the inequality, This obtains
1 Σ ((tt) + C. f(4)
f(ue+1) - (1 GA))((u --
2
27

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
+ C2llBor-1 omm + D Vif(u))m--al
Σ
1=1
+ (L, 1
ii Mc.
Next, we define
A V
E
(V 31 )c
D Fk-1
1=1
L1=k
Observe that
(1
D1
I+ 11+
V
+ 1 B
V3re0
where Dj is defined in Lemma E.2. Thus, we have
f(1e41)=
D1 (i-v8 VB1 +1 (1<(--V
A f(1))
1
Σ
G(() + CTA, f(m)
2
i=1
+ C2 o mm-211 +
D (
+ (Ly 11
Tn Ii, + M,.
Next, we construct an auxiliary variable
TA = II
1
1- VBi VI- +
Dr
1
A Vork (vrik) ) (12 IT = 1.
1=1
Multiplying both sides of the above inequality by II we obtain
d
[a.f(wt+1) IA.-) AA Σ
+ + CallMann m2 2 +
A V:f()))))mm
i=1
d
+ (Ly + 1)
Σ
Ne Ph. + IT.
1=1
With the inequality, we complete the proof.
D.3.3. PROOF OF LEMMA D.3
Proof. For any & E R, we consider
VST (T+1)6
We have
VST (T + 1)6
ST
So + -T
11ge 2
So
T
11
+
(T + 1)0
(T + /ST
(T + 1)
ST
T + /T
So
19
T
11 12
< TT + ST
S +
T /S
(t 1)0 S
T
11
de
(1+))
By multiplying both sides of the above inequality by HA and noting the monotonicity of (II,, as well as the fact that TAT for all T 2 1, the lemma follows.
28

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
D.3.4. PROOF OF LEMMA D.4
Proof.
We take Φ 4 in Lemma D.3 and bound the expectation of the partial sum Σi=1
A4,r.
We have
Talelloel1
T B(llga
E
A4
Σ
E
Σ
E
Σ
E
(1+1)2 SS (1++1//S
(1+ /
1=1
1=1
t=1
Property
T
(A+ 2I, B3) IT +C+
E
(1+ 1)2 /
T
T E [[ax)([wr)))))))))))])[)[)){)))) - -8 + CC+ Σ
< C3
(27)
(E + 1)4
1)+
1m1
1m1
where
A + 2
C4 = C
C =
VSu
Based on the results in Lemma D.2, we can compute:
E [[ [*]] O
E 11 9kll? =011)=0(1))
Substitute the above result into Equation (27), and combine 2p
Σ
1
1)P
(1 1)3
We get
E
MssaA O(1)
can be observed that the right-hand side of the above inequality is independent T.. Thus, according to the Lebesgue's 's Monotone Convergence theorem, we have
TA
Ast a.s.,
and
400
T
E
Ass
lim
IT A4t
lim T
E a A4, 0(1).
T0000
1=1
By setting
toc
( = dd
Σ
and combining Lemma D.3, we have
ST S (T < 11 (T + +1*C.
(28)
Mcanwhile,
+
E[[] Vdv + E
Σ
Ati 0().
(29)
Then through Equation (28), we have
1
In
ST
< 4ln(T + 1) + In
(T=
2
29

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
< 4ln(TT + 1) + in max fer (e, (1+ In (max fer ( ) 4ln(T +1)
s <4In(T+1)
1n(44]221/2 S
41n(T (1 "inn iinmmax {er (
The lemma follows
D.3.5. PROOF OF LEMMA D.5
Proof. According the second conclusion of Lemma D.2, we have
T
d
T
E
Σ
6(1) - Σ
Ie o gall" + O(1) E
To prove the conclusion of this lemma, we only need bound Σ/= E Il g Specifically,
W gh
d
gh.s
B Me, o 9: = E
E
S E
Ut, + n2)
2
to
Property
(t + 1)20
d
1
gh.
E
(30)
f26
ai
(t + 1)26
Sea
(a) 26
(31)
Q1
S 1+4
In step (a) of the above derivation, we apply Lemma D.4 to (f + 1)26. Specifically, according to Lemma D.4, we have
VS, S - (t + 1)
Next, with the estimate for E M/,, o gel we can estimate 7 E
[n,, o gell? To achieve this, note that
T gt 12 =
226
Fi.s
2
Sr.
1
E Mo,
< E
11
dr
St, 1+
0n
i=1 1=1
α1
So.s
22
C
i E (0, 1/2)
0,
2
E
In
de
if 0
a1
(1),
E (0,1/2)
(32)
d2
E
In
8T de
In step (b), we used the following inequality, i.e. the Hölder's 's inequality, to obtain the O(1) result
E
< 5
[c]
E
IT A,00
4-8
Lemma D.I D.4
6/4 1/a.c" d-1
0())
u,d, 24
This completes the proof.
D.3.6. PROOF OF LEMMA D.7
Proof. We only present the case where d = 0. The case where 8 >> 0 can be treated using exactly the same approach. Recall the approximate descent inequality (Lemma4.)
d
d (t()) + Czllmoe, o - Σ A V (u.
(s - -IA.-If(u)) < IA Σ
30

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
d
+ (by + 1)1 1
Tu + I.
2
We divide both sides of the above inequality by It² + 1). Noticing that In (t + 1) < Inn + 2). we obtain
Is,es(uc+1))
II [1x=11((1))
I C2 Me o om-11
2
A V. V. mu-
(33)
In In (t+ 2) In (t+
In (t
In (t (t+1)
Mr
(L) + 1) + 1)
II, (t+(++1)
(34)
Assign
Ma my-1 11
A. V.f(u))ee.. (t
Ω C2
+ +L, +
In H+
In (t +
For the term Σt
4:0 [[]] we can estimate it as
Ma-1 o m
E V.
Σ 1=1
B[4] = C2
In [+1
In + 1)
1=1
1=1
+00
St,il
+ (Ly
( +1)
+o0
Blme 19i.l
0(1) + Σ
E
In ( 1)
1=1
d
E ai ca
0(1) +
Σ
Σ
In (St./o)))
1=1
In step (a), we use Property 4 and Lemma D.2. In step (b). we use the last result from Lemma D.4, which states
Se.5
S < (T
Then, using the series-integral inequality, we bound Σ 1=1
B[Qr] and obtain
00
d
+
(5 o2
E(a.] S 0011+00
Σ
E
In
Sess
Sea
i=1
>2
d Σ
222
< 00
dr
ln?
-(1)+ (B
Next, we use the explicit expression for Ç' given Lemma D.4 to bound El5(2). We have:
In (max fe, [T {))] < +00.
E = E
16
1
2
As result, we have
+00
Σ
B[Qd < +0G.
(35)
31

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
According to the Lebesgue's Monotone Convergence theorem, know that the above result implies
E[2, F--1l < too a.s.
(36)
Next, we take the conditional expectation with respect to f-1 on both sides of Equation (33), which obtains
II (Aa++f((u+t))
Na,)(w) In (t+1)
E
F1-1
(37)
2t+
Based the result from Equation (36) and the Supermartingale Convergence theorem, deduce that TI To (fue)
(C+1) converges
almost surely. Then, according Property bound f(w;) - f using f(t)). This concludes our first result. Next, take the expectation both sides of Equation (33), which yields
f( In +t++
f(ue) In +
S
+ + 0.
(38)
Based on the convergence result of the expectation summation in Equation (35) and summation formula for recursive sequence, we conclude our second result. Thus, the analysis for the case 8 = 0 has been completed. The case d >> 0 could be analyzed using the same method, which concludes the lemma.
D.3.7. PROOF OF LEMMA D.8
Proof. Since the case of 8 > 0 is relatively straightforward, we first analyze the scenario where d >> 0. According to the second conclusion for > in Lemma D.7, we obtain
Holder's inoquality
B B 3/4 E
3/4 3/4 ///1 ATT
II
TT
E
II
A.T
3
ST)
Then according to Lemma D.I, we have E 3 S C,,d,3. For the other term, B[Il Sr.. we can handle the term as follows.
B[ll,,rS]] < So +E
IA
S de + E
Σ II |1de
1=1
T
= du +
E
B[lgel 2 3|
1=1
Property
do +
E (41 +0]
[=1
Lemma
du + ((A BL, CCT. I
This implies
Sr/ < 0,d,3 (dv + ((A ( -((")))
For the case where = 0, we use the same approach as in the case of 8 > 0 and apply the corresponding conclusion for
5 = 0 from Lemma D.7. Thus, we obtain
E B|S 3/4 3/44 In 3/2
D.3.8. PROOF OF LEMMA D.9
Proof. We discuss two cases based on value X. the first case, when À = we have
Vt-1 = (1-
Us +
Di (V 1 1),
1+1
1 1+1
32

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
that is
(1 + 1)0++1 ti + ge²
Summing over all the coordinates, we obtain
(L 1) -EE, + +1leel??
(39)
Multiplying both sides of the above equation by II and noting that III, 2 I4 we have
(t a+ Eeess ell + -1r.1199111
Taking the expectation on both sides, obtain
(t + 1) E|
E m
E A 1 9 11
= + I E [1 11 11,,1,111111
Propent 1
tElll, + (A 2L, B) ELLL,, +
< Eol + (A + 21, B)
[up - - +C
121
Lemma D.7
E + (A M +
if E (0,1/2)
Eellla + (A
i
By iterating the above inequality, we finally have
E 2
+ + ((A+ 2L, C)t,
i (0,
(t + I|T,, Emenl
E BlIl 2 M.,
=
This implies that for any 2
if E (0, 1/2) ElIIA ( =
Ellaa ++1 Ee04
that is
2 (A
if E (0,1/2) i =
sup 21
E.,] (
21 + (A+ BL In² C,
Next, we discuss the scenario when À > 1. In this case, we have the following inequality.
Expor S Ev. (t 1)a 19 12.
We multiply both sides of the above inequality by II and, noting its monotonicity, we have
E1 I H. + Ia (t 1)x 11..11
(40)
Taking the conditional expectation with respect to Ft-1 on both sides of the inequality, we have
Ellla.+ Emets Fr-1] E. + l1.
(1 11aa Bl 1113
According to Property 1 and Lemma D.7, we obtain
11r
(1+ 11.
33

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
+ B)) ((A+ Sup211 (fw)) (*) + +C) +o
i (0,
(141)% In 2I, (A+ B) sup221 ([wx)((()))1))))) +C) Ets (1+1)A>
i
<0000 a.s.
By the Supermartingale Convergence theorem, we obtain that 1,,r2in, converges almost surely, which implies that sup121 Ee, < too a.s. According to Lemma D.I, where sup121 A +o0 a.s., immediately deduce that suP:21 En, < +o0 a.s. Next, we prove that the expected supremum is finite. Taking the expectation on both sides of
Equation (40), we obtain
1
E
E
11
By summing the above recursive inequalities and using the results from Property and Lemma D.7, we can easily prove that
2( C) E (++1)x
if (0,1/2)
sup B <
+00.
22
((A+ C) E (++1)x*
if8
With this inequality we complete the proof.
D.3.9. PROOF OF LEMMA 1.10
Proof. According the result from Lemma D.5, it is straightforward to see that when å >
E a Tt-1 (f(m)
E
1
71-1
V V.f(2))))
VEn-i1 + 1
/mmmi
+ M
1=2
t=1
E
Si(t)
C4.8 < +00.
Next, apply the Lebesgue's 's Monotone Convergence theorem
+o0
Th- [
ETA,
Ma.
< +00 a.s.
Ee
+
1=2
Then, by combining the almost surely boundedness of sup:21 IT and sup121 E,, from Lemma D.I and Lemma D.9, follows
m [f < [V no- 1 [[[])
[[[(w)]] + (upp 3/2
(
sup sup + u)
Σ
to0
II Mh-
V (wx))1
eer
Eve..
< +00 a.s.
According to the L-smoothness assumption (Assumption 2.2), is immediate that
[w:]( -| s Lyll u.ll 1- 3, | mm-illl
that is,
LJß1 || o m--ill)
[[f(4))
[Vvf(
1- 31
223.83
(w.))l + [1- 81)2
0
34

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
This implies
toc
+00
213,39
+oc
Th
(V(()))
2
m n/ [[[
(1 B1)
M o m+-11
According to Property 5, for any 8 O.
1
2 T
T
E 1 m mm-1112 O
Σ
Me, 9:ll2 + 0(11
B1
Eq. (32)
O(1).
Applying the Lebesgue's Monotone Convergence theorem, obtain
1 2
M mm-1/12 too a.s.,
(41)
1 31
that is
+00
213,89
ne V < D (1(2)) +
M a am-1112 +00 a.s.
(1 - 32)
D.3.10. PROOF OF THEOREM 3.1
Proof. According to Lemma D.5, we have:
T ΣE E IAlt
Ca,6
if E (0, if - 0
(it)
<
CG
According to the monotonicity of Tho,, in Property 2 and the monotonicity of IT itself, we obtain the following inequality.
[V
C4.6: Cs + Co
ifg (0,
Σ E TAT T (v++
S Σ E TAT c(0
For the leftmost part of the above inequality, we apply the Cauchy-Sehie Schwarz inequality and obtain
T
| I (w)) )1 T
1)
E | T1+8 /eT + [1]]
Σ
E
T
2 E
V (w:))l
+の ( UT + 1))
which means
T
Ca,s E (VT++ 14)] C. E B
if E (0,
[Vf(w;)]
T5 ( + n³] C. E 1 T + m)) E [In)s)),
if 0
1=1
Combining the results from Lemma D.8, Lemma D.9 and Lemma D.I, we obtain
E 2 2 t (VVT w)] < 2 / /BIT>
BlA 12)
1/2 O(T
ify>1
c Cug o(T
1, 8E [0
ify å 0.
35

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
and
[[[n(Sr)] - ( In(E[(7/))
4
(In 0(InT) O(nn
if E (0, 1/2) if
Combining the two estimates above, we finally obtain
O O(VTIT),
if E (0,
T
E
if > 1, 8=0
(42)
1=1
O(VTInT),
= 6=00 0.
This implies that for any E (0, 1), the inequality
ifg E (0,1/2)
T
T
V f(w;))11
i 1, 8=0
T
8" VT
=f 8=
VT
holds with probability at least -
D.3.11. PROOF OF LEMMA D.6
Proof. From Eq. (42), we have V to 2 0,
T 0.
1
lim E inf +00
V [
<
lim +00 T to
E
Vf(w:)]
t=
Since, for a fixed to. the sequence (inf Ilf TTy is monotonically decreasing and non-negative, by the Lebesgue's 's Monotone Convergence theorem, we readily obtain:
E inf [[((w)]]] E>ta
EE
inf T T to T
lim
[V[(=a)]]
= lim E inf LoSIST
[V(())]]
=
T-+2
The second equality follows from the Lebesgue's Monotone Convergence theorem, which allows the interchange of the limit and expectation. Since inf [[:)(()))) 2 0, we can directly deduce that inf ||V [W((ll = 0 a.s., from the fact that E finfesto [ 0. Furthermore, given the arbitrariness of to, we can obtain that there exists subsequence (wo Je of (we such that
lim /Vf(W,, )l = 0 a.s.
(+0
This completes the proof.
1.3.12. PROOF OF THEOREM 3.2
Proof. According to Lemma D.10, we have
[[()) - -Vf()) < Ly well L5
| mm-11l + 0
This implies that we only need to prove lim;-++00 Vf(u)) = 0 a.s. To achieve this objective, we proceed as follows. For any > we construct the following stopping time sequence (n,m)n21
T1.1 := min (t 2 1: [Vv 1}, T22 min (t > n.1 : [V $ 1),
II this paper, we adopt the following definition of stopping time: Let be random variable defined on the filtered probability space (9, F., FnnneN PP) with values in N U {+oo]. Then is called stopping time (with respect the filtration (Fn)nen) if the condition
(T n. E Fn holds for all n.
36

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
7,2k-1 minft 712k-2 [v)(4) > 0. 7122k min > 712k-1 [V $4.
According to the subsequence convergence result in Lemma D.6, we know that when 72k-1 < +o0 (A k 2 1), it must hold that T2k < +o0 a.s. We now discuss two cases.
When there exists some ko 2 1 such that T26--1 = +00, this implies that eventually (IVV/(u))ll)>> will remain below 1, i.e.
limsup [V <
(43)
+
Next, we focus on the second case, where for all 12 we have T2k-1 < +00. In this situation, we examine the behavior
of sup Sttcra [ue)ll We have
sup Tak-1St<1n Strraa
IV SI+
sup
| Il [Vf(u))]
Tak
S(+
|V
| f
1=T2k-1-1
I-smooth
Thk
S 1+
Lij
1 u-11l
1=
Bq. (2)
F2k
S 1+ Li
Mo gele
1-
Te,1
31L3
T2k
| m
B1
Tka
Our next goal is to prove separately that lim sup
kk,1 = 0 a.s. and lim sup sup T2,2 a.s. For Tk,1, we have
T26-1
T2k -1
d
Me, gill
Tk.1
no Per.ilau locce
T2k--1
72k
Th Ig
TaN
Th gr.e
/vz + 14
T26
1=1
Pm 1
T2k
Σ
Σ ns El
T2k
Σ
nelle. - 11 1-11))
1
- Σ
+
The
Σ
Σ
melleaa Bllgr (l
p
1-
1=
Te.11
Ta.1a
For TK,11 have
Property 1 S
T2k -1
TR.11
Σ
(aA++ (((()))))(((a))))))))))))))))
1-
37

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
$ ((A 22, -up(f(()--)))
Σ
121
(=
T2k Σ
= ((A + 2 B) -f)
(Tran-i
T/t
1=
(a) $ ((A + 21, B) -f
Tak
mlll )
(Tree +
Σ
mell
(=72k-1
In step (a), this due to the fact that, over the interval [T2x-1: T2x), we always have [V > l. Based on Lemma
D.10, we know that
Th [V/())) < +o0 a.s.
By applying the Cauchy's ' convergence principle, we can prove that
lim Σ m ==
On the other hand, it is evident that lime 1rax
0. Meanwhile, based on Lemma D.7 and Lemma D.1, we have
sup(f(wn) /z) S SuppTz!
Sup (TA - /3)) < +00 a.s. f21
121
121
Therefore,
limsup TK,1,1 = lim TR.1,1 = O.
t-+
For 1,,, consider the following martingale difference sequence
T
X
mllaa - Bilgesll F.-1)).
We compute
ne 71 - Bllgcal (onll) ) 2 |
+00 d
EE
E[(1gaal
E
Ellga,a 7
t=1
+00
<d
Ellgel Fr-1l
1=1
1=1
Property/
420
d
(A 2T, B) (wp(f - f*) + +c)
<
111
(21
1=1
i=l
400
<d
Σ
(A+2) 2I B)
sup a (sup[S(1e))= 14) 121
(unp(/(x=-))+++)))))))))
Σ m
t=1
121
Lomma D.I and D.7
00 a.s.
By the Martingale Convergence theorem, obtain
+ d
lim +00000
X,
nellou.sl - Ellgesl F(-1l) too ass.
38

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
Using the Cauchy's 's Convergence principle, we prove that
T2k
sup T 1,2,2
lim Ao +000
Σ (1 E E
72k
Combining the above two limit proofs for T,,1 and T,,,2, we conclude that
lim T,,1
k-++00
Similarly, it can be shown that +o Tk.2 a.s. Combining the limit results for Yx,1 and Yx,2, we conclude that
lim sup +0+000 T2k Stt322k
|V -1+0=1.
Moreover, combining supp Ster2011
[()) < I, we can deduce that
sup [v+]l < a.s. t-++0
Then, due to the arbitrariness of I, we conclude that
lim sup [V a.s.
t-++00
This implies that
lim t10+00
[f(u]] = a.s.
D.3.13. PROOF OF THEOREM 3.3
Proof. Since we have already proved the almost sure convergence in Theorem 3.2, it is natural to attempt prove Li convergence via the Lebesgue's Dominated Convergence theorem. To achieve this, we need to find function h that is mc--mcasuaalle and satisfies IE [4] < +00 and such that for all f 2 1, we have |/ [w:)ll S [/]. Since for all f, we naturally have [[V S sup [[ we only need to prove that E[supe21 ff(w))]l < +oo. We proceed to achieve this goal in the rest of the proof.
Recall the Approximate Descent Inequality (Lemma 4.1). We have
[AIf(W++1) IA.-If(u)) S Ta
((t) + C2llmann m
A V:f(())
d
+ (Tg + 1)
Σ
Ne Hi.s + TT.
(44)
For any À > 0, define the stopping time the first time the sequence (TA,f()))) exceeds X, i.e.,
A = min 2 ( > A).
It can be rigorously verified that is stopping time with respect to the filtration (Ft).21 and satisfies special property
[TA = n]] E Fn for all 2 1. This implies that the preceding time тX - 1 is also a stopping time. Next, for any deterministic time T' 2 3, we define TA.T = TX A T. We then sum the indices of Equation (44) from 1 to TX.T 1. Specifically, we have
TAT -
TA--1
11 Slappl(l) + C2
Σ
11
Σ
A Vel(u))meall
1=1
TA
+ +(1++1)
me
Rit
39

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD Taking the expectation both sides, we obtain
TA.T
[IA..--(((n.)) - E
(
+ C2
I om,
TA,--1
TA,--1
/ V.](
+ (by + I
Σ
Mh
E
U.
Since (,,,, Free is martingale difference sequence and TA,7 S < +oo, by Doob's 's Stopped theorem, we know that
TA.-1
T M =.
This implies
Th---
E
s
E
[
+ C
1 o m
TA
d
TA. d
+
E
+ + Ar..Vef(u))mm..dl
1)
Using Property 5 and Lemma D.2, we obtain
--.-1
TAT-1
C
E
Σ
+E
A V.fl
T d
(Ly
1)
E
omm-11?
+
T d
(Le 1) E
=0 2 [11 o 00il99]
+ +01
O()).
This means
E Marrr-Ifuuu
S M < +00,
where
+00
+oc d
M = E2E
1/ o 11-111
+ E
A V.f(u)mm-Ll
im1
+oo
+ +L,
To 1
40

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
Meanwhile, observe the following event decomposition
T-1
T-1
sup I1s.t1f((u)) > X 25KT
Ta = kj Uba kj.
k=2
k=2
Moreover, since for any * k, we have [TA,T = j] [TAT 0. follows that
T-1
Markov's incquality
sup 25teT
IT IT,
> 1)
Σ
Plza.r = k]
E
k=2
k=
1
M
E
- f((TA))
S
(45)
X
Next, for any K 2 compute E (sup2geer (1s,,-1(((e))
3/4
^ ^K)
We have
E ( sup IT ((w)) 3/4 2
K)
d
(pp)
IT -
AK>0)
AK>
1)
Ju
agieT
(% ida
P
(
3/4
A AK> 1 1
x
12SKT
Fubini's 's thenrem
+00
(1,100 1d
(
sup -as-if(us) 2SECT
3/4
AK > x 2 1))
P
3/4
PP
sup II 11,,)-1((uu)
AK > d
d1
0
25
3/4
<
1 +
TP
sup IT [ 25KT
AK> A dd
+
=
=1+
T
sup 22
A KK/33 > 14/3 da
1
T
sup 22
IT -
> > aa
Bg. (45)
too
M
<
X4/3 yd
1 3M.
Next, we take K - 40o and apply the Lebesgue's 's Monotone Convergence theorem, which yield
E sup (f.-)f(u)) 3/4 251T
" 3M.
3M.
By taking T - +oo and applying the Lebesgue's Monotone Convergence theorem once again, we obtain
[(
3/4
E
1 3M..
122
Note that for any finite we have IA 2 TTx (where IT is defined in Lemma D.1). Thus, we have
3/4
3/4
E
sup f(u))
< E
S 11+ 3M.
122
122
Next, by applying Hölder's inequality, we obtain
[[ sup f(u.)) s 1/3
1/2
3/2 II
8,00
22/3
1//4
sup f(we) 122
f(we))
3/4
Lemma D.I
$
1/33
C//3/2(11 + 3M32/3
122

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
Then, according Property can bound f(w;) f using f(u)). i.e.
f(wL) - f - (L, + 1)(((u) - f*) + (L, + 1)
M o mm-1l1 f
2(1 B1)2
$ {(1,+1)f(u)) + (L, - L.ft
20, (1 3,)
That means
( sup (J(wr) (((n))-)))) (²) 1/2 122
(Ly (b,+ + 1)39
E
s Vb IC1/3 v,d,3/2 (1 3M)
+ L51s4
201 - 81)
Finally, according to Lemma C.2, obtain
$ /2L [(sup (Sup((w))) f()) 1/2 = 122
E
sup
[Vf(we)l|
122
(VI,+ 22
IC
0.33//2 (1 3M)
(L, 1)89 2a, B1)2 Lg -
Adding the first term concludes
sup [V](())]]]
[[V[(( 22L,
(VI, +11 1C
(1+3M)2/
3M)2/3
201(1 - 33)2 + TslM
(L3 + 1)34
+o0.
By combining the almost sure convergence result from Theorem 3.2 with the Lebesgue's Dominated Convergence theorem, we obtain the L1 convergence result, namely
lim [f())) = 0.
E. The Proof of Lemma D.2
E.1. Auxiliary Lemmas for Proving Lemma D.2
Lemma F.1. For any epoch step Z 1, the following inequality holds
|mm| < (1 - 31) Σ of k "119 and Il,., mill (1 (1-13 (01--1) B1) Σ Bi
1 o 9k
1m
km
Proof. Due to Property 4, we have
|mm < B1 1=
11)11
We multiply 1/3 on the both sides of above inequality and obtain
m < 3, (t- 1) 11 + ST '(1 11),,
Iterating the above inequality, we acquire
8 m1,. < || + +(1 -31 Σ
3 11
k=1
that is
|mm]] < 81lmoll 2 + (1 - -B1) Σ
8 11
km
42

---

A Comprchensive Framcwork for Analyzing the Convergence of Adam: Bridging the Gap with SGD
(1- 31)
81 11
Similarly, applying the same approach and noting the monotonicity of Tor,s, we obtain
11,, mell? S (1 - 31) Σ 3 1lm, gxll?.
Lemma E.2. For any t and any positive, monotonically decreasing, adapted process (Z(t), with Z(t) S the following inequality holds
d
S (1- -1-311(11-) vB1)
d
Mo 1 (())( (
8
a
+ D1
Z(k)(v 31) 12 ABI f³)
k=1
n
+ D2
(v31) (11))==+000 Z(kk)llee_, mm-1l1
+ D3
+
Nu
k=1
where
d
A B
=
(v B1 1 A., F Fx-1
1=1
Nn,
=
A P (
- - 18
1=1
D1 2
L
2
(A+ B) +1), D2: =
D3
((A+ B1,
(46)
1- VB
1- /B
Proof. Note that
(ef(w,) (8 (1 -1- - (1- (1-
< B1 V, (T:f(w:-))m:-- + (V. - v.f( (1 (wr)er.l
L-smooth
B1 V (w: 1) + (1 8,) V + Ly 1m-11mmmmmm
By iterating the above recursive inequality, we obtain
(.f(w))mm.l 5 (11-1(1)))) B1)
o (V + LG Σ M o ome-
Then we get that
At. (1- Σ 8 V.
+ L Ar,
3 ()=kZ(k)ll o am--rllm6-.d
km
43

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
Next, we proceed with the calculation.
n1
n + Ls
V3))""A,,,0)///( S (1-
3 (k)) V
1
0 Z(k) ([k))|[[0e_1 o mx
mla
k=1
= (1- 31)
39 A V.f
k=1
11
B1
3
o
= (1 31
31 V.
A= t=
+
t=
= (1- B1)
(B1)*~AA: A..
Am
+ 1,
B1) k- Do.
-ma-1llma-u.
k=1
+00
< <1- Σ
V B1 Des
De.
k=1
1=
T
+ 1 - (VB)) k=1
( 31 -- 7(ko)]]oo>- o
m
n
= -1 - 31) Σ (
T
n
3 n 2(k) Mua-1 m
(47)
1 (VB))
Next, we estimate n, and obtain
V 1n,i
A A/n
( E AAV (Z)))
k=1
Nn.k.
AM 1
1
8
k=1
+
2
E²
AvB.,dd(/3)) (Z(K)o2..11a11 + Σ Nu.k.
1
B
Am
km
44

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
1
1
n
1,, (/ (V:((wx))
Tu
8
k=1
+ 2
(()(VB)))
E VT... [
n +
Σ Nu.k.
(48)
V
Summing Equation (47) over the coordinate components i, we obtain
n + L L d
AV I (11-3) Σ
V
n.
31 n (]kk((()l -
i=1
Eq. (48) (1 - 31)(1
31
d
T/o [k)) B1) (V.
-
8
1=1 k=1
d
2
Z(k) B1) n E|A
/o.
EE [o xn-
i=1 k=1
Lf
31) n- Z(k)lluua_, o 1l
+
Na,
31
k=1
>R N..k
(1 31)(1 vB1)
Tlu 1. 2(k())( (V.[(wx))
k=1
2
Z(k) (1)
B VT I
E |llox| 31
1 k=
I Voix
Lf
n
31 n- 7(k))loo o omm-11l
V31 k=1
Nr,
(49)
k=1
Noting that
Property
E
|1l9 ||
||
S
(A+
- (A+
Using the above inequality to estimate the first term on the right-hand side of Equation (49) yields
d n
1-
Σ
B1 (V)
nu
8
k=1
a
+ D1
z(k) B1) n - (J -f) f*)
k=1
a
+ D2
B1) n- ((k) 11
+ D3
z(k)(v 31) A /
k=
+
N
km
45

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
where
2
(A (A+ +), D2:= L vB Ds
2 1- ([A++),
D1
VBI
Lemma E.3. For any 2 1, <>> 0 and any positive, monotonically decreasing, adapted process (2(1), with
(t) 1, (tt 1) (t) S , VJ, (1) (f2 1), the following inequality holds.
n
d Σ
3(1 3(1-B1) -1)
d
n Mo
Σ
31
Z (t) V:f(w:)mus 5
8
1=1
D1 +1
z(k)( B1) " (f -f)
1 v/n
D2 + F1
(V 3131) (/33)*>>(l/m 1
VBT
+ D3
Z(k)(v (I6llV/3)11 3A JT..
B k=
+
N
1 VBI
(VVB))*
Bi)
8 MM,
(50)
k=1
where
M61, = -
- -g.,),
and Nn,k defined in Lemma E.2.
Proof. According to the update rule of the Adam algorithm (Equation (2.1)), we derive the following recursive formula
-t Vef(we mu, (. + Z(t) (uf( (81m1-1,-- m4,))
- (.).).))........
-Bi Th, )
-Bi((t - 1) (a0
(0)
-B1 1/ 1,1) [.))
+ (Z(t 1) 2.
Bi Z(t - 11- (. (wr)))
+ 81 - 11
(6)
8, (1
+ 47(1)A 1 (..
317(t - (. (1-110100
+ Ly o mm 11 Me. m-111
(0) A i (()
1. 7()A VJ. (V)
Le mi
2/7 Ne. -
2T
-1:((t V - (1- (131)a(()) (e
46

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
b /le 0 10m0-1llm Ne. 1.
(1 31) (.f(we) (Vaf(()))) 9t.s)
M
In step (a), we apply the following substitution
Mo Z(1) 1Ju, 1) (Bor. = 1Jo ..))((1) Th, .z((Z() Z(t 1)).
In step (6), first apply transformation to the fourth term from the previous step, denoted by
-(1 (t) V V.f(we)gr,; -(1 mi V. (1 (().
Next, we combine the second term of this transformation with the first term from the prior step Step (b) in order obtain
((t-1) We then use the inequality 7(t - 1) - Z(t) S の vo,,
Finally, in step (c), we begin by applying an absolute value bound the first term from the previous step:
( $ (....
Next, for the second term in the previous step, we use the following application of the AM-GM inequality
1 ((T)A (.l(w:) S
- 20A
L2LL 2
No -
2T.
2/7
Summing both sides of the above inequality over the coordinate components and applying the arithmetic mean inequality, we obtain
d
1 Z()) VBr [f(w))l
(tt) V V.f(w))m,, S B1
Σ
Z(t
+
2L,
d
d
A, Z ( + Filloo,, mm +++) Σ M
d
(1 B1)
Z(t) (()
i=1
Lemma C22
S
Zt 1) V.f(w: (s.)ww) -
d
d + Fillyer., + mm Σ
(()
M
i=1
d
(1 31)
where
: := vdL, + L2
2
By iterating the above inequality, we obtain
Z mt) V V.f(wy)mu
<
Σ 3 Σ
A k (
Σ
Z(t) v (f(we) f*)
1=1
47

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
+
Fi
91
1
o +m=
+
$1 3 MM
k=1
k=
(1 11)
$1 k 7(k
(((
k=1
We further obtain
E 313) n- Σ
n
VB1
n-1
t
k V
2m1
1=1
km
+ F1
B1
n-t
3
k
11
o ml
1=1
kml
31
Σ
81
k "M
t=1
k=1
n
d
31
Σ
7(1)
(F) -5)
(1 B1)
Σ
VB1
B9 3--ZZ(k)Tn Z(k)
1=1
Lemma C.1
1
n1
Fi
B1
17
mm=
1
B1
31
Σ A=1
8 8
d
+ Σ
31 n-t
2(t) (fu))())) ff
t=1
(1
B1)
Σ
Z(k)))) i. (v:((w)))
(51)
Now, we focus on estimating the term 1 By applying Lemma E.2, we obtain
1 3
no
B
H=
Y=1
D1
Z(k)(v Ae. - fr)
1 V
k=
D2
n
B1 n (2())= |
1
D3
n
((k)((31)) VTL.
1 3
1
Nn,
1 /
3
k=
48

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
where D1,
D2, D3: A V are defined in Equation (46). Substituting the above estimate for Ln,1 back into Equation (51),
obtain
d
3(1- 31)
B1
(t))oe V V.f(wa)me, S
Mek 1. (k)( (10 (V.
8
k=1
D1 +
[(K) ( - -f)
1 VB1
k=1
D2 + F1
+
(V31)* nM -1 0 121
1- vBi
D3
Z(K)(v/11 " V
1 VB1
1
Nn,
VB1
k=
B1)
8 M2
E.2. Proof of Lemma D.2
Proof. First, we compute (wi++1 - f (we). Based on the L-smoothness condition, we make the following estimate
f(wr-1) - f(wr) s ff(w)) (wr+1 - -w)) + L
2 11-1 wey 1|
Mua V Ves(we)mee L 11mm mmll?
(52)
2
Next, we construct AA which is defined as follows
TA
II 1=1
1
(1- VBn +1 a / 111
Dr
+
-1 (12 1), "
TA = 1,
where D1, A & are defined in Equation (46). Note that the Ta., here is specific Z(1) used in Lemma F.2 and Lemma E.3 with y 1- vi We can subsequently apply the results from Lemma E.2 and Lemma E.3. We multiply both sides of Equation (52) by this specific IT and, noting its monotonically decreasing property, we obtain
Lj I mm
(((44)))))))))))))))))))))) - 1*) -
- -5)
TA (if(w:)m + 2
Next, we compute
31 (Ts.t1(((we))) fr) - -Is,(f(wi) -f")).
We have
(B3)
n- nm
(Il fr) ----i - -f(,)(((u.)) f*))
d
Lj n
d
< (V3)) n Σ
II V. +
(vBB) n-
11 o mel?
2
1=1
1=1
1=1
Lemma
3(1 - -1)
Σ
M I.
8
km
tm1
49

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
D1
n
+
+1
Σ
II
(VB)) - ))
1 -
VBI
D2+ + Fi
Lif
+
+
31) R 11 mel??
VBi(L
VBD
2
D3
1
+
Ia, V B1) 31)a-a A
Voi. +
Nu.t
VB1
1- V
t=1
+ Σ
(V3B)
3 M
(53)
k=
We then observe that the left side of the above inequality can be rewritten as
(31)* (ff -f)) - (f(wa() - f³))
(1) )n 'II ([
- 1*) - Σ (Tar()) -8)
1=1
"
Σ
31 (n+1)
(+ MA f() Σ
31 (I, - f*)
++1
= (v B1) (IA - f*)
Σ (v 31 n "I, - ff)
1=1
(( - 1*)
n+1
a
(VB) (1 (1t)) (T - 88)
Σ
3
'I (f(w)) 8r)
Pa+s
F%
Substituting the above transformation back to Equation (53), we obtain
Fx++ + (11 D1
Fxt1
+1
Σ
T. ( (v31) 31 (f,(( (fa -1))
11 VBi
1=1
3(1
- B1)
$ ((B)) - (²)
nu 7 BV
8
+ D2 + F1
Isp)
+
B1
Mn, o m
(Bi(1 vB1)
2
1=1
D3 n
1 n
+
II A-
V +
Nn,
1 V
1
B1)
Σ M
1=1
1=1
Observe that
D1 +1
F² +
(VA
- -}*
V1 3
1=1
Biy n- (1+
(1-V
Di
Σ
+1) Aphe) (s,(s(wr) 5*)
VBi
50

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
n
(VB1) "Is - Fn.
We get
Fxt1 - Fn
$ ((1)))(((w)) 3(1 (1)
d n
Tu ..lll,.( (VV (V:](w:))
8
i=1
+ *
D2 D2+ + Pi
41
a
VBi(1 +(Vi(11 - vB1)
Σ
BBB " "Iyo, omil?
D3
1
+ 1 VBi
II 81
F +
Nu,t
1 /B
(VB1)*
B M k,1
Next, we take the expectation on both sides of the above inequality and note that E[N,,s] = E[M, = 0. We then obtain
E[Futt] - Fm)
3(1 -11
$ (Fw)) -f)
B1 n-t
E [e
Mls.
D2 + Fj
Tif
+
+
B1
E [1,,, o m
VBi(1 vB1)
2
t=1
D3
3 E
+0+0.
31
Summing both sides of the above inequality over the index n from to T, we obtain
F E(Fi)
3(1
31)
T
([ww))-p)
n
1 VBI
8
n=1
T
D2 + Fi
L1
+
+
V B1 Ir
E
[llme mm
(1 VB1)
n=1
D3
Σ (BB)) 3 E A
VB
Lemma C.1 5
(f(wi) - - 3(1 31)
T
Vo.-1,llla Ill (Vi((wn))
V31
8
n=1
D2 + F.
L
T E [llee, o m,,l 12 + vu(1
D3
+
VB
(v
2
vBT)²
To maintain consistency with the notation in the subsequent proofs, replace the index with in the summation ΣT- on the right side of the above inequality as follows.
E| E|Fr+1l= - -E(F
Lemma C.I
3(1 - 31)
d E [T (V.f(..))
1 v ([(w))-f'
8
tm im
51

---

A Comprchensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
1 D
Lg 2
D3
E [l,e mz [2]
(54)
V (1-(1-)))
Voll
vB1)²
Using Lemma E.I, transform the third term the right side
side of the above inequality follows
T E [1lv. o me < (1 - B1)
T
T
Ello gell
Lemma C.I.
S
Σ
E 1l o gxll".
A=
Substituting this back into Equation (54) and rearranging the terms, we obtain the following two inequalities.
1
D3
E (f
f- < [FFi
(f(w))
fr) + V0(1 v
5
D2 Fi
Lf
T
+
Σ
E No. g
(55)
- vBi VBi(11 Bii
and
8
Mr 1. .TA,, (V $
[E
(S(w)) - -
3(1 -11
3(1
31)
VB,
D3
+
8
D2 + Fi
+
L1
Σ
T
E
11 o gell?
(56)
Vo(1 2B
(1 vB1)3(1 - -B))
(BB(1 vB1
2
1=1
Next, we proceed to estimate
T
E A.
We have
T
E [I Ar. (./
1=1
s=1
Sench-- incquality
E
A2 (..
E m-
d
T
No Ta. (V.((())
mm?
Cauchy-Schwad Schwarz inequality
E [a
Cauchyy- Cauchy-Schwarz Schwart inequality
E M I1 [s,((:(())))
Σ
E [T A 11mmlmm11 11
V0
Lemma B.1
VI
3
M (T,
8 E 1199
Ve
T
0
Σ
T.. g. 112]
+ O(I)
In the final step (a), we first apply Property to bound E . [[ for all / < T, by ([ - f*)] for 1 T.
Then, using Equation (55), we further bound EI f*] as [Ir, |l o 9 Finally, we apply Equation (56) to the previous summation. This completes the proof.
52


Reviews:
[{"review_id": "eKA2LqOsME", "reviewer": "Reviewer_JhWZ", "summary": "In the past several years, many efforts have been made to understand the convergence of Adam-like algorithms under different noise assumptions. This paper is a novel paper among these works and is based on an even weaker version of the noise condition called the ABC condition. Under the ABC assumption, the authors provide a non-asymptotic rate of $O(\\log T/\\sqrt{T})$ for sample complexity, independent from the smoothing factor $\\mu$. Additionally, they demonstrate an asymptotic convergence and of the gradient norm to zero in both the sense of almost sure and expectation. These results match the best rates so far with a weaker condition and advance the theoretical understanding of adaptive methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer JhWZ,\n\nThank you for your thoughtful and constructive feedback on our paper. We greatly appreciate the time and effort you’ve put into reviewing our work. We carefully considered your comments, and we would like to address the main concern regarding the differences between our approach and the paper by Hong and Lin (2024), as well as clarify the analytical techniques and assumptions used in our paper.\n\nIn the paper by Hong and Lin (2024), the authors introduce an affine noise variance assumption that differs from the traditional second-moment-based affine noise variance assumption:\n$$\n\\mathbb{E}[\\\\|g_t-\\nabla f(w_t)\\\\|^{2}] |F_{t-1}] \\leq B\\\\|\\nabla f(w_{t})\\\\|^{2} + C.\n$$\n\nInstead, they strengthen the concentration property of the random variables by assuming the following (their Assumption A.3) :\n\n$$\n\\mathbb{E}\\left[\\exp\\left\\\\{\\frac{\\\\|g_{t}-\\nabla f(w_{t})\\\\|^{2}}{B\\\\|\\nabla f(w_{t})\\\\|^{2+\\epsilon}+C}\\right\\\\}|F_{t-1}\\right] \\leq e.\n$$\n\nTheir proof is heavily dependent on this condition, making their approach inapplicable for analyzing the traditional second-moment-based affine variance noise conditions. For a detailed explanation, please refer to their open-access paper: [Hong and Lin, 2024](https://openreview.net/pdf?id=x7usmidzxj).\n\nHong and Lin's proof relies extensively on Lemma B.6, which is proven using concentration inequalities (shown in their Appendix D.2). Under the Exponential-tailed Affine Variance Noise Condition, these inequalities yield an $O(\\ln T)$ order factor for the sample complexity term $\\mathcal{M}_T$. However, when considering traditional affine variance noise conditions based solely on second-order moment assumptions, only an $O(\\text{poly}(T))$ factor can be derived for $\\mathcal{M}_T$, which may not yield the desired results.\n\nOur paper employs the ABC inequality, which is even weaker than traditional affine variance noise conditions. This necessitates fundamentally different analytical methods, particularly based on discrete Martingale analysis, distinguishing our approach from that of Hong and Lin (2024).\n\nThank you again for your time and thoughtful evaluation of our work. If you have any further questions, please don't hesitate to discuss them with us.\n\nSincerely,\n\nAuthors of Paper 1314", "claims_and_evidence": "Not applicable.", "methods_and_evaluation_criteria": "Not applicable.", "theoretical_claims": "The major theoretical conclusions are reasonable, and the key steps in the proofs appear to be correct.", "experimental_designs_or_analyses": "Not applicable.", "relation_to_broader_scientific_literature": "This work is entirely theoretical and does not present any negative broader scientific or societal impacts. The relationship to closely related work is discussed in the \"weaknesses\" part below.", "essential_references_not_discussed": "The authors appropriately cite the most relevant prior work and provide a clear and detailed discussion of how their contributions relate to and advance the existing literature.", "other_strengths_and_weaknesses": "**Strength**\n\nThis paper is generally well-written and easy-to-follow. It gives a clear comparison of the assumptions with closely related work and makes it easy for the reader to understand. From a contribution perspective, compared with prior results, this paper achieves a nearly matching rate and establishes asymptotic convergence for Adam under a weaker ABC condition by leveraging advanced tools from functional analysis. This is valuable to the optimization community.\n\n\n**Weakness**\n\nHowever, the novelty of this work is somehow questionable. While the results in this paper indeed rely on a weaker assumption compared to prior work, the gap between the ABC condition and the affine variance condition or e is not substantial. As a result, the findings, though technically sound, are not entirely surprising. It would be more helpful if the authors could provide more convincing arguments showing that their technique is indeed novel from existing work, particularly [Hong and Lin, 2024]. I will change my score if they clarify how their approach is fundamentally different from existing methods.", "other_comments_or_suggestions": "Not applicable.", "questions_for_authors": "No further questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "I0EffsKZij", "reviewer": "Reviewer_XMp3", "summary": "This paper presents a unified analytical framework for understanding Adam’s convergence under weaker assumptions than those typically used. Specifically, the authors rely on standard L-smoothness and ABC inequality for stochastic gradients to show that Adam achieves non-asymptotic and asymptotic convergence.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nWe sincerely appreciate your thorough evaluation of our manuscript and your insightful feedback. Your recognition of our theoretical framework is highly encouraging.\n\n**Incorporation of Assumption Comparisons into the Main Text:**\n\nWe acknowledge your suggestion to move the discussion comparing our assumptions, particularly the ABC inequality, with previous ones from the appendix to the main body of the paper. We agree that this adjustment will enhance the clarity and accessibility of our work. In the revised manuscript, we will integrate this discussion into the main text, providing a concise comparison and highlighting the theoretical insights gained from using the ABC inequality. Additionally, we will discuss parallel results in stochastic gradient descent (SGD) analyses that employ similar assumptions to further contextualize our contributions.\n\n**Clarification on the Behavior of Adam When $\\beta_{2,t}$ Does Not Approach 1:**\n\nRegarding your concern about the definition of the hyperparameter $\\beta_{2,t}$  converging to 1, we appreciate the opportunity to clarify this point. In scenarios where $\\beta_{2,t}$ does not approach 1, Adam's convergence behavior differs. Specifically, under such conditions, Adam may only ensure that the gradient converges to a small neighborhood around zero rather than exactly to zero. To achieve convergence of the gradient to zero, it is necessary for $\\beta_{2,t}$ to approach 1. This requirement has been highlighted in previous studies, such as the work by [1] on the convergence of Adam. In our current paper, we focused on aligning Adam's convergence results with those of SGD, which led us to adopt the condition where $\\beta_{2,t}$ approaches 1. We acknowledge that this aspect was not explicitly discussed in our manuscript, and we will address this omission in future research by exploring scenarios where $\\beta_{2,t}$ does not approach 1.\n\nThank you once again for your valuable comments and suggestions. Your feedback has been instrumental in improving the clarity and depth of our work.\n\n\n[1] Zhang Y, Chen C, Shi N, et al. Adam can converge without any modification on update rules[J]. Advances in neural information processing systems, 2022, 35: 28386-28399.\n\nSincerely,\n\nAuthors of Paper 1314", "claims_and_evidence": "The main claim of this paper is the convergence of Adam with not very strong conditions. The claims are supported by rigorous math proofs.", "methods_and_evaluation_criteria": "This is a theoretical paper so is not applicable to this question.", "theoretical_claims": "I follow the proof sketch and check some proofs of main lemmas. They seemed to be correct. However, the authors discuss more about the the assumptions, especially for ABC inequality since it is not standard in the analysis. The authors can highlight how to apply this assumption in the proof and also explain briefly why we don't need previous strong assumptions. These can provide more theoretical insights.", "experimental_designs_or_analyses": "This is a theoretical paper so is not applicable to this question.", "relation_to_broader_scientific_literature": "Understanding Adam is important since it achieves great success in LLM training.", "essential_references_not_discussed": "The authors do cite key references on Adam’s analysis under different assumptions.", "other_strengths_and_weaknesses": "This is a solid theoretical paper analyzing Adam and achieves good results in both non-asymptotic and asymptotic settings. My concern is mainly on the presentation of the results and is already pointed out in previous questions. One more concern is the definition of hyperparameter $\\beta_{2,t}$ converging to 1 looks unnatural to me.", "other_comments_or_suggestions": "No other comments.", "questions_for_authors": "In my understanding, the behavior of Adam is quite different from SGD. How the author bridging the gap with SGD in there paper? Only in the part of establishing descent inequality and the final results?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DWDd0NzSnl", "reviewer": "Reviewer_nypN", "summary": "The paper studies the convergence properties of Adam under smooth nonconvex settings. The paper presents convergence results in the sense of almost sure, $L_1$ and non-asymptotic, under relaxed noise assumption, i.e. the ABC inequality. The non-asymptotic convergence result is in the order of $O(1/\\sqrt{T})$, which is generally consistent with that of SGD.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Rebuttal to Reviewer nypN**\n\nDear Reviewer nypN,\n\nThank you very much for your thoughtful feedback and constructive comments on our manuscript. We sincerely appreciate the time and effort you have put into reviewing our work. We are grateful for your insights, and we have carefully addressed each of your points below in the hope of clarifying our contributions and improving the manuscript.\n\n### 1. **Dependence on Dimensionality and $\\beta_1$ in Theorem 3.1**\n\nYou raised a question regarding the dependence on dimensionality and $\\beta_1$ in Theorem 3.1. Specifically, you asked about the formal version of the sample complexity result in the theorem.\n\n**Response:** In Theorem 3.1, the sample complexity result concerning $1-\\beta_1$ and the dimension $d$ is of the order $\\mathcal{O}\\left(\\frac{d}{(1-\\beta_1)^2}\\right)$. This result is consistent with previous works on the convergence of Adam, such as [1]. We would like to emphasize that while it is possible to remove the dependence on the dimension $d$, we cannot avoid reintroducing the dependence on the inverse of the smoothing factor, which is $\\mathcal{O}(\\text{poly}(1/\\mu))$. This is a well-known consensus in previous studies [2]. We hope this clarification addresses your concern.\n\n### 2. **Extension of Results to Other Smoothness Settings**\n\nYou asked whether our results could be extended to other smoothness settings, as in [3, 4, 5], and whether this could potentially remove the additional dependence on dimensionality, helping to bridge the gap between SGD and Adam.\n\n**Response:** We believe that it is highly probable to extend our results to other smoothness settings, and we are excited about exploring this in future work. However, we must admit that this area was not covered in our previous research, and therefore, we cannot provide a definitive answer at this moment. Nonetheless, we plan to address this issue in our future research, where we will explore the possibility of extending our results to more general smoothness assumptions and examine whether the additional dependence on dimensionality can be removed.\n\n### 3. **General Smoothness Cases (e.g., $L_0-L_1$ Smoothness)**\n\nYou inquired whether our proof can extend to more general smoothness cases, such as $L_0-L_1$ smoothness.\n\n**Response:** We are currently investigating this direction and have made some progress. Specifically, we have made the following two extensions so far:\n\n1. **For $(L_0-L_0.5)$ smooth functions:** We can derive convergence results for Adam under the traditional second-moment-based ABC inequality. However, the sample complexity still shows dependence on the inverse of the smoothing factor $1/\\mu$, though we can eliminate the dependence on the dimension $d$.\n\n2. **For $(L_0-L_1)$ smooth functions:** At this stage, our methods are unable to extend the convergence results under the traditional second-moment-based ABC inequality. However, we can obtain convergence results under the traditional second-moment Bounded Variance condition. It is worth noting that, as of now, there are no known results for Adam’s convergence under $(L_0-L_1)$ smoothness with the traditional second-moment Bounded Variance condition.\n\nWe are continuing to investigate these extensions and will include them in future work. We greatly appreciate your interest in this aspect and will strive to address it in subsequent studies.\n\n### 4. **Additional Comments and Acknowledgements**\n\nWe sincerely appreciate your review, which has helped us identify areas for clarification and potential improvement. We value your suggestions and will ensure that these aspects are thoroughly explored in our future research. Your feedback has significantly contributed to the refinement of our manuscript, and we hope that the revisions we have made have addressed your concerns effectively.\n\nIf you have any further questions or suggestions, please do not hesitate to reach out. We are more than happy to discuss any aspects of our work in greater detail. Once again, thank you for your careful review and constructive feedback.\n\nWe look forward to your final assessment.\n\n[1] Bohan Wang, Jingwen Fu, Huishuai Zhang, Nanning Zheng, and Wei Chen. Closing the gap be-\ntween the upper bound and lower bound of Adam’s iteration complexity. Advances in Neural\nInformation Processing Systems, 36, 2024a.\n\n[2] Haochuan Li, Alexander Rakhlin, and Ali Jadbabaie. Convergence of Adam under relaxed assump-\ntions. Advances in Neural Information Processing Systems, 36, 2024.\n\n[3] Bernstein J, Wang Y X, Azizzadenesheli K, et al. signSGD: Compressed optimisation for non-convex problems. International Conference on Machine Learning. PMLR, 2018: 560-569.\n\n[4] Liu Y, Pan R, Zhang T. AdaGrad under Anisotropic Smoothness. arXiv preprint arXiv:2406.15244, 2024.\n\n[5] Xie S, Mohamadi M A, Li Z. Adam Exploits \n$\\mathcal{l}_\\infty$-geometry of Loss Landscape via Coordinate-wise Adaptivity. arXiv preprint arXiv:2410.08198, 2024.\n\nSincerely,  \n\nAuthors of Paper 1314", "claims_and_evidence": "Most of the claims are generally clear. \n1. I do have a question for Theorem 3.1. According to Theorem 3.1, the notation $O()$ doesn't omit the dpendence on dimensionality $d$. I am wondering if this is possible with your assumptions? Or you just simply miss this?\n2. Also regarding $O()$ in Theorem 3.1, could you please also specify the dependence on $1-\\beta_1$?", "methods_and_evaluation_criteria": "No experiments in the paper.", "theoretical_claims": "I didn't check the whole proof for the theoretical claims due to its complexity. Basically the results are reasonable.", "experimental_designs_or_analyses": "No experiments in the paper.", "relation_to_broader_scientific_literature": "This paper moves the convergence results for Adam, which is popular in the literature, a step forward.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n1. The paper is technically solid, making a progress in obtaining better convergence results for Adam under more relaxed settings.\n\nWeakness:\n1. I don't think hiding so much details of the convergence result is appropriate. As I mentioned in Claims and Evidence part, I think it's quite likely that the authors hide the dependence on dimensionality (which can be very large in practice). Also, the dependence on $\\beta_1$ and $\\beta_2$ and others are also important, as this can imply the role of momentum for Adam as well as some possible suggestions for the parameter choices. Thus I think the authors should definitely give a formal statement of Theorem 3.1 at least in the appendix.\n2. The choice for $\\beta_2$ seem to be kind of restricted.", "other_comments_or_suggestions": "1. For Theorem 3.1, it seems kind of weird to state the convergence result in high-probability form, since it has a dependence on the probability as $O(1/s^2)$, while standard high-probability convergence results are usually in the order of $O(log(1/s))$. I think just equation (42) is good enough for the statement.\n\n2. I suggest the authors to distribute some space at least in the appendix to aggregate the definitions for the values. It's really hard to follow the proof or even find out the detailed results of the theorems with a lot of defined values like $C,C_1,...$ with very seperate definitions.\n\n3. Why you are not using the form with numbers noting the lines?", "questions_for_authors": "1. What is the dependence on dimensionality and $\\beta_1$ in Theorem 3.1? Could you provide a formal version?\n\n2. If you do have additional dimensionality dependence, is it possible to extend your results to some other smoothness settings as in [1,2,3], which can potentially remove the additional dependence and fill this gap between SGD and Adam?\n\n3. Can your proof also extend to a more general smoothness case, e.g. $(L_0,L_1)$-smoothness? \n\n[1] Bernstein J, Wang Y X, Azizzadenesheli K, et al. signSGD: Compressed optimisation for non-convex problems. International Conference on Machine Learning. PMLR, 2018: 560-569.\n\n[2] Liu Y, Pan R, Zhang T. AdaGrad under Anisotropic Smoothness. arXiv preprint arXiv:2406.15244, 2024.\n\n[3] Xie S, Mohamadi M A, Li Z. Adam Exploits $\\ell_\\infty $-geometry of Loss Landscape via Coordinate-wise Adaptivity. arXiv preprint arXiv:2410.08198, 2024.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aH9yaRWYlV", "reviewer": "Reviewer_LTUb", "summary": "The authors propose a new theoretical framework with fairly weak assumptions, within which they are able to establish convergence rates for Adam.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer LTUb,\n\nWe sincerely appreciate your thorough evaluation of our manuscript and your positive feedback. Your recognition of our theoretical framework and the establishment of convergence rates for Adam under weak assumptions is highly encouraging.\n\nWe acknowledge your suggestion to include an application example demonstrating the practical implications of our theoretical findings. While our primary focus has been on the theoretical aspects, we understand the value of illustrating how our results can address scenarios previously unmanageable by earlier works. In response, we plan to incorporate a relevant application example in our revised manuscript to highlight the practical applicability of our theoretical contributions.\n\nThank you once again for your insightful comments and for your recommendation to accept our work. Your feedback has been instrumental in enhancing the quality and impact of our manuscript.\n\nSincerely,\n\nAuthors of Paper 1314", "claims_and_evidence": "N/A", "methods_and_evaluation_criteria": "No simulation sutdy nor application on real datasets.", "theoretical_claims": "Given the short time available, it was not possible to fully and rigorously review all the proofs. However, based on what I was able to check, the proofs appear to be correct.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The main contribution rely on a new set of  weak assumptions to obtain theoretical results for ADAM algorithm. More precisely, they obtain analogous rate of convergence as in the literature, but with weaker conditions.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\nThe authors successfully obtain results for Adam under remarkably weak assumptions (smoothness and ABC inequality).\nGiven the short time available, it was not possible to fully and rigorously review all the proofs. However, based on what I was able to check, the proofs appear to be correct and well-detailed.\nI also appreciate the effort made to enhance the readability of the proofs, particularly through the use of the dependency graph.\n\nWeaknesses:\nWhile it is now widely accepted that simulations are not strictly necessary to demonstrate that Adam works, it would have been valuable to present an application example that could not have been theoretically addressed by previous works but can now be handled before moving on to simulations.", "other_comments_or_suggestions": "No comments or suggestions.", "questions_for_authors": "No question.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper provides a comprehensive framework for analyzing the convergence of Adam. The reviewers are generally positive about the paper after the rebuttal. Therefore, I recommend acceptance. The authors are required to incorporate the following points raised by reviewers in the final version of the paper: (i) explicitly mention the dependency on dimension in the theorem statement and the paper; (ii) explain the ABC inequality and compare with other assumptions in the literature; (iii) explicitly acknowledge that the paper does not show a separation between Adam and SGD.
Decision: Accept (poster)