Acutum: When Generalization Meets Adaptability
Authors: Xunpeng Huang
Zhengyang Liu
Zhe Wang
Yue Yu
Lei Li
Venue:  (2020)
Keywords: optimization
momentum
adaptive gradient methods

Abstract: In spite of the slow convergence, stochastic gradient descent (SGD) is still the most practical optimization method due to its outstanding generalization ability and simplicity. On the other hand, adaptive methods have attracted much more attention of optimization and machine learning communities, both for the leverage of life-long information and for the deep and fundamental mathematical theory. Taking the best of both worlds is the most exciting and challenging question in the field of optimization for machine learning. 

In this paper, we take a small step towards such ultimate goal. We revisit existing adaptive methods from a novel point of view, which reveals a fresh understanding of momentum. Our new intuition empowers us to remove the second moments in Adam without the loss of performance. Based on our view, we propose a new method, named acute adaptive momentum (Acutum). To the best of our knowledge, Acutum is the first adaptive gradient method without second moments. Experimentally, we demonstrate that our method has a faster convergence rate than Adam/Amsgrad, and generalizes as well as SGD with momentum. We also provide a convergence analysis of our proposed method to complement our intuition. 

Under review as a conference paper at ICLR 2020
ACUTUM: WHEN GENERALIZATION MEETS ADAPT- ABILITY
Anonymous authors
Paper under double-blind review
ABSTRACT
In spite of the slow convergence, stochastic gradient descent (SGD) is still the most widely used optimization method due to outstanding generalization abil- ity and simplicity. On the other hand, adaptive methods have attracted much more attention of optimization and machine learning communities, both for the leverage of life-long information and for the deep and fundamental mathematical theory. Taking the best of both worlds the most exciting and challenging question the field of optimization for machine learning. In this paper, we revisit existing adaptive gradient methods from a novel point of view, which reveals a fresh un- derstanding of momentum. Our new intuition empowers us to remove the second moment Adam without the loss of performance. Based on our view, we propose novel optimization method, the acule adaptive momentum (Acutum). To the best of our knowledge, Acutum is the first adaptive gradient method without second moments. Experimentally. we demonstrate that our method has faster conver- gence rate than Adam/ Aaam/dd and generalizes as well as SGD with momentum. We also provide a convergence analysis of our proposed method complement our intuition.
INTRODUCTION
With the rapid development of neural network architectures (Goodfellow et al. 2016). training algo- rithms have attracted much more attention in the modern machine learning community. Due the network size and data amount increasing dramatically, calculating the full gradient of data and im- plementing the full gradient descent (GD) become computationally expensive. Therefore, stochastic gradient descent (SGD) (Robbins & Monro 1951) becomes the most practical optimization method for training deep neural networks (DNNs). computes the gradient corresponding to the mini-batch. Although SGD is computationally afford- able, needs a mechanism finettnee the learning rate, e.g., linear decay or exponential decay, to converge efficiently. In fact, it is pretty brittle to tune the learning rate dynamically with SGD.
each iteration, SGD samples mini-batch data and
To release the learning rate tuning burden of SGD and accelerate its convergence, several adaptive variants of SGD were proposed, including Adagrad (Duchi al., (011), Adadelta (Zeiler) 2012). RMSProp (Hinton et al. 2012). Adam (Kingma & Ba 2014), etc. The descent direction is element- wise automatically adapted by the first moment and the second moment with an exponential average of gradients. Such a descent direction has achieved great improvements in practice, while the funda- mental interpretation is still unclear. Besides, the theoretical regret analysis of these online learning algorithms has become completed gradually in convex objective settings. Due to the fast decay of exponential moving average, Adam cannot converge even in simple convex cases as shown in (Reddi) et al. 2019). Amsgrad (Reddi et al.) 2019) addressed this issue by keeping an extra non-decreasing sequence to buffer the fast decay.
On the other hand, although adaptive methods are easy to use and fast to converge, the generaliza- tion results cannot be as good as SGD (Wilson et al. 2017). Various works (Chen & Gu 2018 Luo et al. 2019) have been proposed to make algorithms not only converge faster but also has good generalization. However, these algorithms still inherit the second moment following Adam. Differ- ent from existing works, provide novel view for this problem by revisiting adaptive algorithms Through the view of direction angle between the descent direction and the momentum, we are able to demonstrate fresh understanding of momentum.

---

Under review as a conference paper at ICLR 2020
In summary, we propose new algorithm, called acute adaptive momentum (Acutum), to find adap- tive gradients with only the first moment. To remove the second moments safely, we investigate their properties by reformulating the proximal subproblem of Adagrad. The main observation is that sec- ond moments essentially penalize the projection of the current descent direction on the exponential moving average of previous gradients. The intuition allows Adam without any loss of performance. To the best of our knowledge, it is the first time to remove the second moments for adaptive gradient methods. As shown by our experiment, the proposed algorithm (Acutum) outperforms Adam/Amsgrad in wall-clock time while almost preserving the generalization ability of SGD.
remove second moments in
In particular, we make the following contributions:
We propose a new optimization algorithm called Acutum, which doesn't need to compute the second moments. To the best of our knowledge, it is the first time obtain the adaptive gradients with only the first moments. The intuition behind our algorithm is to remove second moments by attaching their purpose to the first moment through Adagrad's 's proximal subproblem inspiration.
We provide a regret convergence analysis of Acutum on the convex setting, based on the analysis of (Kingma & Bal 2014 Reddi al., 2019 Chen & Gu. 2018), and prove data- dependent regret bound, complementing our intuition.
We also provide various experiments about our proposed Acutum on training modern deep models. The experimental results empirically show that Acutum takes the best from both Adam-type methods and SGD.
Notations. In the rest of this paper, we assume any decision variables E IRd where denotes the
dimension of parameters. We denote the l2 norm of a given vector 0 by |0|| = v - 0.. With slightly abuse of notation, we write arithmetic symbols as element- operations for vectors, e.g., a² = až...." a/b = [ar/by /b,, a2/b2....) 1"" We denote by [x] the greatest integer less than or equal to the real number x. Given any integers I, y, where of O, we denote by (mod y) the remainder of the Euclidean division x by y. In the optimization setting, we denote by fe(-) the loss function when feed the i-th training data into feed a collection of samples, i.e., fs(-) == Eies fi(.). Given any point O E Rd and any convex set X' C IRdd we denote by xT (0) the projection of 0 onto X, i.e., arg nex || O||
model, also denote fs(-) when
2 RELATED WORK
The increasing size of deep neural networks and the amount of train data have dramatically induced the difficulty of training neural networks. The huge parameter size makes the landscape of neural networks more non-convex, and the amount of train data requires more computation resources to cal- culate the gradient. Therefore, all the facts urge researchers to design faster optimization algorithms for deep neural networks, while maintaining a reasonable generalization ability.
SGD-mmmentum is widely used in training large-scale neural networks while the excellent gener- alization ability of SGD is vulnerable to its learning rate. Meanwhile, researchers began to focus on the design of adaptive gradient methods for fast and simple optimizer. Adagrad proposed in (Duchi al. 2011) introduced the second moment obtain a self-adaptive learning rate, and hence freed researchers' hands of parameter tuning. The update rules of Adagrad can be formulated as follows:
g
0+11 = 0 -
V
where g, denotes the stochastic gradient, v, is the accumulation of gradient's second moments, i.e., V, = ? g? and a is the decreasing learning rate with aa = O(1/VB). Theoretically, Ada- grad improves the convergence of regret from O(Vd/VT) to O(1/VT) for the convex objectives with sparse gradients. However, in practice, people realize that adaptive gradient of Adagrad, i.e., g /V goes to very quickly due to v, accumulating to large number quickly as the algorithm proceeds. To make it through, RMSProp (Hinton et al. (012) introduced the exponential decay in the second moment control the accumulation speed of second moment in Adagrad. Furthermore,
2

---

Under review as a conference paper at ICLR 2020
Kingma & Ba 2014) incorporated the momentum into RMSProp and proposed Adam. The detailed procedure of Adam can be formulated as:
m V
0 = 0:
(1)
31) gr, and V, is the where m, is the exponential decay of momentum, i.e., m, --) gg. exponential decay of second moment, i.e., V, =
The faster convergence, robust hyper-parameter: and good performance on CV and NLP's tasks make Adam become one of the most successful optimizers these years. However, (Reddi et al.] 2019) showed Adam does not converge in certain convex cases, and proposed Amsgrad to correct the direction of Adam with imposing an increasing sequence of the second moment.
Although convergence, in theory, is fixed and the training speed is still fast, the generalization ability of adaptive algorithms still worse than SGD with momentum. Thus, there are a lot of studies to improve the generalization performance of Adam types algorithms. Almost all of these works try to make some connections between Adam and SGD-momentum such that the proposed algorithm converges faster like Adam while generalizing better SGD. For example, (Zhang al. (017) proposed a normalized direction-preserving Adam (ND-Adam). To make the direction of the gra- dients preserved, the authors adjusted the learning rate each weight vector whole, instead of each individual weight. It could be thought as an adjustment of learning rate dynamically in each iteration, instead of the learning rate decay. (Loshchilov Hutter 2017) proposed to modify Adam to decay all weights the same regardless of the gradient variances. (Keskar & Socher 2017) proposed improve the generalization performance by investigating a hybrid strategy that begins training with an adaptive method and switches to SGD when appropriate. The experimental results show that it obtains a better generalization with the convergence speed sacrificing. With a similar insight, (Luo et al., 2019) introduced the element-wise clipping technique to the second moment and proposed AdaBound, which allows the algorithm behavior switched from a clipped Adam to SGD-mome momentum as the algorithm proceeds. Besides, (Chen & Gu 2018) proposed Padam which tried to find the balanced state between Adam and GGD-momentum through tuning the order of the second moment in the update paradigm.
All the aforementioned methods try to find the connection between Adam and SGID-momentum, thus all these algorithms take the second moment adaptation as grant. The difference between previous works and ours is that we suggest to remove the second moment and propose an angle based algorithm, by revisiting the original idea of second moment adaptation. Such intuition could be of independent interest in the field of the optimization community.
3 THE ACUTE ADAPTIVE MOMENTUM ALGORITHM
In this section, we first revisit existing adaptive algorithms from a novel point of view, then intro- duce the intuition and provide the algorithm procedure of our method Acutum. The performance guarantees established in Section and evaluation results in Section validate our insights.
From the above section, one may notice that almost all the adaptive methods utilize second moments to adjust the individual magnitude of the updates. However, the efficient calculation of second moments, see Equation (1) is only proposed in Adagrad (Duchi al. 2011). Let's take look the original update paradigm of Adagrad:
0,+1 = - ag G. 1/2122 ge.
(2)
B.g., and gr denotes the stochastic gradient calculated at iteration т. Recall that in each iteration, SGD seeks the optimal solution of a subproblem constructed from quadratic approximation of the objective. Similarly, we can write the update procedure of Adagrad Equa- tion as
where G, - 1
0 = arg min (0 0,)² g:
(0
0²)²
1/2 T G
0.)
2a.
Ti
T2
where the first-order penalty Ti leads the parameter 0, to the opposite direction to the current gradi- g:. Note that Adagrad can adaptively adjust each individual dimension of 0, through introducing
3

---

Under review as a conference paper at ICLR 2020
G2 in the quadratic term T2, while SGD cannot. If we substitute the definition of G2 back into Equa- tion
T2 can be formulated as:
T
1 (0 0.)* G 0.) - 20t 204
1 1(0 (0 0.)²
Σ
2
8-8r
1/2
(0 (0-0.)-
(4)
By Young's incquality (Young 1912), we can obtain an upper bound of T2 as follows:
1
T2 1
|00
01112
(0 0,)" gr
(5)
80t
20
T3
Combining Equation and Equation
3
we can approximate the update rule of Adagrad as fol-
lows:
0 - 0,)² g ||
O R arg min (0 0z)"²
+
100
- 0cll
Sck:
200:
Ts
We can think the upper bound of the Adagrad subproblem as the combination of the standard first and second order penalty as Ti and T3, with a penalty for the projections of current descent 0, on the previous gradients gr, i..., T4.
With these observations in mind, a natural question comes out: how can understand in neural network training tasks or in general online learning tasks?
Before answering this question, we first describe the practical usage of training samples. The train- ing procedure of DNNs can be stated as follows. The algorithm randomly shuffles the whole training dataset and partitions into mini-batch equal size {Ão, A Ap-1 }. then the algorithm fed with the sample in fixed order, say, first Ag, then AG, and so on. The whole procedure repeats after each pass the whole dataset.
To make description more clear, take the first pass gradient calculated on iteration é by using the sample in subset Åc. where 0 S < p due to the first pass. Note that the loss function is the sum of whole samples, e.g., D" 1- (0),, if we utilize fa, (0t) to directly update parameters like SGD, e.g., 0.+1 = 0, a fa, (.)) the batch loss Eier, (0) will decrease since it aligns with the opposite direction of its gradient, e.g., (0.+1
example. Let V fA, (0:) be the
fa. (0:) = - (0))12 O. However, for loss corresponding to the sample not in Å.. it is highly possible that (0++1 0,)²v V fa, (O.) 0. On other words, only using - V fA, (0,) update direction will decrease the loss function corresponding to A but increase total loss function except A..
Ideally, there exists a direction 0.+1 ---1-66 -0 which orthogonal to fa, (0:) for any i * t (mod p), and forms acute angle with V fa. (0.), then 0 guarantee sufficient descent for the loss function corresponding to A₁ while not increase the loss function outside A4.
Then natural update of 0 to achieve the above goal can be obtained by solving the following sub-pr nub-problem:
arg min
02 0
0:112 + (0 0.)²² g:
(6)
8.1. 0, Ja. 0,) = 0, i (mod p).
In practice, however, the computational cost of computing V.,, (0:) for all is expensive in each
iteration. As natural solution, we can approximate Vía (0.) with previous gradients Sa, (0.), which is exactly gi calculated in Adagrad in iteration before iteration t, where i * (mod p).
Hence a soft margin variant of Equation (6) can be formulated as
0.11 arg min 0 0 - -0 C2,1
Σ
(0
0,) gr
+ +c (0 (0, g
(7)
4

---

Under review as a conference paper at ICLR 2020
which is exactly the formulation in Equation (5) and Equation (3) Thus, reasonably sider that Adagrad decreases the cumulative loss by guaranteeing a descent on the current batch loss while does not increase previous batch loss.
V fA, (0+) using previous gradients gi in Adagrad performs well in practice, there is still large accuracy gap. For example, let gt-1 and gt-2 denote the gradients VI (0)-1) and V (A respectively. It is often the case that the approximation error between V (0,) and gt-1 1 smaller than that between V 2 (0.) and gr-2, assuming the ob- jective is local smoothness In other words, the approximation accuracy g, to fa, decays as 7 decreases. Inspired by this observation, we substitute the arithmetic average in Equation (7) exponential moving average and reassign the coefficients of g- like Adam/momentum methods,
Although the approximation
then Equation 7 becomes
0++1 arg min 02 1 02
0.)" (0-
+ c (0 01)" gr.
T=1
This is what RMSProp actually does. Therefore, we obtain the same optimization intuition of RM- SProp Adagrad but add weight of the approximate gradient according to its approximation accu- racy.
adaptive momentum method. Let m, denote the approximated gradient of the previous batch loss at current parameters. With the following observation: (i) if 0; θ.+1 forms acute angles with both g: and m,, rather than penalizing the projection like what Adagrad and RMSProp do, we can obtain both descent on current and previous batches; (ii) handle the case when the estimation of previous gradients using m, is not accurate, we expect the current gradient g: to dominate the descent direction, which is denoted as m, It can be guaranteed by requiring the projection length of m, on gi is less than the length of ge if properly regularizing m,, Then, we propose new iterative subproblem in the following:
Enlightened by the above analysis,
ready propose
oc+1 = arg min C2 ||0
0ell
+ e (0 0.)²
g: + ||g:]
m.
[m,
m
where 1h+11 = g: + ggr
|mm
With such formulation, the following properties hold:
We ensure the above two observations, specifically, with the update of momentum m, we can guarantee that ||m || = O(
We attach the properties of the second moment to the first-order operation, inspired by Adagrad proximal subproblem.
The proposed algorithm Acutum summarized in Algorithm
Algorithm Acute Adaptive Momentum method (Acutum)
Input: initial point 0, E X'; step size {at), momentum parameters {
2: set m. =0
3: for to do
4: Vf.(0.)
5: m, g: + B3, ||gell/ (|mm + +e) m
6: O.+1 IIx (0. Oi m.)
7: end for
8: Return: TT+1
prevent precision overflow caused by tiny ||mm,-ll. 1ll- 31. is the momentum weight. We specify its value the theoretical analysis Section 4 In practice, we simply set 31,, to be Compared with other adaptive gradient methods, Acutum has fewer hyper-parameters, and is much easier to tune deep models. Besides, it is also computation-friet (for both time and space complexities) since the algorithm does not need second moments.
Note that, step 5
'The local smoothness assumption is widely used in the convergence analysis for convex and non-convex objectives, (Nesterov) 1998 Johnson Zhang 2013

---

Under review as a conference paper at ICLR 2020
4 CONVERGENCE ANALYSIS
In this section, we analyze the convergence rate of our proposed algorithm Acutum in an online convex setting, i.e., assume the convexity of sequence of loss functions fI, f2...... ....................... fI, as shown in the following:
Assumption 4.1 (Convexity Assumption). For each loss function f((0) where S t S T, we
assume it is convex. That is, for any x, X, we have
f(l) 2 f(x) + V[i(x) x),
where X' is the feasible set of function f1, fr.
Notice that this assumption is widely used for theoretical analysis, in both stochastic optimization
methods (Johnson & Zhang, 2013; Defazio et al. 2014 Shalev-Shwarky & Zhang 2013) and online learning methods (Duchi et al. 2011] Kingma & Ba (0]42014, Reddi et 2019). Rather than consider the objective as finite-sum function, here analyze the regret from online learning perspective. That to say, at each time step 4, we are given the loss ((0)) after selecting some feasible solution 0,- Then we continue to pick the next point 0.+1 based on the previous losses.
We adopt online regret as the convergence metric, which equals to the relative difference between the algorithm's cumulative loss and the offline minimum value. The definition of regret is straight- forward, i.c.,
R(T) = E....
f(..)
min OEX
fi(0),
where X' is the feasible set all steps. Our purpose is find sequence of points {0e JISEST to minimize the overall regret R(T). We state the main theoretical results in the following theorem.
Theorem 4.2. Suppose Assumption 4.1 holds. We set O, =a= d/t, B1.t =3X-11 where
3, E 1). If diameter of the convex feasible set X are bounded, i.e., |10 00 S D for all 0 E X, and ft has bounded gradients, i.e., [[)](( < Go all 0 X, 1 5 T, then the regret of Algorithm Sanhhimmsatsss satisfies:
D2
d
Vd3D2 2a (1 X)²
R(T) S
VTT 3G log T) d
11g.T
2a
Theorem shows that our proposed algorithm has similar order of step size to online gradient descent, i.e., O(v O(vd/t). because of removing the second moments. In this situation, weight decay and appropriate learning rate decay strategies have much more influence on Acutum than Adam- type optimizers. Also, from the proof of Theorem 4.2 in appendix A.2 we find that the same order regret bound can also be obtained even with a more modest momentum decay 31. = B/t. Furthermore, we show in the following corollary that our Acutum enjoys regret bound of Ô(VT), which is comparable to the best of known bound for general convex online learning problems.
Corollary 4.3. Frame the hypotheses of Theorem 4.2 for all T 1, the regret of Algorithm satisfies R(T) = Ö(VT).
Corollary 4.3 illustrates that Acutum obtains Ry = o(T) for all situations which is independent of the sparsity of the data features. Besides, since lim Rr/ / - 0, Acutum will converge the optimal solution when the objectives are convex.
5 EXPERIMENTS
In this section, we conduct extensive experiments on image classification tasks. We want to validate that Acutum with only first moments not only obtain better generalization performance than adaptive gradient methods, but also converges faster than GGD-momentum.
First, note that introducing weight decay is equivalent adding regularization to the objectives, and has a significant impact on the generalization ability optimizers. To better characterize gener- alization performance, we conduct experiments from two perspectives: (i) In Section record

---

Under review as a conference paper at ICLR 2020
(4) Train Test Accuracy VGGNet
Train Loss Accuracy for Reshec
Train Loss Accuracy for DonseNit
age
ego
ego
amagred
amoged
Train Lode
10
00
0.0
06-
0.
04-
044
00
01
Epochs
Epachs
Epochs
rg0 arogee
12
2
amagred
Test
8
sodum
Epochs
Epochs
Figure 1: With same weight decay, train loss and test accuracy of different optimizers for VGGNet,
ResNet and DenseNet on CIFAR-100.
the convergence of training loss and the test accuracy of all optimizers with fixed weight decays (they optimize the same objective function). (ii) In Section 5.2 we adopt the optimal weight decays for all optimizers, then investigate their generalization ability based on the test accuracy.
Now introduce the experimental settings of experiments, which are general and commonly used. Specifically, we implement all of our codes in Pytorch platform version 1.0+ within Python 3.6+. To obtain sufficient comparisons with adaptive gradient variants. we choose various base- lines, including 3GDDmmometumm, Adam (Kingma & Ba, 2014). Amsgrad (Reddi et al. 2019). Adamw (Loshchilov & Hutter (017). Yogi (Zaheer et al. 2018), Padam (Chen Gu 2018).
Radam (Liu et al.) 20199) and Adabound (Luo et al. 2019)) For the image classification tasks, we use two datasets CIFAR-IO, CIFAR-100 (Krizhevsky et al. 2009). and test three different CNN architectures including VGGNet (Simonyan & Zisserman 2014). ResNet (He et al.] (016) and DenseNet (Huang et al. 2017) To obtain stable convergence, we run 200 epochs, and decay the learning rate by 0.1 every 50 epochs. We perform cross-validation to choose the best learning rates for all optimizers and second moment parameters 32 for all adaptive gradient methods.
5.1 EXPERIMENT WITH FIXED WEIGHT DECAY
We first evaluate CIFAR-100 dataset. In this experiment, the values of weight decay in all optimizers are fixed, and are chosen to be the weight decay in OGD-momentum when it achieves the maximum test accuracy.
From the first row of Figure [ i.e, the training curves of three tests, we observe that our proposed Acutum significantly outperforms Adam, and has comparable rate with Padam and Adabound when we fix the weight decay. Also, in the second row of Figure [ i.e, the test accuracy, our Acutum outperforms all benchmarks except only SGD-momentum. However, the training loss converges much slower when implemented with SGD-momentum which is also recorded in other literature. The above evaluation results validate that our method achieves both fast convergence and good generalization when the weight decay is fixed. Note that the AdamW method reduces training loss quickly, however, there is a large generalization gap between and other optimizers, including CGD-momentum, Acutum, Padam.
5.2 EXPERIMENT WITH OPTIMAL WEIGHT DECAY
In this section, we conduct experiments on CIFAR-10 dataset. Specifically, we find the optimal weight decay for each optimizer which obtain the maximum test accuracy.

---

Under review as a conference paper at ICLR 2020
(a) and Accuracy for VGGNet
(0) and Accuracy Reshttt
[c] Train Loos Accuracy for DersveNet
850
121
222
0.2
2.4
142
544
pedtin
8:33
Train
Train
0.23
822
8:13
6:12
6:11
1:5
133
723
Epachs
Epachs
Spochs
11.3
335
135
53.5
12.9
12.
vain
84.5
$4.
220
702
Epochs
Epochs
Epechs
Figure 2: With different weight decays, train loss and test accuracy of different optimizers for VG-
GNet, ResNet and DenseNet on CIFAR-10.
As shown in Figure 2 Adam, AdamW and Amsgrad perform worse than the other optimizers in the plots of test accuracy. In this optimal weight decay setting, Padam, Adabound and Acutum can even have better test performance than SGD-momentum on VGGNet if sacrificing some convergence rate. Besides, they outperform Adam by more than percentage points for the test accuracy. The experimental results demonstrate that optimizers which converge faster than Acutum generalize worse. Similar to results in previous section, Acutum can effectively bridge the generalization gap, and has a comparable performance with the state-of-the-art Adam's variants while only requiring first moments.
CONCLUSION
In this paper, we revisited the existing adaptive optimization methods from novel point of view. We found that the widely used second moments essentially penalize the projection of the current descent direction on the exponential moving average of previous gradients. In other words, aims to decrease the current batch loss while does not increase previous batch loss. Following such new idea, we investigate how to obtain descent on both current and previous batches. Specifically, we proposed a new method, acute adaptive momentum (Acutum). It removes the computation- complicated second moments and constructed a decent direction by forming acute angles with both current and (approximated) previous gradients. We analyzed its convergence property in the online convex setting. The extensive evaluations demonstrate that our Acutum can effectively bridge the gap between fast convergence and good generalization, i.e., the advantages of both adaptive gradient methods and SGD-momentum.
For future work, it would be interesting evaluate our method in other types of tasks and deep models, especially NL. and GAN problems. Besides, explaining the generalization ability of SGD one the most significant open problems in this field. We also hope that one could improve the convergence rate of SGD by only scheduling the learning rate carefully and dynamically.
REFERENCES
Jinghui Chen and Quanquan Gu. Closing the generalization gap of adaptive gradient methods in training deep neural networks. arXiv preprini /rX6v:/806.0677 2018.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in neural information processing systems, pp. 1646-1654, 2014.
8

---

Under review as a conference paper at ICLR 2020
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(uu):2121-2159, 2011.
lan Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp- 770-778, 2016.
Geoffrey Hinton,
Nitish Srívastava, and Kevin Swersky. Neural networks for machine learning lecture 6a overview of mini-batch gradient descent. Cited on, 14:8, 2012.
Gao Huang. Zhuang Liu, Laurens Van Der Maaten, and Kilian Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 7700-4708, 2017.
Ric Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in neural information processing systems, pp. 315-323, 2013.
Nitish Shirish Keskar and Richard Socher. Improving generalization performance by switching from adam sgd. arXiv preprint arXiv: 17/2.07672 2017.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint TrXiiv:412.66900 2014.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
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: 1908. 190.003900...655, 2019.
Ilya Loshchilov and Frank Hutter. Fixing weight decay regularization in adam. arXiv preprint 2017.
Liangehen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. In Proceedings of the 7th International Conference on Learning Repre- sentations, New Orleans, Louisiana, May 2019.
Yurii Nesterov. Introductory lectures on convex programming volume i: Basic course. Lecture notes, 3(4)5,, 1998.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. arXiv preprint 1rXiv:1904.000
2019.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathemati- cal statistics, pp. 400-407, 1951.
Shai Shalev-Shwarzz and Tong Zhang. Stochastic dual coordinate ascent methods for regularized loss minimization. Journal of Machine Learning Research, 14(Feb):567-599 2013.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1409. 2014.
Ashia C. Wilson, Rebecca Roelofs, Mitchell Stem, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Advances Neural Information Processing Systems, pp. 1148-4158. 2017.
William Henry Young. On classes of summable functions and their fourier series. Proceedings of the Royal Society of London. Series A, Containing Papers of a Mathematical and Physical Character, 87(594):225-229) 1912.
Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive meth- ods for nonconvex optimization. In Advances in Neural Information Processing Systems, pp- 9793-98033 2018.

---

Under review as a conference paper at ICLR 2020
Matthew D Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint arXiv:1212.5701, 2012.
Zijun Zhang, Lin Ma, Zongpeng Li, and Chuan Wu. Normalized direction-preseeviing adam. arXiv preprint arXiv: 04540,944444..... 2017.
10

---

Under review as a conference paper at ICLR 2020
A PROOF OF THE MAIN RESULTS
A.1 SOME IMPORTANT LEMMAS
In this section, we give several important definitions and lemmas which will be used in the proof of the regret convergence.
Lemma A.1. For some convex feasible set X' C RR, suppose 0 = mingex ||0 - -ill and 0₂ =
mingex ||0 02]l then we have 0 02 s ||0 02l1-
Proof. Here, we only provide the proof for completeness. Combining the definition 0₃ minoex ||0 0ill. 02 mingex ||0 02ll with the properties of projection operator, have
0 00)-0))
T 02 0,} 2 0 and (02 00) (0 0z) 20. O.
From the above incqualities, we can obtain
(o.-01)² " (o= 0.) (02 02) 00 0,) < (02 - 01)" (02-0.) 0.) 2 =1002 6.11
With the property that (02 01) (02 0,) 0.)l |
2 0, we have
|10 - 01 2| N 00 0,
|| + 2 (02 01)² (0: (01) 01)) 2000-- 01
01 0.1²
Thus, the proof has been completed. Lemma A.2. In the Algorithm we have |mmlll S 2 |gell at each iteration if the momentum parameter satisfies $1,t S
Proof. With the definition of mys we have
|mml1 g:
B1
gi
m
[m
281 |gd
< ||gel || + 13, ||g:
||g:
1,m1, ||m,-1
m
(1 31,)) 2 Ig
With the condition that 31, - we have ||
S
gell
A.2
PROOF OF THEOREM
Proof. Consider the update rule of Algorithm
| parameters 0 and O, satisfy
11x (0*) = and 11x (0, a:m,;) = 0.+1.
With Lemma A.1
have
0
0-1
< ||0 a,m, 1
= 110 0-1 - 2a, (0, - 0²) + at ||mi 11
(10)
B ||gel
T (0, -²)
0, 0-1 2 + af | 20 gi
m
| +
where follows from the definition of m. Rearrange the items in Equation
10 obtain
g
T (0.
0*) <
1
||0
0- - ||++1 1²)
+ 2
ar |
11
$1,
||g:]]
m (0, 0*)
200
|
1 1
[10,
1-1 - || - 12)))
+
at
|m
+ $1,
|0 - 0" 2
04 |g ?
200
2
20;
(1
1
+ e)
<
1
(10,-
0-1 - 0 0-122)
+ 2
at
|
11 + B1,
110 001
g
200.
20r
2
11

---

Under review as a conference paper at ICLR 2020
where ! holds by the Young's inequality. By Assumption
4.1
with the convexity of all f., we have
T
T
Σ (i((0)) [((0 S gc (02 - 0²)
[=1
Submit Equation (.2)) to the above inequalities, we obtain
Σ (r((0.) -((0
(0.. 0,)² (0 -
201
T1
(1I)
T d
Oit
T
d
T
d
$1
(0t,i
- 07)2
2
2
200e
[=1
i=1
1=1
1=1
Ts
where Bi,,= -x1-1 is monotonically decreasing with L. For Tr, we have
[00. -0:)² - -00+1..5 - 00:)²
2
0t
1=1
T
(02, 104-07 0,)²
1
(0e, 02)² 0032
2
01
a
a--1
1=2 i=1
(12)
D2
00
Σ
d
T ΣΣΣ
d
1
01-1)
2
a1
a2
1==1
1=2
i=
D2
d
D2
00
VdT
2
CT
2a
where we set 0g aa/d/ For T2 in Equation
11
we obtain
T
T
d
2
+
Σ
2
1=1
@1
4avd
1
4GxaVa
$2
apmi
2
FT.
2
S
amp
19r
2
VT
2
VT
i=1
i=1
[=1
T
d
T
-2G 2V d
Mt,i
2G 22
Σ
0t.i
Vi
T 2Go (1 + log T)
d
22G
(13)
where we introduce Lemma A.2 in inequality @. Besides, we get @ through Cauchy- Schwwrz inequality. With similar proof techniques, we have Ta satisfied
d
31,
T-1
d
Vd
GoaBVd d
Di.
2 gi.
+
gr.s
S
Ths +
1gr
2
2VT
2
2VT
i=1
God
T
I9r,il
GoolBVd
Σ
d
T
M
2
2
Vt
i=1
==
Gaa
1
Goa
191
V (1
log T)d Σ
2
t
2
(14)
12

---

Under review as a conference paper at ICLR 2020
Since Equation 14) is sufficient for our regret convergence analysis, have not tried to optimize further. Then, for Tı, we have
T
B (0,,1 2
07)²
T
11,t
(0r.1 - -07)
2
31.
ViX Σ (0., - 07)²
201
20
1=1
1=1
(15)
vd
T
vd3D² VEXL-1
T
VdBD*
20
Dc
t
2a
20
2a (1 A)
1=1
1=1
where ① follows from the definition of 31, and and 2 establishes because of the geometric series summation rule. As result, submitting Equation Equation 15) back into Equation [II
12)
Equation
13 Equation 14 and
we have
D VTT 3G 3G log T)d
vd3D² 2a (1 -1 A)2
R(T) S
1
(16)
2a
This completes the proof.
A.3 PROOF OF COROLLARY 4.3
Proof. From Theorem
we have
D2 R(T) S v VdT + 33 log
d
vd3D2
11 1ll
(17)
2a
2a (1 - 2
For the second term, we have
T Σ
1
Lis S dG VT
(18)
1=1
1=1
Combining the above inequality with Equation
17
obtain
R(T) = Ö(VT)
13


Reviews:
[{"review_id": "rJgbavlCYr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "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": "This paper attempts to remove the use of the second moment in Adam in order to improve the generalization ability of Adam. \n- Apriori, it is not clear why removing the second moment is important. Does it improve the generalization or decrease the runtime substantially?\n- Please clarify how our method compares against Yogi (Adaptive Methods for Nonconvex Optimization, Zaheer' 2018) and the more recent RADAM (ON THE VARIANCE OF THE ADAPTIVE LEARNING\nRATE AND BEYOND, Liu 2019) , both theoretically and empirically. \n- The paper is meandering and confusing. State your update/algorithm and then explain how it compares against the other methods. Besides, there might be technical problems with it. \n\nSee the detailed review below:\n- Section 1: \"the generalization results (of adaptive methods) cannot be as good as SGD\". Please cite the relevant papers, (for example, Wilson. 2017)  that show this empirically. \n-  Section 1: \"the proposed algorithm outperforms Adam in convergence speed\" - Please clarify what \"convergence speed\" refers to. Is it the number of gradient evaluations, the rate of convergence or the wall-clock time. Please state how did you conclude this. \n- Section 2: The update rule of Adagrad is incorrect. The step-size is constant \\alpha and it is decreased over time because of the v_t term. \n- Section 3: There is no guarantee on the approximation in Equation 5. Young's inequality and the resulting upper bound can be quite loose. \n- Section 3: In general, it is not possible to have an update that decreases the loss on the current batch, but does not increase the previous batches loss. It is always possible to construct a counter-example to this. \n- \"In practice, the computational cost of computing\" the gradient for all i is expensive. Indeed, this is batch gradient descent. I am not sure how this is relevant to the discussion in the paper. \n- Cite and compare against the variance reduced methods (Stochastic Average Gradient, Schmidt, 2013; SVRG, Johnson, 2013) as these try to \"approximate\" the full gradient in order to decrease the variance. \n- The derivation/formulation of Equation 8 is not clear to me. Why is the \\hat{m} normalized? \n- In algorithm 1, it seems you need to choose the sequence of step-sizes \\alpha_t and \\beta_t. How is this an adaptive method then? How are these sequences chosen theoretically and practically? Please clarify this. \n- Section 4: Please compare the resulting regret bound to that of Adam, Adagrad and AMSgrad. Why does \\alpha_t = O(1/t)? If we have to decrease the step-size according to a sequence, why should I not use standard SGD?\n- Section 5: \"we decay the learning rate by 0.1 every 50 epochs\" This is not aligned with either the theory or the algorithm you proposed. \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 thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "HJelXDOTFS", "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": "This paper proposes new stochastic optimization methods to achieve a fast convergence of adaptive SGD and preserve the generalization ability of SGD. The idea is to let the search direction opposite to the gradient at the current batch of examples and a bit orthogonal to previous batch of examples. The algorithm is easy to implement and backed up with regret bounds. Several experimental results are also reported to verify the effectiveness of the algorithm.\n\nThe regret bound in Theorem 4.2. is not quite satisfactory. For example, Adagrad in Duchi et al (2011) can achieve the regret bound $O(\\sum_{i=1}^{d}\\|g_{1:T,i}\\|_2)$. However, there is an additional factor of $\\sqrt{d}$ in the regret boun in Theorem 4.2, which is not appealing in high dimensional problems. The regret analysis follows largely from standard arguments.\n\nI can not follow the last identity of (10). It should not hold since there is a missing $\\epsilon$ there.\n\nIn both eq (14) and (15), it is not clear to me why the authors divided the summation into two parts. Also, $\\sqrt{\\sum_{t=1}^{T}\\frac{1}{\\sqrt{t}}}$ should be $\\sqrt{\\sum_{t=1}^{T}\\frac{1}{t}}$ there.\n\n----------------------\nAfter rebuttal:\n\nI have read the author response. Unlike AdaGrad, the proposed algorithm does not show an advantage over standard OGD. I would like to keep my original score.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I did not assess 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": "BkgxL3dCtH", "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": "Balancing the generalization and convergence speed is an important direction in deep learning. This paper propose a new method to balance them. That is very interesting to me. However, I have several concerns as follows.\n1. I cannot agree that \"fewer hyper-parameters\" in Algorithm 1. The authors should provide more materials to support this claim, such as a comparison table of different mathods. \n2. In Theorem 42, how to set the parameter \\epsilon to obtain the conclusion.\n3. The authors should provide more comparison of the theoretical results of different SGD algorithms (such Adam, RMSProp ...)\nSome minor issues:\n1. The conditions of formulation of Eq. (6) should be placed together with Eq. (6).\n2. What is the definition to c_2,0, c_2,1 .... It is not clear to readers.\n3. The presentation and structure of the paper should be improved further, such as adding several subsection in Sec. 3, so that readers could easily follow the main idea of this paper.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "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": {}}]

Author rebuttal:

Meta-review: The paper addresses an important problem of finding a good trade-off between generalization and convergence speed of stochastic gradient methods for training deep nets. However, there is a consensus among the reviewers, even after rebuttals provided by the authors, that  the contribution is somewhat limited and the paper may require additional work before it is ready to be published.
Decision: Reject