SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients
Authors: Feihu Huang
Junyi Li
Heng Huang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Adaptive Gradient
Adam
Universal Framework
Nonconvex Optimization
Deep Learning

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 $\tilde{O}(\epsilon^{-3})$ for finding an $\epsilon$-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

SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients
Feihu Huang, Junyi Li, Heng Huang
Department of Electrical and Computer Engineering, University of Pittsburgh, Pittsburgh, USA huangfeihn2018@@mai.. junyili aeriiaai@gma ai@gmail. com, sang.huang@pite edu
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 faster and universal framework adaptive gradients (i.e., SUPER-ADAMA by introducing 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 rithm can achieve the best known gradient (i.e., stochastic first-order oracle (SFO)) complexity Ó(e for finding an e-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 http://ggthhl.oom///UUU////////
SUPER-ADAN algo-
Introduction
In the paper, we consider solving the following stochastic optimization problem:
min
f(x) : =Eg=Dl((x;
(1)
#EX
where (()) denotes a smooth and possibly nonconvex loss function, and Ç is a random example variable following an unknown data distribution D. Here X' = TRd or X' C Rdd is a compact and convex set. The problem (1) frequently appears in many machine learning applications such the expectation loss minimization. Recently, Stochastic Gradient Descent (SGD) [4] is commonly used solve the problem | such as Deep Neural Networks (DNNs) training [T8] 20), due only requiring a mini-batch samples or even one sample at each iteration. Adaptive gradient methods 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 Ádagrad e.g., SC-Adagra (8 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 (NcurIPS 2021).

---

Table 1: Gradient (i.e., stochastic first-order oracle (SFO)) complexity of the representative adaptive gradient algorithms for finding an e-stationary point of the non-convex stochastic problem (T) Le., fz)]| I or its equivalent variants. For fair comparison, we only provide the gradient complexity and convergence rate in the worst case without considering the sparsity of stochastic gradient. Here T denotes the whole number of iteration, and & denotes mini-batch size. ALR denotes adaptive learning rate. I denotes the smoothness of each component function f(x; E): 2 denotes the smoothness of objective function (ar) Feg (f:: (a:; {)]; 3 denotes the bounded stochastic gradient V f=; 4 denotes the bounded true gradient fx() 5 denotes that f() is Lipschitz continuous;
denotes the smoothness of true gradient V fzx).
Algorithm
Reference
Complexity
Convergence Rate
ALR
Conditions
Adam/ YOGI
36
O(e ")
VT O
+
Vb
specific
1, 2, 3,
Generalized Adam
Ō(e-2)
00 /log(T)
specific
2, 3, 4
Tiys
Padam
16
O(E
0 7T + Tiy
specific
2,3, 4
Adaptive SGD
23
Ōle +)
0 Vinlr)
specific
2,5
VT
AdaGrad-Norm
34
Ō(c-1)
((>/ou(()) 0
specific
2. 4
T176
Ada-Norm-SGD
10
0 ((
specific
2,
AdaBelicf
40
Ōlc-))
0 ((VloR(()
T1/4
specific
2, 2,3, 4
Adam
25
O O(TZT7
specific
2,
STORM
Ō
0 (1u(T)))/ + /in(r) y'T
specific
1,
T17s
SUPER-ADAM (T 0)
Ours
Ö(e-t)
0 ( v(u(T)
/T
T174
universal
2
SUPER-ADAM =
Ours
Ö(e-9)
0( Vin(T) vin(T)
universal
vT
Adagrad, e.g., Adadelta 337, 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 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 order to handle the convergence issue of Adam. YOGI (36) introduces an adaptive denominator constant, and studies effect of the mini-batch size its convergence. Subsequently, Chen et al. studied the convergence of a class of Adam-type algorithms for nonconvex optimization. Zhou et al. 339 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 novel convergence analysis for 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-ve wise learning rates [35). Thus, recently some adaptive gradient methods have been proposed to improve the generalization performance of Adam. For example, AdamW (66 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 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 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-Nome Norm) 34] has been proposed to obtain good generalization performance.
So far, the above adaptive gradient methods still suffer from a high gradient complexity of O(6-1) for finding e-stationary point in the worst case without considering sparsity of gradient. More recently, some faster rrfancc-reduced adaptive gradient methods such STORM [I], Adaptive Normalized

---

SGD [0]. Adam 25 have been proposed. For example, STORM applies the momentum-bisg based variance reduced technique to obtain a lower gradient complexity of O(e-)), 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 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 faster and universal framework of adaptive gradients, i.e. SUPER-ADAM algorithm, by introducing 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 [S] [5]. In summary, our main contributions are threefold:
1) We propose faster and universal framework of adaptive gradients (i.e., SUPER-ADAM) by introducing universal adaptive matrix that includes most existing adaptive gradients. Moreover, framework can flexibly integrate the momentum and variance-reduced techniques.
2) We provide novel convergence analysis framework for the adaptive gradient methods in the nonconvex setting under the milder conditions (Please see Table I
3) We apply a momentum-based variance reduced gradient estimator (SUPER-ADAM
32 to our algorithm
1)), which makes algorithm reach faster convergence rate than the classic adaptive methods. Specifically, under smoothness of each component function f(;;; E), we prove that the SUPER-ADAM (T 1) achieves the best known gradient complexity of Ö(E- for finding an e-stationary point of the problem (T). which matches the lower bound
for stochastic smooth nonconvex optimization M. Under smoothness of the function fzx we prove that the SUPER-ADAM (T 0) achieves gradient complexity of ()
Preliminaries
2.1 Notations
|| || denotes the lg norm for vectors and spectral norm for matrices, respectively. Ia denotes a d-dimensional identity matrix. diag(a) RRd denotes diagonal matrix with diagonal entries (41, az)). For vectors u and v, uP (p > 0) denotes element power operation, u/v denotes element-wise division and max(u, v) denotes element- maximum. (u, 2) denotes the inner product of two vectors u and v. For two sequences {an} and [6x], we write an 0b,,) ) if there exists positive constant C. such that on I Cb and O(-) hides logarithmic factors. A > 0(2 0) denotes a positive (semi)definite matrix. (A) and (max(() denote the smallest and largest eigenvalues of the matrix A, respectively.
2.2 Adaptive Gradient Algorithms
In the subsection, we review some existing typical adaptive gradient methods. Recently, many adaptive algorithms have been proposed to solve the problem ( 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:
1141 Ft mr.t/ VTe,
where = V((x; Er) and v = 1 E
g3. and = 3 with 7) > O is the step size. In fact, Y) only is the basic learning rate that is the same for all coordinates of variable 2,, while Th is the effective learning rate for the i-th coordinate of It, which changes across the coordinates.
yoe.
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:
m a- + (1 - Vf
er -2 + (1 - (2)
(3) where 0n, 02 E 10 and E > 0, and n) = 3h with 7) > 0. However, Reddi et al. (2 found divergence issue of the Adam algorithm, and proposed a modified version of Adam (i.c., Amsgrad), which adopts new step instead of the debiasing step in 3 to ensure the decay of the effective learning rate, defined as
m = mm (1 - af). 0. = v -1)),, T++1 = Ir - nom./(// + E), Vt21
i = mmax(0;111 vt), Fe+1 xt mmmme/ V
(4)
3

---

Algorithm SUPER-ADAM Algorithm
1: Input: Total iteration T, and tuning parameters {14, 0 d > 0;
2: Initialize: 21 X, sample one point & and compute 91 V (z):
3: for 1,2.....4 do
4: Generate adaptive matrix H, E Rdxd; // Given two examples update Hę
5: Case 1: given 3 & (0, 1), >> 0 and Up = 0, B)V (arx; H,
6: == = B1-- +
diag(V/n
A);
7:
Case 2: given [ E 1), A 0 and bo = 0,
8:
by - -b ((xl) H, = (b. + A)
9:
Update ēo+1 = arg min { x) + 27 1 21)² He( - x1)};
10:
Update T++1 (1 14)az + 14
11:
Sample one point E1+1, and compute 9++1 = 0++1 V(((+1i(tt) + (1 -0+t)( +
T T - ( where E {0,
12:
end for
13:
Output: (for theoretical) 25c chosen uniformly random from {ar ) (for practical DT.
Due using the coordinate 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 decoupled weight decay regularization, defined as
m, 01 (1 ai (( Ut a224-1 + (1 (1=
mr mmmm/1111 - d. 0 2/ / (1-a)), T++1 x4z - 7o (arii/// + E) + ArT), (5)
where 02 E (0, 1), > 0, À 0 and E > 0. More recently, to further improve generalization performance, AdaBelief [40] adopts a stepsize according to 'belief" in the current gradient direction,
my = - + 01 (1))) (frz Ee);
it 02 + (1 a:) (Vr) Ee) m2)² +
ni. mmmm11 -a),, ût v1((1 aa), Te+1
m). / +e), A211
(6)
where 01, E (0, 1), and 1): V with 0, and
0.
At the same time, to improve generalization performance, recently some effective adaptive gradient methods 34
have been proposed with adopting the global adaptive learning rates instead of coordinate-wee wise counterparts. For example, AdaGrad-Norm (34] applies global adaptive learning rate to the following update form, for all
2t -z-1 (
b ( by > O,
where 7) >> 0. The adaptive-SGD [23 adopts global adaptive learning rate, defined as for all t 2
k
Te+1 Ft m7t (z(())))
+ Σ [Z.
where 1: > 0, w > and E 2 0. Subsequently, STORM [1 not only uses global adaptive learning rate but also adopts the variance-reduced technique in gradient estimator to accelerate algorithm, defined as for 2 1
k
1)
It-1 = -](tt,
(9)
(w Elm [T(
V ( + (1-on (((r))))))
g++1
where & > 0, and >
SUPER-ADAM Algorithm
In the section, we propose faster and universal framework of adaptive gradients (i.e., SUPER- ADAM) by introducing universal adaptive matrix that includes most existing adaptive gradient forms. Specifically, SUPER-ADAM algorithm is summarized in Algorithm

---

At the step 4 in Algorithm 1 we generate an adaptive matrix H, based on stochastic gradient information, which can include both coordinate- wise and global learning rates. For example, H, generated from the case 1 in Algorithm [ is similar to the coordinate- -wise adaptive learning rate used in Adam [2)] H, generated from the case 2 in Algorithm| T is similar to the global adaptive learning rate used in the AdaGrad-Norm [ 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 novel adaptive matrix Ht, defined as:
by_ ((re)))) V ( Et). -
z1-1)1
H, = (be + A)Ta:
(10)
| - x2-1ll2
where À > O. In the case 4, as the adaptive learning rate used in [40], we can generate a coordinate- wise-type adaptive matrix H, = diag( (v + ^) and global-type adaptive matrix H; = (b. + A)La. respectively, defined as: Mh - + (1 V ( Ex),
= --20r-1 + (1- (V - -m,) be = Bebr-1 + + 32) V - - (1I)
where 82 (0, and À 0. In fact, the adaptive matrix H, can be given in generic form H₁ = A. + Ala, where the matrix A, includes the adaptive information that is generated from stochastic gradients with noises, and the tuning parameter balances these adaptive information with noises.
At the step 9 in Algorithm I
we use generalized gradient descent (i.e., mirror descent) iteration 5 3 15 to update x based on the adaptive matrix He, defined as
fe+1 = arg min #EA'
(1), + 27
(x - (xx)) H2 - =x1}}
(12)
arg min {f(z) (gt, x 21) + - (I H,(x 21)}
1
(13)
ZEX
27
where 7 O is a constant stepsize. In the above subproblem (3) we can omit the constant terms fZz) and 2t). For the subproblem (3). the first two terms of its objective function linear function approximated the function f(z) based on the stochastic gradient It, and the last term can be seen as Bregman distance between x and based on the Bregman function we (x)(x) 1=² Hy,. At the step 10 Algorithm |
we use momentum update to obtain a weighted
solution rz-1 = (1 - x4)xz
xz + M where μ4 E (0, 1] ensures Z++1 X. When X' IRd, the step 9 is equivalent to ē.+1 = Zt "H;" 9b- Then by the step 10, we have
1++1 = (1 - (44 14) 2+ + p4 2t - H, 9t-
(14)
Under this case, y is a basic stepsize as fi in the formula (3) of Adam algorithm, and H, an adaptive stepsize as Ve,
in the formula 33 of Adam algorithm.
At the step 11 of Algorithm D we use the stochastic gradient estimator g+++1 for all / 2 1:
I++1 1 (f + (1 ax+1) [9. + T (V - &())) (15)
where 7 E f0, 1) and 0441 E (0, 1] for all t 1. When 1, we have I++1
(1 ac+1) (gt- v Vfrr estimator used in STORM [II]. When r = O, we have It+1 = a (f f(+1) + (1 -441199
for all l 2 1, which is a momentum-based variance reduced gradient
for all 2 1, which a basic momentum gradient estimator used the Adam algorithm 22
4 Theoretical Analysis
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.
4.1 Some Mild Assumptions
Assumption 1. Variance of unbiased stochastic gradient is bounded, i.e., there exists a constant
0 such that for all x E X, follows E {)] = fzx) and E fx(:: Vf (=))l o².
Assumption 2. The function f(x) is bounded from below in X, i.c., f = inf f(x). Assumption 3. Assume the adaptive matrix H, for all I 2 1 satisfies H, ł pla > 0, and p >
denotes a lower bound of the smallest eigenvalue of H, for all t 2 1.
5

---

11 Assumption 2 ensures the feasi- bility of the problem (T) In fact, all adaptive algorithms in Table require these mild Assumptions 1 and 2. Assumption 3 guarantees that the adaptive matrices H, Fe21 are positive definite and their smallest eigenvalues have a lower bound p > From the above adaptive matrices ( (e2 given in our SUPER-ADAM algorithm, we have p 2 À > O. In fact, many existing adaptive algorithms For example, Zaheer et al. [36] and Zhuang et al. [40] used the 0, which
Assumption 1 is commonly used in stochastic optimization [1
also implicitly use Assumption 3. following iteration form to update the variable x: 1 -t- verte for all 2 0 and
is equivalent to 1++1 = 2; T/, H, m, with H, -diagg/aa + e). Clearly, we have H, - =Ta+ > 0. Ward et al. [34] applied a global adaptive learning rate to the update form in (7). which is equivalent
to the following form: Ht -t-1 nH, f
with H, b, By the above (7).
we have H, = ... 2 Ho = bold > 0. Li et al.
[23] and Cutkosky et al. [T]] applied global
adaptive learning rate to the update forms in (8) and ( which is equivalent to 3++1 = Iz H 9t.
where H₃ = (1/m) and 172 = k/(w + Σ V (=);)))) with &o > 0,w > 0, E (0, 1). By the above (8) and (9. we have H, 2 ... - Ho = (w0 Tk) > 0. Reddi et al. 29 and Chen et al. [6] used the condition 6 = max (0,-,, 2t), and let H, = diag(vE)) thus we have (I) - 0. Without loss of generality, choosing initial point 1 and let (v](=));)) + for all j E [d], we have H, > ... Hi > O. Interestingly, our SUPER-ADAM algorithm includes class of novel momentum- based quasi-Newton algorithms by generating an approximated Hessian matrix H,. In fact, the quasi-Newton algorithms 33 16 38 generally require the bounded approximated Hessian matrices, i.c., Rla 2 He 2 RRly > 0 for all t 1, where R 2 R >> O. Thus Assumption 3 is reasonable and mild. Due to Assumption 3, our convergence analysis can be easily applicd to the stochastic quasi- Newson algorithms.
H, - ... = H1 = diag(v = VI- (
4.2 A Useful Convergence Measure
We provide useful measure to analyze the convergence of our algorithm, defined as
M; fV] 9:1l + - || zell-
(16)
We define a Bregman distance 4
5
associated with function wa(x)) = 1 H2 as follows
Vi 22) = (xr (xx) + (Vwr( x - =x)]] (a - sT.)² H - 2²).
(17)
Thus, the step 9 of Algorithm equivalent to the following mirror descent iteration:
ã+ч1 arg min argmin zex (9., x) + - - (z,
(18)
7
As in 15 we define a gradient mapping (2 Vf(z,), { - att1), where
क arg min ( (VV(()), x) + Vi(x, 21)3. xex
(19)
Let Gx = 1 (x - 1141). According to Proposition in [5), we have [ It, 7)
Ex(x1, v/(xx), S (x)) gell- Since [[ (1x)), 7)ll I Gx Pt, 7)
[r((1, Sr, 7) - (x(x,, Vf(x), 7))l,, we have [ (xxx), ?)ll S [ gt: 7)
[ gell
|x, Ze+ill + +
9e M.. When M. + O, we can obtain
(r Vf(=)), 7) + O. where x; is stationary point or local minimum of the problem [I [15
Clearly, our measure B[M,] is tighter than the gradient mapping measure El]Gx( f(x)), ()))),
4.3 Convergence Analysis of SUPER-ADAM (T 1)
In this subsection, we provide the convergence analysis of our SUPER-ADAM (T= 1) algorithm using the momentum-based variance reduced gradient estimator 32).
Assumption 4. Each component function far; {) L-smooth for all & E D,
[V](z; - V (ll: < L||x - vll. Vx, y E X.
Assumption 4 is widely used in the variance-reduced algorithms 13 11 According Assumption 4, we have || [V(x) - vf(r)] = ||[ (a; (y: E) < E
(x); V((:<))1 S L.I yll
for all z, y E X. Thus the function f() also is L-smooth.

---

Theorem 1. In Algorithm
1 under the Assumptions (1,2,3,4), when X'
C RR, and given
1,
[t (m+t)u73 and a++1
cnt for all 2 0, 0
<
<
1kL g
1/2
10r2
S c
S
m 2/3
k²
m max 1 k3
g// (3k)3/2
and k. O, we have
1
1 T
2v 2V2mm 1/6
2V2G T1/3
B Vf(aa)) S
M S
(20)
T
T1/2
where G= (a))) m 00
L.000 1L In(m + +T).
kpy
SK=L
Remark 1. Without loss of generality, let p = 011), k = 0(1, = O(). and 7 O(1), we have c ((1) and G = of Ö ( Let Ti73 S c, we have T 2 c Since our algorithm only requires to compute two stochastic gradients at each iteration (e.g., only need to compute stochastic g gradients V f (Z1+1: E1+1) and V fzx; E1+1) to estimate 9041). and needs T iterations. Thus, our SUPER-ADAM (T = 1) has gradient complexity o T D(=-)) finding an e-stationary point.
T)) Ó(1). Thus, our algorithm has a convergence rate
Corollary 1. In Algorithm 7 under the above Assumptions (1,2,3,4), when X' = Rd, and given 101."²
1, 14 (m++))73 and 01+1 cup for all 2 0, ?
pm LkL (v 2 4), 13 o² S k²
2/3
m 2 max h2 k3 (3k)372)
82/2
and k O, we have
Σ
T
E [(VDI
maxIsIST
Hell
(2V2G' T1/2
2V2G'
(21)
m//6///3
P
1=1
where G -VT[[(()) 5²) 2o0 2R 8 4m173
In(m + T).
Remark 2. Under the same conditions in Theorem based on the metric [ our SUPER-ADAM (T = 1) still has a gradient complexity of Ō(c²)). Interestingly, the right of the above inequality 21 includes term maxisisT [| that can be seen as an upper bound of the condition number of adaptive matrices {H.)T=1-
P
When using He given in the above case < G.+h as in the existing adaptive gradient methods assuming the bounded stochastic gradient [[] Elloo I G1; When using He given in the above case 2. have maxi ||-+|||
1, we have max ||Hall
Cxte+A as in the existing adaptive gradient methods assuming the [+)] S G2: When using H, given in the above case 3, we have When using H; given in the above case 4, we have maxisisT ||H,ll < 2G
P bounded full gradient max [| L+A
P or MANISEST [[Hell| 2(Gr+a)+> Note that we only study the gradient (sample) complexity of P
X
P
our algorithm in the worst case without considering some specific structures such as the spar- sity of stochastic gradient. Since the adaptive matrix H, can be given H, = A, + Xla. we have maxisesT (A) Here we only can choose a proper tuning parameter X to minigIsT bmin(Ae)+
maxiet<T ||H.]l
P
balance adaptive information with noises in A;- To reduce maxigteT [Hell we can not increase X, but should design the matrix A, with small condition number by some techniques, e.g., clipping [27].
P
4.4 Convergence Analysis of SUPER-ADAM (T 0)
In this subsection, we provide the convergence analysis of our SUPER-ADAM (T = 0) algorithm using the basic momentum stochastic gradient estimator (2) Assumption 5. The function {(x) = Ee[[(x; {)) is L-smooth, i.e.
[ V fz)i s L|[z vll. Vz,y X.
Assumption is widely used in adaptive algorithms
36 40 which milder than Assumption
Theorem 2. In Algorithm 7 under the Assumptions (1,2,3,5, when X C IRd, and given T = 0,
pm//22 8L7 <es 2/2 and m 2 k2 8LK
H4 17 a++1 = cni for all 2 O. k 0.000
we have
Σ
Bl Cx 7f(
- Σ B < T
1
2 2M ml 1/4
2V
T
T1/2
TI/1
7

---

where M = Na))-- + 2x² 2mma
PikL + PTKL In(m + T):
Drkk
Remark 3. Without loss of generality, let p ( k= 0 m 01) and 7 Q(1),
have M = Oo² In(m T)) (1). Thus, our algorithm has convergence rate of Ö (1//4): Considering Ti74 Se, we have 2 E e Since our algorithm requires to compute one stochastic gradient at each iteration, and needs T iterations. Thus, our SUPER-ADAM (T = 0) has a gradient complexity of 1- = A) for finding e-stationary point.
Corollary 2. In Algorithm 1 under the above Assumptions (1,2,3,3,, when X' = Rd and given
14 (m+t))/7 0+++1 cu. all 0,
&
pmm
uLk (v 8), 8LY S m and
P
m 2 k2, we have
T
maxISIST
Hell
(2/2M T1/2
2/2M +
T
m ///41//4
where M' = -x) + 20 + 2umo² In(m + T)
Remark 4. Under the same conditions in Theorem based on the metric EIIV our SUPER-
ADAM (T 0) still has gradient complexity of (O for finding an e-stationary point.
5 Differences between Our Algorithm and Related Algorithms
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 (r = 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 weighted solution F++11 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 It at the step 9 of our algorithm. In fact, this is one of important novelties our paper. However, the STORM only uses a simple gradient descent iteration with specific monotonically decreasing adaptive learning rate.
Similarly, although our SUPER-ADAM (r algorithm uses the stochastic gradient estimator used in these Adam-type algorithms, there exist some significant differences besides using different adaptive learning rates. These Adam-type algorithms
decreasing learning rate 7)+ 3 (Please see the above B 4 and (6). while our algorithm only uses a constant learning rate y besides an adaptive learning rate. Moreover, our algorithm introduces weighted solution dr+1 at the
& (Please see Theorem 2 and uses decreasing parameter a++1 C/4 in the gradient estimator, while these Adam-type algorithms only constant parameter an E (0, 1) in their gradient estimators. Under this case, our algorithm uses these decreasing parameters μ4 and a++1 to control the noises in our gradient estimator, 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 ck estimator is gt+11 0++11 (11++1i + (1 a4+1)9t- Intuitively, with growing t, a++1 +F will become small, so the new noises added in our gradient estimator J++1 will also become less.
step 10 with decreasing parameter f4 /m+z
Numerical Experiments
In this section, we conduct some experiments to empirically evaluate our SUPER-ADAM algorithm on two deep learning tasks in 225 image classification on CIFAR-I0. CIFAR-100 and Image- Net 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-No Norm (23). (5) Adam (25), (6) STORM I| and (7) AdaBelief [40]. For our SUPER-ADAM algorithm, we consider T 1 and = respectively. Without loss of generality, in the following experiments, we only use the case 1 in Algorithm [ to generate adaptive matrix H, and let = 0.0005. All experiments are run over a machine with Intel Xeon E5-2683 CPU and 4 Nvidia Tesla P40 GPUs.
8

---

6.1 Image Classification Task
In the experiment, we conduct image classification task on CIFAR-IO, CIFAR- 100 and Image-Net datasets. We perform training over ResNet-18 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-paramettes, 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 -000, respectively. In Adam+, we use the recommended tuning parameters in [25]. In STORM, the best result is obtained when 6, k = 10 and 100 for CIFAR-IO, while w 3. A = 10 and 100 for ZIFAR-100. For our SUPER-ADAM algorithm, in both CIFAR-10 and CIFAR- datasets, we set & = 1, m 100, c 40, 7 0.001 when = and l = 1, m 100, 20, 7 0.001 when r 0. 2/3
Note that although c > R (c > m 1/2
I in our algorithm, we set at = min(ar, 0.9) at the first (m+-17477 (14 (m++)a77 ) decreases as the number of iteration increases, So Ct++1 = out (a++1 = c(t:) will be less than after the first several iterations.
several iterations. In our algorithm,
We train 34 22 on ImageNet dataset. For all the optimizers, we set the batch size as 256 and trains for 60 epochs. In Amsgrad and AdaBelief, we set learning rate as 0,001. In AdaGrad-Noor Norm. the best learning rate is 30. In Adam we set learning rate as 0.1. In STORM, the best result is obtained when h 5, w 100 and c = 10. For our algorithm, we set k 1, m 100,
c 40, 7 = 0.01 when T 1, and k = 1, m 100, c c= 4, = 0.04 when 7 = 0.
Mare
04-
1.40
094
AdCCre-fom
logetram Loo0
SYOM
logi Loos)
3.30
SCD
Train
AdsG Hoome
Test
SUPER-CAAM --0
SUPENURE/M
100
123
Number Epochs
Numbor Epochs
Number Epochs
Number Escchs
Figure 1: Experimental Results of CIFAR-10 by Different Optimizers over ResNet- 18.
200
AepCid
4.45
ArpOre
logt Trgi Looo)
logi Look)
Trai Accuracy
02
Accuracy
Jaam
S
21773 ADAM 1-12
SUPER-ADAM 2-1
-2.9
30
200
.00
122
150
88
250
30
120
220
200
Number of Epochs
Number of Epochs
Number of Eppccho
Number of Epochhs
Figure 2: Experimental Results of CIFAR- 100 by Different Optimizers over VGG-19.
055
Their Accuraccy Thip-5
05-
Tusl Aecuracy Tepoo
0.5
Trein Loz5
Test Less
SGD
0.35
0.9
Allen
0.5
Alatira Norm
002
0:25
0.55
SU7ER-4241 240
SUPOR 1-00R-200110
023
01
078
Number of tpachs
Number Epochs
Number of Epochs
Number Epocits
Figure 3: Experimental Results of Image-Net by Different Optimizers over ResNet-34.
[ and 2 show that both train and test errors and accuracy results of the CIFAR- and CIFAR-100 datasets, respectively. Our SUPER-ADAN algorithm consistently outperforms the other optimizers with a great margin, especially when we set T 1. When we set 7 = 0, our SUPER- ADAM algorithm gets the comparable performances with Adam/AmsGrad. Figure demonstrates
Figures

---

the results of ImageNet by different optimizers over ResNet-34, which shows that our algorithm outperforms the other optimizers, especially set condition number of He and the l2 norm of full gradient (i.e..) [x+)]] decrease as the number of iteration increases. From these results, we find that since the condition number of H, decreases as the number of iteration increases, so it must has an upper bound. Thus, these experimental results
in our algorithm. Figure [egure]ssoone shows that both the
further demonstrate that the above convergence results in Corollaries [ and 2 are reasonable.
6.2 Language Modeling Task
In the experiment, we conduct language mod- eling task on the Wiki-Text2 dataset. Specif- ically, we train 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
0m-11 Lne
Goct
No of Grodients
25
Conciton Number 1I
Casc L
(2922 Te]
Caae
<2
to space limitation, we provide the experimental results for the transformer in the supplementary materials. In the experiment, 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 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 0.001 in LSTM In AdaGrad-Noo learning rate 20. In AdaBelief algorithm, we set the learing rate 0.1. STORM algorithm. we set w = 50, k = 10 and e = 100. In our SUPERR-DDNN algorithm, we set k- = 1, m = 100, 40, 7 0.001 when 1, while k- I, m 100, 20, 7 = 0.01 when 0.
25
set the batch
00
50
125 190
30
50
153
Number of Epochs
Number of Epochs
Figure 4: The condition number of H, and the lo norm of full gradient (i.c..//V (xx))) for CIFAR- 10 by our SUPER-ADAM algorithm r 1 and 0, respectively. Cases and 2 are two choices of adaptive matrix H₃ given in Algorithm
algorithm, the best learning rate is 40. In Adam algorithm, we use the
3GD
Alart
Ata Jeog vd Maphrecolem
Aragre
Amagredd
730
AdaCred-Marrs
Train Loss
32
STORN
Test CC
Acatede'
SU'E LAUAN (ND
SIPER JDMM 2--
SUPER
TrEIn
SAPESAAAR (
20
20 Number Fpochs
Number of Fpochs
Number Foochs
Number Fpochs
Figure 5: Experimental Results of WikiText-2 by Different Optimizers over LSTM.
Figure 5 shows that both train and test perplexities (losses) for different optimizers. When T= 1, our SUPER- ADAM algorithm outperforms all the other optimizers. When = O, our SUPER-ADAM optimizer gets a comparable performance with the other Adam-type optimizers.
Conclusions
In the paper, we proposed novel faster and universal adaptive gradient framework (i.e., SUPER- ADAM) by introducing a universal adaptive matrix including most existing adaptive gradient forms. In partieular, 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.
10

---

References
Y. Arjevani. Carmon, J. C. Duchi, D. J. Foster, N. Srebro, and B. Woodworth. Lower bounds for non-convex stochastic optimization. arXiv preprint urXiv:1912.02535 2019.
[2] Barzilai and Borwein. Two-point step size gradient methods. IMA journal of numerical analysis, 8(1),14,-448, 1988.
[3] A. Beck and M. Teboulle. Mirror descent and nonlinear projected subgradient methods convex optimization. Operations Research Letters, 31(3):167-175. 2003.
[4] Y. Censor and A. Lent, An iterative row-action method for interval convex programming. Journal of Optimization theory and Applications, 34(3):321-353, 1981.
[5] Y. Censor and S. A. Zenios. Proximal minimization algorithm withd-functions. Journal of Optimization Theory and Applications, 73(3):451 464. 1992.
[6] J. Chen, D. Zhou, Y. Tang, Z. Yang. and Q. Gu. Closing the generalization gap of adaptive gradient methods in training deep neural networks. arXiv preprint arXiv:/80m 1808006663 2018.
[7] S. Chen, G. Niu, C. Gong. J. Li. J. Yang, and M. Sugiyama. Large-margin contrastive learning with distance polarization regularizer. In International Conference Machine Learning, pages 1673-1683, PMLR, 2021.
X. Chen, S. Liu, R. Sun, and M. Hong. On the convergence of class of adam-type algorithms for non-convex optimization. In 7th International Conference on Learning Representations, ICT. 2019, 2019.
[9] Z. Chen, Xu, E. Chen,
Yang. Sadagrad: Strongly adaptive stochastic gradient methods. In International Conference on Machine Learning, pages 913-921, PMLR, 2018.
[10] A. Cutkosky and H. Mchta. Momentum improves normalized sgd. arXiv preprint 2rXiv:2002.00300, 2020.
[11] A. Cutkosky and Orabona. Momentum- variance reduction non-convex sgd. In Advances Neural Information Processing Systems, pages 15210-15219, 2019.
[12] J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
[13] C. Fang, J. Li, Z. Lin, and T. Zhang. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems, pages 689-699, 2018.
[14] S. Ghadimi and G. Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2366 2013.
[15] S. Ghadimi, G. Lan, and H. Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematiaal Programming, 155(1-2):2773355 2016.
[16] D. Goldfarb, Ren, Bahamou. Practical quasi-newton methods training deep neural networks.
arXiv preprint wwXiv:2006.0889 2020.
[17] Goodfellow, Bengio, and A. Courville, Deep learning. MIT press, 2016.
[18] Goodfellow, Pouget-Abadie, Mirza, Xu. D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. Advances in neural information processing systems, 27, 2014.
[19] Z. Guo, Y. Xu, W. Yin, R. Jin, and Yang. stochastic moving-average estimators for non-convex optimization. arXiv preprint arXiv:2104. 11.4./48444 /4840, 2021.
[20] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and puttern recognition, pages 770-778, 2016.
[21] S. Hochreiter and J. Schmidhuher. Long short-term memory. Neural computation, 9()):1335-1780, 1997.
[22] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint 4rXiv:1412.6980.
2014.
[23] X. Li and F. Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In The 22nd International Conference Artificial Intelligence and Statistics, pages 983 992. PMLR, 2019.
11

---

[24] L. Liu, H. Jiang, P. He, W. Chen, X. Liu, J. Gao. and J. Han. On the variance of the adaptive learning rate and beyond. arXiv preprint arXiv: 1908.0326.. 2019.
[25] M. Liu, W. Zhang, F. Orabona, and T. Yang. Adam+: A stochastic method with adaptive variance reduction. arXiv preprint arXiv:2011.11885. 2020.
[26] I. Loshchilov and F. Hutte. Decoupled weight decay regularization. In International Conference on Learning Reprexentations, 2018.
[27] L. Luo, Y. Xiong, Y. Liu, and X. Sun. Adaptive gradient methods with dynamic bound of learning rate. arXiv preprint arXiv:1902.0e 09844. 2019.
[28] M. C. Mukkamala and M. Hein. Variants of rmsprop and adagrad with logarithmic regret bounds. In International Conference on Machine Learning, pages 2545-2553. PMLR, 2017.
[29] S. J. Reddi, S. Kale, and S. Kumar. On the convergence of adam and beyond. In International Conference Learning Representations, 2018.
[30] K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:/409. 1556, 2014.
[31] M. Staib, S. Reddi, S. Kale, S. Kumar, and S. Sra. Escaping saddle points with adaptive gradient methods. In International Conference Machine Learning, pages 5956-5965. PMLR, 2019.
[32] Q. Tran-Dinh, N. H. Pham, D. T. Phan, and L. M. Nguyen. Hybrid stochastic gradient descent algorithms for stochastic nonconvex optimization. arXiv preprint arXiv:/905.059220, 2019.
[33] X. Wang. S. Ma. D. Goldfarb, and W. Liu. Stochastic quasi-newton methods for nonconvex stochastic optimization. SIAM Journal Optimization, 27(2):22--56,, 2017.
[34] R. Ward, X. Wu, and L. Bottou. Adagrad stepsizes: Sharp convergence nonconvex landscapes. In International Conference on Machine Learning, pages 6677-6686. PMLR, 2019.
[35] A. C. Wilson, R. Roelofs, M. Stern, N. Srebro, and B. Recht. The marginal value of adaptive gradient methods in machine learning. In Advances in neural information processing systems, pages 4148-4158, 2017.
[36] Zaheer, S. Reddi, Sachan, Kale, and S. Kumar. Adaptive methods nonconvex optimization. In Advances neural information processing systems, pages 9793-9803, 2018.
[37] M. D. Zeiler. Adadelta: adaptive learning rate method. arXiv preprint a 2012.
[38] Q Zhang, F. Huang, C. Deng, and H. Huang. Faster stochastic quasi-newton methods. IEEE Transactions on Neural Networks and Learning Systems, 2021.
[39] D. Zhou, J. Chen, Y. Cao, Y. Tang, Z. Yang, and Q Gu. On the convergence of adaptive gradient methods nonconvex optimization. arXiv preprint I 1801.18887777777 05671, 2018
[40] J. Zhuang. T. Tang, Y. Ding, C. Tatikonda, N. Dvorek, X. Papademetris, and J. Duncan. Adabelief optimizer: Adapting stepsizes by the belief in observed gradients. Advances in Neural Information Processing Systems, 33, 2020.
12


Reviews:
[{"review_id": "jztbKscUKGY", "reviewer": "Reviewer_Tq1x", "summary": "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. ", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "Some comments:\n \n1.  I recommend the authors to proofread the paper again. \nSome typos: \n1) In the line 9: “our framework can flexibly integrates …” should be “our framework can flexibly integrate…”\n2) In the line 115: “proposed to adapt the stepsize” should be “proposed to adopt the stepsize”\n3) At the step 13 of super-adam algorithm, there is a symbol error: “[g_t - ” should be “[ g_t + ”.\nIn the line 436, the gradient estimator g_{t+1} is right. So I think that this symbol error at the step 13 of algorithm is a typo. \n4) In the line 145, “g_t - \\nabla f(x_{t+1};\\xi_{t+1})” should be “g_t - \\nabla f(x_t;\\xi_{t+1})”.\n \n2.  I also recommend the authors to detail the adaptive learning rates used in the super-adam algorithm in the experiment. \n\n----After Rebuttal----\nAs the author's rebuttal well addressed my main concerns, I increased my score to 8 to support this paper. Thanks.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "TPo2KQL_ffA", "reviewer": "Reviewer_eztp", "summary": "This paper proposes a universal framework for adaptive gradients methods by introducing a universal adaptive matrix. It also offers the theoretical convergence analysis for this optimizing method, and proves that this method can achieve the complexity of $O(\\epsilon^{-3})$ for finding an $\\epsilon$-stationary point. ", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "The main concern is about the practicability of SUPER-Adam in the Case 2 in Algorithm 1. It is known that the number of parameters of modern DNNs is typically more than 10 million, such as the number of parameters of VGG16 is ~134 million and that of ResNet18 is 33 million. Therefore, $H_t$ in SUPER-Adam in Case 2 will be at least 8 order of magnitude larger than that in $H_t$ in SUPER-Adam in Case 1 that is commonly used, so we need to scale the learning rate $\\eta_t$ by a factor of $>10$ million to maintain the comparable convergence rate with Adam. This overlarge factor may be impractical. Actually, from Section 6.1, we know the authors also did not set $\\eta$ so large.\n\nWhen $M_t \\rightarrow 0$ , SUPER-Adam in the Case 1 cannot ensure $\\rho H_t^{-1} \\rightarrow I_d$ in Eq. (17), and then $\\Vert\\nabla f(x_t) \\Vert \\rightarrow 0$ will not hold. In this case, Theorem 1 and Theorem 2 might be somewhat meaningless. \n\n\nTheorem 1 and Theorem 2 and their proofs are obviously followed the paper that proposed STORM with a little change, but the authors did not report this close relation. Therefore, the bright spot of the convergence analysis is discounted\n\nFrom the 1st and 5th subfigure of figure 2, we know the learning rate for SUPER-Adam decays by a factor (maybe 10) at the 70th and 100th epoch, respectively, which is not described in experimental settings. Moreover, this learning rate decay strategy seems to be not used for other optimizing methods except AdaBlief. Hence, the comparison may be unfair. Additionally, it is known that SGD-type methods commonly perform better for image classification than adaptive gradient methods, so I would like to see SGD will be also compared to SUPER-Adam.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The author need to  address the problesm above. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 hours"}, "extra_text": {}}, {"review_id": "PlHtwKlRNJF", "reviewer": "Reviewer_v7co", "summary": "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. \n \n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "I have the following major comments/questions:\n\n1) In the theoretical analysis, the parameter $\\rho$ is very important. Could you summarize the impact of this parameter on the convergence analysis? E.g., how it affects the convergence properties of the proposed algorithm?\n\n2) In the super-adam algorithm, we can choose flexible adaptive learning rates. Could you give us a guide on how to choose a good adaptive learning rate in the experiment? \n \nMinor comments:\n\n1) In Abstract, the line 9: “…can flexibly integrates…”  should  be  “… can flexibly integrate…”;\n \n2) In the convergence analysis, the gradient estimator $g_{t+1}$ is right (in the line 436).  At step 13 of the super-adam algorithm,  there exists a symbol error:  $g_t -$ should be  $g_t +$.\n \n3) In the experiment, do you use the same adaptive learning rates in super-adam ($\\tau=1$) and super-adam ($\\tau=0$) ? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "P2Mz7GfAA3B", "reviewer": "Reviewer_PnCw", "summary": "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.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "The unified framework is new to me, but the only algorithmic innovation is line 12 in Algorithm 1. The choices of $\\tau=0$ or $\\tau=1$ are nothing but hyper-parameters which make the algorithm use the standard gradient estimator or the STORM estimator. I have the following concerns.\n\n1. Convergence Measure. The authors claim that the proposed measure in (15) is tighter than existing measures. I agree that it is the case when we are facing unconstrained nonconvex optimization with non-coordinate-wise adaptive learning rate. What about constrained case and adaptive case in which the preconditioning matrix is not identity? I do not think it is still tighter. For example, the gradient mapping may not be a lower bound for the measure in (15). In unconstrained adaptive learning rate case, $\\rho H_t^{-1}$ should be very small when $t$ gets large, so it is also not an upper bound of the gradient norm. For fair comparison, is it possible to prove the convergence measure in the usual sense (i.e., gradient mapping in constrained case and gradient norm in unconstrained adaptive case)? \n\n2. As I mentioned, line 12 is the only difference compared with existing methods. Why line 12 is important to recover the convergence rate of STORM? There is no doubt that in unconstrained case, without line 12 and with $\\tau=1$, the algorithm is the same as STORM and hence can recover $O(\\epsilon^{-3})$ rate. Also I would like to ask the same question in terms of SGD.\n\n3. After inspecting Lemma 2 and Lemma 3 and Theorem 3 in this manuscript, I think the proofs are almost adapted from STORM paper, except for plugging in the Lemma 1 in [10] and the line 11 of Algorithm 1. Please clarify what are the technical innovations when compared with Lemma 1, Lemma 2 and Theorem 1 in the STORM paper. \n\nExperiments:\nFor SUPER-ADAM with $\\tau=1$, since the algorithm need to calculate two stochastic gradients at one iteration, so the running time might be slow. Is it possible to report the running time results?\n\nFrom my point of view, the theoretical contribution is minimal for unconstrained problems, since SGD and STORM are already optimal with different assumptions, and SUPER-ADAM's algorithm design is very similar to them except for the line 12. The convergence measure when using coordinate-wise adaptive learning rate for unconstrained problems is not comparable with the usual gradient norm. \n\nSUPER-ADAM might be interesting in constrained case. However, the convergence measure is not comparable with gradient mapping, and there are no empirical studies for constrained problems in this submission. \n\nDue to these reasons, it is hard to say that the algorithm is universal.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: During the discussion phase, the paper has received intensive discussion between the authors and the reviewers about the merits and the concerns. Two reviewers have a strong favor of accepting this paper given that the paper presents a new analysis of Adam method for constrained non-convex optimization and also an improved variant of Adam by using recursive variance reduction methods with an optimal complexity. The major concerns are from the used convergence measure that is different from the standard convergence measure, and the authors' argument about its implication for the convergence of the standard  measure in terms of (proximal) gradient norm. The AC agrees that the presented results are interesting and the analysis of the Adam-style methods for constrained non-convex optimization is novel. The concern about the inconsistency between the presented convergence measure and the standard convergence measure is understandable given that the paper considers the constrained non-convex optimization. However, the authors should weaken their argument about its implication for the convergence of the gradient  norm or add more evidence such as empirical results presented in the rebuttal for further supporting their claim. The AC believes the concern should be addressable, and hence recommends an acceptance.  


Decision: Accept (Poster)