{'fraction_non_alphanumeric': 0.044157850944966125, 'fraction_numerical': 0.01295613930821348, 'mean_word_length': 4.379475703324808, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Novel Convergence Analysis for Algorithms of the Adam Family

Since its invention in 2014, the Adam optimizer has received tremendous attention. On one hand, it has been widely used in deep learning and many variants have been proposed, while on the other hand their theoretical convergence property remains to be a mystery. It is far from satisfactory in the sense that some studies require strong assumptions about the updates, which are not necessarily applicable in practice, while other studies still follow the original problematic convergence analysis of Adam, which was shown to be not sufficient to ensure convergence. Although rigorous convergence analysis exists for Adam, they impose specific requirements on the update of the adaptive step size, which are not generic enough to cover many other variants of Adam. To address theses issues, in this extended abstract, we present a simple and generic proof of convergence for a family of Adam-style methods (including Adam, AMSGrad, Adabound, etc.). Our analysis only requires an increasing or large"momentum"parameter for the first-order moment, which is indeed the case used in practice, and a boundness condition on the adaptive factor of the step size, which applies to all variants of Adam under mild conditions of stochastic gradients. We also establish a variance diminishing result for the used stochastic gradient estimators. Indeed, our analysis of Adam is so simple and generic that it can be leveraged to establish the convergence for solving a broader family of non-convex optimization problems, including min-max, compositional, and bilevel optimization problems. For the full (earlier) version of this extended abstract, please refer to arXiv:2104.14840.


Introduction
Stochastic adaptive methods originating from AdaGrad for convex minimization [7,18] have attracted tremendous attention for stochastic non-convex optimization [2,13,17,23,28,32,34]. Adam [12] is an important variant of AdaGrad, which is widely used in practice for training deep neural networks, and many variants of Adam were proposed for improving its performance, e.g. [14,17,31]. Its analysis for non-convex optimization has also received a lot of attention [3]. For more generality, we consider a family of Adam-style algorithms. The update is given by Adam-style: where h t denotes an appropriate mapping function whose specific choices are given later. One criticism of Adam is that it might not converge for some problems with inappropriate momentum parameters. In particular, the authors of AMSGrad [21] show that Adam with small momentum parameters can diverge for some problems. However, we notice that the failure of Adam shown in AMSGrad [21] and the practical success of Adam come from an inconsistent setting of the momentum parameter for the first-order moment. In practice, this momentum parameter (corresponding to 1 − β t in (1)) is usually set to a large value (e.g., 0.9). However, in the failure case analysis of Adam [21] and many existing analysis of Adam and their variants [3,14,17,22,31], such momentum parameter is set as a small value or a decreasing sequence. We provide the first analysis of Adam and other variants with a more natural increasing or large momentum parameter for the first-order moment.
Several recent works have tried to prove the (non)-convergence of Adam. In particular, Zou et al. [35] establish some sufficient condition for ensuring Adam to converge. In particular, they choose to increase the momentum parameter for the second-order moment and establish a convergence rate in the order of log(T )/ √ T , which was similarly established in [6] with some improvement on the constant factor. Zaheer et al. [31] show that Adam with a sufficiently large mini-batch size can converge to an accuracy level proportional to the inverse of the mini-batch size. Chen et al. [3] analyze the convergence properties for a family of Adam-style algorithms. However, their analysis requires a strong assumption of the updates to ensure the convergence, which does not necessarily hold as the authors give non-convergence examples. Different from these works, we give an alternative way to ensure Adam converge by using an increasing or large momentum parameter for the first-order moment without any restrictions on the momentum parameter for the second-order moment and without requiring a large mini-batch size. This seems more natural and consistent with the practice. Indeed, our analysis is applicable to a family of Adam-style algorithms, and is agnostic to the method for updating the normalization factor in the adaptive step size as long as it can be upper bounded. The large momentum parameter for the first-order moment is also the key part that differentiates our convergence analysis with existing non-convergence analysis of Adam [3,12,21], which require the momentum parameter for the first-order moment to be decreasing to zero or sufficiently small.
A key in the analysis is to carefully utilize the design of the stochastic estimator of the gradient. Traditional methods that simply use an unbiased gradient estimator of the objective function are not applicable to many problems and also suffer slow convergence due to large variance of the unbiased stochastic gradients. Recent studies in stochastic non-convex optimization have proposed better stochastic estimators of the gradient based on variance reduction technique (e.g., SPIDER, SARAH, STORM) [5,9,20,26]. However, these estimators sacrifice generality as they require that the unbiased stochastic oracle is Lipschitz continuous with respect to the input, which prohibits many useful tricks in machine learning for improving generalization and efficiency (e.g., adding random noise to the stochastic gradient [19], gradient compression [1,27,33]). In addition, they also require computing stochastic gradients at two points per-iteration, making them further restrictive.
In Adam-style methods, the stochastic estimators are based on the moving average. In order to generate a sequence of iterates {x 0 , x 1 , . . . , x T }, we usually need to track another sequence of {g(x 0 ), g(x 1 ), . . . , g(x T )}, where g is a Lipschitz continuous mapping that is useful for constructing the gradient of the objective function. However, g(x t ) can be only accessed through an unbiased stochastic oracle denoted by O g such that for any input x, it returns a random variable . For more generality, we do not assume that O g is Lipschitz continuous with respect to the input even g is Lipschitz continuous. One example of such stochastic oracle is O g (x) = g(x; ζ) + ξ, where E ζ [g(x; ζ)] = g(x) and ξ is a zero-mean random noise (e.g., zero-mean Gaussian noise). Therefore, the variance-reduced stochastic estimators based on SPI-DER, SARAH or STORM are not applicable. Instead, we will consider another stochastic estimator based on moving average, i.e., we maintain and update a sequence of {z 1 , . . . , z T } by We refer to this estimator sequence for tracking {g(x 1 ), . . . , g(x T )} as stochastic moving average estimator (SEMA) in contrast to SPIDER/SARAH/STORM. It the literature, stochastic methods that employ the above estimator are usually referred to as momentum methods [3,4,16], with 1 − β t called the "momentum" parameter. Besides in Adam-style methods, SEMA has been widely used in other stochastic non-convex optimization methods such as in stochastic compositional minimization [8,10,24,25]. Although the SEMA has been widely used in practice, its power for solving a broad range of stochastic optimization problems has not been fully discovered. We present a simple and intuitive proof of convergence of a family of Adam-style algorithms with an increasing or large momentum parameter for the first-order moment, which include many variants such as Adam, AMSGrad, Adabound, AdaFom, etc. A surprising result is that Adam with an increasing or large momentum parameter for the first-order moment indeed converges at the same rate as SGD without any modifications on the update or restrictions on the "momentum" parameter for the second-order moment. In our analysis, β t is decreasing in the same order of step size, which yields an increasing "momentum" parameter 1 − β t . This increasing momentum parameter is more natural than the decreasing (or small) momentum parameter, which is indeed the reason that makes Adam diverge on some examples [21]. Our increasing/large "momentum" parameter 1 − β t is also consistent with that the large value close to 1 used in practice [12]. To the best of our knowledge, this is the first time that Adam was shown to converge for non-convex optimization with a more natural large "momentum" parameter for the first-order moment. We also prove that averaged variance of the stochastic estimator of the gradient decreases over time. A comparison of the results in this paper with existing results is summarized in Table 1. Moreover, our analysis can be extended to analyze the convergence of Adam-style algorithms for a broader family of non-convex optimization problems, including compositional optimization, min-max optimization and bilevel optimization problems [11].

Notations and Preliminaries
Notations and Definitions. Let · denote the Euclidean norm of a vector or the spectral norm of a matrix. Let · F denote the Frobenius norm of a matrix. A mapping h is L-Lipschitz and ∇ y f (x, y) denote the partial gradients with respect to x and y, respectively. Denote x an element-wise square and element-wise square-root, respectively. Table 1: Comparison with previous results. "mom. para." is short for momentum parameter. 1st and 2nd are short for first order and second order, respectively. "-" denotes no strict requirements and applicable to a range of updates. ↑ represents increasing as iterations and ↓ represents decreasing as iterations. ǫ denotes the target accuracy level for the objective gradient norm, i.e., E[ ∇F (x) ] ≤ ǫ.
Problem Method batch size ↑ or ↓ 1st mom. para.
We will consider non-convex minimization (4), which has broad applications in machine learning. This paper focuses on theoretical analysis and our goal for these problems is to find an ǫstationary solution of the primal objective function F (x) by using stochastic oracles.

Definition 1 Consider a differentiable function F (x), a randomized solution x is called an
Before ending this section, we present the widely used stochastic momentum method for solving non-convex minimization problem min x∈R d F (x) through an unbiased stochastic oracle that returns a random variable O F (x) for any x such that E[O F (x)] = ∇F (x). For solving this problem, the stochastic momentum method (in particular stochastic heavy-ball (SHB) method) that employs the SEMA update is given by where v 0 = O F (x 0 ). In the literature, 1 − β is known as the momentum parameter and η is known as the step size or learning rate. It is notable that the stochastic momentum method can be also written as z t+1 = βz t − ηO F (x t ), and x t+1 = x t + z t [29], which is equivalent to the above update with some parameter change shown in Appendix A. The above method has been analyzed in various studies [10,16,29,30]. Nevertheless, we will give a unified analysis for the Adam-family methods with a much more concise proof, which covers SHB as a special case. A core to the analysis is the use of a known variance recursion property of the SEMA estimator stated below.

Lemma 2 (Variance Recursion of SEMA)[Lemma 2, [24]] Consider a moving average sequence
where E t denotes the expectation conditioned on all randomness before O h (x t ).
We refer to the above property as variance recursion (VR) of the SEMA.

A Novel Analysis of Adam with a Large Momentum Parameter
In this section, we consider the standard stochastic non-convex minimization, i.e., where F is smooth and is accessible only through an unbiased stochastic oracle. These conditions are summarized below for our presentation.

Assumption 1 Regarding problem (4), the following conditions hold:
• ∇F is L F Lipschitz continuous; • F is accessible only through an unbiased stochastic oracle that returns a random variable Remark: Note that the variance bounded condition is slightly weaker than the standard condition An example of a random oracle that satisfies our condition but not the standard condition is . . , d} is randomly sampled and e i denotes the i-th canonical vector with only i-th element equal to one and others zero. For this oracle, we can show that In the following we present a novel analysis of Adam-style methods based on VR of SEMA. The update rule of Adam-style rules has been given in (1). A key to our convergence analysis of Adam-style algorithms is the boundness of the step size scaling factor s t = 1/( √ u t+1 + G 0 ), which is presented as an assumption below for more generality. We denote byη t = η t s t . (1), we assume that s t = 1/( √ u t+1 + G 0 ) is upper bounded and lower bounded, i.e., there exists 0 < c l < c u such that c l ≤ s t ∞ ≤ c u .

Assumption 2 For the Adam-style algorithms in
Remark: Under the standard assumption O F (x) ∞ ≤ G [12,21], we can see many variants of Adam will satisfy the above condition. Examples include Adam [12], AMSGrad [21], AdaFom [3], Adam + [15], whose u t shown in Table 2 all satisfy the above condition under the bounded stochastic oracle assumption. Even if the condition O F (x) ∞ ≤ G is not satisfied, we can also use the clipping idea to make u t bounded. This is used in Adabound [17], whose u t is given by where c l ≤ c u and Π [a,b] is a projection operator that projects the input into the range [a, b]. We summarize these updates and their satisfactions of Assumption 2 in Table 2. Note that SHB also satisfies Assumption 2 automatically. To prove the convergence of the update (1). We first present a key lemma.
With the above lemmas, we can establish the following convergence of Adam-style algorithms.
Remark: We can see that the Adam-style algorithms enjoy an oracle complexity of O(1/ǫ 4 ) for finding an ǫ-stationary solution. To the best of our knowledge, this is the first time that the Adam with a large momentum parameter 1 − β was proven to converge. One can also use a decreasing step size η t ∝ 1/ √ t and decreasing β t = 1/ √ t (i.e, increasing momentum parameter) and establish a rate of O(1/ √ T ) as stated below.

Conclusion & Discussion
In this paper, we have provided a simple and generic convergence analysis for a family of Adamstyle methods for solving non-convex minimization problems. We leveraged the variance recursion of the stochastic moving average estimator and established the convergence of practically used Adam and its variants. Our results bring some new insights to make the Adam method converge or convergence better. Indeed, the Lemma 3 paves the way for the convergence analysis of many Adam-style algorithms for solving a broader family of problems, including non-convex strongly concave minmax optimization problems, non-convex stochastic compositional optimization problems, and nonconvex bilevel optimization problems. It is also worth mentioning that we can also prove a faster convergence of the Adam-style algorithms under a strong Polyak-Łojasiewicz condition. We will explore this direction and examine how it will affect the convergence rate in the future work.
Finally, it is worth mentioning that the oracle complexities established in this paper are optimal under a general stochastic unbiased oracle model. In addition, one can also replace the variance recursion of the stochastic moving average estimator by that of other stochastic estimators (e.g. STORM) to prove an optimal convergence under Lipchitz continuous oracle model.

Appendix A. Stochastic Momentum Method
In the literature [29], the stochastic heavy-ball method is written as: To show the resemblance between the above update and the one in (3), we can transform them into one sequence update: We can see that SHB is equivalent to (3) with η ′ = ηβ and β ′ = (1 − β).

Appendix B. Proof of Lemma 3
Proof Due to the smoothness of F , we can prove that under η t L F ≤ c l /(2c 2 u ) Appendix C. Proof of Theorem 1 Proof By applying Lemma 2 to v t+1 , we have Hence we have, Adding the above inequality with Lemma 3, we have ) and 2βσ 2 c ≤ c l /(4c u ), 2βσ 2 cL 2 F η 2 c 3 u ≤ c l /8 (i.e, ηL F ≤ 1 √ 2cu ), we have As a result, ∇F (x t ) 2 ≤ 2∆ 0 c u βT c l + 4(F (x 0 ) − F * ) ηc l T + 4βσ 2 c u c l .
With β ≤ ǫ 2 c l 12σ 2 cu , T ≥ max{ 6∆ 0 cu βǫ 2 c l , 12∆ F ηǫ 2 c l }, we conclude the proof for the first part. For the second part, we have As a result, Thus, 16η T σ 2 L F c 2 c l c 5 u (T + 1) ln(T + 2).
Setting T ≥ O( ), we conclude the proof for the first part. For the second part, we have Then, which concludes the proof of the second part.