Accelerating First-Order Optimization Algorithms
Authors: Ange Tato
Roger Nkambou
Venue:  (2020)
Keywords: Neural Networks
Gradient Descent
First order optimization

Abstract: Several stochastic optimization algorithms are currently available. In most cases, selecting the best optimizer for a given problem is not an easy task. Therefore, instead of looking for yet another ’absolute’ best optimizer, accelerating existing ones according to the context might prove more effective. This paper presents a simple and intuitive technique to accelerate first-order optimization algorithms. When applied to first-order optimization algorithms, it converges much more quickly and achieves lower function/loss values when compared to traditional algorithms. The proposed solution modifies the update rule, based on the variation of the direction of the gradient during training. Several tests were conducted with SGD, AdaGrad, Adam and AMSGrad on three public datasets. Results clearly show that the proposed technique, has the potential to improve the performance of existing optimization algorithms.

Under review as a conference paper at ICLR 2020
USING THE VARIATION OF THE GRADIENT TO ACCEL- ERATE FIRST-ORDER OPTIMIZATION ALGORITTMM
Anonymous authors Paper under double-blind review
ABSTRACT
Several stochastic optimization algorithms currently available. In most cases, selecting the best optimizer for a given problem is not an easy task. Therefore, in- stead of looking for yet another absolute best optimizer, accelerating existing ones according to the context might prove more effective. This paper presents a simple accelerate first-order optimization algorithms. When
and intuitive technique applied to first-order optimization algorithms, it converges much more quickly and achieves lower function/loss values when compared to traditional algorithms. The proposed solution modifies the update rule, based on the variation of the di- rection of the gradient during training. Several tests were conducted with SGD, AdaGrad, Adam and AMSGrad on three public datasets. Results clearly show that the proposed technique, has the potential to improve the performance of existing optimization algorithms.
INTRODUCTION
The majority of existing optimization algorithms are first-order methods - use first derivatives of the function to minimize -, based on the gradient descent technique. These techniques (c.g. the back propagation of error) are used to find a matrix of weights that meets the error criterion. Adam (Adaptive Moment estimation) (Kingma & Ba 2014) is probably the most popular (Goodfellow jet al. 2016 Isola et al. (017). However, Adam (while possessing convergence proof issues) has recently been proven unable converge to the optimal solution for simple convex optimization setting (Reddi et al. 2018). AMSGrad addresses this issue by endowing Adam and other adaptive stochastic methods with a long-term memory. Unfortunately, Adam can still outperform AMSGrad in some cases| Therefore, instead of looking for the absolute best optimizer, finding a way to accel- erate the existent would be of greater use. In this perspective, we propose simple technique aiming at improving the empirical performance (find a lower minimum for the loss function) of any first- order optimization algorithm, while preserving their property. We will refer to the solution when applied to existing algorithm A as AA for (Accelerated Algorithm). For example, for AMSGrad and Adam, the modified versions will be mentioned as AAMSGrad and AAdam. The solution is based the variation of the direction of the current gradient with respect to the direction of the previous update. We conducted several tests on problems where the shape of the loss is simple (has convex form) like Logistic regression, but also with non-trivial neural network architectures such as Multi-layer perceptron, deep Convolutional Neural Networks and Long Short-Term Memory. We used MNIST, CIFAR-10 10 and IMDB movie reviews Maas et al. (201T) datasets to validate the solution. Our experiments are limited to SGD, AdaGrad, Adam and AMSGrad.
RELATED WORK
2.1 HOW GRADIENT DESCENT METHOD WORKS
Let (x) be function parameterized by model's parameters & E R", sufficiently differentiable of which one seeks a minimum. The gradient method builds a sequence that should - in principle work towards finding the minimum. For this, we start from any value Zo (i.e. a random value) and

---

Under review as a conference paper at ICLR 2020
construct the recurrent sequence by:
2 - xz - - a. Vfe((t))
where is the learning rate. For adaptive methods like Adam, the learning rate varies for each parameter. This method is ensured to converge even the input sample not linearly separable, to minimum of the error function for well-chosen learning rate. There exist several variants of this method two basic categories: first-order and second-order methods. While first-order methods use first derivatives of the function to minimize, second-order methods make use of the estimation of the Hessian matrix (second derivative matrix the loss function with respect to its parameters) (Schaul al. 2013 LeCun al. 1993). The latter determines the optimal learning rates (or step size) to take for solving quadratic problems. While such approach provides additional information useful for optimization, computing accurate second-order derivatives is too computationally expen- sive for large models. Furthermore, the computed value usually equals to bad approximation of the Hessian. this paper, we will only focus on first-order techniques.
2.2 EXISTING FIRST ORDER OPTIMIZATION ALGORIHMM
Adam is a first-order gradient-based algorithm of stochastic objective functions, based on adaptive estimates of lower-order moments. The first moment, once normalized by the second moment, gives the direction of the update. Adam updates directly estimated using running average of the first and second moment of the gradient. It computes adaptive learning rates for each parameter. In addition to storing an exponentially decaying average of past squared gradients Ut, Adam also keeps an exponentially decaying average of past gradients ma, similar to momentum. It has two main components: momentum component and an adaptive learning rate component. Adam has bias- correction feature that helps slightly outperform previous adaptive learning rate methods towards the end of optimization when gradients become sparser (Ruder) 2016). To our knowledge, Adam is one of the latest state-of-the-art optimization algorithms used by many practitioners of machine learning. There exist several techniques to improve Adam such as fixing the weight decay (Loshchilov & Hutter 2017), using the sign of the gradient in distributing learning cases (Bernstein et al. 2018), 8), or switching from Adam to SGD (Keskar & Socher, 2017). However, it has been recently proven that Adam is unable to converge to the optimal solution for simple convex optimization setting (Reddi ct al. 2018). A more recent algorithm (AMSGrad) fixes this problem by endowing the techniques with long-term memory. The main difference between AMSGGrdd and ADAM is that AMSGrad maintains the maximum of all v (exponentially decaying average of past squared gradients) until the present time step and uses this maximum value for normalizing the running average of the gradient. The original paper claims that AMSGrad either performs similarly, or better than Adam on some commonly used problems in machine learning. The update rule of AMSGrad is as follows:
F141
Tt.
Vū: + Mh,
m = B1 -=--1 + (1 B1) ((((x))
Vt
B2 11-1 + (1- 32) fz()z))
m:
mn = 1 g
Ut
6 = max Cr
3
Recall that an optimizer aims to look for parameters that minimize function, knowing that we do not have any knowledge on what this function looks like. If we knew the shape of the function to minimize, would then be easy to take accurate steps that lead to the minimum. While we can't plan for the shape, each time we take step (using any of the optimizers) we can know if we passed a minimum by computing the product of the current and the past gradient, and check whether is negative. This informs us on the curvature of the loss surface and is - as far as we know the only accurate information available in real-time. The proposed method exploits this knowledge to improve the convergence of an optimizer. None of the existing techniques uses the variation of the direction of the gradient as information to compute the next update. The technique can be seen as a momentum technique with condition that specifies when add momentum.
2

---

Under review as a conference paper at ICLR 2020
3 A METHOD TO ACCELERATE FIRST-ORDER OPTIMIZATION ALGORITHMS
3.1 NOTATION
||Mil denotes the 12-noo 12-norm of hth row of M. The projection operation FI for A E St (the set of all positive definite d matrices) is defined as arg mingez || f) for y E RR.. F has bounded diameter Do if || yll S Doo forall x, y E F. All operations applied on vectors or matrices are clement-wise.
3.2 INTUITION AND PSEUDO-CODE
The intuition behind proposed solution is presented in this section. The pseudo-code of our the method applied to the generic adaptive method setup proposed by Reddi et al. (2018) illustrated in algorithm For Adam, c/r(g1, gr) = (1 B2) Ei B5-$9 9.. For AMRSgrad, (e ..., 9c)
(1 - 32) diag E 32 35-13?
Algorithm Accelerated Generic Adaptive Method Setup
Input: 31 E F, step size (at > O) sequence of functions (sPt, 1/2 )=)
t g-l
S threshold
repeat
9t (xe()))
V, (1 .... gt)
if' 9r m > 0 and m 9t |> S then
gm, St + m,
B1 m4-1 + (1 - 31)mm
else
31 M4-1 + (1 -1-6 B1)
4cf1 Ft a.m V.
Tr+1 11 (I (8++1)
++
until 1> T
Lets take the famous example of the ball rolling down a hill. If we consider that our objective is to bring that ball (parameters of our model) to the lowest possible elevation of the hill (cost function), what the method does is to push the ball with a force higher than the one produced by any optimizer, if the ball is still rolling in the same direction. This is done by adding the sum between the current computed gradient (ge) and the previous gradient (gt-1) or the previous moment (m--1) to the step currently being computed instead of only Dt- The ball will gain more speed continues go in the same direction and lose its current speed as soon as it will pass over a minimum. To avoid the oscillation of the ball over a minimum, a constraint past gradient and the current one. This difference should be more than a threshold (S <| 9t-1 9t order for the acceleration be effective when updates became smaller.
added concerning the difference between the
The higher the threshold, the closer we will get to the original algorithm. However, S should not be too small (see section 5.2). Another solution could to stop accelerating the ball and let the original optimizer take full control of the training once the direction changes for the first time. This solution may also work, but would converge slower. this paper, we will only focus on the case where the gradient St is replaced by 9t M4-1 9: + 9t-1 when computing m, in Adam and AAmsGrad (see algorithm [ for details) or 9t in other optimizers (SGD and AdaGrad for example) if the direction does not change. That change since the quantity I, (Reddi et al,, 2018)- which essentially measures the change in the inverse of learning rate of the adaptive method with respect time will keep its property.
made to the optimizer do not alter its convergence
3

---

Under review as a conference paper at ICLR 2020
Algorithm 2 Accelerated Generic Gradient Descent Method
Input: 21 F, step size (a 0)
t
S threshold
repeat
9: (z:)
new-g
if 9t 9t-1 > 0 and 9t-1 9t
then
new-9 St + 9t-1
2(+1 Zt O2 new g
[ [-1+1
until 1> T
3.3 CONVERGENCE ANALYSIS
We assume that if we able to prove that modifying optimizer with the proposed method does not alter its convergence, then the same applies for the other optimizers. Thus, we only analyse the convergence of one deterministic optimization method AGD (Accelerated Gradient Descent) and one non-deterministic method (AAMSGrad).
For deterministic methods such as GD, the convergence analysis consists in finding upper bound of the difference between the function value at the (-th iteration and the minimal value (f(z)) f(x") )) where is the function minimize, x² is the optimal solution and x; is the solution found by the algorithm at time f.
Theorem 1. Let f R + be a L-Lisschitz convex function and x² argming (x). Then, GD with step-size S L/L satisfies the following
T. =x11²-
Σ t=
(f(1)1) - f(x"))
||
1| 1=1
L
- f(x)) <
1:00
-x"1""
x²11
2T
In particular, & || 11² iterations suffice to find an e-approximate optimal value x. GD has a sublinear convergence rate O(1/T).
For AGD, since (f(xT-1) = &V f(TT) if ( Vf(zr) > 0 with k 2 1 we have
Let f Rd + IR be a L-Lipschitz convex function and x* argmin fxx). Then, AGD with step-size satisfees the following:
Theorem 2.
L(1 (1+ k)
f(xT) f(x')=
<
1!
2T
AGD has sub-linear convergence rate of O(L/T) which is the same GD. The method does not alter the convergence of the algorithm.
For AAMSGrad, the analysis differs slightly from GD (deterministic methods) but the underlying goal remains the same. We used the online learning framework (Zinkevich) 2003). As such, the convergence result for AAMSGrad is taken with respect to the regret since expected values of the gradients of the stochastic objective are difficult to compute. The regret is defined as
T
R(T) = Σ -
(4)
4

---

Under review as a conference paper at ICLR 2020
Theorem 3. Assume that FF has bounded diameter Doo and lV I G for all [T] and I E With 04 VT AAMSGrad achieves the following guarantee, for all T 2 1:
D& VT
d
D
T
1/2 1
Ry S 20(1 1 B1)
(U 1/2
4(1 31)
1=1
1=1
(5)
20x / (og(T)
d
(1 -1- (1-33) 7) B2)
The proof of this bound is given in the appendix. The following result falls as an immediate corollary of the above result:
Corollary 3.1. Let B1c = 3, , (0, Theorem
then we have
Rr S D2g VT
B. Go
CTT +
2a 51)
- 411-8))(1 -
(6)
20 1 (Tg(T)
+ (1 - - (1-))) B2)
191.,,1l2
i=1
The regrel of AAMSGRAD can be bounded by O(2GxoVT) V(G
The term
Id 11-Talll can also be bound by O VT) since E |1g., << dG VT
Kingma
Ba 2014
EXPERIMENTS
We investigated different models: Logistic Regression, Multilayer perceptron (MLP), Convolutional Neural Networks (CNN) and Long Short-Term Memory (LSTM). We used the same parameter initialization for all of the above models. 31 was set to 0.9 and Bg was set 0.999 as recommended for Adam (Kingma & Ba (2114) and the learning rate was set to 0.001 for Adam, AAdam, AMSGrad, implemented using Keras
AAMSGrad and 0.01 for the remaining optimizers. The algorithms and the experiments were performed using the built-in Keras models, making only small edits to the default settings. For each model, all the optimizers started with the same initial values of weights. For the accelerated versions AAdam and AAMSGrad, we will only show the variant where the value of m, was changed according to algorithm [] However, both solutions (m4-1 + 9t or 9t-1 9t) worked well during our experiments. The experiments were repeated 10 times and we calculated the mean of the estimated mean model skill. Thus, each point in the following figures represents the average result after 10 trainings one epoch (one pass over the entire dataset). The number of epochs varied from 10 to for all experiments over fit with higher number of epochs). For AMSGrad, only considered the version with 'max' on Ut. not the diagonal. The full code for this project is publicly available (tensorflow and keras)
this paper (there good chance for models to
4.1 BASICS PROBLEMS
We first tested the proposed method basics functions: convex function x² (with the mini- mum fixed at 0) and a non-convex function x² (minimum - -oo). As seen in figure [ the acceler- ated versions are able reach lower loss function value compared the originals in both cases.
4.2 IMAGE RECOGNITION
No pre-processing was applied to MNIST images. All optimizers were trained with a mini-batch size of 128. All weights were initialized from values truncated using normal distribution with standard deviation of O.I. We used the 'softmax cross entropy' as the activation function. Again, for AAMSGrad used 9--1 instead of m in the if-else condition and the computation of the
hhtp://tiny.ccllgmdddz
5

---

Under review as a conference paper at ICLR 2020
Re. soating part. a- -2, berning 1a0 DOL
Bvl w ste dig peit 03 learning reto 0.23
-20
180
150
30
16
30
56
Figure 1: Minimizing basics functions with starting points -10 for x.2 and x 0.3 for x². For AAdam, we used Dt-1 instead of m4-1 in the if-else condition and the computation of the new step. No threshold was set.
Mait Legatic Depresserr
145T Noune Hoteeks
logue
Alagy
AGCO
ADCD
35-
00
12-
4.15
68-
16
(a)
(b)
34-
03
(d)
(c)
(f)
Figure 2: Logistic regression training negative log likelihood on MNIST images (a). MLP on
MNIST images (b). Loss training step. Convolutional neural networks on cifar10. Training cost over 30 (c) and 20 epochs (d). CIFAR-10 with c32-c32-c64--66 (c) and c32-c64-c128-c128 (d) architectures. Logistic Regression training negative log likelihood on IMDB movie reviews (e). LSTM training negative log likelihood on IMDB movie reviews (f). Loss on training step. No threshold was set when training the LSTM model.
new step. Logistic regression has well-studied convex objective, making it suitable for comparison of different optimizers without worrying about local minimum issues. We implemented the same model used for comparing Adam with other optimizers the original paper on Adam. In figure 2a we can see that the accelerated versions outperform the original algorithms from the beginning to the end of the training.
Multi-layer perceptron (MLP) is powerful model with non-convex objective functions that consists in an input layer, an output layer, and n hidden layers where n > 1. our experiments, we selected models that were consistent with previous publications in the area. A simple neural network model with one fully connected hidden layer with 512 hidden units and ReLU activation was used for this experiment with mini-batch size of 128. Figure 2b shows the results of running MLP on MNIST data. Again, the accelerated versions outperform (reach a lower minimum) the original algorithms on the training step.

---

Under review as a conference paper at ICLR 2020
4.3 CIFAR-10 DATASET
LeCCnn et al. 1995) are neural networks where layers represent convolving filters (Krizhevsky al., 2 applied local features. CNNs are now used in almost every task in machine learning (i.e. speech analysis (Abdel-Hamid et al.) 2014), text classification (Tato et al.) 2017, etc.). We considered the multi-class classífication problem on the standard CIFAR-TO dataset, which consists of 60,000 labelled examples of 32 x 32 images. We used CNN with several layers of convolution, pooling and non-linear units. In particular, the first architecture (which results are shown in figure 2c). contains 4 convolutional layers with 32 channels for the first two layers and 64 channels for the other two. The kernel of each of the 4 convolutional layers has a size of x followed by one fully connected layer of size 212. The network uses 2 max pooling. It also contains three dropout layers with keep probabilities of 0.25, 0.25 and 0.5, respectively applied 1) between the two first convolutional layers and the other convolutional layers; 2) between the two last convolutional layers and the flatten layer; and 3) between the fully connected layers. The mini-batch size is set 128 like in previous experiments. The code for this architecture was taken from Keras. Results for this problem are reported in figures 2c and 2d As we can see, accelerated algorithms performed considerably better than originals on the two different architectures.
CNNs
4.4 IMDB MOVIE REVIEWS DATASET
Finally, we experimentally evaluated our method on imdb movie reviews data This dataset consists of 25,000 movies reviews from IMDB, labelled by sentiment (positive/negaative) Reviews have been pre- pre-processed and encoded as a sequence word indexes. We then ran a Logistic Regression and LSTM models. LSTM has become core component of neural Natural Language Processing (NLP) Tai et al. 2015). The LSTM architecture (Hochreiter & Schmidhuber 1997) can learn long-term dependencies using memory cell that is able preserve states over long periods of time. We used the built-in LSTM architecture of Keras with 32 units, a recurrent dropout of 0.2 and dropout of 0.2. An embedding layer preceded the LSTM. The dimensionality of character embedding was set to 32 and the batch size was set to 32. We took the first 5,000 most frequent words. Results are presented in figures 2e and 2 As expected, accelerated versions consistently outperformed original algorithms. Nevertheless, for Adam and AMSGrad, the results were not very clear from logistic regression (2e), which may be due to the sparse nature of the data. More analyses on sparse problems should be considered in the future.
DISCUSSION
5.1 ANALYSIS OF THE EXECUTION TIME
The proposed method add to the original algorithms, test (if-else) which might slow the execution time. What if we gave the same execution time to all algorithms, investigating whether the proposed method allows the algorithm to reach lower minimum? In figure we performed two experiments where we evaluated the minimum reach by each optimizer given a fixed time. For function x² we set the starting point at = and the time the accelerated versions did less iterations but reached a lower function/loss values when compared to the original algorithms under the same execution time. Moreover, we ran the logistic regression on the MINST dataset with a fixed time of t 10s. Again, as accelerated versions largely outperformed the original algorithms. Thus, even if the method takes time compared to original algorithms, it is able to reach lower loss values given the same time of execution.
0.0005s. As we can see (Figure 3 left side),
see (Figure 3 right side)
5.2 HOW TO CHOOSE THE THRESHOLD ?
The choice of the parameter S is very important to ensure the effectiveness of the approach. In Figure 4 we tested different values of S with LR on MNIST. As we can see, when the value is high, the accelerated versions seem to behave like the original optimizers. When the value is too small,
cnn.py

---

Under review as a conference paper at ICLR 2020
Axl 2e1-aa starting pontur carsin oiee- 3.01 tiee - 2.000s
MM S7 Legidi: Regresston fome 10
1.9
3430
4500
175
1425
150
$430
125
1.20
0230
0.7
0.0
025
0.0
103
300
255
53
1.5
2066
375
Figure 3: Convergence analysis with a fixed time.
the accelerated versions converge faster at the beginning but fail to reach a better minimum. Note that, for AAMSGrad, S should be smaller than the one set for AAdam since the U, used to compute the step size in AMSGrad is higher (the max value) than in Adam. We would like to mention that during all our experiments with SGD and AdaGrad we did not set a value for S. S was only set for AAdam and AAMSGrad.
Akdin
1771
1211
32%
1:2
A.0
32
130
3:40
(a)
(b)
(c)
Figure 4: Experiments on the variation of the value of
6 CONCLUSION
In this paper, we have presented simple and intuitive method that modifies any optimizers update rule to improve its convergence. There can be no optimizer working best for all problems. Each opti- mizer has its advantages and disadvantages. No one tell in advance which will be the best choice for a specific case. The solution we have presented has the potential to speed up the convergence of any first-order optimizer based on the variation of the direction of the gradient the first moment (m, for moving average methods). Instead of using the gradient as is for computing the next step, we used the sum of the current gradient and the past gradient (similar momentum techniques) to compute the current step when both values have the same sign (the direction did not change), and keep the current gradient otherwise. We conducted successful experiments with four well-known optimizers (SGD, AdaGrad, Adam and AMSGrad) on different models using three public datasets (MNIST, CIFRA- 10 and IMDB movies reviews). In all our experiments, the accelerated versions outperformed the originals. In worst cases, both had the same convergence, which suggests that the accelerated versions were least as good as the originals.
This work took those optimizers one-step further and improved their convergence without noticeably increasing complexity. The only drawback of the proposed solution is that it requires slightly more computation than the standard approach (as it has to compute the if-else instruction), and implies to specify a new parameter S. However, we found that the extra time taken by the technique was compensated by the better minimum reached. The new update rule depends only the variation of the direction of the gradient, which means that it can be used in any other first-order optimizer for the same goal. The technique is intuitive and straightforward to implement.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Ossama Abdel-Hamid, Abdel-rahman Mohamed, Hui Jiang, Li Deng, Gerald Penn, and Dong Yu. Convolutional neural networks for speech recognition. IEEE/ACM Transactions on audio, speech, and language processing, 22(10): 1545, 2014.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Anima Anandkumar. signsgd: compressed optimisation for non-convex problems. arXiv preprint urXiv:1802.04434, 2018.
lan Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT press Cambridge, 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Phillip Isola, Jun-Yan Zhu, Tinghui Zhou, and Alexei A Efros. Image-to-image translation with conditional adversarial networks. arXiv preprint, 2017.
Nitish Shirish Keskar and Richard Socher. Improving generalization performance by switching from adam to sgd. arXiv preprint 172iv:171,.07628, 2017.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Alex Krizhevsky, lya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Yann LeCun, Patrice Y Simard, and Barak Pearlmutter. Automatic learning rate maximization by on-line estimation of the hessian's eigenvectors. In Advances in neural information processing systems, pp. 156-163, 1993.
Yann LeCun, Yoshua Bengio, et Convolutional networks for images, speech, and time series. The handbook of brain theory and neural networks, 336) 1995.
Ilya Loshchilov and Frank Hutter. Fixing weight decay regularization in adam. arXiv preprint arXiv:1711.05101, 2017.
Andrew I. Maas, Raymond E Daly, Peter T Pham, Dan Huang, Andrew Y Ng. and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th annual meeting of the association for computational linguistics: Human language technologies-volume ppp 142-150. Association for Computational Linguistics, 2011.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. 2018.
Sebastian Ruder. An overview of gradient descent optimization algorithms. arXiv preprint 1eXx041609. 2016.
Tom Schaul, Sixin Zhang, and Yann LeCun. No more pesky learning rates. In International Con- ference on Machine Learning, pp. 343-351, 2013.
Kai Sheng Tai, Richard Socher, and Christopher Manning. Improved semantic representations from tree-structured long short-term memory networks. arXiv preprint 15300055 2015.
Ange Tato, Roger Nkambou, Aude Dufresne, and Miriam H Beauchamp. Convolutional neural network for automatic detection of sociomoral reasoning level. pp. 284 289.289, 2017.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp. 928-936. 2003.

---

Under review as a conference paper at ICLR 2020
A APPENDIX
A.1
PROOF OF THEOREM 3
The proof presented below along the lines of the Theorem Reddi et al. (2018), which provides proof of convergence for AMSGrad.
The goal to prove that, the regret of AAMSGrad bounded by:
D& VT
1/2 D2
I
1/2
Rr S
20(1
B1) 1=1
4(1
31)
t=
1=1
20 20 + log(T)
11g.r::ll2
(1-8)))(1 7)v (2)
1=1
Proof. For each optimization method, we have
2++1 Ze oU
Where is the step size. Note that, the value of the update U is the gradient (or slope) of line. For example, this line is the slope of the tangent of the loss at Iद in SGD.
AAMSGrad has 2 rules for the update which different depending on whether the direction of the update changes or not. The current step taken by AAMSGrad is:
(a) F441 = F.V (xt a/m2/ vi)
gr m4-1 >
< II p.VVv (2r 2a, |mm Vvx))
(9)
m, 31 m4-1 (1 -1)) Jo m
(b) Te+1 = 11 F. P.VRi (xte - at///// V
sinon
[(1 - B1 31) S 181m-11 + (1 - 31)9.
(10)
Which lead us to:
m = 1 +1--B1)g + +(1 (11 -3, 31)m,-1
m2 < 2 (Bime-1 31)9:)
(11)
Ma < 2 2-me
All operations are element wise. When the direction of the current update changes from the past one, the current update is the same in AMSGrad (rule (b)). When the direction stays the same, the update is equal to the sum between the update that AMSGrad would have taken and the value (1 3 (nule (2)). Thus the regrel bound of AAMSGrad is
Rr I max RT( RT(h)
(12)
Where RT(,) is the regrer when consider only the second update rule of AAMSGrad. Please note that, the bound RTop is similar to that of AMSGrad. Ri(W)) the regres we consider only the first rule. The proof will consist of finding the bound for RT(a)- The second update rule of AAMSGrad can be rewritten as follows:
Je+1 S II ( - U) where U = 2 22.x,, V, V..,V"/ 1/2
(13)
If we ignore the value 2, the proof will be the same as proving the convergence of AMSGrad. Thus, we will not rewrite the demonstration but it easy to see that, after doing the same steps as Sashank J et al, have
10

---

Under review as a conference paper at ICLR 2020
D
d
T
-1/2
2,
1-122
D
T d
1/2
RT(a)= $
)
2(1 31)
QT
4(1 - B1)
a2
[=1
Aml
1
20y 1 + (Tg
+ (1 3:) v) (1- 82) i=1
111.,,
(14)
D2 VT
D2
Bix02s 1/2
(07,) 1/3 + 4(1 - 31)
2a(1 - -11)
0t
t=
2a / + (Tg
d
32) 119.:
(1 (1-33) (1-3))(11-))
Because RT(,) S Rr(a), the regret bound of AAMSGrad is:
Rr S (ar(a))(a)) Br()) = Rr(a)
(15)
Which complete the proof.
A.2 ADAM AADAM
Depending on the starting point of the algorithm, Adam can reach a minimum that is not optimal or oscillate around the minimum (as shown Figure left side). This is principally due the fact that I 1++1 can potentially be indefinite for t E [T] Reddi et al. (2018) with:
Vi+1 O+++1
VVi
T++1=
(16)
an
However, this quantity remains < for non-exponential moving average algorithms such as SGD) AdaGrad (to be observed that AMSGrad resolves this specific problem). Since the technique amplified the step taken by the original algorithm, we could not expect more than for AAdam to behave like Adam (as shown in Figure 5. Thus, depending on the starting point, AAdam may reach a better minimum faster, or only behave like Adam.
2.2
Alayii
0.0-
Acm
0.34
ASOD
034
032-
0.0
0.0
0.5
Figure 5: Adam vs AAdam
Overall, the proposed technique can be easily applied to other kinds of optimizers. For example, for NAG (Nesterov Accelerated Gradient) we will have (all operations are element-wise):
It+1 = Ve - a (v())) + (y--())-
if ())) V
(17)
Vo+1 = Z:+1 + 3(x - 21)
11


Reviews:
[{"review_id": "HklyD34pKS", "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": "The authors present an acceleration technique for first-order optimization algorithms by comparing the directions of gradients in consecutive steps, which works for SGD, Adam, and AMSGrad.  Empirically it seems to work well with some standard evaluations with CNN for MNIST and CIFAR10 and LSTM for IMDB, beating the non-accelerated versions in convergence speed. However there are some issues with the parameter choice and proofs. Below are my specific comments: \n\n1. Setting the parameter S seems to be difficult and problem-dependent. S controls the size of the region near the optimum where the algorithm falls back to the non-accelerated version. But S depends on the size of the gradient, which is problem-dependent. If we need to tune S for the algorithm to work well on a particular dataset, then it defeats the purpose of acceleration in the first place. \n\n2. The setting of S also depends on batch size if mini-batch stochastic gradient algorithms are used. In the update rules S is compared against |g_t-1 - g_t|, and this quantity is directly related to the variance of gradients, which in term depends on the batch size. This makes it even more difficult to set a priori. \n\n3. What is k in Theorem 2? In the line above Theorem 2, why is it the case that the gradient at x_T-1 is k times the gradient at x_T? Also, if we compare equations 2 and 3, the regret bound for the `accelerated' version is k times worse than the original non-accelerated SGD. How could this happen? \n\n4. In the proofs in the Appendix I see no mention of the parameter S, which is very strange since it is part of the update condition. The size of S affects the convergence, as shown in Figure 4. It is odd to have a regret bound in Theorem 3 that is completely independent of S. \n\nUnless the authors can address these issues I don't think the current paper is suitable for publication yet. \n\n\n\n\n", "extra_scores": {"experience_assessment": "I have read many 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": {}}, {"review_id": "Hkgw-7intr", "reviewer": "AnonReviewer1", "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": "The paper describes a technique to speed up optimizers that rely on gradient\ninformation to find the optimum value of a function. The authors describe and\njustify their method and show its promise in an empirical evaluation.\n\nThe proposed method sounds interesting and promising, but the empirical\nevaluation is unclear. In particular, details are missing on the exact\nexperimental setup and some of the presented results are unconvincing. I refer\nto the results of the basic function optimization (Figure 1), which shows that\nseveral of the considered optimizers are unable to even get close to the optimum\nof x^2 after several hundred iterations. It seems that this is extremely easy\nfunction to optimize -- why are the considered optimizers performing so poorly\non it? How were the hyperparameters of the optimizers set? This presumably\naffects the other results presented in the paper as well, and puts the\nimprovement of the proposed method in question.\n", "extra_scores": {"experience_assessment": "I have read many 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": "H1eOoyPTFr", "reviewer": "AnonReviewer3", "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": "Summary:\n\nThis paper presents an adaptive method which can be used alongside existing accelerated gradient methods. The paper is difficult to read due to mistakes and poorly defined mathematical notation. I believe that the paper is missing reference to related methods. The theoretical analysis in the paper is difficult to follow and provides little insight into the benefits of the proposed approach.\n\nOverview:\n\nThere are many mistakes throughout the paper which have made it difficult to read.\n\nOverall, I felt that this paper was missing a discussion of the effect of stochasticity on the proposed method. The issue with measuring the variation in the gradient direction is that in regimes where the gradient noise is dominating the signal the gradient direction at each time step is poorly correlated with overall optimization progress --- thus it seems intuitively ineffective to rely on the gradient direction to adjust the algorithm.\n\n1)  At the bottom of page 2, the authors write \"knowing that we do not have any knowledge of what this function looks like\". While minor, I would point out that we are able to compute local statistics of the function and so certainly we have _some_ knowledge.\n\n2) The authors claim that no techniques exist which use the variation of the direction of the gradient. One such example is in [1] which uses (in one case) the variation of the gradient direction to determine and appropriate time to restart the momentum computation. \n\n3) In section 3.2, the Adam moment computation is missing a \"diag\". Assuming that AMRSGrad is AMSGrad (mistyped), then this term is incorrect and matches Adam.\n\n4) There are many mistakes in the Algorithm 1 box.\n\n- The wrong $F$ is used in the input (should be $\\mathcal{F}$).\n- The algorithm takes as input a sequence of functions ($\\phi, \\psi$) which are not used.\n- Within the if statement, $gm_t = g_t + m_t$. I believe this should be an $m_{t-1}$. It is not clear what the vector $gm$ is exactly, and then $\\dot{g}$ is used afterwards which is also not defined.\n- The algorithm checks for $|m_{t-1} - g_t| > S$ while the text uses $|g_{t-1} - g_t| > S$.\n\n5) The first line of section 3.3 is quite worrying: \"We assume that if we are able to prove that modifying one optimizer with the proposed method does not alter its convergence, then the same applies for the other optimizers\". This seems like a dangerous assumption to make and should at the very least be carefully verified empirically. Following this, I am not sure what the authors mean by \"deterministic\" and \"non-deterministic\" methods.\n\n6) I do not understand the claim above Theorem 2 that $\\nabla f(x_{T-1}) = k \\nabla f(x_T)$. Under what conditions does this hold and how is $k$ computed? If I understand correctly, the bound provided in Theorem 2 is worse than that given for gradient descent. Moreover, the bound does not depend on the hyperparameter $S$ introduced in Algorithm 1 and provides limited insights into the method. I could not find a proof of Theorem 2 in the paper or appendix.\n\n7) There are serious flaws with the experimental evaluation in this paper.\n\na) There is no tuning over hyperparameter settings for any of the optimizers.\n\nb) The basic problems are very limited, even for toy problems. The 1D deterministic quadratic tells us very little about the performance of the optimizer. And the 1D cubic problem is particularly confusing. Unless I am mistaken, the gradient will always have the same sign (3x^2) and thus the acceleration condition will never be triggered.\n\nc) I believe that Figure 2 explores stochastic optimization problems which as discussed at top is a crucial evaluation. Unfortunately, due to lack of parameter tuning it is difficult to infer much about the comparison between the methods.\n\nd) Figure 4 compares performance variation over changing the threshold. The y-axis scale across each plot changes making the comparison unnecessarily difficult --- the scale should be the same.\n\nMinor:\n\n- TYPO Line 2, \"minimize ---,\"\n- End of intro, MNIST and CIFAR not cited while IMDB is. Citation uses citet not citep.\n- Bottom of page 2, \"\"\n- Top of section 3.2, \"The pseudo code of our the method\"\n\nReferences:\n\n[1] Adaptive Restart for Accelerated Gradient Schemes, Brendan O'Donoghue and Emmanuel Candes\n\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 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: All reviewers recommend rejection, and the authors have not provided a response.

Decision: Reject