Domain-Independent Dominance of Adaptive Methods
Authors: Pedro Savarese
David McAllester
Sudarshan Babu
Michael Maire
Venue:  (2020)

Abstract: From a simplified analysis of adaptive methods, we derive AvaGrad, a new optimizer which outperforms SGD on vision tasks when its adaptability is properly tuned. We observe that the power of our method is partially explained by a decoupling of learning rate and adaptability, greatly simplifying hyperparameter search. In light of this observation, we demonstrate that, against conventional wisdom, Adam can also outperform SGD on vision tasks, as long as the coupling between its learning rate and adaptability is taken into account. In practice, AvaGrad matches the best results, as measured by generalization accuracy, delivered by any existing optimizer (SGD or adaptive) across image classification (CIFAR, ImageNet) and character-level language modelling (Penn Treebank) tasks. This later observation, alongside of AvaGrad's decoupling of hyperparameters, could make it the preferred optimizer for deep learning, replacing both SGD and Adam.

Under review as a conference paper at ICLR 2020
DOMAIN-INDEPENDENT DOMINANCE OF ADAPTIVE METHODS
Anonymous authors Paper under double-blind review
ABSTRACT
From a simplified analysis of adaptive methods, we derive AvaGrad, a new opti- mizer which outperforms SGD vision tasks when its adaptability is properly tuned. We observe that the power of our method is partially explained by a decou- pling of learning rate and adaptability, greatly simplifying hyperparameter search. In light of this observation. we demonstrate that, against conventional wisdom, Adam can also outperform SGD on vision tasks, long as the coupling between its learning rate and adaptability is taken into account. In practice, AvaGrad matches the best results, as measured by generalization accuracy, delivered by any existing optimizer (SGD or adaptive) across image classification (CIFAR, ImageNet) and character-level language modelling (Penn Treebank) tasks. This later observation, alongside of AvaGrad's s decoupling of hyperparameters, could make it the preferred optimizer for deep learning, replacing both SGD and Adam.
INTRODUCTION
Deep network architectures are becoming increasingly complex, often containing parameters that can grouped according to multiple functionalities, such as gating, attention, convolution, and generation. Such parameter groups should arguably be treated differently during training, as their gradient statistics might be highly distinct. Adaptive gradient methods designate parameter-wise learning rates based gradient histories, treating such parameters groups differently and, in principle, promise to be better suited for training complex neural network architectures.
Nonetheless, advances in neural architectures have not been matched by progress in adaptive gradient descent algorithms. SGD is still prevalent, in spite of the development of seemingly more sophisticated adaptive alternatives, such RMSProp (Dauphin al., 2015) and Adam (Kingma & Ba, 2015). Such adaptive methods have been observed to yield poor generalization compared to SGD in classification tasks (Wilson al., 201 and hence have been mostly adopted for training complex models (Vaswani et al., 2017; Arjovsky et al., 2017). For relatively simple architectures, such as ResNets (He et al., 2016a) and DenseNets (Huang et al., 2017), SGD is still the dominant choice.
At theoretical level, concerns have also emerged about the current crop of adaptive methods. Recently, Reddi et al. (2018) has identified cases, even in the stochastic convex setting, where Adam (Kingma & Ba, 2015) fails to converge. Modifications to Adam that provide convergence guarantees have been formulated, but have shortcomings. AMSGrad (Reddi et al., 2018) requires non-increasing learning rates, while AdamNC (Reddi et al., 2018) and AdaBound (Luo et al., 2019) require that adaptivity be gradually eliminated during training. Moreover, while most of the recently proposed variants do not provide formal guarantees for non-convex problems, the few current convergence rate analyses in the literature (Zaheer et al., 2018; Chen et al., 2019) do not match SGD's. 's Section 3 fully details the convergence rates of the most popular Adam variants, along with their shortcomings.
Our contribution marked improvements to adaptive optimizers, from both theoretical and practical perspectives. At the theoretical level, focus convergence guarantees, deriving new algorithms:
Delayed Adam. Inspired by Zaheer et al. (2018)'s analysis of Adam, Section 4 proposes a simple modification for adaptive gradient methods which yields a provable convergence rate of (1//TT) in the stochastic non-convex setting the same SGD. Our modification can be implemented by swapping two lines of code and preserves adaptivity without incurring extra memory costs. To illustrate these results, we present non-convex problem where Adam fails to converge to

---

Under review as a conference paper at ICLR 2020
stationary point, while Delayed Adam Adam with proposed modification provably converges with rate of OLL/VT).
AvaGrad. Inspecting the convergence rate of Delayed Adam, we show that would improve with an adaptive global learning rate, which self-regulates based on global statistics of the gradient second moments. Following this insight, Section proposes new adaptive method, AvaGrad, whose hyperparameters decouple learning rate and adaptability.
Through extensive experiments, Section 6 demonstrates that AvaGrad is not merely a theoretical exercise. AvaGrad performs well as both SGD and Adam in their respectively favored usage scenarios. Along this experimental journey, we happen to disprove some conventional wisdom, finding adaptive optimizers, including Adam, be superior to SGD for training CNNs. The caveat is that, excepting AvaGrad, these methods are sensitive to hyperparameter values. AvaGrad is a uniquely attractive adaptive optimizer, yielding near best results over wide range hyperparameters.
PRELIMINARIES
2.1 NOTATION
[61, b2. Rdd we use the following notation: 1 for element- wise division (1 (== 1 02 ................................ D) va for element-wis. square root (vā [Vai, /áz........ ......... D) + b for element-wise addition + [ai + b1, as + b2, ... D) a O for element-wise multiplication (a O b = b1 a2b2....1).. .). Moreover, ||a]| is used to denote the f--norm: other norms will be specified whenever used (e.g.. Ila)).o)
02, 02,,02.000 For vectors [01,
For subscripts and vector indexing, we adopt the following convention: the subscript t is used to denote an object related to the I-th iteration of an algorithm (e.g., wy E Rd denotes the iterate at time step f); the subscript is used for indexing: wy lR. denotes the i-th coordinate of E IRd. When used together, precedes i: W/, E denotes the i-th coordinate of We TR.d
2.2 STOCHASTIC NON-CONVEL OPTIMIZATION
In the stochastic non-convex setting, we concerned with the optimization problem:
min f(w) Eg-D [fs (w)]
wERd
where D is probability distribution over set S of "data points". We also assume that f is M -smooth in w, as is typically done in non-convex optimization:
M Y w. w f(w') & fww + (Vf(w), w' w) + ||w [ww-wll" w'll
Methods for stochastic non-convex optimization are evaluated in terms of number of iterations or gradient evaluations required achieve small loss gradients. This differs from the stochastic convex setting where convergence is measured w.r.t. suboptimality f(w) - min (ww). We assume
that the algorithm takes sequence of data points S (SI...., ST) from which it deterministically computes sequence of parameter settings wi...., wr together with distribution P over {1,..., T).
We say an algorithm has convergence rate of O(g(T)) if EE S-DT (<P(()))
[V+(())) < O(g(T))
where, as defined above, f(w) E.-D [w)].
We also assume that the functions fa have bounded gradients: there exists some Go such that [ f. (w)ll < Go for all E S and Rd, Throughout the paper, also let G2 denote upper bound on [[w)]
3 RELATED WORK
Here we present brief overview optimization methods commonly used for training neural networks, along with their convergence rate guarantees for stochastic smooth non-convex problems.
2

---

Under review as a conference paper at ICLR 2020
We consider methods which, each iteration receive compute gradient estimate:
Jt = (uc
D
(3)
and perform an update of the form:
W++11 = w0 Ote 3 m
(4)
where Ory E IR is the global learning rate, W/ E Rd are the parameter-wise learning rates, and my Rd is the update direction, typically defined as:
m, -3, m + (1 (1- B1,eg. and mig 0.
(5)
Non-momentum methods such as SGID, AdaGrad, and RMSProp (Dauphin al., 2015; Duchi et al., 2011) have m = ge (i.e,, B1,, = 0), while momentum SGD and Adam (Kingma & Ba, 2015) have 31. (o, 1). Note that while a can always be absorbed into n/o representing the update in this form
will be convenient throughout the paper.
SGD uses the same learning rate for all parameters, i.e. 7)2 = T. Although SGD is simple and offers no adaptation, it has a convergence rate of O(1/vT) with either constant, increasing, or decreasing learning rates (Ghadimi & Lan, 2013), and is widely used when training deep networks, especially CNNs (He et al., 201 6a; Huang et al., 2017). At the heart of its convergence proof is the fact that Es, [ov, 7p ge] a4 fw,)
Popular adaptive methods such as RMSProp (Dauphin et al., 2015), AdaGrad (Duchi et al., 2011), and Adam (Kingma & Ba, 2015) have т)
1 vor+e*
where 2 Rd is given by:
Ut = -2, + (1 32,09 and 1o = 0.
(6)
As it is an estimate of the second moments of the gradients, the optimizer designates smaller learning rates for parameters with larger uncertainty in their stochastic gradients. However, in this setting ") and 8t are no longer independent, hence Eg, [og @ ge] * 0g E,,, [nd @ ( This "bias" cause RMSProp and Adam to present convergence issues, even in the stochastic convex setting (Reddi et al., 2018).
Recently, Zaheer al. (2018) showed that, with constant learning rate, RMSProp and Adam have convergence rate of O(o² + 1/T), where o² suPwERd E.ND their result does not generally guarantee convergence. Chen et al. (2019) showed that AdaGrad and AMSGrad enjoy convergence rate OloogT/VD T/vT) when a decaying learning rate is used. Note that both methods constrain 1); in some form, the former with 32, with t), and the latter explicitly enforces it 2 ,y for all j < t (77: is point-wise non-increasing). In both cases, the method is less adaptive than Adam, and yet analyses far have not delivered convergence rate that matches SGD's.
V - V f())] hence
- 1/t (adaptability diminishes
4 SGD-LIKE CONVERGENCE WITHOUT CONSTRAINED RATES
We first take a step back to note the following: to show that Adam might not converge the stochastic convex setting, Reddi et al. (2018) 8) provide a stochas- tic linear problem where Adam fails to converge w.r.t. suboptimality. Since non-convex optimization evaluated w.r.t. norm of the gradients, a different instance is required to characterize Adam's behavior in this setting.
Algorithm DELAYED ADAM
Input: w1 E Rd. a, 0, S1, 32, E [0, 1)
1: Set mo 0, vo = 0
2: for / 1 to T do
3: Draw 8, D
4: Compute 9i = fe, (w:)
5:
m, = f1. + (1 B1,1).
The following result shows that even for a quadratic problem, Adam indeed does not converge to a sta- tionary point:
6:
T /ir 1tc
7:
wi+1 Wt 0t T/t 174
8:
Un = 32,11-1 + (1 - -3,1)
end for
Theorem 1. For any 0 and constant $2,1 32 E [0, 1). there is stochastic convex optimization
problem for which Adam does not converge stationary point.
3

---

Under review as a conference paper at ICLR 2020
Proof. The full proof is given in Appendix A. The argument follows closely from Reddi et al. (2018), where we explicitly present a stochastic optimization problem:
C 2 with probability
1+6
min f(w) D [w)]] wE(0.1]
fa(w)=
p
- w, otherwise
We show that, for large enough C' (as a function of 6, 32), Adam will move towards w = 1 where (1) 8. and that the constraint w [0, 1] does not make w 1 stationary point.
This result, like the one in Reddi et al. (2018), relies on the fact that 7/r and 8, are correlated: upon draw of the rare sample O the learning rate The decreases significantly and Adam takes small step in the correct direction. On the other hand, a sequence of common samples increases 7/ and Adam moves faster towards w 1.
Instead of enforeing Th to be point-wise non- non-increasing in t (Reddi et al., 2018), which forces the optimizer to take small steps even for a long sequence of common samples, we propose simply have be independent of s,. As an extra motivation for this approach, note that successful proof strategies (Zaheer et al., 2018) to analyzing adaptive methods include the following step:
Ee, Ie @ g.] E., 11/=11 + ?h- 7T-1) @ gi] T)- O V.((w)) + E., [(T - 7)-1)) @ gel
(8)
where bounding E.,, [nn 1)-1) ) ④ ge], seen as a form of bias, is a key part of recent convergence analyses. Replacing 7/2 by 7 in the update equation of Adam removes this bias and can be implemented by simply swapping lines of code (updating 7) after w), yielding a simple convergence analysis without hindering the adaptability of the method in any way. Algorithm provides pseudo- code when applying this modification, highlighted in red, to Adam, yielding Delayed Adam. The following Theorem shows that this modification is enough to guarantee SGD-like convergence rate of O(1 /T) in the stochastic non-convex setting for general adaptive gradient methods.
Theorem 2. Consider any optimization method which updates parameters as follows:
Wt++1 We Qx -h ② 9t
(9)
where 9t = (W.), 8t D, and at, are independent of st- Assume that fwi) f(w*)= S D. f(w) EE-D [fa(w]] is M-smooth, and [w))ll S Goo for all & E SSW E R.d. Moreover, let 7 Ei= O4 min; 11.5-
For 04 = 7V TMGZ
(F((Z)s)) = p(7) for all 8, S, then:
MDG
Σ1 1 + ot [!nell
S-DT [Vf(())))
ES-DT
(10)
t~P((s)
2T
E Yt min, Mets
where P assigns probabilities p(t) x 04 min, Tt.s
Proof. The full proof is given in Appendix B, along with analysis for the case with momentum S1 E (0, 1) in Appendix B.I, and in particular 31.+ B1/Vt, which yields a similar rate.
The convergence rate depends on ||vel and min; Th.s which are random variables for Adam-like algorithms. However, if there are constants H and L such that 0 < L S Th, S H xi for all and f, then rate of O(1/VT) is guaranteed. This is the case for Delayed Adam, where 1/(G2 + e) S Mr.i < 1/c for all t and i. Theorem 2 also requires that and 7) are independent of 8t, which can be assured to hold by applying a "delay" their respective computations, necessary (i.e., replacing N by 77-1, as in Delayed Adam).
Additionally, the assumption that pl p(()s:) = p(Z), meaning that single sample should not affect the distribution of Z = Σt= 04 min, 77... is required since P is conditioned on the samples S (unlike in standard analysis, where Z ΣT ag and a; is deterministic), and is expected hold T + co. Practitioners typically use the last iterate wT or perform early-stopping: in this case, whether the assumption holds not does not affect the behavior of the algorithm. Nonetheless, we also show in Appendix B.2 a similar rate that does not require this assumption to hold, which also yields a (1//TT) convergence rate taken that the parameter-win learning rates are bounded from above and below.
4

---

Under review as a conference paper at ICLR 2020
5 AVAGRAD: AN ADAPTIVE METHOD WITH ADAPTIVE VARIANCE
Now, consider the implications of Theorem 2 for Delayed Adam, where 7) VE. .te² and hence
Algorithm 2 AVAGRAD
Input: wi E ER 0re
0, 0,,,,,,,2,0 E [0, 1)
1/(G2 + <) S Tt. & 1/c for all and
1: Set mo 0, U0 = 0
For fixed Tt 7, chosen a-priori (that is, without knowledge of the realization of (m:)=1)) we can optimize y to minimize the worst-case rate using 11 d//²² and min, /r, G2 This yields =" (c), and a convergence rate of O(1/c), sug- gesting that, least in the worst case, e should be chosen to be as large as possible, and the learning rate a should scale linearly with (hence, also being large).
2: for t 1 to T do
3: Draw 8t DD
4: Compute = V fa, (w;)
5:
my = 11 (1 B1,2)9
6:
T)t vu-i+e W/++1
7:
T1
① m
/
8:
U, = 1-- + (1 32,1
9:
end for
What if we allow Tt vary in each time step?
For example, choosing "t = vd/ ||mell yields convergence rate with a linear dependence on (+E min, ne.s
While using 1/(G₂ + <) S Tt, S 1/c we see that in the worst-case this is also O(1/c), this dependence differs from the one with fixed 7/2 = y in few aspects. Most notably, if consider different scalings of т)
S Tva E min: n1.2
max; 7n..2
- (e.g., small and Vee-i+e
varying vt-1). 1), the convergence rate with fixed y can get arbitrarily worse, while for 7 vd/ |/vell 1, while for fixed y get dependence Σ 1+7"m which again can be large if ne is either large or small. Eis1 77
remains unchanged. In particular, for the case d = 1, we have (+ Ei min, Ne.
1==
[ive
Lastly, multiplying the learning rate by vd/ ||vell removes its dependence on e in the worst-case setting, making the two hyperparameters more separable.
The choice Yt vd/ Inell. motivated by the above facts, yields method which name AvaGrad Adaptive VAriance Gradients, presented as pseudo-code in Algorithm 2 with the proposed scaling highlighted in red. We call it "adaptive variance" method since, if we scale up down the variance of the gradients, and hence also i and Yt, the convergence guarantee in Theorem 2 does not change, while for fixed learning rate (as is not uncommonly done in practice, except for discrete decays during training (Zagoruyko & Komodakis, 2016; Merity et al., 2018)) it can get arbitrarily bad.
6 EXPERIMENTS
6.1
SYNTHETIC DATA
To illustrate empirically the implications of Theorem I and Theorem 2, we set up synthetic stochastic optimization problem with the same form as the one used the proof of Theorem
999 w² w, otherwise
2 with probability
0.002
min f(w)= B[)(ww) wE(0,]]
fa(w)
(11)
This function has a stationary point w* = 1-0.002 1 and satisfies Theorem 1 for 31 = 0, B2 =
999-0.00 0.002 2.
0.99, e = 10-8 We proceed to perform stochastic optimization with Adam, AMSGrad, and Delayed Adam, with constant learning rate o; 10-5 For simplicity, let P be uniform over (1,...,77 T)), since a₁ is constant.
Figure 1 shows the progress of Ei= wy and 2 Er [V 2| for each iteration t: as expected, Adam fails to converge to the stationary point w", while both AMSGrad and Delayed Adam converge. Note that Delayed Adam converges significantly faster, likely because it has no constraint the learning rates.
5

---

Under review as a conference paper at ICLR 2020
1.0
1.0
0.8
0.8
Adam
AMSGrad
0.4
0.4
Delayed Adam
Adam
0.2
AMSGrad
0.2
Delayed Adam
0.0
0.0
t
1e7
t
1e7
Figure 1: Plots of Adam, AMSGrad, and Delayed Adam trained the synthetic example in Equation 11, with stationary point at w" R 0.5. Left: The expected iterate sampled uniformly from (Wi..... we). for each iteration As predicted by our theoretical results, Adam moves towards w = with | [ww)ll = 1. while Delayed Adam converges to w". Right: The expected norm squared of the gradient, for w randomly sampled from (wi....,w:] w... Delayed Adam converges significantly faster than AMSGrad, while Adam fails to converge.
6.2 IMAGE CLASSIHCATION WITH CNNS
Our theory suggests that, in the worst case, e should be chosen large as possible, at which point the learning rate should scale linearly with it. As first experiment to assess this hypothesis, we analyze the interaction between a and when training Wide ResNet 28-4 (Zagoruyko & Komodakis, 2016) on the CIFAR-10 10 dataset (Krizhevsky, 2009). Our training follows Zagoruyko & Komodakis (2016): images are channel-wise normalized, randomly cropped, and horizontally flipped during training. The learning rate is decayed by a factor of 5 at epochs 60, 120 and 160, and the model is trained for a total 200 epochs with a weight decay of 0.0005. Appendix C describes additional experimental details.
use a validation set of 5,000 images to evaluate the performance of SGD and different adaptive gradient methods: Adam, AMSGrad, AdaBound (Luo et al., 2019), AdaShift (Zhou et al., 2019), and our proposed algorithm, AvaGrad. Additionally, we also assess whether performing weight decay as proposed in Loshchilov & Hutter (2019) instead of standard T.2 regularization positively impacts the performance of adaptive methods: we do this by also evaluating AdamW W and AvaGradW.
We each adaptive method with different powers of 10 for c, from its default value 10-8 up to 100, which is large enough such that adaptability should be almost completely removed from the algorithm. We also vary the learning rate of each method with different powers of 10, multiplied by 1 and 5 (e.g., 0.05, 0.1, 0.5, 1.0, 1.0....). Figure 2 shows the results for Adam and AvaGrad. Our main findings are twofold:
The optimal for every adaptive method is considerably larger than the values typically used in practice, ranging from 0.1 (Adam, AMSGrad, AvaGradW) to 10.0 (AvaGrad, AdamW). For Adam and AMSGrad, the optimal learning rate is a = 0.1, value 100 times larger than the default.
All adaptive methods, except for AdaBound, outperform SGD terms of validation performance. Note that for SGD the optimal learning rate is 0.1, matching the value used in work such as He al. (2016a); Zagoruyko Komodakis (2016); Xie al. (2017), which presented state-of-the-arr results at time of publication.
However, the fact that adaptive methods outperform SGD in this setting is not conclusive, since they are executed with more hyperparameter settings (varying e as well as a). Moreover, the main motivation for adaptive methods is to be less sensitive to hyperparameter values; performing extensive grid search defeats their purpose.
Aiming for fair comparison between SGD and adaptive methods, also train Wide ResNet 28- 10 on both CIFAR-10 and CIFAR-100, 100, evaluating the test performance of each adaptive method with its optimal values for and found in the previous experiment. For SGD, confirmed that

---

Under review as a conference paper at ICLR 2020
Adam
AvaGrad
1000
c0
30000.0
69
500.0-
5000.0
50
50
50.0
0.5
0.55
30
0.005
0.05
-20 0.005
20
0,0009
Se407
10
0.0003
100
16:20
1e-06
3.0001
0.01
100.0
Figure 2: Validation error Wide ResNet 28-4 trained on the CIFAR- 10 dataset with Adam (left) and AvaGrad (right), for different values of the learning rate and parameter where larger yields less adaptability. Best performance achieved with small adaptability (c 0.001).
Table 1: Test performance of SGD and popular adaptive methods in benchmark tasks. Red indicates results with the recommended optimizer, following the paper that proposed each model, and any improved performance is given in blue. The best result for each task is in bold, and numbers in parentheses present standard deviations of runs for CIFAR.
CIFAR-10 10
CIFAR-I00
ImageNet
Penn Treebank
Method
(Test Err %)
(Test Err %)
(Top-1 Val Err %)
(Test Bits per Character)
SGD
3.86 (0.08)
19.05 (0.24)
24.01
1.238
Addm
3.64 (0.06)
118.96 (0.21)
23.45
1.I82
AMSGrad
3.90 (0.17)
18.97 (0.09)
23.46
1.187
AdaBound
5.40 (0.24)
22.76 (0.17)
27.99
2.863
AdaShift
4.08 (0.11)
18.88 (0.06)
N/A
1.274
AdamW
4.11 (0.17)
20.13 (0.22)
27.10
1.230
AvaGrad
3,80 (0.02)
18.76 (0.20)
23.58
1.179
AvaGradW
3.97 (0.02)
19.04 (0.37)
23.49
1.175
the learning rate 0.1 still yielded the best validation performance with the new architecture, hence the fact that we transfer hyperparameters from the Wide ResNet 28-4 runs does not unfairly advantage adaptive methods in the comparison with SGD. With larger network and different task (CIFAR-100), this experiment should also capture how hyperparameters of adaptive methods transfer between tasks and models.
On CIFAR-10, SGD achieves 3.86% test error (reported as 4% in Zagoruyko Komodakis (2016)) and is outperformed by both Adam (3.64%) and AvaGrad (3.80%). On CIFAR-100, SGD (19.05%) is outperformed by Adam (18.96%). AMSGrad (18.97% AdaShift (18.88%) AvaGrad (18.76%) and AvaGradW (19.04%). We believe these results surprising, they show that adaptive methods can yield state-of-te of fe--hhe-n art performance when training CNNs as long as their adaptability is correctly controlled with c.
As final evaluation of the role of adaptability when training convolutional networks, we repeat the previous experiment on the ImageNet dataset (Russakovsky et al., 2015), training ResNet 50 (He et al., 2016b) with SGD and different adaptive methods, transferring the hyperparameters from our original CIFAR- results. Training follows Gross & Wilber (2016): the network is trained for 100 epochs with a batch size of 256, the learning rate is decayed by factor of 10 epochs 30, 60 and 90, and weight decay of 0.0001 is applied. SGD yields 24.01% % top-1 validation error, underperforming Adam (23.45%) AMSGrad (23.46%) AvaGrad (23.58% (8%) and AvaGradW (23.49%). Again, note that the hyperparameters used for SGD match the ones He al. (2016a), He et al. (2016b) and Gross & Wilber (2016): 6): initial learning rate of 0.1 with momentum of 0.9. Table summarizes.
7

---

Under review as a conference paper at ICLR 2020
Adam
AvaGrad
20
20
2000
18
2.0
1/
200
17
0.-
1.6
155
20.0
1.5
-15
0.002
04007
02-
C.01
1e:00
16-00
0.0001
6.01
200.6
Figure 3: Validation bits cese-eer-chaaaaae (lower is better) of a 3-layer LSTM with 300 hidden units, trained on the Penn Treebank dataset with Adam (left) and AvaGrad (right), for different values of the learning rate a and parameter where larger yields less adaptability. Best performance is achieved with high adaptability (c < 0.0001).
6.3 LANGUAGE MODELLING WITH RNNS
is perhaps not very surprising that to perform optimally in the image classification tasks studied previously, adaptive gradient methods required large values of and hence were burely adaptive. Here, we consider a task where state-of-the-ar results are typically achieved by adaptive methods with low values for language modelling with recurrent networks. In particular, character-level language modelling on Penn Treebank dataset (Marcus et al., 1994; Mikolov et al., 2010) with LSTMs, following Merity et al. (2018). The model is trained for 500 epochs, and the learning rate is decayed by 10 at epochs 300 and 400. A batch size 128, a BPTT length of 150, and weight decay of 1.2 10-6 used, along with dropout.
perform
We evaluate the validation performance of SGD, Adam, AMSGrad, AdaShift, AdaBound, Adam W, AvaGrad and AvaGradW with varying learning rate and adaptability parameter when training 3-layer LSTM with 300 hidden units in each layer. Figure 3 shows that, in this task, smaller values for are indeed optimal: Adam, A.SGGrad and AvaGrad performed best with learning rates for both Adam and AMSGrad, a = 0.002, agree with the value used in Merity et al. (2018). Both AvaGrad and AvaGradW performed best with a 200: the former with 10 the latter with c = 10-5
10 The optimal
Next, we train a 3-layer LSTM with 1000 hidden units per layer (the same model used Merity et al. (2018), where it was trained with Adam), choosing values for which yielded the best validation performance in the previous experiment. For SGD, we again confirmed that learning rate of 20 performed best on the validation set. Table 1 (right column) reports all results.
In this setting, AvaGrad and AvaGradW outperform Adam, achieving bit- bit-per-characters of 1.179 and 1.175 compared to 1.182.
6.4 HYPERPARAMETER SEPARABILITY AND DOMAIN- NOMAIN-INDEPPNDENCE
One of the main motivations behind AvaGrad is that it removes the dependence between the learning rate a and the adaptability parameter e, at least in the worst-case rate of Theorem 2. Observing the heatmaps in Figure 2 and 3, we can see that indeed AvaGrad offers more separability between and c, when compared to Adam. For example, for e 2 0.0001, has little to no interaction with the learning rate opposed to Adam where the optimal increases linearly with For language modelling on Penn Treebank, the optimal learning rate for AvaGrad was a 200 for every choice of e, while for image classification CIFAR-10 10, we had 1.0 for all values of except for E {10-6, 100). This suggests that AvaGrad enables a grid search over a and (with quadratic complexity) to be broken into two line searches over and separately (linear complexity).
8

---

Under review as a conference paper at ICLR 2020
7 CONCLUSION
As neural architectures become more complex, with parameters having highly heterogeneous roles, parameter-wise learning rates are often necessary for training. However, adaptive methods have both theoretical and empirical gaps, with SGD outperforming them in some tasks and having stronger theoretical convergence guarantees. In this paper, we close this gap, by first providing a convergence rate guarantee that matches SGD's, s, and by showing that, with proper hyperparameter tuning, adaptive methods can dominate in both computer vision and natural language processing tasks. Key to our finding is AvaGrad, our proposed optimizer whose adaptability is decoupled from its learning rate.
Our experimental results show that proper tuning the learning rate together with the adaptability of the method is necessary to achieve optimal results in different domains, where distinct neural network architectures are used across tasks. By enabling this tuning to be performed linear time, AvaGrad takes leap towards efficient domain-agnosti training of general neural architectures.
REFERENCES
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein GAN. arXiv e-prints, 2017.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of adam-type algorithms for non-convex optimization. ICLR, 2019.
Y. Dauphin, H. de Vries, Chung, and Bengio. Rmsprop and equilibrated adaptive learning rates for non-convex optimization. corrL, 2015.
J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. ICML, 2011.
Saced Ghadimi and Guanghui Lan. Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming. SIAM, 2013.
Sam Gross and Martin Wilber. Training and investigating residual nets. https://githunt com/ facebook / fb. resnet torch, 2016
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. CVPR, 2016a.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. ECCV, 2016b.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 1997.
Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks. CVPR, 2017.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. ICLR, 2015.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. 2019.
Liangchen Luo, Xiong, Yuanhao, Liu, Yan, and Xu. Sun. Adaptive gradient methods with dynamic bound of learning rate, ICLR, 2019.
Mitchell Marcus, Grace Kim, Mary Ann Marcinkiewicz, Robert MacIntyre, Ann Bics, Mark Ferguson, Karen Katz, and Britta Schasberger. The penn treebank: Annotating predicate argument structure. In Proceedings of the Workshop on Human Language Technology, 1994.
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and Optimizing LSTM Language Models. arXiv e-prints, 2017.
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. An Analysis of Neural Language Modeling at Multiple Scales, arXiv e-prints, 2018.

---

Under review as a conference paper at ICLR 2020
Tomas Mikolov, Martin Karafiát, Lukás Burget, Jan Honza Cernocký, and Sanjeev Khudanpur. Recurrent neural network based language model. INTERSPEECH, 2010.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. ICLR, 2018.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael S. Bernstein, Alexander C. Berg, and Fei-Fei Li. Imagenet large scale visual recognition challenge. IJCV, 115(3), 2015.
Nitish Srivastava, Geoffrey E. Hinton, Alex Krizhevsky, llya Sutskever, and Ruslan Salakhutdinov. Dropout: simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15(1), 2014.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention All You Need. arXiv e-prints, 2017.
Ashia C. Wilson, Rebecca Roelofs, Mitchell Stern, Nathan Srebro, and Benjamin Recht. The Marginal Value of Adaptive Gradient Methods in Machine Learning. NIPS, 2017.
Saining Xie, Ross B. Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual transformations for deep neural networks. CVPR, 2017.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. BMVC, 2016.
Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. NIPS, 2018.
Zhiming Zhou, Qingru Zhang, Guansong Lu, Hongwei Wang, Weinan Zhang, and Yong Yu. Adashift: Decorrelation and convergence of adaptive learning rate methods. ICLR, 2019.
10

---

Under review as a conference paper at ICLR 2020
Appendix
A PROOF OF THEOREM
Proof. Consider the following stochastic optimization problem:
C 2 with probability
1+5
min f(w) = EnnD [fs] fa(w) =E|0,1]
(12)
w, otherwise
where C
1-
wIVI-5 Note that Vf(w) pCw - (1-p). and f' minimized at
w
1-P cp
c1+
The proof follows closely from Reddi's linear example for convergence in suboptimality. We assume w.l.o.g. that 31 0. Consider:
9t
9t
u++1
Wt
-17
11
(13)
/ +e
1 + +1 (1- B2)g +e
E
A
W1++1
9t
-
7
17
VB20r-1 + (1 - -32) +
(14)
-Cw
pE
+11 - p)E
B201 + (1 - C2) +
12 + (1 B2)
+
Ti
T2
where the expectation is over all the randomness in the algorithm up to time as all expectations follow in the proof. Note that 7i = for wi O. For w. >> 0 we bound Ti as follows:
-Cw
Ti 2 (1 32)
(15)
VI - B2
Hence, Ti 2 min(0,
-1 -
V1-B3
As for T2, we have, from Jensen's 's inequality:
[T2]
(16)
/B2E [v--1] +
B2
Now, remember that w (1 B2)
Σ(=]
1-1 1 hence: i==
[-1
E 1111l
(1 32)
8/
9
1-1
=(1 - 32)
Σ
8
at-i-1 (1 1 C (wl))
(17)
i=1
[-1
< (1- 82) Σ
8
at-i-1 (1 (1-p-) + 2C
1=1
< (1 - 8
8/ )
p pC < (1+
and thus:
E [T
(18)
3 8)C + 1 3g +e
11

---

Under review as a conference paper at ICLR 2020
Plugging in the bounds for T₁ and T2 in Equation 14:
E A 1 -1
B2 + (1 (1- V 8)C + 1 B2 +
1 1+0
(19)
7 C+1
1 while the above quantity becomes non- Hence, for large enough C, and C 6, w negative, and hence EE [w]] 2 w1. In other words, Adam will, in expectation, drift away from the stationary point, towards w = 1, at which point [ = 6. For example. 5 = implies that lim + Σ E [V)()]] = 1. To see that w = is not a stationary point due to the feasibility constraints, check that VS(1) = > that is, the negative gradient points towards the feasible region.
I+3
B PROOF OF THEOREM 2
Proof. Throughout the proof we use the following notation for clarity:
H max T
L min nt.
(20)
We start from the fact that / is M-smooth:
M | well?
f(wi+1) - (w:) + (Vf(w)) ut- wi)
(21)
and use the update W++1 = W02 a4 : ?) m
af
f((++1) S f(we) - ai (V f(wr) mi o mn) +
||m, 3 nell
2
a M.M ||eell
S f(w)) - at (V f(w)), m, mm
2
s (((w)) - . (w]) m. or B1.0) (VI(w)) On) a af ||me 1
a2MG2 1|
S ((w)) a. (w)) 1| 10 mz 31,,) (V/((x), 2 hm)
$ f(w)) + C a1 - B1.) (V)(())) @ mm) + a M. |nd]
(22)
where in the first step we used the fact that ||m c 1 Σi_ mi S max, mi Σi= nh. S G ||r=|] in the second we used m, = ( ft. in the third we used Cauchy- Schwwrz,
and in the fourth we used [ < G2, along with ||m @ nell = v V m 1 <
max; Mhi v Ei mi_1, S G2H,
Now, taking the expectation over 8t, and using the fact that E., [oi] = V (w:), and that f/. a₁ are both independent of se:
a.M |nd 2
Esg [f(w++1)] < f(m) + a,Br,,G3H ax(1 - B1,) (V)(w,), Vf(w:) 3 m²) +
< f(w) + a. - a 3,) [V L, a²MG2
||
2
(23)
where in the second step we used 31, - 31 and (V.(w,) Vf(w)) = Ei V
vf(w)
2
min, nh. Σd_ (f( L, [V]((w]]
Re-arranging, we get:
a (1 [Vf((:)) < f(w) E., [f(())))] + G.H,, M,M
11
(24)
2
12

---

Under review as a conference paper at ICLR 2020
Now, defining p(t) ock 2
where Z = Ei= arLe, dividing by Z(1 31) and summing over t:
T
T Σ
f(wr) - Es, [f(w]+1)) tn a a/M ||
Σ pt) (V) v Z(1 31) 1=1
2
(25)
Now, taking the conditional expectation over samples S given Z:
Es
Σ p(t) [V=()))) 2
$
Es [f(w))]Z -Es [.., [f [f(w++)) (w)+1))l1])
2(1 - 31)
T
0r G. + af ll 2 (2)
+
Σ
E
2
t=1
[ss [[(n)) - .Es [s 1)12
7(1
B1)
(26)
Crll,, afMG² llmell? (2))
Σ
E
t=1
(f(w)) - -Es [f(WT+1)
Z(1 31)
ar,1,, afMG2 |m 2
Σ
E
2
where in the second step used Es [R,, (f(we+))) )} |2| Ess (s(w++1) )] which follows from the assumption that p( (1))) = Z)), and the third step follows from a telescoping sum, along with the fact that Es [f(w]) f(wi). Now, using f(w1) Es [f(T++1] - f(w1) - -(ww)) D:
Es
T
p(t) [VF 2
< Z(1 31)
(D+
Es
G, +
a MG 11 11
Z 1
)
2
(27)
Then, taking the expectation over Z:
1
T
D
Mf |lnal ]
Es
p(t) V [f (w:)
S
+ HH
(28)
Z(1
31)
T
2D Now, let O4 =?tV
TMG2
T
Es
Σ p(1) (w:))))
S SEs
1
Σ
+
2D G..H.
+2 ltvell
7(1 - 31)
T
TMG2
T
2dTG2
< E
1+
+ + Immll
T 2(1 31) t=1
MD
(29)
where used the fact that G2 Go Vd.
13

---

Under review as a conference paper at ICLR 2020
Now, recall that Z Σ arle
2D TMG
Ei=l Ncce
V
Em 14 HaV
2
+ |l
Es Σ p(t) [V
< Es
1
MDGz
MD
(1 B1)
27
E1=1 7elx
E1=1 1 1
2dTGG
+ + ||
MDG
Es
(1 31)
27
E1=1 7chx
(30)
Setting 31,1 81 0 and checking that Σt= p(t) [ -EmP(()s)) [IV f (w)) (w)))l
([V((w))l'
MMDG
Σ/= 1 1+ 7/ ||elll
[VT((,))] S
(31)
SnD2 t- (((()
27
Σ1=1 Mohe
Recalling that L, min, Thos proves the claim.
B.
THE CASE WITH FIRST-ORDER MOMENTUM
For the case $1.0 O, assume that B1.
& vi
in Equation 30:
T
MDG2 27
Σ
T
Br 1
1
v
2dTC?
MD
78 || 1
Es
Σ p(t) [+
5
Es
(1
31)
Ex=1 Teha
MDG
B1
2dT MD
(max, y H1)
ET= vi Mi=1 (1+ 72 llmell
+I
Ess
(1 31)
2T
E1=1 Th
MDG²
2T
2dG MD
(max, 7H) +IT (1 [1+ llmill?))
Es
(1 31)
2T
Et=1 Ych,
(32)
where in the last step we used ET= V8 S 2VT.
1
Similarly to the guarantee in Equation 31, we can show a O(1/vT) convergence rate if we further assume that there exist constants H and such that < S Mr. S H xo for all and (i.e., the parameter-wise learning rates are bounded away from zero and also from above), and that y is bounded similarly. For example, having ?t yields:
Es Σ p(t) (
1
MDG2
Es
2TH
2dG2 MD
+ -T (1 (1+ 2dH2)
(1
31)
2T
Σ1=17
MDG2
2dGG
7-1 42+
MD + 7dH2
T(1 - -1)
2T
(33)
where in the first step used 1/n/11 < dH², H, H, and L2 2 L.
Note that for any constant the above
14

---

Under review as a conference paper at ICLR 2020
B.2 THE CASE WITH UNCONDITIONAL DISTRIBUTION OVER ITERATES
To show similar bound without the assumption that p( st) ) - p(),, we can alternatively bound Lr
and |leell using the worst case over possible samples S. From (24) we have, with SL. 0:
aj (sups lImell?)
(nf Ta on 31) (w(w)))1 S (ww)) Es, [f(W++1) 9
(34)
2
Now, define p(t) Og (infg Tx)) Z with Z = = 04 (infs T4) instead. As long as 0z does not depend on S, is no longer a random variable. Following the same steps as above leads to the following:
Σl + 78 (sups Imell
MDG² 2T
[[ $ (CP(()
(35)
SND?
E1=1 V/ (infs Lc)
In particular, if there are constants H and L such that 0 < L S n1ss S H < do for all i and I, can
bound sups ||nell 2 s dH² and inf L 2 L, yielding:
[IVf(w)))
MDG
Σ 1 1+ 1
E S (w(())
$
(36)
2T
-E 7t
Hence a O(IvVT) follows long as 7/t can be upper and lower bounded accordingly by constants.
C EXPERIMENTAL DETAILS
C.I CIFAR
The CIFAR-10 and CIFAR-I00 datasets (Krizhevsky, 2009) consist of 60,000 RGB images with 32 x 32 pixels, with standard split of 50,000 and 10,000 training and test images, sampled from 10 and 100 classes, respectively. We pre-process the dataset with channel-wise normalization using statistics from the training set, and for data-augmentatioon we flip each image horizontally with 50% probability, along with random cropping, achieved by first padding 4 black pixels to each edge of the image and then extracting a random 32 x 32 crop.
For the hyperparameter exploration with a Wide ResNet 28-4, we measure performance on validation set of 5,000 images sampled from the training set, while for the final results with the Wide ResNet 28- 10, we report results on the test set.
Each Wide ResNet is trained with batch size of 128 for total of 200 epochs a single GPU, with the learning rate being decayed by a factor of 5 at epochs 60, 120 and 160. A weight decay 0.0005 is used with every optimization method. For SGD, methods, we use 31 = 0.9, B2 = 0.999, as suggested in their respective papers. For AdaBound, we the default a" 0.1 and 7 10-3 3 For AdaShift, use the default 10.
momentum of 0.9, while for adaptive
C.2 IMAGENET
The ILSVRC 2012 datasets (Russakovsky et al., 2015) is composed of 1.2M training and 50,000 validation RGB images, sampled from total of 1,000 classes. We train a ResNet 50 (He et al., 2016b), and report results using single-crops of 224 x 224 images for evaluation. We follow Gross & Wilber (2016) for data-augmentation and training specifics: in particular, we decay the learning rate by factor of 10 at epochs 30, 60 and 90, and use weight decay of 0.0001. We use 4 GPUs for training, with total batch size of 256 (64 per GPU).
C.3 PENN TREEBANK
We follow Merity et al. (2018) for both the model and optimization details for the Penn Treebank dataset (Mareus et al., 1994) for character-level language modelling (Mikolov et al., 2010). Again,
15

---

Under review as a conference paper at ICLR 2020
measure validation performance for the small-scale experiments, and test performance for the large-scale ones.
More specifically, train 3-layer LSTM (Hochreiter & Schmidhuber, 1997) with embedding size of 200, and decay the learning rate by a factor of 10 at epochs 300 and 400, while the model is trained for total of 500 epochs. We regularized with weight decay of 1.2 x 10-6, a weight dropout (Merity et al., 2017) of p = 0.5, and dropout (Srivastava al., 2014) of p 0.1 for the input and output layers and 0.25 for the hidden-layer.
batch size of 128 and BPTT length of 150. The model is
16


Reviews:
[{"review_id": "rklCY7VJ9r", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "In this paper, the authors present a new adaptive gradient method AvaGrad. The authors claim the proposed method is less sensitive to its hyperparameters, compared to previous algorithms, and this is due to decoupling the learning rate and the damping parameter.\n\nOverall, the paper is well written, and is on an important topic. However, I have a few concerns about the paper, which I will list below.\n\n1. The fact that adaptive gradient methods converge with a fast rate when the sum in the denominator is taken till the t-1th iterate has appeared in previous papers before [1]. The convergence rate analysis for this case is fairly simple, and I am not sure if analyzing RMSProp/Adam in this setting should be considered a significant contributions of the paper.\n\n2. The proposed algorithm AvaGrad is a simple but interesting idea. I have a number questions about the experimental evaluation though, which makes it hard for me to evaluate the significance of the results presented:\n\na) Was momentum used with SGD?\n\nb) How is the optimal hyperparameters (learning rate and damping, i..e, epsilon, parameters) selected?\n\nc) Do any of these conclusions change when trying out a very small or very large batch size?\n\nd) I am not convinced that using the same optimal hyperparams as the WRN-28-4 task on the WRN-28-10 and ResNet50 models is a reasonable experiment. Why is this a good idea? While this does support the claim that adaptive gradient methods are less sensitive to hyperparameter settings, but makes the other claim about AvaGrad generalizing just as well as SGD weaker?\n\ne) One of the key claims that adaptive gradient methods generalize better when using a large damping (epsilon) parameter has appeared in previous papers as well [2, 3].\n\n\nOverall, in my view, this is a borderline paper mostly because I think a number of the results presented have been shown in other recent papers. My score reflects this. However, I think decoupling the learning rate and the damping parameter by normalizing the preconditioner is a simple but interesting idea, and I am willing to increase my score based on the discussion with the authors and other reviewers.\n\n\n[1] X. Li and F. Orabona. On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes. In AISTATS 2019\n[2] M. Zaheer, S. Reddi, D. Sachan, S. Kale, and S. Kumar. Adaptive methods for nonconvex optimization. in NeurIPS 2018.\n[3] S. De, A. Mukherjee, and E. Ullah. Convergence guarantees for rmsprop and adam in non-convex optimization and an empirical comparison to nesterov acceleration. arXiv:1807.06766, 2018.\n\nA few more minor comments:\n\n1. The authors say that methods like AMSGrad fail to match the convergence rate of SGD. But this statement seems misleading since it is not clear whether the worse rate is due to the analysis (which gives an upper bound) or the algorithm?\n\n2. In the related work section, the authors discuss convergence rates of algorithms with constant and decreasing step sizes together. This can be confusing to the reader, and it is best to explicitly mention the setting under which the different results were derived.\n\n=======================================\n\nEdit after rebuttal:\nI thank the authors for the detailed response and for the updated version of the paper. After discussion with other reviewers, we are still not convinced that the hyperparameter tuning in the experiments (especially the baselines) is rigorous enough. This is especially important given that this paper proposes a new optimizer. We are also concerned about the novelty of the results, and believe most of these results have appeared in previous work. So I am not increasing my score. I would encourage the authors to do a more rigorous experimental evaluation of the proposed algorithm.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "r1lrEWi3YB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:\nThis paper proposes a new adaptive method, which is called AvaGrad. The authors first show that Adam may not converge to a stationary point for a stochastic convex optimization in Theorem1, which is closely related to [1]. They then show that by simply making $eta_t$ to be independent of the sample $s_t$, Adam is able to converge just like SGD in Theorem2. Theorem2 follows the standard SGD techniques. Next, they propose AVAGRAD, which is based on the idea of getting rid of the effect of $\\epsilon$. \n\nStrength:\nThe experiment results are impressive. They show that Adam can outperform SGD on vision tasks.\nRecently, people have found out that $\\epsilon$ is a very sensitive hyper-parameter. It is good to see some research directly addresses this problem. \n\nWeakness:\nThe word \"domain\" is confusing. \nIf the Adam-type algorithms are the delayed version in Table 1?\nIt is not compatible with AdamW. \nThe results on the image datasets seem too good to be true.\n\nImplementation Issue:\n***Many implementation details in the below discussion are different from the paper (e.g. hyperparameters and network architecture). So the following experiment results may not be used for assessment of the quality of the proposed method.***\nI tried the proposed Delayed Adam on CIFAR-10 using the codebase in (https://github.com/LiyuanLucasLiu/RAdam/tree/master/cifar_imagenet). The performance seems the same as Adam. Delayed Adam even leads to a *divergence* problem, especially with a large learning rate (0.03). The divergence problem never happens when using Adam and AdamW with the same hyperparameters.\nImplementation details: \n1. Replace the optimizer with the original PyTorch Adam implementation. (https://github.com/pytorch/pytorch/blob/master/torch/optim/adam.py) \n2. Swap line 96 and 108 as suggested in the paper. \n3. Modified line 89 (bias_correction2=1 - beta2 ** (state['step']-1)) \n4. Do not run line 97-107 when state['step']==1. \n5. Run the following code: python cifar.py -a resnet --depth 20 --epochs 164 --schedule 81 122 --gamma 0.1 --wd 1e-4 --optimizer adam  --beta1 0.9 --beta2 0.999  --checkpoint ./logdir --gpu-id 0 --model_name adam_003 --lr 0.03\n\nIf the authors can provide more implementation details, I would promote my rating. \ne.g., \n1. Are you still using bias correction in the proposed method? If so how do you use them?\n2. Do you update the model for the first step?\n\nReference:\n[1] On the convergence of adam and beyond\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HkgBFoJCKS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "In this paper the authors develop variants of Adam which corrects for the relationship of the gradient and adaptive terms that causes convergence issues, naming them Delayed Adam and AvaGrad. They also provide proofs demonstrating they solve the convergence issues of Adam in O(1/sqrt(T)) time. They also introduce a convex problem where Adam fails to converge to a stationary point.\n\nThis paper is clearly written and has reasonable experimental support of its claims. However in terms of novelty, AdaShift was published at ICLR last year (https://openreview.net/forum?id=HkgTkhRcKQ) and seems to include a closely related analysis and update rule of your proposed optimizers. In AdaShift instead of correcting for the correlation between the gradient and eta_t, they correct for the relationship between the gradient and the second moment term v_t. Could you further clarify the differences between the two, both in your approach to deriving the new update rule and the algorithms themselves? Additionally, their Theorem 1 could be compared to yours, but noting the differences for these seems less important. If the optimizers are unique enough, including AdaShift in your experiments would be very useful for demonstrating their differences.\n\nRegarding experiments, while it is true that adaptive methods are supposed to be less “sensitive” to hyperparameter choices, the limits of the feasible ranges for each hyperparameter could vary drastically across problems (especially, as previously demonstrated, across different batch sizes.) Thus, not retuning across experiments seems like it could negatively affect performance for any of the transferred hyperparameter settings. Instead of demonstrating hyperparameter insensitivity by carrying over hyperparameter settings, one could instead retune for each problem and show that a higher percent of hyperparameter combinations result in the same/similar best performance (similar to what is done in Fig. 2, but also showing a (1-dimensional) SGD version which would presumably contain fewer high performing settings.)\n\nSome additional comments:\n-The contribution of Theorem 1 is a nice addition to the literature.\n-Your tuning of epsilon is great! I believe more papers should include epsilon in their hyperparameter sweeps.\n-Scaling epsilon with step size makes sense when considering that Adam is similar to a trust region method, where epsilon is inversely proportional to the trust region radius. However, in section 5 implying that epsilon should be as large as possible in the worst case seems like an odd result given that this would always diminish your second moment term as much as possible, defeating the point of the additional Adam-like adaptivity. Can you comment on why this diminished adaptivity would be desirable in the worst case scenario analyzed?\n-The synthetic toy problem is much appreciated, more papers should start with a small, interpretable experiment.\n-Was SGD with momentum used? If not, this may not be a fair comparison, as I believe it is much more common to use momentum with SGD. If momentum was used, was the momentum hyperparameter tuned? If not, this may be advantageous to the Adam based methods, as they have more versatile adaptability and thus may not need as much care with their selection of momentum values.\n-Was a validation set used for CIFAR? You note in appendix C that there are 50k train and 10k test. You mention validation performance in the main text, so this is just double checking.\n-The demonstration in figures 2, 3 of decoupling the step size and epsilon in interesting! Given that the best performing values seem to be on the edges of the ranges tested, I would be curious if the trend continues for more extreme values of alpha and epsilon (one could sparsely search along the predicted trendlines.)\n\nNits:\n-“Vanilla SGD is still prevalent, in spite of the development of seemingly more sophisticated adaptive alternatives...” This could use some citations to back up the claim, because as far as I know it is much more common to use SGD with momentum and is actually rare to use vanilla SGD (the DenseNets and Resnets citations use momentum=0.9.)\n-It would be nice to highlight in color the diff from vanilla Adam in the Algorithm sections.\n-It is not super clear from the text how in eq 26 you get \\sum{E[f(w_t)|Z]} = f(w_1)\n-I may be misreading something, but I believe the H in the leftmost term in the last line of eq 33 should be an L.\n-In section 5, “for a fixed learning rate (as is typically done in practice, except for discrete decays during training)” seems like an overly broad claim, given that authors commonly use polynomial, linear, exponential, cosine, or other learning rate decay/warmups. Granted for some CIFAR and ImageNet benchmarks there are more common discrete learning rate schedules, but that does not seem to be the overwhelmingly prevalent technique.\n\nOverall, while this area of analyzing Adam and proposing modifications is a popular and crowded subject, I believe this paper may contribute to it if my concerns are addressed. While I currently do not recommend acceptance, I am open to changing my score after considering the author comments!\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes an adaptive gradient method for optimization in deep learning called AvaGrad.  The authors argue that AvaGrad greatly simplifies hyperparameter search (over e.g. ADAM) and demonstrate competitive performance on benchmark image and text problems.  In thorough reviews, thorough author response and discussion by the reviewers (which are are all appreciated) a few concerns about the work came to light and were debated.  One reviewer was compelled by the author response to raise their recommendation to weak accept.  However, none of the reviewers felt strongly enough to champion the paper for acceptance and even the reviewer assigning the highest score had reservations.  A major issue of debate was the treatment of hyperparameters, i.e. that the authors tuned hyperparameters on a smaller problem and then assumed these would extrapolate to larger problems. In a largely empirical paper this does seem to be a significant concern.  The space of adaptive optimizers for deep learning is a crowded one and thus the empirical (or theoretical) burden of proof of superiority is high.  The authors state regarding a concurrent submission: "when hyperparameters are properly tuned, echoing our results on this matter", however, it seems that the reviewers disagree that the hyperparameters are indeed properly tuned in this paper.  It's due to these remaining reservations that the recommendation is to reject.  
Decision: Reject