SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients
Year: 2022

Abstract:
Adaptive gradient methods have shown excellent performances for solving many machine learning problems. Although multiple adaptive gradient methods were recently studied, they mainly focus on either empirical or theoretical aspects and also only work for specific problems by using some specific adaptive learning rates. Thus, it is desired to design a universal framework for practical algorithms of adaptive gradients with theoretical guarantee to solve general problems. To fill this gap, we propose a faster and universal framework of adaptive gradients (i.e., SUPER-ADAM) by introducing a universal adaptive matrix that includes most existing adaptive gradient forms. Moreover, our framework can flexibly integrate the momentum and variance reduced techniques. In particular, our novel framework provides the convergence analysis support for adaptive gradient methods under the nonconvex setting. In theoretical analysis, we prove that our SUPER-ADAM algorithm can achieve the best known gradient (i.e., stochastic first-order oracle (SFO)) complexity of Õ( −3) for finding an -stationary point of nonconvex optimization, which matches the lower bound for stochastic smooth nonconvex optimization. In numerical experiments, we employ various deep learning tasks to validate that our algorithm consistently outperforms the existing adaptive algorithms. Code is available at https://github.com/LIJUNYI95/SuperAdam

heading: 1 Introduction
text: In the paper, we consider solving the following stochastic optimization problem:
min x∈X
f(x) := Eξ∼D[f(x; ξ)], (1)
where f(x) denotes a smooth and possibly nonconvex loss function, and ξ is a random example variable following an unknown data distribution D. Here X = Rd or X ⊂ Rd is a compact and convex set. The problem (1) frequently appears in many machine learning applications such as the expectation loss minimization. Recently, Stochastic Gradient Descent (SGD) [14] is commonly used to solve the problem (1) such as Deep Neural Networks (DNNs) training [18, 20], due to only requiring a mini-batch samples or even one sample at each iteration. Adaptive gradient methods are one of the most important variants of SGD, which use adaptive learning rates and possibly incorporate momentum techniques, so they generally require less parameter tuning and enjoy faster convergence rate than SGD. Meanwhile, compared to SGD, adaptive gradient methods escape saddle points faster [31]. Thus, recently adaptive gradient methods have been widely developed and studied. For example, the first adaptive gradient method i.e., Adagrad has been proposed in [12], which significantly outperforms the vanilla SGD under the sparse gradient setting. Subsequently, some variants of Adagrad e.g., SC-Adagra [28] and SAdagrad [9] have been proposed for (strongly) convex optimization. Unfortunately, Adagrad has been found that it does not be well competent to the dense gradient setting and the nonconvex setting. To address this drawback, some other efficient variants of
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Adagrad, e.g., Adadelta [37], Adam [22], have been presented by using exponential moving average instead of the arithmetic average.
Adam [22] recently has been shown great successes in current machine learning problems, e.g., it is a default method of choice for training DNNs [17] and contrastive learning [7]. Unfortunately, Reddi et al. [29] still showed that Adam is frequently divergent in some settings where the gradient information quickly disappear. To deal with this issue, some variants of Adam algorithm, e.g., AMSGrad [29], YOGI [36] and generalized Adam [8] have been proposed. Specifically, AMSGrad [29] applies an extra ‘long term memory’ variable to preserve the past gradient information in order to handle the convergence issue of Adam. YOGI [36] introduces an adaptive denominator constant, and studies effect of the mini-batch size in its convergence. Subsequently, Chen et al. [8] studied the convergence of a class of Adam-type algorithms for nonconvex optimization. Zhou et al. [39] analyzed the convergence of a class of adaptive gradient algorithms for nonconvex optimization, and the result shows the advantage of adaptive gradient methods over SGD in sparse stochastic gradient setting. Meanwhile, Liu et al. [24] studied the variances of these adaptive algorithms. More recently, Guo et al. [19] presented a novel convergence analysis for a family of Adam-style methods (including Adam, AMSGrad, Adabound, etc.) with an increasing or large momentum parameter for the first-order moment.
Although the above these adaptive gradient methods show some good empirical performances, their generalization performance is worse than SGD (with momentum) on many deep learning tasks due to using the coordinate-wise learning rates [35]. Thus, recently some adaptive gradient methods have been proposed to improve the generalization performance of Adam. For example, AdamW [26] and Padam [6] improve the generalization performance of Adam by decoupling weight decay regularization and introducing a partial adaptive parameter, respectively. Luo et al. [27] proposed a new variant of Adam (i.e., Adabound) by employing dynamic bounds on learning rates to improve the generalization performance. Subsequently, AdaBelief [40] has been presented to obtain a good generalization by adopting the stepsize according to the ‘belief’ in the current gradient direction. In addition, the norm version of AdaGrad (i.e., AdaGrad-Norm) [34] has been proposed to obtain a good generalization performance.
So far, the above adaptive gradient methods still suffer from a high gradient complexity of O( −4) for finding -stationary point in the worst case without considering sparsity of gradient. More recently, some faster variance-reduced adaptive gradient methods such as STORM [11], Adaptive Normalized
SGD [10], Adam+ [25] have been proposed. For example, STORM applies the momentum-based variance reduced technique to obtain a lower gradient complexity of Õ( −3). To the best of our knowledge, all these existing adaptive gradient methods only use some specific adaptive learning rates with focusing on either pure theoretical or empirical aspects. Thus, it is desired to design a universal framework for the adaptive gradient methods on both theoretical analysis and practical algorithms to solve the generic problems.
To fill this gap, in the paper, we propose a faster and universal framework of adaptive gradients, i.e., SUPER-ADAM algorithm, by introducing a universal adaptive matrix. Moreover, we provide a novel convergence analysis framework for the adaptive gradient methods under the nonconvex setting based on the mirror descent algorithm [5, 15]. In summary, our main contributions are threefold:
1) We propose a faster and universal framework of adaptive gradients (i.e., SUPER-ADAM) by introducing a universal adaptive matrix that includes most existing adaptive gradients. Moreover, our framework can flexibly integrate the momentum and variance-reduced techniques.
2) We provide a novel convergence analysis framework for the adaptive gradient methods in the nonconvex setting under the milder conditions (Please see Table 1).
3) We apply a momentum-based variance reduced gradient estimator [11, 32] to our algorithm (SUPER-ADAM (τ = 1)), which makes our algorithm reach a faster convergence rate than the classic adaptive methods. Specifically, under smoothness of each component function f(x; ξ), we prove that the SUPER-ADAM (τ = 1) achieves the best known gradient complexity of Õ( −3) for finding an -stationary point of the problem (1), which matches the lower bound for stochastic smooth nonconvex optimization [1]. Under smoothness of the function f(x), we prove that the SUPER-ADAM (τ = 0) achieves a gradient complexity of Õ( −4).

heading: 2 Preliminaries

heading: 2.1 Notations
text: ‖ · ‖ denotes the `2 norm for vectors and spectral norm for matrices, respectively. Id denotes a d-dimensional identity matrix. diag(a) ∈ Rd denotes a diagonal matrix with diagonal entries a = (a1, · · · , ad). For vectors u and v, up (p > 0) denotes element-wise power operation, u/v denotes element-wise division and max(u, v) denotes element-wise maximum. 〈u, v〉 denotes the inner product of two vectors u and v. For two sequences {an} and {bn}, we write an = O(bn) if there exists a positive constant C such that an ≤ Cbn, and Õ(·) hides logarithmic factors. A 0( 0) denotes a positive (semi)definite matrix. δmin(A) and δmax(A) denote the smallest and largest eigenvalues of the matrix A, respectively.

heading: 2.2 Adaptive Gradient Algorithms
text: In the subsection, we review some existing typical adaptive gradient methods. Recently, many adaptive algorithms have been proposed to solve the problem (1), and achieve good performances. For example, Adagrad [12] is the first adaptive gradient method with adaptive learning rate for each individual dimension, which adopts the following update form:
xt+1 = xt − ηtgt/ √ vt, (2)
where gt = ∇f(xt; ξt) and vt = 1t ∑t j=1 g 2 j , and ηt = η√ t
with η > 0 is the step size. In fact, ηt only is the basic learning rate that is the same for all coordinates of variable xt, while ηt√vt,i is the effective learning rate for the i-th coordinate of xt, which changes across the coordinates.
Adam [22] is one of the most popular exponential moving average variant of Adagrad, which combines the exponential moving average technique with momentum acceleration. Its update form is:
mt = α1mt−1 + (1− α1)∇f(xt; ξt), vt = α2vt−1 + (1− α2)(∇f(xt; ξt))2 m̂t = mt/(1− αt1), v̂t = vt/(1− αt2), xt+1 = xt − ηtm̂t/( √ v̂t + ε), ∀ t ≥ 1 (3)
where α1, α2 ∈ (0, 1) and ε > 0, and ηt = η√t with η > 0. However, Reddi et al. [29] found a divergence issue of the Adam algorithm, and proposed a modified version of Adam (i.e., Amsgrad), which adopts a new step instead of the debiasing step in (3) to ensure the decay of the effective learning rate, defined as
v̂t = max(v̂t−1, vt), xt+1 = xt − ηtmt/ √ v̂t. (4)
Algorithm 1 SUPER-ADAM Algorithm 1: Input: Total iteration T , and tuning parameters {µt, αt}Tt=1, γ > 0 ; 2: Initialize: x1 ∈ X , sample one point ξ1 and compute g1 = ∇f(x1; ξ1); 3: for t = 1, 2, . . . , T do 4: Generate an adaptive matrix Ht ∈ Rd×d; // Given two examples to update Ht: 5: Case 1: given β ∈ (0, 1), λ > 0 and v0 = 0, 6: vt = βvt−1 + (1− β)∇f(xt; ξt)2, Ht = diag( √ vt + λ);
7: Case 2: given β ∈ (0, 1), λ > 0 and b0 = 0, 8: bt = βbt−1 + (1− β)‖∇f(xt; ξt)‖, Ht = ( bt + λ ) Id;
9: Update x̃t+1 = arg minx∈X { 〈gt, x〉+ 12γ (x− xt) THt(x− xt) }
; 10: Update xt+1 = (1− µt)xt + µtx̃t+1; 11: Sample one point ξt+1, and compute gt+1 = αt+1∇f(xt+1; ξt+1) + (1 − αt+1) [ gt +
τ ( ∇f(xt+1; ξt+1)−∇f(xt; ξt+1) )] , where τ ∈ {0, 1};
12: end for 13: Output: (for theoretical) xζ chosen uniformly random from {xt}Tt=1; (for practical ) xT .
Due to using the coordinate-wise learning rates, these adaptive gradient methods frequently have worse generalization performance than SGD (with momentum) [35]. To improve the generalization performance of Adam, AdamW [26] uses a decoupled weight decay regularization, defined as
mt = α1mt−1 + (1− α1)∇f(xt; ξt), vt = α2vt−1 + (1− α2)(∇f(xt; ξt))2 m̂t = mt/(1− αt1), v̂t = vt/(1− αt2), xt+1 = xt − ηt ( αm̂t/( √ v̂t + ε) + λxt ) , (5)
where α1, α2 ∈ (0, 1), α > 0, λ > 0 and ε > 0. More recently, to further improve generalization performance, AdaBelief [40] adopts a stepsize according to ‘belief’ in the current gradient direction,
mt = α1mt−1 + (1− α1)∇f(xt; ξt), vt = α2vt−1 + (1− α2)(∇f(xt; ξt)−mt)2 + ε m̂t = mt/(1− αt1), v̂t = vt/(1− αt2), xt+1 = xt − ηtm̂t/( √ v̂t + ε), ∀ t ≥ 1 (6)
where α1, α2 ∈ (0, 1), and ηt = η√t with η > 0, and ε > 0.
At the same time, to improve generalization performance, recently some effective adaptive gradient methods [34, 23, 11] have been proposed with adopting the global adaptive learning rates instead of coordinate-wise counterparts. For example, AdaGrad-Norm [34] applies a global adaptive learning rate to the following update form, for all t ≥ 1
xt = xt−1 − η∇f(xt−1; ξt−1)/bt, b2t = b2t−1 + ‖∇f(xt−1; ξt−1)‖2, b0 > 0, (7)
where η > 0. The adaptive-SGD [23] adopts a global adaptive learning rate, defined as for all t ≥ 1
ηt = k( ω + ∑t−1 i=1 ‖∇f(xi; ξi)‖2 )1/2+ε , xt+1 = xt − ηt∇f(xt; ξt), (8) where k > 0, ω > 0, and ε ≥ 0. Subsequently, STORM [11] not only uses a global adaptive learning rate but also adopts the variance-reduced technique in gradient estimator to accelerate algorithm, defined as for all t ≥ 1
ηt = k( ω + ∑t i=1 ‖∇f(xi; ξi)‖2 )1/3 , xt+1 = xt − ηtgt, (9) gt+1 = ∇f(xt+1; ξt+1) + (1− cη2t )(gt −∇f(xt; ξt+1)),
where k > 0, ω > 0 and c > 0.

heading: 3 SUPER-ADAM Algorithm
text: In the section, we propose a faster and universal framework of adaptive gradients (i.e., SUPERADAM) by introducing a universal adaptive matrix that includes most existing adaptive gradient forms. Specifically, our SUPER-ADAM algorithm is summarized in Algorithm 1.
At the step 4 in Algorithm 1, we generate an adaptive matrix Ht based on stochastic gradient information, which can include both coordinate-wise and global learning rates. For example, Ht generated from the case 1 in Algorithm 1 is similar to the coordinate-wise adaptive learning rate used in Adam [22]. Ht generated from the case 2 in Algorithm 1 is similar to the global adaptive learning rate used in the AdaGrad-Norm [34] and Adaptive-SGD [23]. Moreover, we can obtain some new adaptive learning rates by generating some specific adaptive matrices. In the case 3, based on Barzilai-Borwein technique [2], we design a novel adaptive matrix Ht defined as:
bt = |〈∇f(xt; ξt)−∇f(xt−1; ξt), xt − xt−1〉|
‖xt − xt−1‖2 , Ht = (bt + λ)Id, (10)
where λ > 0. In the case 4, as the adaptive learning rate used in [40], we can generate a coordinatewise-type adaptive matrix Ht = diag( √ vt + λ) and a global-type adaptive matrix Ht = (bt + λ)Id, respectively, defined as: mt = β1mt−1 + (1− β1)∇f(xt; ξt),
vt = β2vt−1 + (1− β2)(∇f(xt; ξt)−mt)2, bt = β2bt−1 + (1− β2)‖∇f(xt; ξt)−mt‖, (11) where β1, β2 ∈ (0, 1) and λ > 0. In fact, the adaptive matrix Ht can be given in a generic form Ht = At + λId, where the matrix At includes the adaptive information that is generated from stochastic gradients with noises, and the tuning parameter λ > 0 balances these adaptive information with noises.
At the step 9 in Algorithm 1, we use a generalized gradient descent (i.e., mirror descent) iteration [5, 3, 15] to update x based on the adaptive matrix Ht, defined as
x̃t+1 = arg min x∈X
{ 〈gt, x〉+ 1
2γ (x− xt)THt(x− xt)
} (12)
= arg min x∈X
{ f(xt) + 〈gt, x− xt〉+ 1
2γ (x− xt)THt(x− xt)
} , (13)
where γ > 0 is a constant stepsize. In the above subproblem (13), we can omit the constant terms f(xt) and 〈gt, xt〉. For the subproblem (13), the first two terms of its objective function is a linear function approximated the function f(x) based on the stochastic gradient gt, and the last term can be seen as a Bregman distance between x and xt based on the Bregman function wt(x) = 1 2x
THtx. At the step 10 in Algorithm 1, we use momentum update to obtain a weighted solution xt+1 = (1 − µt)xt + µtx̃t+1, where µt ∈ (0, 1] ensures xt+1 ∈ X . When X = Rd, the step 9 is equivalent to x̃t+1 = xt − γH−1t gt. Then by the step 10, we have
xt+1 = (1− µt)xt + µtx̃t+1 = xt − γµtH−1t gt. (14)
Under this case, γµt is a basic stepsize as ηt in the formula (3) of Adam algorithm, and H−1t is an adaptive stepsize as 1√
v̂t in the formula (3) of Adam algorithm.
At the step 11 of Algorithm 1, we use the stochastic gradient estimator gt+1 for all t ≥ 1: gt+1 = αt+1∇f(xt+1; ξt+1) + (1− αt+1) [ gt + τ ( ∇f(xt+1; ξt+1)−∇f(xt; ξt+1) )] , (15)
where τ ∈ {0, 1} and αt+1 ∈ (0, 1] for all t ≥ 1. When τ = 1, we have gt+1 = ∇f(xt+1; ξt+1) + (1− αt+1) ( gt −∇f(xt; ξt+1) ) for all t ≥ 1, which is a momentum-based variance reduced gradient estimator used in STORM [11]. When τ = 0, we have gt+1 = αt+1∇f(xt+1; ξt+1) + (1− αt+1)gt for all t ≥ 1, which is a basic momentum gradient estimator used in the Adam algorithm [22].

heading: 4 Theoretical Analysis
text: In this section, we study the convergence properties of our algorithm (SUPER-ADAM) under some mild conditions. All detailed proofs are in the supplementary materials.

heading: 4.1 Some Mild Assumptions
text: Assumption 1. Variance of unbiased stochastic gradient is bounded, i.e., there exists a constant σ > 0 such that for all x ∈ X , it follows E[∇f(x; ξ)] = ∇f(x) and E‖∇f(x; ξ)−∇f(x)‖2 ≤ σ2. Assumption 2. The function f(x) is bounded from below in X , i.e., f∗ = infx∈X f(x). Assumption 3. Assume the adaptive matrix Ht for all t ≥ 1 satisfies Ht ρId 0, and ρ > 0 denotes a lower bound of the smallest eigenvalue of Ht for all t ≥ 1.
Assumption 1 is commonly used in stochastic optimization [15, 11]. Assumption 2 ensures the feasibility of the problem (1). In fact, all adaptive algorithms in Table 1 require these mild Assumptions 1 and 2. Assumption 3 guarantees that the adaptive matrices {Ht}t≥1 are positive definite and their smallest eigenvalues have a lower bound ρ > 0. From the above adaptive matrices {Ht}t≥1 given in our SUPER-ADAM algorithm, we have ρ ≥ λ > 0. In fact, many existing adaptive algorithms also implicitly use Assumption 3. For example, Zaheer et al. [36] and Zhuang et al. [40] used the following iteration form to update the variable x: xt+1 = xt−ηt mt√vt+ε for all t ≥ 0 and ε > 0, which is equivalent to xt+1 = xt − ηtH−1t mt with Ht = diag( √ vt + ε). Clearly, we have Ht εId 0. Ward et al. [34] applied a global adaptive learning rate to the update form in (7), which is equivalent to the following form: xt = xt−1 − ηH−1t ∇f(xt−1; ξt−1) with Ht = btId. By the above (7), we have Ht · · · H0 = b0Id 0. Li et al. [23] and Cutkosky et al. [11] applied a global adaptive learning rate to the update forms in (8) and (9), which is equivalent to xt+1 = xt −H−1t gt, where Ht = (1/ηt)Id and ηt = k/ ( ω + ∑t i=1 ‖∇f(xi; ξi)‖2 )α with k > 0, ω > 0, α ∈ (0, 1). By the above (8) and (9), we have Ht · · · H0 = (ωα/k)Id 0. Reddi et al. [29] and Chen et al. [6] used the condition v̂t = max(v̂t−1, vt), and let Ht = diag( √ v̂t), thus we have
Ht · · · H1 = diag( √ v̂1) = √ 1− α2diag(|∇f(x1; ξ1)|) 0. Without loss of generality, choosing an initial point x1 and let (∇f(x1; ξ1))j 6= 0 for all j ∈ [d], we have Ht · · · H1 0. Interestingly, our SUPER-ADAM algorithm includes a class of novel momentum-based quasi-Newton algorithms by generating an approximated Hessian matrix Ht. In fact, the quasi-Newton algorithms [33, 16, 38] generally require the bounded approximated Hessian matrices, i.e., κ̂Id Ht κ̄Id 0 for all t ≥ 1, where κ̂ ≥ κ̄ > 0. Thus Assumption 3 is reasonable and mild. Due to Assumption 3, our convergence analysis can be easily applied to the stochastic quasi-Newton algorithms.

heading: 4.2 A Useful Convergence Measure
text: We provide a useful measure to analyze the convergence of our algorithm, defined as
Mt = 1
ρ ‖∇f(xt)− gt‖+
1 γ ‖x̃t+1 − xt‖. (16)
We define a Bregman distance [4, 5, 15] associated with function wt(x) = 12x THtx as follows
Vt(x, xt) = wt(x)− [ wt(xt) + 〈∇wt(xt), x− xt〉 ] = 1
2 (x− xt)THt(x− xt). (17)
Thus, the step 9 of Algorithm 1 is equivalent to the following mirror descent iteration:
x̃t+1 = arg min x∈X
{ 〈gt, x〉+ 1
γ Vt(x, xt)
} . (18)
As in [15], we define a gradient mapping GX (xt,∇f(xt), γ) = 1γ (xt − x + t+1), where
x+t+1 = arg min x∈X
{ 〈∇f(xt), x〉+ 1
γ Vt(x, xt)
} . (19)
Let GX (xt, gt, γ) = 1γ (xt − x̃t+1). According to Proposition 1 in [15], we have ‖GX (xt, gt, γ) − GX (xt,∇f(xt), γ)‖ ≤ 1ρ‖∇f(xt) − gt‖. Since ‖GX (xt,∇f(xt), γ)‖ ≤ ‖GX (xt, gt, γ)‖ + ‖GX (xt, gt, γ) − GX (xt,∇f(xt), γ)‖, we have ‖GX (xt,∇f(xt), γ)‖ ≤ ‖GX (xt, gt, γ)‖ + 1 ρ‖∇f(xt) − gt‖ = 1 γ ‖xt − x̃t+1‖ + 1 ρ‖∇f(xt) − gt‖ = Mt. When Mt → 0, we can obtain ‖GX (xt,∇f(xt), γ)‖ → 0, where xt is a stationary point or local minimum of the problem (1) [15]. Clearly, our measure E[Mt] is tighter than the gradient mapping measure E‖GX (xt,∇f(xt), γ)‖.

heading: 4.3 Convergence Analysis of SUPER-ADAM (τ = 1)
text: In this subsection, we provide the convergence analysis of our SUPER-ADAM (τ = 1) algorithm using the momentum-based variance reduced gradient estimator [11, 32]. Assumption 4. Each component function f(x; ξ) is L-smooth for all ξ ∈ D, i.e.,
‖∇f(x; ξ)−∇f(y; ξ)‖ ≤ L‖x− y‖, ∀x, y ∈ X .
Assumption 4 is widely used in the variance-reduced algorithms [13, 11]. According to Assumption 4, we have ‖∇f(x)−∇f(y)‖ = ‖E[∇f(x; ξ)−∇f(y; ξ)]‖ ≤ E‖∇f(x; ξ)−∇f(y; ξ)‖ ≤ L‖x− y‖ for all x, y ∈ X . Thus the function f(x) also is L-smooth.
Theorem 1. In Algorithm 1, under the Assumptions (1,2,3,4), when X ⊂ Rd, and given τ = 1, µt =
k (m+t)1/3 and αt+1 = cµ2t for all t ≥ 0, 0 < γ ≤ ρm1/3 4kL , 1 k3 + 10L2γ2 ρ2 ≤ c ≤ m2/3 k2 , m ≥ max ( 3 2 , k 3, 8 3/2 (3k)3/2 ) and k > 0, we have
1
T T∑ t=1 E‖GX (xt,∇f(xt), γ)‖ ≤ 1 T T∑ t=1 E [ Mt ] ≤ 2 √ 2Gm1/6 T 1/2 + 2 √ 2G T 1/3 , (20)
where G = f(x1)−f ∗ kργ + m1/3σ2 8k2L2γ2 + k2c2σ2 4L2γ2 ln(m+ T ).
Remark 1. Without loss of generality, let ρ = O(1), k = O(1), m = O(1), and γ = O(1), we have c = O(1) and G = O ( c2σ2 ln(m+ T ) ) = Õ(1). Thus, our algorithm has a convergence rate
of Õ (
1 T 1/3
) . Let 1
T 1/3 ≤ , we have T ≥ −3. Since our algorithm only requires to compute two
stochastic gradients at each iteration (e.g., only need to compute stochastic gradients∇f(xt+1; ξt+1) and ∇f(xt; ξt+1) to estimate gt+1), and needs T iterations. Thus, our SUPER-ADAM (τ = 1) has a gradient complexity of 2 · T = Õ( −3) for finding an -stationary point. Corollary 1. In Algorithm 1, under the above Assumptions (1,2,3,4), when X = Rd, and given τ = 1, µt = k(m+t)1/3 and αt+1 = cµ 2 t for all t ≥ 0, γ = ρm1/3 νkL (ν ≥ 4), 1 k3 + 10L2γ2 ρ2 ≤ c ≤ m2/3 k2 ,
m ≥ max ( 3 2 , k 3, 8 3/2 (3k)3/2 ) and k > 0, we have
1
T T∑ t=1 E‖∇f(xt)‖ ≤ max1≤t≤T ‖Ht‖ ρ ( 2 √ 2G′ T 1/2 + 2 √ 2G′ m1/6T 1/3 ) , (21)
where G′ = νL(f(x1)− f∗) + ν 2σ2 8 + ν2k4c2σ2 4m1/3 ln(m+ T ). Remark 2. Under the same conditions in Theorem 1, based on the metric E‖∇f(x)‖, our SUPER-ADAM (τ = 1) still has a gradient complexity of Õ( −3). Interestingly, the right of the above inequality (21) includes a term max1≤t≤T ‖Ht‖ρ that can be seen as an upper bound of the condition number of adaptive matrices {Ht}Tt=1. When using Ht given in the above case 1, we have max1≤t≤T ‖Ht‖ρ ≤ G1+λ λ as in the existing adaptive gradient methods assuming the bounded stochastic gradient ‖∇f(x; ξ)‖∞ ≤ G1; When using Ht given in the above case 2, we have max1≤t≤T ‖Ht‖ρ ≤ G2+σ+λ λ as in the existing adaptive gradient methods assuming the bounded full gradient ‖∇f(x)‖ ≤ G2; When using Ht given in the above case 3, we have max1≤t≤T ‖Ht‖
ρ ≤ L+λ λ . When using Ht given in the above case 4, we have max1≤t≤T ‖Ht‖ ρ ≤ 2G1+λ λ
or max1≤t≤T ‖Ht‖ρ ≤ 2(G2+σ)+λ
λ . Note that we only study the gradient (sample) complexity of our algorithm in the worst case without considering some specific structures such as the sparsity of stochastic gradient. Since the adaptive matrix Ht can be given Ht = At + λId, we have max1≤t≤T ‖Ht‖
ρ = max1≤t≤T δmax(At)+λ min1≤t≤T δmin(At)+λ . Here we only can choose a proper tuning parameter λ to
balance adaptive information with noises in At. To reduce max1≤t≤T ‖Ht‖
ρ , we can not increase λ, but should design the matrix At with a small condition number by some techniques, e.g., clipping [27].

heading: 4.4 Convergence Analysis of SUPER-ADAM (τ = 0)
text: In this subsection, we provide the convergence analysis of our SUPER-ADAM (τ = 0) algorithm using the basic momentum stochastic gradient estimator [22]. Assumption 5. The function f(x) = Eξ[f(x; ξ)] is L-smooth, i.e.,
‖∇f(x)−∇f(y)‖ ≤ L‖x− y‖, ∀x, y ∈ X .
Assumption 5 is widely used in adaptive algorithms [36, 8, 40], which is milder than Assumption 4. Theorem 2. In Algorithm 1, under the Assumptions (1,2,3,5), when X ⊂ Rd, and given τ = 0, µt =
k (m+t)1/2
, αt+1 = cµt for all t ≥ 0, k > 0, 0 < γ ≤ ρm 1/2 8Lk , 8Lγ ρ ≤ c ≤ m1/2 k , and m ≥ k 2,
we have
1
T T∑ t=1 E‖GX (xt,∇f(xt), γ)‖ ≤ 1 T T∑ t=1 E [ Mt ] ≤ 2 √ 2Mm1/4 T 1/2 + 2 √ 2M T 1/4 ,
where M = f(x1)−f ∗ ργk + 2σ2 ργkL + 2mσ2 ργkL ln(m+ T ).
Remark 3. Without loss of generality, let ρ = O(1), k = O(1), m = O(1) and γ = O(1), we have M = O ( σ2 ln(m + T ) ) = Õ(1). Thus, our algorithm has convergence rate of Õ ( 1
T 1/4
) .
Considering 1 T 1/4 ≤ , we have T ≥ −4. Since our algorithm requires to compute one stochastic gradient at each iteration, and needs T iterations. Thus, our SUPER-ADAM (τ = 0) has a gradient complexity of 1 · T = Õ( −4) for finding an -stationary point. Corollary 2. In Algorithm 1, under the above Assumptions (1,2,3,5), when X = Rd, and given τ = 0, µt = k(m+t)1/2 , αt+1 = cµt for all t ≥ 0, k > 0, γ = ρm1/2 νLk (ν ≥ 8), 8Lγ ρ ≤ c ≤ m1/2
k , and m ≥ k2, we have
1
T T∑ t=1 E‖∇f(xt)‖ ≤ max1≤t≤T ‖Ht‖ ρ ( 2 √ 2M ′ T 1/2 + 2 √ 2M ′ m1/4T 1/4 ) ,
where M ′ = νL(f(x1)− f∗) + 2νσ2 + 2νmσ2 ln(m+ T ). Remark 4. Under the same conditions in Theorem 2, based on the metric E‖∇f(xt)‖, our SUPERADAM (τ = 0) still has a gradient complexity of Õ( −4) for finding an -stationary point.

heading: 5 Differences between Our Algorithm and Related Algorithms
text: In this section, we show some significance differences between our algorithm and some related algorithms, i.e., STORM algorithm [11] and Adam-type algorithms [22, 29, 40]. Although our SUPER-ADAM (τ = 1) algorithm uses the same stochastic gradient estimator used in the STORM, there exist some significant differences:
1) Our algorithm focuses on both constrained and unconstrained optimizations, but STORM only focuses on unconstrained optimization.
2) In our algorithm, we introduce a weighted solution xt+1 at the step 10 by using momentum update. Under this case, our algorithm can easily incorporate various adaptive learning rates and variance reduced techniques. Specifically, we can flexibly use various adaptive learning rates and different stochastic gradient estimators gt at the step 9 of our algorithm. In fact, this is one of important novelties of our paper. However, the STORM only uses a simple gradient descent iteration with a specific monotonically decreasing adaptive learning rate.
Similarly, although our SUPER-ADAM (τ = 0) algorithm uses the same stochastic gradient estimator used in these Adam-type algorithms, there exist some significant differences besides using different adaptive learning rates. These Adam-type algorithms use a decreasing learning rate ηt = η√t (Please see the above (3), (4) and (6)), while our algorithm only uses a constant learning rate γ besides an adaptive learning rate. Moreover, our algorithm introduces a weighted solution xt+1 at the step 10 with a decreasing parameter µt = k√m+t (Please see Theorem 2) and uses a decreasing parameter αt+1 = cµt in the gradient estimator, while these Adam-type algorithms only use a constant parameter α1 ∈ (0, 1) in their gradient estimators. Under this case, our algorithm uses these decreasing parameters µt and αt+1 to control the noises in our gradient estimator, so our algorithm does not require some additional assumptions such as the bounded (stochastic) gradient assumption in our convergence analysis for the constrained optimization. For example, when τ = 0, our gradient estimator is gt+1 = αt+1∇f(xt+1; ξt+1) + (1−αt+1)gt. Intuitively, with growing t, αt+1 = ck√m+t will become small, so the new noises added in our gradient estimator gt+1 will also become less.

heading: 6 Numerical Experiments
text: In this section, we conduct some experiments to empirically evaluate our SUPER-ADAM algorithm on two deep learning tasks as in [25]: image classification on CIFAR-10, CIFAR-100 and ImageNet datasets and language modeling on Wiki-Text2 dataset. In the experiments, we compare our SUPER-ADAM algorithm against several state-of-the-art adaptive gradient algorithms, including: (1) SGD, (2) Adam [22], (3) Amsgrad [29], (4) AdaGrad-Norm [23], (5) Adam+ [25], (6) STORM [11] and (7) AdaBelief [40]. For our SUPER-ADAM algorithm, we consider τ = 1 and τ = 0, respectively. Without loss of generality, in the following experiments, we only use the case 1 in Algorithm 1 to generate adaptive matrix Ht and let λ = 0.0005. All experiments are run over a machine with Intel Xeon E5-2683 CPU and 4 Nvidia Tesla P40 GPUs.

heading: 6.1 Image Classification Task
text: In the experiment, we conduct image classification task on CIFAR-10, CIFAR-100 and Image-Net datasets. We perform training over ResNet-18 [20] and VGG-19 [30] on CIFAR-10 and CIFAR-100 datasets, respectively. For all the optimizers, we set the batch size as 128 and trains for 200 epochs. For the learning rates and other hyper-parameters, we do grid search and report the best one for each optimizer. In Adam, Amsgrad and AdaBelief algorithms, we set the learning rate as 0.001. In AdaGrad-Norm, the best learning rate is 17 for CIFAR-10 and 10 for CIFAR-100, respectively. In Adam+, we use the recommended tuning parameters in [25]. In STORM, the best result is obtained when w = 6, k = 10 and c = 100 for CIFAR-10, while w = 3, k = 10 and c = 100 for CIFAR-100. For our SUPER-ADAM algorithm, in both CIFAR-10 and CIFAR-100 datasets, we set k = 1, m = 100, c = 40, γ = 0.001 when τ = 1, and k = 1, m = 100, c = 20, γ = 0.001 when τ = 0. Note that although c > m 2/3
k2 (c > m1/2
k ) in our algorithm, we set αt = min(αt, 0.9) at the first several iterations. In our algorithm, µt = k(m+t)1/3 (µt = k (m+t)1/2
) decreases as the number of iteration t increases, so αt+1 = cµ2t (αt+1 = cµt) will be less than 1 after the first several iterations.
We train a ResNet-34 [20] on ImageNet dataset. For all the optimizers, we set the batch size as 256 and trains for 60 epochs. In Adam,Amsgrad and AdaBelief, we set learning rate as 0.001. In AdaGrad-Norm, the best learning rate is 30. In Adam+, we set learning rate as 0.1. In STORM, the best result is obtained when k = 5, w = 100 and c = 10. For our algorithm, we set k = 1, m = 100, c = 40, γ = 0.01 when τ = 1, and k = 1, m = 100, c = 4, γ = 0.04 when τ = 0.
Figures 1 and 2 show that both train and test errors and accuracy results of the CIFAR-10 and CIFAR-100 datasets, respectively. Our SUPER-ADAM algorithm consistently outperforms the other optimizers with a great margin, especially when we set τ = 1. When we set τ = 0, our SUPERADAM algorithm gets the comparable performances with Adam/AmsGrad. Figure 3 demonstrates
the results of ImageNet by different optimizers over ResNet-34, which shows that our algorithm outperforms the other optimizers, especially set τ = 1 in our algorithm. Figure 4 shows that both the condition number of Ht and the `2 norm of full gradient (i.e.,‖∇f(xt)‖) decrease as the number of iteration increases. From these results, we find that since the condition number of Ht decreases as the number of iteration increases, so it must has an upper bound. Thus, these experimental results further demonstrate that the above convergence results in Corollaries 1 and 2 are reasonable.
6.2 Language Modeling Task
In the experiment, we conduct language modeling task on the Wiki-Text2 dataset. Specifically, we train a 2-layer LSTM [21] and a 2- layer Transformer over the WiKi-Text2 dataset. For the LSTM, we use 650 dimensional word embeddings and 650 hidden units per-layer. Due to space limitation, we provide the experimental results for the transformer in the supplementary materials. In the experiment, we set the batch size as 20 and trains for 40 epochs with dropout rate 0.5. We also clip the gradients by norm 0.25 in case of the exploding gradient in LSTM. We also decrease the learning by 4 whenever the validation error increases. For the learning rate, we also do grid search and report the best one for each optimizer. In Adam and Amsgrad algorithms, we set the learning rate as 0.001 in
LSTM In AdaGrad-Norm algorithm, the best learning rate is 40. In Adam+ algorithm, we use the learning rate 20. In AdaBelief algorithm, we set the learing rate 0.1. In STORM algorithm, we set w = 50, k = 10 and c = 100. In our SUPER-ADAM algorithm, we set k = 1, m = 100, c = 40, γ = 0.001 when τ = 1, while k = 1, m = 100, c = 20, γ = 0.01 when τ = 0.
Figure 5 shows that both train and test perplexities (losses) for different optimizers. When τ = 1, our SUPER-ADAM algorithm outperforms all the other optimizers. When τ = 0, our SUPER-ADAM optimizer gets a comparable performance with the other Adam-type optimizers.

heading: 7 Conclusions
text: In the paper, we proposed a novel faster and universal adaptive gradient framework (i.e., SUPERADAM) by introducing a universal adaptive matrix including most existing adaptive gradient forms. In particular, our algorithm can flexibly work with the momentum and variance reduced techniques. Moreover, we provided a novel convergence analysis framework for the adaptive gradient methods under the nonconvex setting. Experimental studies were conducted on both image classification and language modeling tasks, and all empirical results verify the superior performances of our algorithm.
Acknowledgments and Disclosure of Funding
This work was partially supported by NSF IIS 1845666, 1852606, 1838627, 1837956, 1956002, OIA 2040588.

Review summaries:
This paper presents a universal adaptive gradient framework (i.e., super-adam), which can flexibly incorporate the momentum and variance reduced techniques to effectively accelerate the convergence of the algorithm. Moreover, it provides a sound convergence analysis framework for the super-adam under the nonconvex setting. Experimental results on some deep learning tasks demonstrate the efficiency of the proposed super-adam algorithm. Super-adam may have broad applications in training deep learning models. Overall, I recommend accepting this paper.    

This paper proposes a faster and universal framework of adaptive gradients (super-adam) for nonconvex stochastic optimization. Specifically, super-adam introduces a universal adaptive matrix that includes most existing adaptive gradient forms and many new adaptive learning rates. In particular, it can flexibly integrate the momentum and variance reduced techniques. Moreover, this paper provides an effective and interesting theoretical analysis framework based on a new convergence metric. Meanwhile, it provides the extensive experimental results to demonstrate the efficiency of the super-adam algorithm. Overall, it is an interesting and innovative paper. It will have a wide range of applications in machine learning. 

This manuscript introduces a unified framework (i.e., SUPER-ADAM) of adaptive gradient methods for nonconvex optimization. It is proved that a universal convergence measure converges with a fast rate, which recovers the $O(\epsilon^{-3})$ complexity by STORM. Another result is that it also recovers $O(\epsilon^{-4})$ result by SGD, when individual function does not have a Lipschitz-continuous gradient. Numerical experiments on image classification and language modeling shows that SUPER-ADAM has faster convergence rate when training deep neural networks.