Adam$^+$: A Stochastic Method with Adaptive Variance Reduction
Authors: Mingrui Liu
Wei Zhang
Francesco Orabona
Tianbao Yang
Venue:  (2021)
Keywords: Adaptive Gradient Methods
Deep Learning
Nonconvex Optimization

Abstract: Adam is a widely used stochastic optimization method for deep learning applications. While practitioners prefer Adam because it requires less parameter tuning, its use is problematic from a theoretical point of view since it may not converge.  Variants of Adam have been proposed with provable convergence guarantee, but they tend not be competitive with Adam on the practical performance. In this paper, we propose a new method named Adam$^+$ (pronounced as Adam-plus). Adam$^+$ retains some of the key components of Adam but it also has several noticeable differences: (i) it does not maintain the moving average of second moment estimate but instead computes the moving average of first moment estimate at extrapolated points; (ii) its adaptive step size is formed not by dividing the square root of second moment estimate but instead by dividing the root of the norm of first moment estimate. As a result,  Adam$^+$ requires few parameter tuning, as Adam, but it enjoys a provable convergence guarantee. Our analysis further shows that Adam$^+$ enjoys adaptive variance reduction, i.e., the variance of the stochastic gradient estimator reduces as the algorithm converges, hence enjoying an adaptive convergence. We also propose a more general variant of Adam$^+$ with different adaptive step sizes and establish their fast convergence rate. Our empirical studies on various deep learning tasks, including image classification, language modeling, and automatic speech recognition, demonstrate that Adam$^+$ significantly outperforms Adam and achieves comparable performance with best-tuned SGD and momentum SGD.

Under review as a conference paper at ICLR 2021
ADAM A STOCHASTIC METHOD WITH ADAPTIVE VARIANCE REDUCTION
Anonymous authors Paper under double-blind review
ABSTRACT
Adam is widely used stochastic optimization method for deep learning applica- tions. While practitioners prefer Adam because it requires less parameter tuning, its use is problematic from theoretical point of view since it may not converge. Variants of Adam have been proposed with provable convergence guarantee, but they tend not be competitive with Adam on the practical performance. In this paper, we propose new method named Adam (pronounced as Adam-plus). Adam+ retains some of the key components of Adam but also has several no- ticeable differences: (i) it does not maintain the moving average of second mo- ment estimate but instead computes the moving average of first moment estimate at extrapolated data points; (ii) its adaptive step size is formed not by dividing the square root of second moment estimate but instead by dividing the root the norm of first moment estimate. As a result, Adam requires few parameter tuning, as Adam, but it enjoys a provable convergence guarantee. Our analysis further shows that Adam enjoys adaptive variance reduction, i.e., the variance of the stochastic gradient estimator reduces as the algorithm converges, hence enjoy- ing an adaptive convergence. We also propose a more general variant of Adam with different adaptive step sizes and establish their fast convergence rate. Our empirical studies on various deep learning tasks, including image classification, language modeling, and automatic speech recognition, demonstrate that Adam* significantly outperforms Adam and achieves comparable performance with best- tuned SGD and momentum SGD.
INTRODUCTION
Adaptive gradient methods (Duchi et al., 2011; McMahan & Streeter, 2010; Ticleman & Hinton, 2012: Kingma & Ba, 2014; Reddi et al., 2019)
of the most important variants of Stochastic Gradient Descent (SGD) in modern machine learning applications. Contrary to SGD, adaptive gra- dient methods typically require little parameter tuning still retaining the computational efficiency of SGD. One of the most used adaptive methods is Adam (Kingma & Ba, 2014), which is considered by practitioners
the de-facto default optimizer for deep learning frameworks. Adam computes the update for every dimension of the model parameter through moment estimation, i.e., the estimates of the first and second moments of the gradients. The estimates for first and second moments are updated using exponential moving averages with two different control parameters. These moving averages are the key difference between Adam and previous adaptive gradient methods, such as Adagrad (Duchi et al., 2011).
Although Adam exhibits great empirical performance, there still remain many mysteries about its convergence. First, it has been shown that Adam may not converge for some objective func- tions (Reddi et al., 2019; Chen et al., 2018b). Second, moving average brings from theoretical point of view, especially its effect the convergence rate. Third, it has been empirically observed that adaptive gradient methods can have worse generaliza- tion performance than its non-adaptive counterpart (e.g., SGD) on various deep learning tasks due to the coordinate-wi wise learning rates (Wilson et al., 2017).
unclear what is the benefit that the
The above issues motivate
design new algorithm which achieves the best of both worlds, i.e. provable convergence with benefits from the moving average and enjoying good generalization performance in deep learning. Specifically, we focus on the following optimization problem:
min F(w). wERd

---

Under review as a conference paper at ICLR 2021
Table I: Summary of different algorithms with different assumptions and complexity results for find- ing an e-stationary point. "Individual Smooth" means assuming that F(w) = E (w: {)] and that every component function f(w; E) is L-smooth. "Hessian Lipschitz" means that | - |x y holds for y.y and LH 2 O. "Type I" means that the complexity depends on E - gg: where g1,T, stands for the i-th row of the matrix (g),.... gr| with g being the stochastic gradient at t-th iteration and T being the number of iterations. "Type II" means that complexity depends on E [| II], where 2, is the variance-reduced gradient estimator I-th
V F
iteration.
Alpaciiaut
Indiviaual Smooth
Hessinn Lipuctttz
Worse Compleury better than
Dana dependeet Complessy
Gimeralizal Adain (C5mm ct 30156)
PAdton (Chen al., 2018.)
Sugewise Adagnad (Chen
2019)
No
No
Type I
SGD with
Stepsine (1. Orahona, 20199
oltagnd--omm (Want ct al. 2019)
SPIDUR
2018)
STORM (Curlosky Orahonn,
SNVRG (2ou et al. 2018)
No
Yes
N/A
Prex Prox-SAR SAR All (Pham al. 2000)
SCD
2019)
Normallzed momentum SGD
No Yes
N/A
(Cunkosky Mehra, 2020)
Alam"
Type II
where we only have access to stochastic gradients of F. Note that F could possibly be nonconvex in w. Due to the non-convexity, our goal is to design a stochastic first-order algorithm to find the e-stationary point, i.e., finding such that E [[|V [[//F())]] II] S with low iteration complexity.
Our key contribution is the design and analysis of a new stochastic method named Adam+. Adam+ retains some of the key components of Adam but it also has several noticeable differences: (i) it does not maintain the moving average of second moment estimate but instcad computes the moving average of first moment estimate extrapolated points; (ii) its adaptive step size is formed not by dividing the square root of coordinate-wise second moment estimate but instead by dividing the root of the norm of first moment estimate. These features allow us to establish the adaptive convergence of Adam+. Different from existing adaptive methods where the adaptive convergence
depends on the growth rate of stochastic gradients (Duchi et al., 2011: McMahan & Streeter, 2010;
Kingma & Ba, 2014; Luo et al., 2019; Reddi et al., 2019; Chen et al., 201 8a;;; Ward et al., 2019;
Li & Orabona, 2019; Chen et al., 2019), our adaptive convergence due the adaptive variance reduction property of our first order moment estimate. In existing literature, the variance reduction usually achieved by large mini-batch (Goyal et al., 2017) or recursive variance reduction (Fang et al., 2018; Zhou et al., 2018; Pham et al., 2020; Cutkosky & Orabona, 2019). In contrast, we do not necessarily require large minibatch or computing stochastic gradients at two points per-iteration to achieve the variance reduction. In addition, we also establish a fast rate that matches the state-of-the- art complexity under the same conditions of a variant of Adam Table provides an overview of our results and summary of existing results. We refer readers to Section F for comprehensive survey of other related work. We further corroborate our theoretical results with an extensive empirical study on various deep learning tasks.
Our contributions are summarized below.
We propose a new algorithm with adaptive step size, namely Adam+, for general noncon- vex optimization. We show that it enjoys a new type of data-dependent adaptive conver- gence that depends on the variance reduction property of first moment estimate. Notably, this data-dependent complexity does not require the presence of sparsity stochastic gra- dients to guarantee fast convergence as in previous works (Duchi et al., 201 I; Kingma & Ba, 2014; Reddi et al., 2019; Chen et al., 2019; 2018a). To the best of our knowledge, this is the first work establishing such new type of data-dependent complexity.
We show that a general variant of our algorithm can achieve 3 worst-case complex- ity, which matches the otate-of-the-art complexity guarantee under the Hessian Lipschitz assumption (Cutkosky& & Mehta, 2020).
We demonstrate the effectiveness of our algorithms on image classification, language mod- eling, and automatic speech recognition. Our empirical results show that our proposed algorithm consistently outperforms Adam on all tasks, and it achieves comparable perfor- mance with the best-tuned SGD and momentum SGD.
2

---

Under review as a conference paper at ICLR 2021
Algorithm Adam :: Good default settings for the tested machine learning problems are a
0.1,a= 1, 3 = 0.1, = 10
1: Require:
2 1: stepsize parameters
2: Require: 3 E (0, 1): Exponential decay rates for the moment estimate
3: Require: gr( (:)::: unbiased stochastic gradient with parameters at iteration /
4: Require: Wo: Initial parameter vector
5: Zo 9o(wo)
6: for t = -....,,
T' do
7: Set = max(liz, (e))
a13"
8:
Wi+1
1/.22
9: W6+1 (1 1/3)w, 1/8- W141
10: ZІ-1 (1 Byzz+ B9c+1 (W++1)
11:
end for
2 ALGORITHM AND THEORETICAL ANALYSIS
In this section, we introduce our algorithm Adam+ (presented in Algorithm 1) and establish its convergence guarantees. Adam+ resembles Adam in several aspects but also has noticeable differ- ences. Similar to Adam, Adam also maintains an exponential moving average of first moment (i.e., stochastic gradient), which denoted by Z,, and uses it for updating the solution in line 8. However, the difference is that the stochastic gradient is evaluated on an extrapolated data point We+1, which an extrapolation of two previous updates w, and Wt+1- Similar Adam, Adam* also uses an adaptive step size that is proportional to 1/ |l 1/2 Nonetheless, the difference lies its adaptive step size is directly computed from the square root of the norm of first moment estimate 2,. In contrast, Adam uses an adaptive step size that proportional to V/VV,, where V, an exponential moving average of second moment estimate. These two key components of Adam*, i.e., extrap- olation and adaptive step size from the root norm of the first moment estimate, make it enjoy two noticeable benefits: variance reduction of first moment estimate and adaptive convergence. We shall explain these two benefits later.
Before moving to the theoretical analysis, we would like to make some remarks. First, it is worth mentioning that the moving average estimate with extrapolation is inspired by the literature of stochastic compositional optimization (Wang et al., 2017). Wang al. (2017) showed that the ex- trapolation helps balancing the noise in the gradients, reducing the bias in the estimates and giving a faster convergence rate. Here, our focus and analysis techniques are quite different. fact, Wang et al. (2017) focuses on the compositional optimization while consider general nonconvex op- timization setting. Moreover, the analysis in (Wang et al., 2017) mainly deals with the error of the gradient estimator caused by the compositional nature of the problem, while our analysis focuses on carefully designing adaptive normalization to obtain an adaptive and fast convergence rates. A similar extrapolation scheme has been also employed in the algorithm NIGT by Cutkosky & Mehta (2020). In later sections, we will also provide more general variant of Adam + which subsumes NIGT special case.
Another important remark is that the update of Adam is very different from the famous Nesterov's momentum method. Nesterov's momentum method, the update of wi+1 uses the stochastic gradi- ent at an extrapolated point Wt-1 = Wi+1 - (reii--(wwapp 7(W++1 -w,) with momentum parameter (0, 1). In contrast, in A the update of W using the moving average estimate an extrapolated point W W++1 + (1/ 1) (W++11 w.). Finally, A does not employ coordinate- wise learning rates as in Adam, and hence is expected to have better generalization performance ac- cording to Wilson al. (2017).
2.1 ADAPTIVE VARIANCE REDUCTION AND ADAPTIVE CONVERGENCE
In this subsection, we analyze A by showing its variance reduction property and adaptive convergence. To this end, we make the following assumptions.
Assumption 1. There exists positive constants L, A, Lu,, a and initial solution wo such that
(i) F is L-smooth, i.e. [|F((x) FF()) & L x|x-~x yll, Vx.y Rd..
3

---

Under review as a conference paper at ICLR 2021
(ii) For Vx R we have access to a first-order stochastic oracle time t ge such that E [x((x)] = VF(x), (x) VF(X)]I o².
(iii) V is a -mo-thotth mupping, i.e, [[) (2F(y)]I Lu||x yll, TR..
(iv) F(oo) - F. _ A < oo, where F. = inf weRd F(w).
Remark: Assumption (i) and (ii), (iv) are standard assumptions made in literature of stochastic non-convex optimization (Ghadimi & Lan, 2013). Assumption (iii) is the assumption that deviates from typical analysis of stochastic methods. We leverage this assumption to explore the benefit of moving average, extrapolation and adaptive normalization. It is also used in some previous works for establishing fast rate of stochastic first-order methods for nonconvex optimization (Fang et al., 2019; Cutkosky & Mehta, 2020) and this assumption essential get fast rate due the hardness result in (A (Arjevani et al., 2019). is also the key assumption for finding a local minimum in previous works (Carmon al., 2018; Agarwal et al., 2017; Jin et al., 2017).
We might also assume that the stochastic gradient estimator in Algorithm satisfies the following variance property.
Assumption 2. Assume that Billgo(wo) VF F S o f 2 1.
o and Blllg( VF((s) <
When Go (resp. 9t) is implemented by a mini-batch stochastic gradient with mini-hatch size S, then o (resp. o can be set as / by Assumption (ii). We differentiate the initial variance and intermediate variance because they contribute differently to the convergence.
Remark:
We first introduce lemma to characterize the variance of the moving average gradient estimator z..
Lemma 1. Suppose Assumption I and Assumption 2 hold and 1. Then, there exists a sequence of random variables de satisfying || V F((w))ll
< for VI 2 0,
8
CL
Wx+1 w
E
2
1
E
[0
+2,8
+
E
2
B3
8
1
E
+2880 [
mm
+
E
[CT A
gda-3 $112
2
where C 1944.
Remark: Note that 6, is upper bound of ||z, VF(w:))l the above lemma can be used to illustrate the variance reduction effect for the gradient estimator 2,. To this end, we can bound ||z,|| 25? + 2 small enough a. Hence, we have ES S (1 (1- (1-B//4]3 3/4)) + 2.3 + (F small constant c. As the algorithm converges with E|]| ((w)) and / decreases to zero, the variance of 2, will also decrease. Indeed, the above recursion of z, 's variance resembles that of the recursive variance reduced gradient estimators (c.g., SPIDER (Fang et al., 2018), STORM (Cutkosky & Orabona, 2019)). The benefit of using Adam is that we do not need to compute stochastic gradient twice at each iteration.
then the term CI22 3 can be canceled with -8/482 with
with a
We can now state our convergence rates for Algorithm
Theorem 1. Suppose Assumption and Assumption hold. Suppose [[VF(w)] S G for any
W E Rd. By choosing the parameters such that a S 36CL a S 41, and co = 8", we have
T E VF t=1
GE
El=
A
1803
Σ
+
+ 30,00
(1)
T
aT
ST
In addition, suppose the initial batch size is To and the intermediate batch size is m, and choose - with 6 < 1, we have
T E BIFF((:
GT
[
1802
30o²
(2)
T
aT
71-0T
m7
4

---

Under review as a conference paper at ICLR 2021
Theorem 2. Suppose Assumption and Assumption 2 hold. By choosing parameters such that 640g 2. & 1/120, a 1, cu 0, 1/T with 2/3 then takes T O (c~4.5) number of iterations to ensure that
E [VF((:)))
S Se
663/2
Remarks:
From Theorem we can observe that the convergence rate of Adam crucially depends on the growth rate of E Σ | which gives data-dependent adaptive complexity. If
E Σ [zel|
T with 1, then the algorithm converges. Smaller implies faster
convergence. Our goal is to ensure that + Ei= Bl/ _ Choosing = 1 - a, m = (1) and To T O and we end up with T = 0 - complexity.
Theorem 2 shows that in the ergodic sense, the Algorithm Adam always converges, and the variance gets smaller when the number of iteration gets larger. Theorem 2 rules out the case that the magnitude of z; converges to constant and the bound (2) in Theorem becomes vacuous.
To compare with Adam-style algorithms (e.g., Adam, AdaGrad), these algorithms' vergence depend on the growth rate of stochastic gradient, i.e., Σ /l/TT, where gI:T, = [ . .... denotes the i-th coordinate of all historical stochastic gradients. Hence, the data determines the growth rate of stochastic gradient. If the stochastic gradi- ents are not sparse, then its growth rate may not be slow and these Adam-style algorithms may suffer from slow convergence. In contrast, for Adam the convergence can be ac- celerated by the variance reduction property. Note that have E E ||2,1] /T s
E (6. + [VF(W)))) /T. Hence, Adam 's convergence depends on the variance
reduction property of 2e.
2.2 A GENERAL VARIANT OF ADAM:: FAST CONVERGENCE WITH LARGE MINI-BATCH
Next, we introduce a more general variant of Adam + by making a simple change. In particu- lar, we keep all steps the same in Algorithm I except the adaptive step size is set as We (. where p [1/2, 1) is parameter. We refer to this general variant of Adam as power normalized Adam (Nadam+). This generalization allows us to compare with some ex- isting methods and to establish fast convergence rate. First, we notice that when setting p == 1 and 5/4 and /3 1/T4/7 Nadam is almost the as the stochastic method NIGT (Cutkosky & Mehta, 2020) with only some minor differences. However, we observed that normalizing by || leads slow convergence practice, so we are instead interested in p < Below, we will show that N with < 1 can achieve fast rate of 1/e3.5, which is the same as NIGT.
Theorem 3. Under the same assumption as in Theorem further assume of o2 o²/To and o o² e//. By using the step size me-
max [uxx(1xx]]3/8... 3/8,), in Algorithm I with C - 1/14, 6o 2/4/3
a/31/3
order to have E. [|| (ww))]] S e for randomly selected solution w from (W1,..., WT), it suf- fice to set = 12)
2), the initial batch size To 1/3 = ((c-1/2), the intermediate batch size as m 1/53 O(e 3/2), which ends up with the total complexity O(e 3.5).
Remark: Note that the above theorem establishes the fast convergence rate for Nadam with p 2/3. Indeed, we can also establish fast rate of Adam (where p 1/2) in the order of 0 with details provided in the Appendix E.
3 EXPERIMENTS
In this section, we conduct empirical studies to verify the effectiveness of the proposed algorithm on three different tasks: image classification CIFAR10 and CIFAR 100 dataset (Krizhevsky al.,
5

---

Under review as a conference paper at ICLR 2021
ResNet18 training on CIFAR10
ResNet18 training on CIFAR10
0.95
Training Accuracy
0.98
Test Accuracy
0.9
0.96
0.85
SGD
SGD
0.94
Momentum SGD Adagrad
Momentum SGD
Adegrad
0.92
Adam
0.8
Adam
NIGT
NIGT
Adam+
0.75
100
200
400
100
200
300
400
Number of Epochs
Number of Epochs
Figure 1: Comparison of optimization methods for ResNet18 Training on CIFARIO.
2009), language modeling on Wiki-Text2 dataset (Merity, 2016) and automatic speech recognition on SWB-300 dataset (Saon et al., 2017). We choose tasks from different domains demonstrate the applicability for the real-world deep learning tasks in a broad sense. The detailed description is presented in Table 2. We compare our algorithm Adam with SGD, momentum SGD, Adagrad, NIGT and Adam. We choose the same random initialization for each algorithm, and run a fixed number of epochs for every task. For Adam choose the default setting 31 0.9 and B2 0.999 as in the original Adam paper.
Table 2: Summary of setups in the experiments.
Domain
Task
Architecture ResNet18 VGG19
Dataset
Computer Vision
Image Classification
CIFARIO
Computer Vision
Image Classification
CIFARION
Natural Language Processing
Language Modeling
Two-layer LSTM
Wiki-Text2
Automatic Speech Recognition
Speech Recognition
Six-layer BiLSTM
SWB-300
3.1 IMAGE CLASSIHICATION
CIFARIO and CIFAR100 In the first experiment, we consider training ResNet18 (He et al., 2016) and VGG19 (Simonyan & Zisserman, 2014) to do image classification task on CIFARIO and CI- FARI00 dataset respectively. For every optimizer, we use batch size 128 and run 350 epochs. For SGD and momentum SGD, we set the initial learning rate to be 0.1 for the first 150 epochs, and the learning rate is decreased by factor of 10 for every 100 epochs. For Adagrad and Adam, the initial learning rate is tuned from (0.1, 0.01, 0.001} and we choose the one with the best performance. The best initial learning rates for Adagrad and Adam are 0.01 and 0.001 respectively. For NIGT, we tune the their momentum parameter from {0.01, 0.1, 0.9) (the best momentum parameter we found is 0.9) and the learning rate is chosen the same as in SGD. For Adam+, the learning rate is set ac- cording to Algorithm 1, in which we choose = 0.1 and the value of a is the same as the learning rate used in SGD. We report training and test accuracy versus the number of epochs in Figure I for CIFAR10 10 and Figure for CIFAR 100. We observe that our algorithm consistently outperforms all other algorithms
both CIFAR10 10 and CIFAR100, in terms of both training and testing accuracy. Notably, we have some interesting observations for the training of VGG19 on CIFAR 100. First, both Adam and NIGT significantly outperform SGD, momentum SGD, Adagrad and Adam. Second, Adam+ + achieves almost the same final accuracy as NIGT, and Adam+ converges much faster in the early stage of the training.
3.2 LANGUAGE MODELING
Wiki-text2 In the second experiment, we consider the language modeling task on WikiText-2 dataset. We use a 2-layer LSTM (Hochreiter & Schmidhuber, 1997). The size of word embeddings is 650 and the number of hidden units per layer is 650. We run every algorithm for 40 epochs, with batch size 20 and dropout ratio 0.5. For SGD and momentum SGD, we tune the initial learning rate from 10.1, 0.2, 0.5, 5, 10, 20) and decrease the learning rate by factor of when the validation error

---

Under review as a conference paper at ICLR 2021
VGG19 training on CIFAR100
VGG19 training on CIFAR100
0.7
Training Accuracy
Test Accuracy
0.95
0.6
SGD
0.5
SGD
0.9
Momentum SGD Adagrad
Adegrad
Momentum SGD
Adam
0.4
Adam
NIGT
NIGT
0.85
0.3
100
200
400
200
300
400
Number of Epochs
Number of Epochs
Figure Comparison of optimization methods for VGG19 training on CIFARIO0.
LSTM Training on Wikitext-2
LSTM Training on Wikitext-2
Training Perplexity
Momentum SGD
300
Momantum SGD
150
Adagrad
Test Perplexity
Adagrad
NIGT
Adam
250
NIGT
Adam
Adam+
Adam+
100
200
150-
50
100
50
20
Number of Epochs
Number of Epochs
Figure 3: Comparison of optimization methods for two-layers LSTM training on WikiText-2.
saturates, For Adagrad and Adam, we tune the initial learning rate from {0.001, 0.1, We report the best performance for these methods across the range of learning rate. The best initial learning rates for Adagrad and Adam are 0.01 and 0.001 respectively. For NIGT, we tune the initial value of learning rate from the same range as in SGD, and tune the momentum parameter B from (0.01, 0. 0.9), and the best parameter choice is 3 = 0.9. The learning rate and 3 are both decreased by a factor of when the validation error saturates. For Adam+, we follow the same tuning strategy as NIGT.
We report both training and test perplexity versus the number of epochs in Figure 3. From the Fig- ure, we have the following observations: First, in terms of training perplexity, algorithm achieves comparable performance with SGD and momentum SGD and outperforms Adagrad and NIGT, and it is worse than Adam. Second, in terms of test perplexity, grad, NIGT and momentum SGD, and it is comparable to SGD. An interesting observation that Adam does not generalize well even if it has fast convergence in terms of training error, which is consistent with the observations in (Wilson et al., 2017).
algorithm outperforms Adam, Ada-
3.3 AUTOMATIC SPEECH RECOGNITION
SWB-300 In the third experiment, we consider the automatic speech recognition task on SWB-300 dataset (Saon et al., 2017). SWB-300 contains roughly 300 hours of training data of over 4 million samples (30GB) and roughly 6 hours of held-out data of over 0.08 million samples (0.6GB). Each training sample is a fusion of FMLLR (40-dim), i-Vector (100-dim), and logmel with its delta and double delta. The acoustic model is a long short-term memory (LSTTM) model with bi-directional layers. Each layer contains 1,024 cells (512 cells in each direction). On top of the LSTM layers, there is a linear projection layer with 256 hidden units, followed by a softmax output layer with 32,000 (i.e., 32,000 classes) units corresponding to context-dependent HMM states. The LSTM is unrolled with 21 frames and trained with non-overlapping feature uub-sequences of that length. This model contains over 43 million parameters and is about 165MB large. The training takes about 20 hours on 1 V100 GPU. To compare, we adopt the well-tuned Momentum SGD strategy as described in (Zhang et al., 2019) for this task the baseline: batch size is 256, learning rate is
7

---

Under review as a conference paper at ICLR 2021
LSTM Training on SWB-300
LSTM Training on SWB-300
Momentum SGD
3.5
Momentum SGD
Adagrad
Adagrad
Training Loss
NIGT
Test Loss
NIGT
Adama
Adam
2.5
2.5
2-
1.5
1.5
10
Number of Epochs
Number of Epochs
Figure 4: Comparison of optimization methods for six-layers LSTM training on SWB-300.
10 <10
ResNet18 training on
12 10 VVG119 training on CIFAR100
10
2-
2-
Adam+
2
10 Number of Itenations (1)
8
12
14
5 Number Ierations (4)
10
15
x10
Figure 5: The growth of quantity Σ E |z, in Adam +
0.1 for the first 10 epochs and then annealed by V.5 for another 10 epochs, with momentum 0.9. We grid search the learning rate of Adam and Adagrad from {0.1, 0.01, 0.001 , and report the best configuration
have found (Adam with learning rate 0.001 and Adagrad with learning rate 0.01). For NIGT, we also follow the same learning rate setup (including annealing) as in Momentum SGD baseline. In addition, we fine tuned / in NIGT by exploring 3 in {0.01, 0.1, 0.9} and reported the best configuration (3=0.9). For Adam+, we follow the same learning rate and annealing strategy as in the Momentum SGD and tuned B in the same way in NGIT, reporting the best configuration (3=0.01). From Figure 4, Adam achieves the indistinguishable training loss and held-out loss w.r.t. well-tuned Momentum SGD baseline and significantly outperforms the other optimizers.
3.4 GROWTH RATE OF E ||z||]
In this subsection, we consider the growth rate Ei= gence rate as shown in Theorem 1. We report the results of both ResNet18 training CIFAR10 dataset and VGG19 training on CIFAR 100 dataset. From Figure 5, we can observe that it quickly reaches plateau and then grows very slow rate with respect the number of iterations. This phenomenon verifies the variance reduction effect and also explains the reason why Adam enjoys fast convergence speed in practice.
||z |]. since they crucially affect the conver-
4 CONCLUSION
In this paper, design new algorithm named Adam to train deep neural networks efficiently. Different from Adam, Adam updates the solution using moving average of stochastic gradients calculated at the extrapolated points and adaptive normalization on only first-order statistics of stochastic gradients. We establish data-dependent adaptive complexity results for Adam from the perspective of adaptive variance reduction, and also show that variant of A achieves state-of-the-art complexity. Extensive empirical studies on several tasks verify the effectiveness of the proposed algorithm. We also empirically show that the slow growth rate of new gradient estimator, providing the reason why Adam enjoys fast convergence in practice.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Naman Agarwal, Zeyuan Allen-Zhi Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma. Finding approxi- mate local minima faster than gradient descent. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1 1195-118 1199, 2017.
Zeyuan Allen-Zhu and Elad Hazan. Variance reduction for faster non-convex optimization. In International conference on machine learning, pp. 699-707, 2016.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. arXiv preprint arXiv:192..022. 19/2.02365, 2019.
Yair Carmon, John Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for nonconvex optimization. SIAM Journal Optimization, 28(2):155-1172,, 2018.
Jinghui Chen, Dongruo Zhou, Yiqi Tang, Ziyan Yang, and Quanquan Gu. Closing the gener- alization gap of adaptive gradient methods in training deep neural networks. arXiv preprint 100.v0800006766 2018a.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of class of Adam-type algorithms for non-convex optimization. arXiv preprint arXiv:
2018b.
Zaiyi Chen, Zhuoning Yuan, Jinfeng Yi, Bowen Zhou, Enhong Chen, and Tianbao Yang. Universal stagewise learning for non-convex problems with convergence on averaged solutions. In Interna- tional Conference on Learning Representations, 2019.
Ashok Cutkosky and Harsh Mehta. Momentum improves normalized SGD. arXiv preprint
arXiv:2002.03305, 2020.
Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction non-convex SGD. In Advances in Neural Information Processing Systems, pp. 15236-15245, 2019.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 1200u))2121-2159, 2011.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex op- timization via stochastic path-integrated differential estimator. In Advances Neural Information Processing Systems, pp. 689-699 2018.
Cong Fang, Zhouchen Lin, and Tong Zhang. Sharp analysis for nonconvex SGD escaping from saddle points. arXiv preprint arXiv:1902.00244 2019.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochas- tic programming. SIAM Journal on Optimization, 23(4):2341-233) 2366,, 2013.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, An- drew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch SGD: Training imagenet 2017.
in hour. arXiv preprint arXiv:1706.0260
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9()): 1735-1780) 1997.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael Jordan. How escape saddle points efficiently. arXiv preprint (oXxv:/703.00885 2017.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances neural information propuiiioorrosssiieee processing systems, pp. 315-323, 2013.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.66 1412,6980 2014.

---

Under review as a conference paper at ICLR 2021
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. CIFAR-10 and CIFAR-100 100 datasets. URI: https://wwe: cs. toronto. edu/kriz/cifar. html, 6:1, 2009.
Lihua Lei, Cheng Ju, Jianbo Chen, and Michael Jordan. Non-convex finite-sum optimization via
SCSG methods. In Advances in Neural Information Processing Systems, pp. 2348-2358, 2017.
Kfir Levy. Online to offline conversions, universality and adaptive minibatch sizes. In Advances in
Neural Information Processing Systems, pp. 1613-1622, 2017.
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 983- 992, 2019.
Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and beyond. arXiv preprint arXiv: 1rXI1::908.00265, 2019.
Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. arXiv preprint arXiv:1902.09843, 2019.
H Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex opti- mization. arXiv preprint 1002::0002.4903 2010.
Stephen Merity. The WikiText long term dependency language modeling dataset. Salesforce Meta- mind, 9, 2016.
Nhan H Pham, Lam M Nguyen, Dzung T Phan, and Quoc Tran-Dinh. ProxSARAH: An efficient algorithmic framework for stochastic composite nonconvex optimization. Journal of Machine Learning Research, 21(110):1-45 2020.
Sashank Reddi, Ahmed Hefnny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In International conference on machine learning, pp. 314- 323, 2016.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. arXiv preprint arXiv:1904.092.77 099.97,, 2019.
George Saon, Gakuto Kurata, Tom Sercu, Kartik Audhkhasi, Samuel Thomas, Dimitrios Dimitri- adis, Xiaodong Cui, Bhuvana Ramabhadran, Michael Picheny, Lynn-Li Lim, Bergul Roomi, and Phil Hall. English conversational telephone speech recognition by humans and machines. In Interspeech, 2017.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 14Xiv 2014.
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5 learning. University of Toronto, Technical Report, 2012.
coursera: Neural networks for machine
Mengdi Wang, Ethan X Fang, and Han Liu. Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-valus functions. Mathematical Programming, 161(1-2): 419-449, 2017.
Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. SpiderBoost and momentum: Faster variance reduction algorithms. In Advances in Neural Information Processing Systems, pp. 2406-2416. 2019.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. AdaGrad stepsizes: Sharp convergence noncon- vex landscapes. In International Conference on Machine Learning, pp. 6677-6686, 2019.
Ashia C Wilson, Rebecca Roclofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Advances in Neural Information Processing Systems, pp. 4884158, 2017.
Yang You, Igor Gitman, and Boris Ginsburg. Scaling SGD batch size to 32k for imagenet training. arXiv preprint arXiv: 7708 03888, 6, 2017.
10

---

Under review as a conference paper at ICLR 2021
Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep 2019.
learning: Training BERT in 76 minutes. arXiv preprint
Jingzhao Zhang, Hongzhou Lin, Suvrit Sra, and Ali Jadbabaie. On complexity of finding stationary points of nonsmooth nonconvex functions. arXiv preprini arXiv:2002.041300 2020.
Wei Zhang, Xiaodong Cui, UIrich Finkler, Brian Kingsbury, George Saon, David Kung, and Michael Picheny. Distributed deep learning strategies for automatic speech recognition. In ICASSP'2019, May 2019.
Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic nested variance reduction for nonconvex optimization. In Advances in Neural Information Processing Systems, pp. 3921-3932, 2018.

---

Under review as a conference paper at ICLR 2021
A
PROOF OF LEMMA
Proof. The proof is similar to that of Lemma 12 in (Wang et al., 2017). Define
[ - =) ift 2 k 0 (11 - 3) if k =0
(3)
By the definition of c((h) and the update of Algorithm I, we have
Sh (1+1) = -1 (1-
=1, 1,
Wi
Wi+1
Ze+1 Σ
(th (2) (
O
Define m1+11 -k== Sk We+1 Wk++ 11 1 Ek= (8)
[ - F ((w--1) ]]
where V V[[W++15 CR++1) is unbiased stochastic first-order oracle for F(w (Wi+1) with bounded vari- ance of Note that F is a -moshh mapping (according to Assumption (ii)), then by Lemma 10 of (Wang al., 2017), we have
1|2
VF(w.))1 & (Lum, + ||m+]])2 & 2 + 2|
Define q++1 2017), we have
Ei
||W++1 W
According to Lemma 11 (a) and (b) of (Wang et al.,
(1 (1-2) 2 (m, + 4x²) +
18
m4+1
49 1
W -
Taking squares on both sides of the inequality and using the fact that (a+b)² S (1+ + for 3 > 0, we have
(m++1 + 49 -
+ 2
(1-3) 3
-
(m, + 402)² +
2
324
Wi+1 well"
3
g2
(4)
8
972
<
(m4 + 44, +
WH+1 WW+1-wll"
well"
g3
where the last inequality holds since 1/3
Define 0f = 2 (m, + 4q²)² + 2 || Il then we have ||a, VF(w.))l < 8, for all Denote Fi+1 by the r-algebra generated by Ei..... E.111 Taking the summation of (4) and according the bound of n, derived in Lemma 11 (c) of (Wang et al., 2017). we have
B
1944L2
W w.ll
E [
1
6 + 23
2
g3
Taking expectation on both sides yields
1944T.2 W++1 w
E
[
S
E
22
+
2
g3
Note that max((1x]11//..ro)
arga
we have
3
E 1
55
283
+ + [E 34a 3 -
B PROOF OF THEOREM
Proof. By Lemma 1 and the update rule of Algorithm 1, we have
3
CL a gg ||
12 <
+ 2,8
2 + E
2
63 (max( ||z 1/2, E0))
(5)
8
2CL (11661111 + | [9]]
<
E
[2]
+
2,3
02 +
2
/3
12

---

Under review as a conference paper at ICLR 2021
where the second inequality holds since (max([|z)))4 eo)) (,))/))))))))))" 2 Fw:)((
and |zze|2 I 21|6;11 + |
Note that 2
< 1/18. Plugging it in (5), we have
83
B (W:(l))l
R
[
1 2,3
E
(6)
18
18
Summing over t ,,..., T on both sides of (6) and with some simple algebra, we have
T
6
82
T
T
5,00
2 m
VF(w))]
(7)
8
By Assumption (i) and by the property of T-smooth functiio, we know that
F(W++1) F(w,) V P(w:)(w1++] w.) I.
[well-
=F(w,) T/6 V F(W:) + L ||
2
$ F(w,) M F(w:)(Z: - VF(w.) + VF((w)) + 11 (11z [112--1 VF(w:))l + +IVF(w::)]
F(w,) (n: 1/
71 FTF. ) - VF((w:) + L | F(w.)ll
S F(w,)
11
I.) |VF((.,)] + T/ TT ||ze F(w.)ll2.
2
Noting that f)
[| 11/2,0)))))) a - 1/4L and cp = 80, we know that neL S 1/4. Hence we
ag
max
have
[VF(w:)]l = (Fw(w.) F(w.+1)) + 3/12 - VF(w:))1.
Taking summation over t I...., T' and taking expectation yield
T
4(F(w.) - F(We+1))
E [
< E
+ 3
Bl|z, - VF(w.)11
11
1=1
(8)
4(F(w.) - F(((+1))
E
+3
E [89]
1/e
1=1
Combining (7) and (8) yields
4(F(w.) F(We+1))
9 (8) 224)
E
+
E
17p
t=l
T
3
15,302
+
V
F(:
m
8
By some simple algebra, we have
T
8(F(w.) F(W+1))
T
18
(8?
12-1
T
BIVF(w))
+
3
B
m
1=1
Then we have
8 max (1|z 6n) (F(w.) F(we+1))
180
E EI SE
+3030 m.
(9)
a.
3T
Noting that [(w:)) - F(W++1)) S Gre Gnellzll we have
T T
8GE Σ Σ1=1
|z
A
180
E E|/FF()))
+ 30,00
(10)
T
aT
3T
13

---

Under review as a conference paper at ICLR 2021
C PROOF OF THEOREM 2
Before introducing the proof, we first introduce several lemmas which are useful for our analysis.
Lemma 2. Adam* with T)t max((1z:||//2.co) and Eo satisfies
F(W++1)= - F(w,) S a3 (w, + 9 - (F(3)))13/2)
64a43413
Proof. By the L-smoothness and the update of the algorithm, we have
L. wr++1 wel?
F(we+1) F(w)) S V F(w:)((w(+1 w.)
(VF(W:),
a² @2B211112e112
(11)
S -33
max ([|ze|| 1/2,,0)) .o)
(max (12,111/2,co))
Define A, = Ze (F((.)) If V W: 2 2/|aell. we have
(z,, VF(w.))
|V )11 + ( VF(w.))
max 1/,
max VFF + 1111,co)
VF(w.)1
|VF((.))
(12)
2 -A 1/11
3
|VF W. 3/2
+ 8 1//.113/2.
If VF(())) < 2|] we have
(z,, VF(w.))
(F((W)) 11 (A.. VF(w.))
max (| 12,
max V F (w:) + 13,
(13)
G|| 2
|VF(w.))
61|A 3/2
3/2
+ 8
A 1/2
3
By (12) and (13), we have
12, VF((:))
[VF(::)
+ +8 3//2.
(14)
max (|2:|12/2,50)
3
By (11) and (14), we have
/VVF(w 3/22
F(w(+1) F(we) S aB
+8/1, 13/2)
IVF(w:))
22 13/2 3//2
x²
03
+
1,1/2111//2 3//2
a 32
min a20
+
3
3r
3
VF FV((w,) (w:))
18//2
2 2|
3/2
64
ag
11/2
LB82L
3
3(8a
V ww))
13/2
1/22
$ 0,
+
11/2
6
3
where the last inequality holds because ||z,|| 3/2
2 2
|I
3/2 2, 13/2.
Lemma 3. For Adam* + with m)- = max
[|..|| 1/2,0) there exist random variables ö, such that
3/22 0++1
8 E 68 + 2/33/2 3/23/2232_00 3/2 +E
320
3/2
| W
E
<
1
2
32
14

---

Under review as a conference paper at ICLR 2021
Proof. The proof shares the similar spirit of Lemma 12 in (Wang al., 2017), but adapt the proof for our purpose. Define
[3 - =) ift k > 0
(1- 3) ift 2 k =0
(15)
By the definition of (()) and the update of Algorithm 1, we have
(1+1) -1 (0)
(1) (W &k
W
2,+1
k=
k=
Define M4+1 = Ex= k= Sk
W 11. 74+1 Ex= 1i F 1)]]
where V [[( Ek+11 is unbiased stochastic first-order oracle for ((Wk+1) with bounded vari- ance o². Note that F a -m-oohhth mapping (according to Assumption 1), then by Lemma 10 of (Wang al., 2017), we have
22 FF(w.) |//22 15/2 S (Lym + ||mel)) 21
3/2 mi + 11/2.
3/2
Define q++1 2017), we have
Ei=o (1) || We+1ll- According to Lemma 11 (a) and (b) of (Wang et al.,
M++1 + 4q S (1 (1 (1-2)
- (m, + 4q,)) + Wi+1 - -
18
B
Taking the power 3/2 on both sides of the inequality and using the fact that (a + b)3/2 s
g 3/2 +
V1+ 312022 for B > 0, we have
(me+1 + 44(411)
3/2
+
1/2
1
3
3/2
(m, + 4qh))
442)3/2
3/2
+ (1+
2 1/2 80
| - W (16)
2
2
B
83/2
160
(m: + 4q
3//3
3/2
|| w
where the last inequality holds since 1/B 2 1.
By the definition of we have n4++1 (1 3)mz + (V - F(W++1)). Denote Fit1 by the alagebaa generated by E1...., E.+11 Noting that
E
| 3/2 F
(E [1Ime+111 11
(1 ([1)3/2)3/2111 ||o||/// 2 +//3/203/
(17)
where the last inequality holds by invoking Lemma 11(c) of (Wang et al., 2017). Define 5 2L 3/2 (m, + 444)3/3 + 2||me|] || 1//2, then have ||z, VF (F(w:))13 to (16) and (17), we have
3/2 for all t. According
E (
< 31-2
3 | + 2/33/2
3/2 320 1202
H
We+1 well
8²
Taking expectation both sides yields
E
3/2
<
8 2
E
3/22
+ 2/33/223/ 3/2 +E
320L 3/2
| w
Lemma 4. Adam with learning rate n)-
a3
and 640a L
3/2
< 1/120 satisfies
max
2727E (3/2)
T Σ e (VF(WW
101A
+ 4/4 3/2 3/2
3,33 T,3/2
a&T
8T
100
To ensure that 1 EE E [[VF((())))33
< 3/2 we can choose 8 = 3, -922))
15

---

Under review as a conference paper at ICLR 2021
Proof. By Lemma 3 and noting that f72
a/
we have
max
||||
1/2,co)
E
1++1
3/2
1
3
2
E
3//2
//22 + EE 3/2 2,58//2
320 a 11,11/11//
3/2
g2
(18)
8
E
3/2
+ 2/3
3/2
2
E
640L
3/2
a
(IVF((W))
3/2 {
Note that 640a L
_ 1/120. Plugging it into (18), have
593
3/2
R
2/2
3/2 + 2/33/2 :+1
V
(19)
120
120
Summing over f 1,...,? on both sides of (19) and with some simple algebra, we have
T
3
3/2
Σ
B 3/2
E
(+1
5/21/2 3/2
E
B
59
t=1
By Lemma 2, taking expectation both sides, have
[[F(w++1) F(w.)] S ag
E (II
13/21
1//2
9E
8/22
64
(20)
6
3
Summing (20) over / I....,T yields
83/2
5
0
T
E
[F(::))33/2) s ((w:))FFtta)
27TE
T
4//31/2
3/2
6
504
B
3
1=1
Hence, we have
(88/2)
1014
2727E
E
VVF
+ 454531/22
22155a283
o/T
33/2
101A
2727E
3//2
+ 45453
/2
0²3T
3T
100
Lemma 5. Under the same setting of Lemma 4, we know that to ensure that $ ΣT= E 3/2 we need T = (9/)) iterations.
33/2
S
Proof. From (19) and Lemma 4, we have
Σ
T
593
E
3/2
E [9/2] + 2/3322 3/
+
E
B
FF(
V
F
120
120
1=1
Noting that B - with 0 such that
<
1, then we know that there exists universal constant C >
T
59
E
0
3/2
5
2/2
E
1
VF(w))1
(21)
T
120
-
Tb/2
120
[=1
1=1
Take
From Lemma 4, we know that it takes T
O 9/2) iterations to ensure that
# ΣT E [IIFF(w))))/?
3/2 In addition, From (21), we know that takes T O(e 9/2)
iterations to ensure that ΣT E 6 S 3/2
We can easily prove Theorem 2 by incorporating the results in Lemma 4 and Lemma 5. It is also evident to see that if 8 = 1/7" with < < 1, then it takes T' O (poly(1/e)) number of
iterations to ensure that $ ET= E simultaneously.
8
3/2
< 3/2 and $ IE E [ [[]) < 3/2 hold
16

---

Under review as a conference paper at ICLR 2021
D PROOF OF THEOREM 3
Proof. Define Y min
8" |
/ with 60 = 2.8%. Then we know that 7/: ony and S 2
Note that v J.- so we have 7): By the L-smoothness of F. we have
F(We+1) 5 F(.)) + F(w:)(We41 -we) + L
||We+1 well
S F(w,) 7/: V. F(wi)z +
11 (2
+
7t
|2r11
1
7el1zel??
21,
2L
= F(Wi) 7/ V F(w.) (2: VF(w,) + VF(w.)) +
11
+
7t
| 1|
2I mel
1
/e||2= 2
2
2L
(0)
S F(w.)) TI V F(W.) (2. V/(.))+ VFFw.))
(1 L + T.
(122: - VF(w:))l1 + 1[
2T. ||122112
1
(
S F(w:)
[VF(w:))
The 2タ4 VF(W.))l + (1E + 2n (Ik,- (V
2T. Tml
1
Tellzel'
1|
2
F(w,)
2
11
n T.
7) |IVF(w:)1( + (n:
2e
L
+ M1 1|z VF((w))]
2
2L 7
1
12
(0)
I F(w))
2L Y1 |ze1?
+ L - VFF(w:)
(22)
where (a) holds since || < 2/|2:
1111..0000 (b) holds since V F(w: S
(IV F(w.)] + 2. - V/(w)) (c) holds due to 3/2 ni 7 2 0 (since Te S 21. we have
- 2 2Z
1 and note that 2 s 2r
By the definition of /t. we have
| 2/3
|
||z |2,111/3)
||, 11/3
|//314/33
Yo 11|lzel22 2 32"||z|||' 21/3
min
= (zz0||z,||2
min
3a
BuED
2,92a
(23)
(n)
|
12/3
82a | 1/2/3
82a |zr| 2/3
3a |2/l 12/1
where (a) holds since x 2 x
2
1
2²
2
2
x
2 hold for any x and let x
|/.3
g
Combining (22) and (23), we have
82a 1
|
2/3
32a
||z||2/0
8 [ze 1/3
1/3 < vel 7r|1z11'' 1|2
< (F(w.) - F(w:+1)) +
+ VF(w:))1
2
2
Ba
2L (F((:))
F(wz+1)) + 8r 12e12111//
22|22
VF(w:))1
2//2
If 9
< 1 we have 3a || 4/3 < 4L (F(wi) - F(W1+1)) 41|zz VF(W))) If 2//..13/5
2//
2.
2. then 3a
>
| 2/3 and hence we have 3d 12 4/3 < 330, As result, we have
ge1 z 4/3 < 4L (F(w.) - F(We+1)) + 41|z: - 22 33a.
(24)
Taking summation on both sides of (24) over 1, L,..., T yields
F(w,) F(W++1)
T
1z 4/3 < 4L
+
Zz
FF(w:)]l + 32T..
(25)
go
3a
Define A, = 2t (w:), then we have
[VF(w))) 1/3 < 2/13
+ 2//3,11//3
(26)
17

---

Under review as a conference paper at ICLR 2021
Hence,
1/3
2|1/3
T F(w.)= F((e+1)
T
12
|
4/3
+ 121.
12z
VF(w:)]l + 3,32aT
Ba
G00
(8)
T
||
g2a +
+
12L
T
F(w:) -((e++))
Σ
T
12
1z VF(w,)) 332aT
8
2
3ra
B
1=1
t=1
T
F(w.)
F(We+1)
14
12L
1z
VF( + 4,32uT
8a
3a
(27)
where (a) holds due to (25) and (26). (b) holds because min e +
x² 4/3
By Lemma I, we know that
8
CLLLTAIIZI 1+1
E
[8]
+
232022 +
2
33
(a)
8
CLLaa g4a ||z||1
1
E
[
+ 200002 +E
2
max(1 2 18/3 , 33)
B
E
+
2
+ E
CI.2 34a | 4/3
2
Note that Cl2a4 S 11/14, we have
g4a-3
[zz]
4/3
[
< [
-6 2,300 +
(28)
14
Taking summation on both sides of (28) over t 1,..., T, we have
E
[o9]
840
[2e||
1/3
E [
+ 2800T
14
(29)
E [
T
|.0 2
||
1//3
+ + +
8
14
where the last equality holds since = 4/33.
Taking expectation on both sides of (27) and combining (29), we have
Σ E | |1/3
T
4/3 + [VF(())))
<
12LA
14E [67]
28
T
E
[|z 1/3]
+ 4,32T.
ga
Bi+a
3a
As result, we have
T M
E
(VF
<
12LA
+
14 [7]]
28,30
+ 4,32a
T 1=1
BoT
BI+aT
30
Suppose initial batch size is To. the intermediate batch size is m, and 4/3, then we have
T [[FF(::))
12LA
140²
280²
Σ
E
<
+
4,38/3
(30)
B4/3T
3T/TTT
31/3m
- the interme- diate batch size m 1/33 0(c-3/1/) which ends up with the total complexity -3.5). n
We choose 9 = 062/22) - the initial batch size To
18

---

Under review as a conference paper at ICLR 2021
E A NEW VARIANT OF ADAM
Theorem 4. Assume that [V;((;;)]
5) S G almost surely for every w E Rd Choose
23 (0)) with 4/3, and we have
max
12LA BOT
14
oi
2836²
Σ
IVF(W.)
+ 4,880.
T
BI+aT
30
Denote the initial batch size and the intermediate batch size are To and m respectively, then we have
T T
12LA
140²
280²
E
|
(w:))13/2)
<
+
ToTai +
Ba-Im + 4,380.
BOT
To ensure that + Ei=
E [IVF( < 3/2 we choose 3 = 2/8 0(1/6)), the initial
batch size is To = 8/8 and m 1/e2.66600 1.655 then the total computational complexitty is (1//6..62)
Proof. Define >/- min
8a
with Eo 238 Then we know that T ar and Yt S 1
|
1172
co
Note that a S 1. so we have 1) S 21.
By the L-smoothness of F, we have
L
F(W1+1) & F(w.) + F(w:) - -w.) +
|| - wwll?
2
< F(w:)) F...F((W:2.. +
+
7t
|ze|12
1
V/a
Ti|1zel1
2
2L
2T.
F(wi) 7o FTF(FW) (ze (F(w.) + VF(w)))
+
7tt
||z 11
2L //llzz|11
1
2
2L
2 F(w:) 7 V F(w.) (z, VF(w.) + VF(w.))
[1 L (11z, VF(w;))l + |
2L Yt. ||z,11
(8) Th
2 F(w))
[V:(w:))
11²
11t |22 VF(Wi11 + (1) + 7t) (lzz- V
1
Ye rellze|?
2
2
2L
F(W.)
1/t
T.
7) |/VF(w.))1 + (12 + 7t + 1)t
||: - -VF(w:)
2L 7112 2
1
2
L 2
(0) 1
1
I F(Wi)
|zel?
+ |
Y/
2L
(31)
where (a) holds since ||2.|| < 2212,2-V FF(( 112 F(w:)) (b)
holds since V ((w. )2+ S
(I F' (W.,. [w.)) and note that 7 S 2
(V((w)))))) (c) holds due v/ np z (since 7) S DI we have
of 2 2L
By the definition of /t, we have
|z
1/2
1zel
[ze 1/2
[z(|]
7el1ze112 2 [|e|l min
= 322 [2:ll
min
3a
3000
33a
2,320
(32)
[z,
1/2
82a
||z
|zzl|
=8 -111 |/|12113/
1/3/2
3a
2
2
where (a) holds since x 2 x
21
2
2
2
x
2
!
hold for any x and let x
|x, 1/2
g
Combining (31) and (32), we have
| | 3/2 < 57.1z, 2 + 320 2
8200| 2+
< 2L (F(w:) - F(w++1)) +
+ +211zz VF(w:))
2
g
=FW.(F(w:)) - F(w++1)) + 1/
+ + - VF(w.))12.
2 1|/2
19

---

Under review as a conference paper at ICLR 2021
If 9
2/|z: ||/ _ 2: we have 8 ||z|| I (F((1) F(W++1)) - Iz VF(w))l If
g
2/2,/11/3
2 then 3a > |ze| 1//2, and hence we have 3 |2 1|/22 S gLa. As result, we have
5 |z 3/22 f 4L (F(w)) F(w(+1)) + 4 VF(w:))
(33)
Taking summation on both sides (33) over 1, ..... yields
F(w,) F(We+1)
4 3a
Zr 3/2 4L
Zt
VF((:))1 + B3aT.
(34)
30
Define A Zz
VF W then we have
[F((w))
1l 3/2 - 2/12/113/2
+ 22//2211//2.
(35)
Hence, we have
r
3/2 +
T
F(w:) - F((e+1)
T
12
2
A
3/2 + 12L
Σ
124
V [f(w:)]l + 3,3
Ba
30
t=1
m=1
[=1
(8)
3
||
33a +
F(wi) - =((w+1))
12
+
12L
Σ
||z 4=(w:)|1++333) 333
8
3a
Ba
1=1
F(we)
F(We+1)
14
< 12T
VF(w;)]12 + 4,33aT,
Ba
(36)
where (a) holds due to (34) and (35), (b) holds because min c² +
23
4/3/2
3
3
By Lemma 1, we know that
8
CL fl 11
E
E
82
2,32 + R +
2
B3
(a)
3
CL2 4/44 122
E
66
+ 288002 02 +E
2
max (1 |/ 11 (0),33
3
1
E
+
2 +
[CL 1gda-3 ||
2
Note that CL
<
14G1/Z we have
B
3 |ze 12
E
<
E
5 -
[241] + 2,3202 2 E
(37)
2
14G
Taking summation on both sides of (37) over 1.....7 T, we have
E
T
34a-4 4
E
2,3 2T +
E
3
14
1=1
E
[59]
T
(8at 1
11
2.30T'+4
Σ
E
(38)
3
14G
E
[o]]
T
|0 |z,
13/2
<
280
2T
+
E
3
14
where the equality holds since
4/3 and last inequality holds since ||z.|| < G.
20

---

Under review as a conference paper at ICLR 2021
Taking expectation both sides of (36) and combining (38), we have
E8 ||z,13/2 3//2 +
||FF(w)))
12L(F(w1)) F&)
14E [89]
28,0²
T
|
[3//
+ 43
3a
g2ta
8a
1=1
As result, we have
12L(F (w1) F2)
14E
6
28,8² g0
T E
|V
+ 4,300
8OT
B
Bl+aT
F RELATED WORK
Adaptive Gradient Methods Adaptive gradient methods were first proposed in the framework of online convex optimization (Duchi et al., 2011; McMahan & Streeter, 2010), which dynamically incorporate knowledge of the geometry of the data to perform more informative gradient-based learning. This type of algorithm was proved to have fast convergence if stochastic gradients are sparse (Duchi et al., 2011). Based on this idea, several other adaptive algorithms were proposed to train deep neural networks, including Adam (Kingma & Ba, 2014), Amsgrad (Reddi et al., 2019), RMSprop (Tieleman Hinton, 2012). There are many work trying to analyze variants adaptive gradient methods in both convex and nonconvex case (Chen al., 2018a; 2019; 2018b; Luo et al., 2019: Chen et al., 201 8a;b; Ward et al., 2019; Li & Orabona, 2019; Chen et al., 2019). Notably, all of these works able to establish faster convergence rate than SGD, based the assumption that stochastic gradients are sparse. However, this assumption may not hold in deep learning. In contrast, our algorithm can have faster convergence than SGD even if stochastic gradients not sparse, since our algorithm's 's new data-dependent adaptive complexity does not rely on the sparsity of stochastic gradients.
Variance Reduction Methods Variance reduction is a technique achieve fast rates for finite sum and stochastic optimization problems. It was first proposed for finite-sum convex optimiza- tion (Johnson & Zhang, 2013) and then it was extended in finite-sum nonconvex (Allen-Zhu & Hazan, 2016; Reddi et al., 2016 6; Zhou et al., 2018) and stochastic nonconvex (Lei et al., 2017; Fang al., 2018; Wang et al., 2019; Pham et al., 2020; Cutkosky Orabona, 2019) optimization. To prove faster convergence rate than SGD, all these works make the assumption that the objective function an average of individual functions and each one of them is smooth. In contrast, our analysis does not require such assumption and to achieve faster-than-SGDi rate.
Other Related Work Arjevani et al. (2019) show that SGD is optimal for stochastic nonconvex smooth optimization, if one does not assume that every component function is smooth. There are recent work trying establish faster rate than SGD, when the Hessian of the objective function is Lipschitz (Fang et al., 2019; Cutkosky & Mehta, 2020). There are several empirical papers, includ- ing LARS (You al., 2017) and LAMB (You al., 2019)), which utilize both moving average and normalization for training of deep neural networks with large- batch sizes. Zhang et al. (2020) consider an algorithm for finding stationary point for nonconvex nonsmooth problems. Levy (2017) considers convex optimization setting and design algorithms which adapts to the smoothness pa- rameter. Liu al. (2019) introduced Rectified Adam to alleviate large variance at the early stage. However, none of them establish data-dependent adaptive complexity as in our paper.
G A WITH FIXED LEARNING RATE
We report the results on image classification with CIFARIO on ResNet18. We further considered the A with fixed learning rate 0.1 and do not employ any learning rate annealing scheme. We report our result on Figure 6, in which "Adam+ Fixed Stepsize" uses the default setting of from the Figure, Adam with fixed stepsize still outperforms Adam,
Algorithm 1. As
21

---

Under review as a conference paper at ICLR 2021
ResNet18 training on CIFAR10
0.95
0.9
Test Accuracy
0.85
SGD
Momentum SGD
Adagrad
Adam
0.8
Adam+ Fixed Stepsize
NIGT
Adam+
0.75
0
100
200
300
400
Number of Epochs
Figure 6:
Comparison of Adam and Adam+ with Fixed Stepsize
ResNet18 training on CIFAR10
14
12
log log(E. EE [2,]])
8
6
4
Adam+
2
0
4
6
10
12
log(Number of Iterations)
Figure 7: log (i [|z]])
versus log(t)
Adagrad and momentum SGD, we use the same learning rate scheduler of SGD for Adam then Adam performs the best.
H GROWTH RATE ANALYSIS OF EL_ 1
Z
We provide the log-log plot (log() Mt 1-1 ||x versus log(!)) for the ResNet18 training CIFARIO experiment, as illustrated in Figure 7. We can see that the slope around 0.8. Although the slope is not small, we (which corresponds to the epoch number 154). At this particular epoch, the training and test accuracy not the best need to keep the training until epoch 350. Then our algorithm A is able
from Figure that the slope becomes almost zero after the iteration 6 x 10
22

---

Under review as a conference paper at ICLR 2021
to take advantage of the slow growth rate of Ei= ||z,|| for large t and enjoys faster convergence, which is consistent with Figure 1.
23


Reviews:
[{"review_id": "s8NR9uFBFbB", "reviewer": "AnonReviewer1", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new optimizer called Adam+, with two main distinctions from standard Adam template: 1) the first order moment estimate is computed using the gradient evaluated at an extrapolated iterate. 2) the step size is scaled with the square root of the norm of the first order moment, rather than the exponential moving average (EMA) in the previous work. Under Lipschitz continuous gradient, Hessian and bounded gradient assumptions, the complexity for finding a point with small gradient norm is $\\epsilon^{-3.5}$, which is a SOTA complexity. The practical performance of the algorithm is evaluated in a range of different tasks and the performance is shown to be consistently promising and comparable to SGD/Momentum SGD.\n\nStrengths:\n- I think the algorithm template, and the connection to variance reduction is interesting. In particular, I saw a similar algorithm in [1, Alg. 2]. Of course the algorithm in [1] is designed for a more general setting, so it has important differences. But in my opinion, the fact that a similar algorithm works in such a general setting as [1], shows the strength and potential of Adam+.\n\n- The authors consider a large variety of tasks in different domains (Table 2) which is important to judge the consistency of the method in practice.\n\n- The paper is clear and well-written, the comparison with previous work is fair and comprehensive, to my knowledge.\n\nWeaknesses and suggestions for improvement: I have several concerns about the potential impact of both theoretical and practical results. Mainly:\n\n- By referring to Wilson et al., 2017, the authors argue that diagonal step sizes in adaptive algorithms hurt generalization. First, I find this claim rather vague, as there has been many followups to Wilson et al., 2017, so I suggest the authors to be more precise and include more recent observations. Moreover, one can use non-diagonal versions of these algorithms. For example, see [2 and Adagrad-norm from Ward et al., 2019], it is easy to consider similar non-diagonal versions of Adam/AMSGrad/Adagrad with first order momentum (a.k.a. AdamNC or AdaFOM), then, are these algorithms also supposed to have good generalization? I think it is important to see how these non-diagonal adaptive methods behave in practice compared to SGD/Adam+ for generalization to support the authors' claim.\n\n- I think the algorithm seems more like an extension of momentum SGD, than Adam.\n\n- It is nice to improve \\eps^{-4} complexity with Lipschitz Hessian assumption, but what happens when this assumption fails? Does Adam+ get standard \\epsilon^{-4}?\n\n- From what I understand in remark after Lemma 1, the variance reduction is ensured by taking $\\beta$ to $0$. The authors use $1/T^{a}$ for some $a\\in(0,1)$. Here, I have several questions. First, how does such a small $\\beta$ work in practice? If in practice, a larger $\\beta$ works well and theory requires $\\beta\\to 0$ for working, it shows to me that theoretical analysis of the paper does not translate to the practical performance. When one uses $\\beta$ values that work well in practice, does the theory show convergence?\n\n- Related to the previous part, I am also not sure about \"adaptivity\" of the method. The authors need to use Lipschitz constants $L, L_H$ to set step sizes. Moreover $\\beta$ is also fixed in advance, depending on horizon $T$, which is the main reason to have variance reduction on $\\|z_t-\\nabla f(w_k)\\|$. So, I do not understand what is adaptive in the step size or in the variance reduction mechanism of the method. \n\n- For experiments, the authors say that Adam+ is comparable with \"tuned\" SGD. However, from the explanations in the experimental part, I understand that Adam+ is also tuned similar to SGD. Then, what is the advantage compared to SGD? If one needs the same amount of tuning for Adam+, and the performance is similar, I do not see much advantage compared to SGD. On this front, I \nsuggest the authors to show what happens when the step size parameter is varied, is Adam+ more robust to non-tuned step sizes compared to SGD? \n\nTo sum up, I vote for rejection since 1) the analysis and parameters require strict condition, 2) it is not clear if the analysis illustrates the practical performance (very small $\\beta$ is needed in theory), 3) practical merit is unclear since the algorithm needs to be tunes similar to SGD and the results are also similar to SGD.\n\n[1] Zhang, Lin, Jegelka, Jadbabaie, Sra, Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions, ICML 2020.\n[2] Levy, Online to Offline Conversions, Universality and Adaptive Minibatch Sizes, NIPS 2017.\n\n======== after discussion phase ==========\n\nI still think that the merit of the method is unclear due to reasons: 1) It is not clear how the method behaves without Lipschitz Hessian assumption. 2) The method only obtains the state-of-the-art complexity of $\\epsilon^{-3.5}$ with large mini-batch sizes and the complexity with small mini-batch sizes (section 2.1) is suboptimal (in fact drawbacks such as this needs to be presented explicitly, right now I do not see enough discussions about this.). 3) Adaptive variance reduction property claimed by the authors boils down to picking \"small enough\" $\\beta$ parameter, which in my opinion takes away the adaptivity claim and is for example not the case in adaptive methods such as AdaGrad. 4) The comparison with AdaGrad and Adam with scalar step sizes is not included (the authors promised to include it later, but I cannot make a decision about these without seeing results) and I am not sure if Adam+ will bring benefits over them. 5) Presentation of the paper needs major improvements. I recommend making the remarks after Lemma 1 and theorems clearer, by writing down exact expressions and the implications of these (for example remarks such as \"As the algorithm converges with $\\mathbb{E}[\\|\\nabla F(w_)\\|^2]$ and $\\beta$ decreases to zero, the variance of $z_t$ will also decrease\" can be made more rigorous and clearer, by writing down exactly the bound for the variance of $z_t$ by iterating the recursion written with $\\mathbb{E}\\delta_{t+1}$ and highlighting what each term does in the bound. This way will be much easier for readers to understand your paper).\n\nTherefore, I am keeping my score.", "extra_scores": {}, "extra_text": {}}, {"review_id": "YtNGoJoOd12", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper proposes the Adam+ algorithm that maintains an exponential moving average of the first moment and normalizes it by its $p$-th moment for some $p \\in (1/2, 1)$. When $p = 2/3$, with appropriate hyperparameters, Adam+ achieves the state-of-the-art complexity $O(1/\\epsilon^{3.5})$ to obtain an approximate first-order stationary point for smooth objectives with smooth Hessians. The proof technique is similar to that for SCGD by Wang et al. (2017), which construct a Lyapunov function for algorithms of this kind. \n\nPros:\n(1) The idea of using fractional normalization is interesting.\n\n(2) The proof involves bounding the (4/3)-th moment of the average gradient norm, which is novel to me.\n\n(3) The algorithm performs well on the examples considered in the paper.\n\nConcerns:\n(1) The rate $O(1/\\epsilon^{3.5})$ requires the inner batch size to be $O(\\epsilon^{-1.5})$. The requirement of large batch sizes seem to be essential for the proof. But it is not a very realistic setting. By contrast, the NIGT algorithm (Cutkosky and Mehta, 2020) does not require large batches while achieves the same convergence rate. Moreover, for both Theorem 1 and 3, an extra assumption that $||\\nabla F(x)||\\le G$ is imposed, which is not required by NIGT. Is the analysis for Adam+ unnecessarily loose, given that Adam+ and NIGT are almost identical?\n\n(2) Adam+ seems to be not scale-invariant even if the term $\\epsilon_0$ is ignored in $\\eta_t$. When $f$ becomes $Cf$, $L$ becomes $CL$, and $\\nabla g$ becomes $C\\nabla g$. Since the scale of $w$ does not change, we should expect the sequence $w_{k}$ to be invariant to $C$. Equivalently, we want $\\eta_t z_t$ to be invariant. If Adam+ with $p = 2/3$ is scale-invariant, then $z_t$ becomes $C z_t$, in which case $\\eta_t z_t \\propto \\alpha C^{1/3}z_{t} / ||z_{t}||^{2/3}$. As a result, $\\alpha$ should scale as $C^{-1/3}$. However, in Theorem 3, $(CL)^2 \\alpha^4 = O(1)$, implying that $\\alpha$ scales as $C^{-1/2}$. This contradicts with the scale-invariance. Therefore, Adam+ is not scale-invariant. If my argument is correct, Adam+ seems to be problematic. Could you clarify how scale invariance can be achieved? Does $\\beta$ or other parameters implicitly depend on the smoothness parameter?\n\n(3) The $O(poly(1/\\epsilon))$ in Theorem 2 is $O(\\epsilon^{-4.5})$, right? If so, please clarify this rate since $O(poly(1/\\epsilon))$ is too vague.\n\n(4) The sharp slope change in Figure 5 is unexpected. Is this due to the decreased step size? If the curve before the turning point is fitted by $T\\rightarrow T^{\\alpha}$, what is estimate of $\\alpha$? I suspect that the estimated alpha is close to $1$. If so, the point made in Theorem 1 would be undermined. \n\n(5) For experiments on CIFAR10 and CIFAR100, the performance of Adam seems to be very poor. For instance, NIGT substantially outperforms Adam, but even in Cutkosky and Mehta (2020) the gap is not as large as the presented one. Is the best tuned result presented for Adam?\n\nTypos:\n\n(1) In page 12 and 15, $\\zeta_{t}^{(k)}$ should be $\\zeta_{k}^{(t)}$, \n$w_{t} = \\sum_{k=0}^{t}\\zeta_{k}^{(t)}\\hat{w}_{t+1}$ should be $w_{t} = \\sum_{k=0}^{t}\\zeta_{k}^{(t)}\\hat{w}_{k+1}$, and $z_{t+1} = \\sum_{k=0}^{t}\\zeta_{k}^{(t)}\\nabla f(\\hat{w}_{t+1}; \\xi_{t+1})$ should be $z_{t+1} = \\sum_{k=0}^{t}\\zeta_{k}^{(t)}\\nabla f(\\hat{w}_{k+1}; \\xi_{k+1})$ (The equations fail to be displayed for no reason)\n\n(2) Page 12: $||z_{t} - \\nabla F(w_{t})||^2\\le (Lm_{t} + ||n_{t}||)^2$ should be $||z_{t} - \\nabla F(w_{t})||^2\\le (L_{H}m_{t} + ||n_{t}||)^2$.\n\n(3) Page 12-13, equation (5)-(6): $\\sigma^2$ should be $\\sigma_{m}^2$.\n\n(4) Page 13, the last equation: the first term should has a constant $8$.\n\n(5) Page 15, equation (15): $n_{k+1}$ and $n_{k}$ should be $n_{t+1}$ and $n_{t}$, respectively.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Vx2up5z-YHc", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper propose a new variant of ADAM, which replace 2nd order momentum with 1st order momentum. \n\nPros: \n1. It saves the number of saved parameters (i.e., without using 2nd order momentum).\n2. This paper provide convergence analysis. The author is able to derive a data dependent convergence rate under mild conditions.\n3. The theoretical analysis and implication is very clear. The variance reduction property of the 1st order momentum provides a good characterization of the convergence of the algorithm.  \n4. Provide comprehensive empirical study on various benchmark datasets and neural networks in computer vision and natural language processing. The proposed ADAM+ converge faster compared with competitors. \n\nCons/Questions:\n1. Section 2.2, what does it mean by \"Large Mini-Batch\"\n2. In addition to the training curves, it is better to present a quantitative empirical results (for specific metrics) when comparing different optimizers. E.g., final classification accuracy on CIFAR-10\n3. In the experiments of WikiText2, the convergence of ADAM is much faster than the competitor? What are the learning rate used for ADAM and other competitors? It would be better to report the best hyper-parameter combination for each experiment. \n4. A hyper-parameter sensitivity analysis of ADAM+ is needed.\n\nMinor:\n1. missing reference: On the Variance of the Adaptive Learning Rate and Beyond", "extra_scores": {}, "extra_text": {}}, {"review_id": "4b6Tl_mq3pp", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Objective of the paper: The paper proposes a new optimizer \"Adam+\" that computes the first moment estimate at extrapolated points and the step size is normalized by the root of the norm of the first moment estimate. The paper establishes a convergence theory for Adam+ and conducts experiments on different deep learning tasks to demonstrate the advantage of Adam+.\n\nStrong points. The paper proposes a novel algorithm to train the deep neural network. It has both theoretical guarantee and empirical evidence to justify the advantage of Adam+. The paper logic is clear  and well-organized.\n\nWeak points: \n1. The theoretical guarantee is problematic.  In Theorem 1, the right hand side of (1) has $\\sum_t \\|z_t\\|$ which could scale linearly with $T$. The right hand side and the left hand side share the same structure sum of gradients and hence it is not appropriate to claim this bound meaningful in terms of $T$. This is different from the Adam AdaGrad's proof, where $\\|g_{1:T,i}\\|$ scales with $\\sqrt{T}$ and hence produces a $1/\\sqrt{T}$ regret.\n2.  The empirical result does not cover Transformer like models, which achieve SOTA performance on language understanding and favor Adam optimizer. Moreover, it is known that the performance of Adam is sensitive to the learning rate [1].   For fair comparison, the paper should also tune the hyper-parameters of Adam at least its learning rate.\n\n\nI do not recommend the publication for now.\n\nMinor,\nIn Abstract: at extrapolated data points. --> at extrapolated points\n\n[1]  Choi, Dami, et al. \"On empirical comparisons of optimizers for deep learning.\" arXiv preprint arXiv:1910.05446 (2019).\n\nAfter rebuttal\n\nThanks for the feedback. However, I am not persuaded by the answers of Q1 and Q2 and would keep the score unchanged. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new variant of adaptive stochastic gradient method that has notable differences from Adam, and claims the advantage of adaptive variance reduction. While the algorithm construction looks novel, there are several concerns by the expert reviewers on the theoretical results of the paper, including lack of clarity and its guidance/relevance to the practical performance. There are also questions on the practical merit of the paper pointing to in limitations on the numerical experiments. I recommend rejection of the paper in the current form, and hope the reviews can help the authors to improve it in both theoretical and empirical aspects. 
Decision: Reject