Optimistic Adaptive Acceleration for Optimization
Authors: Jun-Kun Wang
Xiaoyun Li
Ping Li
Venue:  (2020)

Abstract: This paper considers a new variant of AMSGrad called Optimistic-AMSGrad. AMSGrad is a popular adaptive gradient based optimization algorithm that is widely used in training deep neural networks. The new variant assumes that mini-batch gradients in consecutive iterations have some underlying structure, which makes the gradients sequentially predictable. By exploiting the predictability and some ideas from Optimistic Online learning, the proposed algorithm can accelerate the convergence and also enjoys a tighter regret bound. We evaluate Optimistic-AMSGrad and AMSGrad in terms of various performance measures (i.e., training loss, testing loss, and classification accuracy on training/testing data), which demonstrate that Optimistic-AMSGrad improves AMSGrad.

Under review as a conference paper at ICLR 2020
OPTIMISTIC ADAPTIVE ACCELERATION FOR OPTI- MIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
This paper considers a new variant of AMSGrad called Aptimistic-AMSCOA AMSGrad (Reddi et al. (2018) a popular adaptive gradient based optimization algorithm that is widely used in training deep neural networks. The new variant assumes that mini-batch gradients in consecutive iterations have some underlying structure, which makes the gradients sequentially predictable. By exploiting the pre- dictability and some ideas from Optimistic Online learning, the proposed algorithm accelerate the convergence and also enjoys a tighter regret bound. We evaluate Optimistic-AMSI and AMSGrad in terms of various performance measures (i.e., training loss, testing loss, and classification accuracy training/testing data), which demonstrate that Optinistic-AMSGrra improves AMSGrad.
INTRODUCTION
Nowadays deep learning has been very successful in numerous applications, from robotics (e.g., Levine et al. 2017)), computer vision (e.g., He al. (2016); Goodfellow et al. (2014)). reinforcement learning (e.g.. Mnih et al. (013)). ) to natural language processing (e.g., Graves et al. (2013)). A common goal in these applications is learning quickly. It becomes desired goal due to the presence of big data and/or the use of large neural nets. To accelerate the process, there are variety of training algorithms proposed in recent years, such AMSGRAD (Reddi et al. (2018)),
ADAM (Kingma & Ba (2015)). ), RMSPROP (Tieleman & Hinton (012 ADADELTA (Zeiler (2012). and NADAM (Dozat (0166). etc.
All the prevalent algorithms for training deep nets mentioned above combine two ideas: the idea of adaptivity from ADAGRAD (Duchi al. (2011): McMahan & Streeter (2010) and the idea of momentum from NESTEROV'S METHOD (Nesterov 2004)) or HEAVY BALL method (Polyak (1964)). (1964)(1964)).
ADAGRAD is an online learning algorithm that works well compared to the standard online gradient descent when the gradient is sparse. Its update has notable feature: the effective learning rate is different for each dimension, depending on the magnitude of gradient each dimension, which might help in exploiting the geometry of data and leading to better update. On the other hand, NESTEROV'S ' METHOD or HEAVY BALL Method (Polyak (1964)) is an accelcrated optimization algorithm whose update not only depends the current iterate and current gradient but also depends on the past gradients (i.e., momentum). State-of-the-ar algorithms like AMSGRAD (Reddi et al. (2018)) and ADAM (Kingma & Ba (2015)) leverage the ideas to accelerate training neural nets.
In this paper, we propose an algorithm that goes further than the hybrid of the adaptivity and momentum approach. Our algorithm is inspired by OPTIMISTIC ONLINE LEARNING (see e.g. Chiang et al. (2012); Rakhlin & Sridharan (2013a b): Syrgkanis et al. 2013); Aberrnttyy et al. (2018)) OPTIMISTIC ONLINE LEARNING considers that good guess of the loss function in each round is available and plays an action by utilizing the guess. By exploiting the guess, algorithms in OPTIMISTIC ONLINE LEARNING can enjoy a smaller regret than the ones without exploiting the guess. We combine the OPTIMISTIC ONLINE LEARNING idea with the adaptivity and the momentum ideas to design a new algorithm - OPTIMISTIC- AMSGRAD. We also provide theoretical analysis of OPPIMIITIC-MMSGRAD The proposed al algorithm not only adapts to the informative dimensions, exhibits momentum, but also exploits a good guess of the next gradient to facilitate acceleration. We conduct experiments and show that PPTIMISTIC-AMSS AMSGRAD improves AMSGRAD in terms of various measures: training loss, testing loss, and classification accuracy on training/testing data over epochs.

---

Under review as a conference paper at ICLR 2020
2 PRELIMINARIES
We begin by providing some background in online learning, as it will be the main tool to design and analyze our proposed algorithm. We follow the notation in the literature of adaptive opti- mization (Kingma & Ba (2015); Reddi et al. (2018)). For any vector v E I, u/v represents element-wise wise division, u² represents dlement-wise square, v represents element-wise square-root.
We denote 91:r(u] [i] as the sum of the ith element of T vectors 91, .......... 9r E R
2.1
A BRIEF REVIEW OF ONLINE LEARNING AND OPTIMISTIC ONLINE LEARNING
The standard setup of online learning is that, in each round 4, an online learner selects an action wt E K C Rd. then the learner observes (-) and suffers loss ((wr after the learner commits the action. The goal of the learner is minimizing the regret,
((wretr((wx)) == Ei= - (((("
l((w"),
which is the cumulative loss of the learner minus the cumulative loss of some benchmark w' E AC
The idea of OPTIMISTIC ONLINE LEARNING (e.g.. Chiang et (2012); Rakhlin & Sridharan (2013a b): Syrgkanis et al. 2015 Abernethy et al. (018)) is as follows Suppose that, in each round I, the learner has a good guess m²(-) of the loss function (.).) before playing an action wy- Then, the learner should exploit the guess m,(-) to choose an action w) since m,(-) is close to the true loss function (-). For example, Syrgkanis et al. 2015) proposes an optimistic-variane of BELLLO--TE--RUUUS REGULLARZZED-EADDEA (FTRL). FTRL (see e.g. Hazan (2016)) is online
learning algorithm whose update
Wt arg min (w,, TT-1) + R(w),
where y/ is parameter, R(-)) is 1-strongly convex function with respect to a norm (I) []] on the constraint KC, and Lt-1 == Σ 9s is the cumulative sum of gradient vectors the loss functions
(i.e., Is == (l,(w.) ) up to but not including L. FTRL has regret at most O OVV V IIaell.). On the other hand, OPTIMISTIC-FII FTRIL (Syrgkanis et al. (2015) has the update
arg min (w, L + m.) + 1 R(w),
where m, the learner's guess of the gradient vector St = (w,) Under the assumption that loss functions are convex, the regret of OPTIMISTIC-FTRLL is at most O Σi= 119: mell-). which can be much smaller than the regret of FTRL if my is close to Jt. Consequently. OPTIMISTIC-FTRE can achieve better performance than FTRL. On the other hand, if m, far from gt, then the regret of OPTIMISTIC-FTRL would be only constant factor worse than that of its non-optimistic counterpart.
In Section we will provide a strategy to obtain My. At moment, we just would like to use this example of FTRL to emphasize the importance of leveraging good guess m, for updating wt. in order to achieve a faster convergence rate (or equivalently, small regret). We will have a similar argument when we compare OPTIMISTIC-AMSGRA and AMSGRAD.
2.2 ADAM AND AMSGRAD
ADAM (Kingma & Ba (2015) popular algorithm for training deep nets. It combines the momentum idea (Polyak (1944)) with the idea of ADAGRAD (Duchi et al. (20TT)). which has effective different learning rates for different dimensions. The effective learning rate of ADAGRAD iteration for dimension j proportional to inverse of / ">]= where gs [/] is the jeh element of the gradient vector gs in time This adaptive learning rate might help for accelerating the convergence when the gradient vector is sparse (Duchi et al. (20IT)). However, when applying ADAGRAD to train deep nets, it is observed that the learning rate might decay too fast (Kingma & Ba (2015). ). Therefore, Kingma & Ba (2015) propose using a moving average of gradients divided by the square root of the second moment of the moving average (element-wise fashion), for updating the
model parameter w (i.e., lines 5,6 and of Algorithm []. Yet, ADAM (Kingma & Ba (2015)) fails at
'mmagine that if the learner would had been known (())) before committing its action, then it would exploit the knowledge determine its action and consequently minimizes the regret.
2

---

Under review as a conference paper at ICLR 2020
Algorithm 1 AMSGRAD (Reddi et al. (2018)
1: Required: parameter 31, 92, and Tj.-
2: Init: wi E K S CR" and 6g = cl ER.
3: for t to do
4: Get mini-batch stochastic gradient vector gt at wt.
5: 0, 1 + (1 81 )g:.
6:
820=-1 + (1 B2)gr
7: ig max(ft-11) [.)
8: w1+1 = wi Ve."
(element-wise division)
9: end for
some online convex optimization problems. AMSGRAD (Reddi al. (2018)) fixes the issue. The algorithm of AMSGRAD is shown in Algorithm [ The difference between ADAM and AMSGRAD
lies on line 7 of Algorithm T ADAM does not have the max operation on line 7 (i.e., 0g = U/ for
ADAM) while AMSGRAD adds the operation to guarantee non-increasing learning rate, Ve. which
helps for the convergence (i.e., average regret RegreI, suggested that $1 = 0.9 and 3g = 0.99.
+ 0). For the parameters of AMSGRAD, is
T
3 OPTIMISTIC-AMSGRAN
Algorithm 2 OPTIMISTII-AMMSGRAD
1: Required: parameter 31. 82, and mr-
2: Init: W1 W/112 E Rd and 0s vo E Rd. do 4: Get mini-batch stochastic gradient vector dr at we.
3: for f = 1
5: 0, 3,0,-1 + (1- 81 )ge.
6: de $20 + (1 (g) m4)*
7:
ūt max(f(-1,2))
8:
W & = IIx [W,-3 vo.]
9:
we+1 He [ M6+1 v
het1
where hec1 B101-1 + (1 Br 31)e4+1
and me+1 is the guess of gt+1-
10: end for
We propose a new optimization algorithm, OPTIMISTI-AMMGRRN shown in Algorithm In each iteration, the learner computes gradient vector It (l,(w,) at w, (line 4), then it maintains an exponential moving average of 0g IR (line 5) and E R2 (line 6), which is followed by the max operation obtain E H (line 7). The learner also updates an auxiliary variable w E I. (line 8). uses the auxiliary variable update and commit W (line 9), which exploits the guess me++ of 9++1 1 to get Wx+1. As the learner's s action set is K. C Rdd we adopt the notation [Tx[[]] for the projection IC if needed.
We see that OPTIMISTIC-AMSGRAA has three properties:
Adaptive learning rate of each dimension as ADAGRAD Duchi et al. (001)) l). (line 6, line and line 9)
Exponentially moving average of the past gradients NESTEROV'S METHOD (Nesterov) (004)) and the HEAVY-BALL method (Polyak (1944). (line 5)
Optimistic update that exploits good guess of the next gradient vector as optimistic online
learning algorithms (c.g. Chiang et al. (2012): Rakhlin & Sridharan 201 b): Syrgkanis
et (2015)). (line
The first property helps for acceleration when the gradient has sparse structure. The second one from the well-recognized idea of momentum which can also help for acceleration. The last one, perhaps less known outside the ONLINE LEARNING community, when the prediction the next gradient good. This property will be elaborated in the following subsection in which provide the theoretical analysis of AETTMISTIC-AMGGII
actually lead to acceleration

---

Under review as a conference paper at ICLR 2020
Observe that the proposed algorithm does not reduce AMSGRAD when m, 0. Furthermore, if = Id (unconstrained case), one might want to combine line and line 9 and get a single line as he-1 Yet, based on this expression, we see that Wx+11 is updated from Wr+11 = : 1/ Ve. T ve, " instead of wy. Therefore, while OPTIMISTIC-AMSGRA update compared to A.SSGRDD, the difference of the updates is subtle. In the following analysis, we show that the interleaving actually leads to certain cancellation in the regret bound.
8
looks like just doing an additional
3.1 THEORETICAL ANALYSIS OF OPTIMISTIC-AMSGH
We provide the regret analysis here. To begin with, let us introduce some notations first. We denote the Mahalanobis norm || || := v ((, H-) for some PSD matrix H. We let (h( ==
(a, diag ( 1/2xx) for PSD matrix H!
diag (e 1/2 where diagf represents the diagonal
matrix whose len. diagonal element is 02 [i] in Algorithm 2 We define its corresponding Mahalanobis norm || 11,, = (c, diag (6. J./2,3 where we slightly abuse the notation the to represent the PSD) matrix H H²/² = diag 1/2. Consequently, (-x is 1 1-strongly convex with respect to the norm II- llv. = Vi,, diag ( )1/2.3. Namely, (-a-) satisties (x) 2 (v(()) + (v)( a--u--u u)
v e
for any point u, A consequence of I-strongly convexity of (+) is that B (u, 2 2
where the Bregman divergence (,,((,, v) is defined as B (u, == ( ve(2) (v)( u
with (-) as the distance generating function. We can also define the corresponding dual norm
|l ll: v(, diag(&
We prove the following result regarding to the regret the convex loss setting. The proof available in Appendix B For simplicity, we analyze the case when 81 = 0. One might extend our analysis to more general setting 51 = [0, 1).
Theorem 1. Let 31 O. Assume that K. has bounded diameter Doo Suppose that the learner incurs sequence of convex loss functions {kx(-)-- OPTIMISTIC-AMGRRR (Algorithm 2 has regret
Regrety S 1 D2 Σ1
07
11/2 Boy (w w21/))
Et= Dt 11g.
me me
(1)
Muiin
(w,) and Mmii = min; th- The result holds for any benchmark w" E K. and any step size sequence {m....
where 9:
Corollary 1. Suppose that Vt is always monotone increasing (i.e. 0r vt, Vl). Then,
Regret, I I D2 Ei [(1 32) ΣT 3 "(g [i] m. k2))
Mmin B (w w112)
It m4 12 1
m
We should compare the bound of 2 with that of AMSGRAD Reddi et al. (001 which is
Regret, S /T D2 EL_ 1. + D2 E Ed
A10,1)1/22 (1-A1)
2ny 11 (1)
1Vl 11
Ele [1]l:
where the result was obtained by setting the step size 7) = n/V.. Notice that 0, in (3) is the one in Algorithm ( (AMSGRAD). For fair comparison, let us set 1/2 = n// /I in (2) so that 7 y and Tmii 17/ VT and also let us set 31 = 0 in 3 so that their parameters have the same values ours in the analysis. By comparing the first term in and
(3. we clearly see that if ge and m, are close,
the first term in would be smaller than 2n
TT
Di=1 11) of (3.
'The boundedness assumption also appears the previous works (Reddi et al. 2018 Kingma & Ba 2015 ).
It to he necessary in regret analysis. If the boundedness assumption is lifted, then might construct scenario such that the benchmark is w² oc and learner's 's regret is infinite.
"The following conclusion in general holds for (1). when v, may not be monotone-inereasing For brevity, we only consider the that 0, Ve, fr has clean expression in this case.
4

---

Under review as a conference paper at ICLR 2020
( and 33. see that Be, (w=", (w=,,1122)
Now let us switch the second term in
Do in while
n/
For the last term 2 we have
Σ 1=1 2
Te 11gt
-mel-lle mell
Th 119. -mel melb:z + +1
(0rl)) mrl1)
2
a=1
Σ
Mt 111
mel +1 Σ
(gr mm [i])
f=1
(((1 B2) Eim $22" 22'-1
(g. [1]
mm [0])
d T
[0 me [i])
[((1 32)
3))
1 [g.li] 1
m. m, [i))
To interpret the bound, let us make rough approximation such that
t-
Σ
5
[9 m,, (gell] m
We then further obtain an upper-bound
11 2 Ilge m4 mlllep.
17
i mil
MV 1 + log T
El( m).r M112,
Vt
where the last inequality is due Cauchy-Schwarz. The bound means that when gr and m. are sufficiently close, the last term in (2) is smaller than that in (3)
To conclude, as the second term in 2 (which is approximately Dxo) likely be dominated by the other terms, the proposed algorithm improves AMSGRAD when the good guess m, is available.
4 PREDICTING m
From the analysis in the previous section, we know that whether OPTIMISTIC-AMGGRAD converges faster than its counterpart depends on how m, is chosen. In OPTIMISTIC- ONLINE LEARNING, m. is usually set to
9t-1, i.e., using the previous gradient as guess of the next one. The choice can accelerate the convergence to an equilibrium some two-player zero-sum games (Rakhlin & Sridharan (20 3a b): Syrgkanis et al.] (2015); Daskalakis et al. (208)), in which each player uses an optimistic on onne learning algorithm against its opponent.
This paper is, however, about solving optimization problems instead of solving zero-sum games. We propose to use the extrapolation algorithm of (Scieur et al. (2016)). Extrapolation studies estimating the limit of sequence using the last few iterates (Brezinski & Zaglia (201)). Some classical works include Anderson acceleration (Walker & (201 minimal polynomial extrapolation (Cabay & Jackson (1976)), reduced rank extrapolation (Eddy (1979)). These methods typically assume that the sequence [Zte E Rd has linear relation
Ft A(x x²) +
and A IRdx is unknown, necessarily symmetrie, matrix. The goal is to find the fixed point of x=" [Scieur et al. (2016) relaxes the assumption to certain degrees, by assuming that the sequence {2:} Id satisfies
- xx A( 1 ee,
where e, is a second order term satisfying ||, l2 = 0 [||1 =13 and A E Rdxd is an unknown matrix. The extrapolation algorithm we used is shown in Algorithm Some theoretical guarantees regarding the distance between the output and x are provided in (Scicur et al. (2016)).
5

---

Under review as a conference paper at ICLR 2020
Algorithm 3 REGULARIZED APPROXIMATE MINIMAL POLYNOMIAL EXTRAPOLATION (RMPE) (Scieur et al. (0166)
1: Input: sequence {a, E Rd1 parameter À > O.
2: Compute matrix
[21 ;o....,2r 2r-1] gdxr.
3: Ohtain by solving U U =
4: Get c = 2/(2"11 1).
5: Output: c the approximation of the fixed point x="
For OPTIMISTIC-AMGRRAN we use Algorithm get m4+1. The following describes the procedure.
Call Algorithm with input being sequence of some past + iterates, { Wpy Wt-1, Wt- 2:. We-r), where r a parameter.
from the output of Algorithm Set ux+1 2 0:00-+44
Output m4+1 ((it+))
That is, the latest iterates are the input Algorithm 3 The prediction of the gradient m4+1 is by computing mini-batch stochastic gradient at the output, namely at W of Algorithm 3
We would like to emphasize that the choice of algorithm for gradient prediction is surely not unique. We propose to use the recent result among various related works. Indeed, one can use any method that can provide reasonable guess of the gradient in next iteration.
The work (Scieur et al. (2016) leverages its extrapolation algorithm to post-process the trajectory gradient descent and obtains a point that is closer an optimal point. In contrast, we use the extrapolation algorithm on the fly to accelerate the convergence (of OPTIMISTIC-AMSGEA
Remark:
5 EXPERIMENTS
Datasets and neural nets: The experiments were conducted on CIFARIO and CIFAR 100 datasets, and a noisy variant MNIST dataset (MNIST-back-Imaa) (Larochelle et al. (2077) D. We train Res-18 18 HHe et al. (2016)) for CIFARI0 and CIFARION datasets and four-layer convolutional neural net for the noisy MNIST dataset.
In all the experiments described in the following of this section, the following hyper- parameters:
Step size 7) = 0.001.
31 0.9, $2 0.99.
Number of training samples in each batch: batch_size 64.
(Optimisic-AMMSGG Number previous iterates stored for gradient prediction: r = (i.c., 5 means the latest five iterates stored for gradient prediction).
As these classification tasks, on CIFAR 10 and CIFAR 100, after getting the guess of the next iterate ú by the extrapolation method, we construct the guess of the next gradient 74441 by computing mini-batch of stochastic gradient of the negative log likelihood loss 6 at úú,- (instead of the gradient of the cross entropy loss 1. The slight modification leads better performance.
the entropy loss for training the neural nets. For training
SUNIST-bac--iman takes random patches from black and white as noisy background. The dataset 12,00 training samples and 50,000 test samples.
Specifically, we use neural model defined the tutorial page httpt::tt////tii hagghttpess//ihhhb.cmmmpprrrrree
exampl 1 es http//llbb//tttee//e////// /mni st/ma/ p.py
"Assume K classification problem. Denote the values on the output layer di E R for sample i with true lahel ys E [K]. its negative log likelihood loss defined [y] See function nll loss in PyTorch for details.

---

Under review as a conference paper at ICLR 2020
CIFAR10~Res-18
Training Accuracy (%)
95
Train Accuracy
0.8
90
Training Loss
AMSGrad OPT--MSSrrad
0.6
85
0.4
80
AMSGrad OPT- MPT--A
0.2
75
Train Loss
ReFAR1
70
20
40
60
80
100
20
40
60
80
100
Epochs
Epochs
0.6
CIFAR10+Res-18
Testing Accuracy (%)
95
Test Accuracy
AMSCrad
Testing Loss
0.5
OPT AMSGrad
90
85
0.4
AMSGrad OPT AMSGrad
80
0.3
Test Loss
CIFAR10+Res-18
75
100
20
80
100
# Epochs
# Epochs
Figure 1: CIFAR 10 + Res-18. We compare OPTIMISTIC AMMSSADD with AMSGRAD in terms of training (cross-entropy) loss, training accuracy, testing loss, and testing accuracy. All measures are plotted against the numbers of epochs. (One epoch means all training data points are used once). We can see that OPTIMISTIC-AMSSCO noticeably improves AMSGRAD in all four measures.
CIFAR100~Res-18
Training Accuracy (%)
Train Accuracy
1.8
70
Training Loss
AMSGrad
65
1.6
OPT-AMSGrad
60
1.4
55
AMSSCra OPT-AMSGrad
1.2
50
45
Train Loss
CIFAR100+Res-18
0.8
40
100
20
60
80
# Epochs
# Epochs
2
70
CIFAR100+Res-18
Testing Accuracy (%)
Test Accuracy
65
Testing Loss
1.8
AMSGrad
60
1.6
55
AMSGrad
-50
OPT-AMSCrad
1.4
45
Test Loss
Res-R10
1.2
40
20
40
60
80
100
20
40
60
80
100
Epochs
Epochs
Figure 2: CIFAR 100 + Res-18. We compare OPTIMISTIC-AMSS with AMSGRAD in terms of training (cross-entropy) loss, training accuracy, testing loss, and testing accuracy.
Results: Figure
I shows the result on CIFARIO+Res: 18 and Figure 2 shows the result on
CIFAR100+Rey- 18. Figure shows the result on MNIST-back-img dataset From the results
"Note that our results on MNIST-back-inas image actually improved those reported in (Larochelle et al (2007 ).
which did not convolutional nets. The test accuracy comparable to that reported in (Li 2010 which

---

Under review as a conference paper at ICLR 2020
100
Training Accuracy (%)
MNIST-Image CNN
MNIST-Image CNN
0.4
Training Loss
AMSGrad
95
PPT--AMSrrad
0.2
AMSGrad
90
OPT AMSGrad
Train Loss
Train Accuracy
1
2
3
4
5
6
8
10
2
4
5
6
7
9
10
# Epochs
Epochs
0.6
96
MNIST-Image CNN
Testing Accuracy [%)
94
Test Accuracy
Testing Loss
0.5
92
AMSGrad
OP AMSGral
90
0.4
88
AMSGrad
86
OPT- AMSGrad
0.3
84
82
Test Loss
MNIST-Imagh CNN
0.2
80
6 # Epochs
8
10
6 # Epochs
Figure 3: MNIST-back- + CNN. We compare SETTIMISIIC-MMSGRA with AMSGRAD in terms of training (cross-entropy) loss, training accuracy, testing loss, and testing accuracy.
shown on the figures, it is clear that CRMMIISICCAMSGRRA noticeably improves AMSGRAD in terms of the standard performance measures: training (cross entropy) loss, testing loss, training classification accuracy, and testing classification accuracy. All results are plotted against the number of training epochs. The results also suggest that OPTIMISTIC-AMSGE
finds better point that generalize well than AMSGRAD. In Appendix D.2 we report OPTIMISTIC-MMSGE ent values of the parameters We find that the algorithm performance is not sensitive the choice of
with differ-
we provide comprehensive survey of the related works. There has been a trend in studying adaptive optimization methods from different respects. We compare our contribution and some of the related works, in particular AO-FTRL Moohri & Yang (2016) and OPTIMISTIC-ADII provide the experimental results for the comparison to modilied version of OPTIMISTIC-ADAM,
Comparisons with related works. In Appendix A
(Daskalakis et al. (2018)). Moreover, in Section D. we
6 CONCLUSION
We propose OPTIMISTIC-AMSGRAN that combines the ideas of optimistic online learning and A AMSGRAD to accelerate optimization. For training deep neural networks, APTIMISTIC-AMSGRMM significantly improves AMSGRAD in terms various performance measures practice (e.g. training loss, testing loss, and classification accuracy on training/testing data). Though we only provide the theoretical analysis in the convex setting, the experiment in non-convex optimization shows some promising results. The results seem to suggest that OPTIMISTIC-AME AMGRAD not only minimizes the training loss faster but it can also find a point that generalizes better than the basclines. As the success of OPTIMISTIC-AB AMSTTCAA relies a good guess of the next gradient, future work includes improving predicting gradients. Exploring the possibility
developing a new way to obtain a better guess of the gradient would be an interesting direction. One possibility is by considering a very recent work of (Dutta et al. (2019) which proposes a new extrapolation algorithm.
developed the second-order tree-split formulation for boosted trees. Also kernel methods.
Li (018 for comparisons with
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Jacob Abernethy, Kevin A. Lai, Kfir Y. Levy, and Jun-Kun Wang. Faster rates for convex-coneave games. COLT, 2018.
Naman Agarwal, Brian Bullins, Xinyi Chen, Elad Hazan, Karan Singh, Cyril Zhang, and Yi Zhang. Efficient full-matrix adaptive regularization. ICML, 2019.
Rohan Anil, Vineet Gupta, Tomer Koren, and Yoram Singer. Memory efficient adaptive optimization. NeurlPS, 2019.
Gary Becigneul and Octavian-Fugen Ganea. Riemannian adaptive optimization methods. ICLR, 2019.
C. Brezinski and M. Zaglia, Extrapolation methods: theory and practice. Elsevier, 2013.
S. Cabay and L. Jackson. A polynomial extrapolation method for finding limits and antilimits of vector sequences. SIAM Journal on Numerical Analysis, 1976.
Jinghui Chen and Quanquan Gu. Closing the generalization gap of adaptive gradient methods in training deep neural networks. arXiv:1806.00 06763, 2018.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of adam-type algorithms for non-convex optimization. ICLR, 2019a.
Zaiyi Chen, Zhuoning Yuan, Jinfeng Yi, Bowen Zhou, Enhong Chen, and Tianbao Yang. Universal stagewise learning for non-convex problems with convergence averaged solutions. ICLR, 2019b.
Chao-Kai Chiang, Tianboo Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. COLT, 2012.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. ICLR, 2018.
Timothy Dozat. Incorporating nesterov momentum into adam. ICIR (Workshop Track), 2016.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research (JMLR), 2011.
Aritra Dutta, El Houcine Bergou, Yunming Xiao, Marco Canini, and Peter Richtarik. Direct nonlinear acceleration. arXiv: 1692, 2019.
R. Eddy. Extrapolating to the limit of vector sequence. Information linkage between applied mathematics and industry, Elsevier, 1979.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Marde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. NIPS, 2014.
Alex Graves, Abdel rahman Mohamed, and Geoffrey Hinton. Speech recognition with deep recurrent neural networks. ICASSP, 2013.
Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned stochastic tensor optimiza- tion. ICML, 2018
Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. CVPR, 2016.
Nitish Shirish Keskar and Richard Socher. Improving generalization performance by switching from adam to sgd. arXiv:1712.07628, 2017.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. ICLR, 2015.

---

Under review as a conference paper at ICLR 2020
Hugo Larochelle, Dumitru Erhan, Aaron Courville, James Bergstra, and Yoshua Bengio. An empirical evaluation of deep architectures on problems with many factors variation. ICML, 2007.
Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep visuomotor policies. NIPS, 2017.
Ping Li. Robust logitboost and adaptive base class (abe) logitboost. UAI, 2010.
Ping Li. Several tunable GMM kernels. /005::8800022... 2018.
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. AISTAT, 2019.
Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and beyond. arXiv:1908. 03265, 2019.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. ICLR, 2019.
Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. ICLR, 2019.
James Martens and Roger Grosse. Optimizing neural networks with kronecker-factored approximate curvature. ICML, 2015.
H. Brendan McMahan and Matthew J. Streeter. Adaptive bound optimization for online convex optimization. COLT, 2010.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. NIPS (Deep Learning Workshop), 2013.
Mehryar Mohri and Scott Yang, Accelerating optimization via adaptive prediction. AISTATS, 2016.
Yurii Nesterov. Introductory lectures convex optimization: A basic course. Springer, 2004.
B. Polyak. Some methods of speeding up the convergence of iteration methods. Mathematics and Mathematical Physics, 1964.
Alexander Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. NIPS, 2013a.
Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequence. COLT, 2013b.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. ICLR, 2018.
Damien Scieur, Alexandre d' Aspremont, and Francis Bach. NIPS, 2016.
Regularized nonlinear acceleration.
Matthew Staib, Sashank J. Reddi, Satyen Kale, Sanjiv Kumar, and Suvrit Sra. Escaping saddle points with adaptive gradient methods. ICML, 2019.
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E. Schapire. Fast convergence of regularized learning in games. NIPS, 2015.
T. Tieleman and G. Hinton. Rmsprop: Divide the gradient by running average of its recent
magnitude. COURSERA: Neural Networks for Machine Learning, 2012.
Paul Tseng. On accelerated proximal gradient methods for convex-concave optimization. 2008
H. F. Walker and P. Ni. Anderson acceleration for fixed-point iterations. SIAM Journal on Numerical Analysis, 2011.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization. ICML, 2019.
10

---

Under review as a conference paper at ICLR 2020
Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. NIPS, 2017.
Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. NeurlPS, 2018.
Matthew D. Zeiler. Adadelta: An adaptive learning rate method. arXivv1212.5701, 2012.
Dongruo Zhou, Yiqi Tang, Ziyan Yang, Yuan Cao, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization.
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.
Fangyu Zou and Li Shen. On the convergence of adagrad with momentum for training deep neural networks. 1808. 2018.
A COMPARISON TO RELATED WORKS
A.1 COMPARISON TO SOME NON-CONVEX OPTIMIZATION WORKS
Recently, Zaheer et al. (2018) Chen et al. (019a): : Ward et al. 2019); Zhou et al. (2018); Zou &
Shen 22088); Li & Orabona. (2099) provide some theoretical analysis of ADAM-type algorithms
when applying them to smooth nonconvex optimization problems. For example, [Cen et al. (2019a) Ollog T/vT), Yet, this data independent bound does not show an advantage over standard stochastic gradient descent. Similar concerns appear in other papers.
provide a bound, which is min Elll (w)) =
To obtain some adaptive data dependent bound (e.g.. bounds like (2) or (3) that are in terms of the gradient norms observed along the trajectory) when applying OPTIMISTIC- AMMII-AAMGRADD to nonconvex optimization, one can follow the approach of (Agarwal et al. (219) or (Chen et (019b)). ). They provide ways to convert algorithms with adaptive data dependent regret bound for convex loss functions (e.g.. ADAGRAD) to the ones that can find an approximate stationary point of non-convex loss functions. Their approaches are modular so that simply using OPTIMISTIC-AMSCOI base algorithm their methods will immediately lead to a variant of OPTIMISTIC- -AATTCCAAMGAAAAAA that enjoys some guarantee nonconvex optimization. The variant can outperform the ones instantiated by other ADAM-type algorithms when the gradient prediction my is close to gt. We omit the details since this is a straightforward application.
as the
A.2 COMPARISON TO MOHRI& & YANG 2016
Mohri & Yang (2016) proposes AO-FTRL, which has the update of the form Wi+1 arg min (E:=1 9.) w + m/+ + Fa:e (w)) where ro: is 1-strongly convex loss function with respect to some norm (l()) that may be different for different iteration t. Data dependent
regret bound was provided in the paper, which (o:r(w") )+ ETT llg. mell(o) ( for any benchmark w E K. We see that if one selects To: (w) == (w, diag (ú,) ) )1/2w) and || [l(e) == v(, diag 1/2.), then the update might be viewed as an optimistic variant of ADAGRAD. However, no experiments was provided in (Mohri & Yang (2016)).
A.3 COMPARISON TO OPTIMISTIC-ADAM OF (DASKALAKIS ET AL. (2018)
We are aware that Daskalakis et al. (0088) proposed one version of optimistic algorithm for ADAM, which is called OPTIMISTIC-ADI ADAM in their paper. We want to emphasize that the goals are different. OPTIMISTIC-ADAM in their paper is designed to optimize two-player games (e.g.. GANs (Goodfellow et al. )). while the proposed algorithm in this paper is designed to accelerate optimization (e.g., solving empirical risk minimization quickly). Daskalakis al. (2018) focused training GANs (Goodfellow et al. (2014)) GANs is a two-player zero-sum game. There have been some
related works in OPTIMISTIC ONLINE LEARNING like (Chiang et al. 2012); Rakhlin & Sridharan
11

---

Under review as a conference paper at ICLR 2020
Algorithm 4 OPTIMISTIC-AAAMM (Daskalakis et al. (2018))
1: Required: parameter $1, $2, and 77..
2: Init: Wi E K.
3: for t= to T do
4: Get mini-batch stochastic gradient vector Ir E Rd at wy.
5: 0, = 1100-1 + (1 B1 gt.
6: Dr = 120 + +(1 -22)9..
7: Wi+1 = [w/e 2nt _,_
+ ne /r--
0--1
vvc
8: end for
(2013a b): Syrgkanis al. (015)) showing that if both players some kinds of OPTIMISTIC- update, then accelerating the convergence to the equilibrium of the game is possible. Daskalakis al. (2018) were inspired by these related works and showed that METTMISTTCCMMRRR-DEESST can avoid the cycle behavior in bilinear zero-sum game, which accelerates the convergence. Furthermore, Daskalakis et al. (2018) did not provide theoretical analysis of OPTIMISTIC-ADAM while we give some analysis for the proposed algorithm.
For comparison, we replicate OPTIMISTIC-ADAN in Algorithm OPTIMISTIC- in Algo- rithm Jusess the previous gradient as the guess of the next gradient. Yet, the update cannot be written into the same form as our (Algorithm 2 actually uses two interleaving sequences of updates {w, ) {w,- } The design and motivation of both algorithms are different.
-MMGRAD (and vise versa). OPTIMISTIC-AMSGRR
A.4 OTHER WORKS ABOUT ADAPTIVE GRADIENT METHODS
There has been spate of research in improving adaptive gradient methods from different respects. Anil et al. (2099 develop a method reduce memory overheads adaptive gradient methods like ADAGRAD and ADAM. Zhou et al. 2019) propose decorrelation between the second moment term i/ and the gradient g. by temporal shifting deal with the converegeee issue of ADAM. Luo et al. (2019) show that an extreme effective learning rate might happen during the execution of ADAM, which can cause the non-convergence. They propose an operation to clip the effective learning rate that avoids the extreme learning rate. Gupta et al. (2018) propose new adaptive gradient method by designing a preconditioned matrix for the update. Liu et al. (2019) study a heuristic called the learning rate "warm-up" and propose new variant of ADAM by including variance rectification term. [Becigneul& & Ganea (2019) propose a counterpart of ADAM for Riemannian manifolds. Other directions include improving the generalization of adaptive gradient methods (e.g. Loshchilov &
Hutter (2019); Chen & Gu (2018); Keskar & Socher. (2017): Luo et al. (2019), comparing adaptive
gradient methods and standard SGD with momentum (e.g. Wilson et al. 2017): Loshchilov & Hutter
(2019), or showing that an adaptive optimization method can escape saddle points (Staib et al. (2019))
B PROOF OF THEOREM
We provide the regret analysis here. To begin with, let us introduce some notations first. We denote the Mahalanobis norm || || = H., for some PSD matrix H. We let v)(()) := (r, diag 6. 1/2xr) for PSD matrix H!!²
( 1/2 where diag( represents the diagonal
matrix whose den diagonal element is 0g in Algorithm 2 We detine its corresponding Mahalanobis norm ||. 11 = ((, diag )1/23,, where we abuse the notation w to represent the PSD matrix H² == diag ) 1/2. Consequently, (hx()) is 1-strongly convex with respect to the norm || llv. :=
Vi, diag 1//.33 Namely, (-) satisfies (h)( 2 (1(()) + (1ix (v), u - v) + 2 u1( for any point u, V. A consequence of 1-strongly convexity of vb((-) that B., (u, llll u ul where
the Bregman divergence By, (u, v) defined as B,, (u, r) := (w) (w) (1)( u -u--0 v) and (e(+)) serves as the distance generating function of the Bregman divergence. We can also define the the corresponding dual norm
llez
V(, dia -1/2...
12

---

Under review as a conference paper at ICLR 2020
Proof. [of Theorem
I By regret decomposition, we have that
Regrety Σ (ww)
min
Σ ((w))
WER
(6)
21= (wn - w', vle(we))
Ei= (we t m²) (we W + (w w², ==,,',","", ge),
where we denote Dt = Vle(wr).
Recall the notation (1) and the Bregman divergence B (u, v) we defined in the beginning of this
section. For $1 = O, we can rewrite the update on line 8 of (Algorithm{)) as
W/ M++5 = arg min Th (w, (.)
By (w, w (x-));
and rewrite the update on line 9 of (Algorithm 2
Wr++ arg miDlee 7/4 (w, me+1) + B (w, (ew, w+++))
(8)
Now we are going to exploit useful inequality (which appears in e.g., Tseng 2008)); for any update of the form v arg minlee (w, 0) By (w, v). holds that
(á- u, 0) Bw v) Bu w) (20 v),
(9)
for any KC. By using 9 for 8 we have
(w, - ( S TJt
(Bv... (w W w/ - B (Wo+g. wi) - B (we, w1-z)),
(10)
and, by using (9) for (7), we have
(We+) - wn .gh) S (Bo, , ((-z)) - Big (w", (w", (e++z) - Byr (w0+)) (11)
So, by and 11 we obtain
Regret,
t=1 (wee - 3 -ma) + (w, - w 3, m.) + (Wo+3 - -w"
T E l - W 110r-1199- mellaz.
(12)
(Ber 1 (W $ (/-5) Bur (We+,, wt) B (wis w
+ B (w", w B (w", m++t)= - Bur (W(+). ( w)))
which is further bounded by
Et=1 2np ||w, We- - 1i2-_,, + 119r melli;, + m +B (Bor (we+g 22 f1lwe+ - -will
B (Wi, (/(+)) + Bi. (w", (,-z) B (w", , Bar (W444: W;= (,- 4)) 1 (Brr (w", ,u,,uu44) Br, (w" werz))
< E (16 I1gs mellvi + me
+ B (W++3 } W w)-3) }) - BB, (we+ ( W.- -))3)))+-
(13)
where (a) because ||l, - w Iarr 11gt mellwy, = inf 2 l|w w 11,,,, + lgg
mell:: by Young's inequality and that vi- 1-) (-) is 1-strongly convex with respect to llv...
To proceed, notice that
Boas (w" ( Bas, (w" w00,,e++)) (w- w diaggaiao (ogg 2//3)(ux wo+g)) S (mmxxx("" [i] W/++ (8])2) (Ed (2/210) 222/((1)) (:))
(14)
13

---

Under review as a conference paper at ICLR 2020
and
B (,, - 1) Bu w
(15)
(1 } t diag 01- 01/ )202) w/- S 0,
as the sequence { is non-decreasing. Therefore,
Regrety
1 Ei= [
Bu (u ww122
+ Σ 2 l1ge m mellizz
Tnnin
71
C DISCUSSION OF ITERATION COST OF OPTIMISTIC-AMSGRAD
We observe that the iteration cost (i.e., actual running time per iteration) of our implementation of CEMMISTIC-AMGRRAAA roughly times larger than the standard AMSGRAD in the empirical minimization task. Here, we report the breakdown analysis for the computational overhead. The overhead mostly comes from the extrapolation step. Specifically, the extrapolation step consists of: (a) The step of constructing the linear system (U U). The cost of this step can be optimized and reduced d, since the matrix U only changes one column time. (b) The step of solving the linear system. The cost of this step is ) which is negligible as the linear system is very small (5-by-5 if 5). (c) The step that outputs an estimated gradient as a weighted average of previous gradients. The cost of this step is x d. So. the computational overhead is 2rd + r Yet, we notice that step (a) and (c) parallelizable.
Memory usage: Our algorithm needs a storage of past gradients to get an estimated gradient. Though seems quite demanding compared to the standard AMSGrad, is relatively cheap compared to Natural gradient method (e.g.. Martens & Grosse (015)), Natural gradient method needs to store some matrix inverse.
14

---

Under review as a conference paper at ICLR 2020
D MORE EXPERIMENTS
D.1 A COMPARISON WITH MODIFIED OPTIMISTIC-ADAM
DASKALAKIS ET AL.
2018)
Algorithm 5 OPTIMISTIIC-ADAM+H,
Required: parameter 31, 82, and ?t. 2: Init: W1 E K. and üp = = el E Ra
3: for 1 to T do
4: Get mini-batch stochastic gradient vector Je E R at w..
5: 0: = B,0,-1 + B1 )t
6:
12 + B2)9t
7: & = mnxx(0=-1,1;))
8:
wi+1 - 1w
201e
6_ + mo
8--1 Vor-1"
vol
9: end for
Here we also compare OPTIMISTIC-AMSGGR with another baseline, which we called OPTIMISTIC- Ū as shown in Algorithm [ APTLMISTIC-ADAM-22 is OPTIMISTIC-ADAM (Algorithm 4
of (Daskalakis et al. (2018) with the additional max operation Ú; max(0:-1, vy) to guarantee that the weighted second moment is monotone increasing. Figure and show the results. We observe that our method dominates the other two methods.
95
CIFAR10+Res-18
Train Accuracy
Training Accuracy
0.8
AMSGrad
90
Training Loss
Aadaad
0.6
OPT-Adam
85
AMSGrad
0.4
80
OPT-AMSCrad
OPT Adam++
0.2
75
Train Loss
CIFAR10+Res-18
0
70
20
40
60
80
100
20
60
80
100
# Epochs
Epochs
0.6
95
CIFAR10+Res-18
Testing Accuracy (%)
Test Accuracy
AMSGrad
Testing Loss
90
0.5
HPTT-MdGrad
85
AMSGrad OPT-AMSGrad
0.4
80
OPT-Adam
0.3
Test Loss
CIFAR10+ReS-18
75
20
40
60
80
100
20
60
80
100
# Epochs
Epochs
Figure 4: CIFAR 10 18. We compare three methods: OPTIMISTIC-AMGGRAN AMSGRAD, and OPTIMISTIC-AA ADAMC-, in terms of training (cross-entropy) loss, training accuracy, testing loss, and testing accuracy. We observe that OPTIMISTIC-AMGGRA consistently improves the two baselines.
15

---

Under review as a conference paper at ICLR 2020
2
75
CIFAR100+Res-18
Train Accuracy
1.8
Training Accuracy
70
Training Loss
AMSGrad
65
1.6
OFT-AMSGrad
OPT A
60
1.4
55
AMSGrad
1.2
OPT AMSGrad
50
45
Train Loss
CIFAR100+Res-11
0.8
40
20
40
60
80
100
20
60
80
100
# Epochs
Epochs
2
70
RiFAR100+Res-18
Test Accuracy
AMSGrad
Testing Accuracy
65
Testing Loss
1.8
OPT-AMMSrrad
60
OPT-Adam+
1.6
55
AMSGrad
OPT-AMSGrad
50
OPT Adam++
1.4
45
CIFAR100+Ress
Test Loss
1.2
40
40
60
80
100
20
40
60
80
100
# Epochs
Epochs
Figure 5: CIFAR 100 Res-18. We compare three methods: OPTIMISTICAAMGGRAD AMSGRAD,
and OPTIMISTIC-ADAM-., in terms of training (cross-entropy) loss, training accuracy, testing loss, and testing accuracy.
100
Training Accuracy (%)
MNIST-Image CNN
MNIST-Image + CNN
0.4
Training Loss
AMSGrad
95
OPG-AMdGrad
OPT-Adam+0
AMSGrad
0.2
OPT-AMSCrad
OPT Adam+
Train Loss
Train Accuracy
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
10
# Epochs
Epochs
0.6
96
MNIST-Image CNN
Testing Accuracy
94
MNIST-Image CNN
Testing Loss
0.5
AMSGrad
92
OPT- APT--MdGrad
OPT-Adam-+
90
0.4
88
AMSGrad OPT-AMSGrad
86
0.3
84
OPT Adam+
82
Test Accuracy
Test Loss
0.2
80
1
2
3
4
5
6
7
8
9
10
1
2
4
5
6
7
8
10
# Epochs
#
Epochs
Figure 6: MNIST-back-image noisy dataset + four-layer convolutional neural network.
16

---

Under review as a conference paper at ICLR 2020
D.2 CHOICE OF DIFFERENT VALUES
Recall that our proposed algorithm has the parameter r in addition to the step size that governs the of past information. Figure] 7 8 and cnmpcoe the performance under different values r r= 3, 5, 10. From the result we see that the choice of r does not have significant impact on learning performance. Taking consideration both quality of gradient prediction and computational issues, appears that is good choice, although the results for = 3 do not differ much.
CiFAR10+Res-18
CIFAR10+Res-18
95
Training Accuracy
0.8
AMSGrad
Training Loss
OPT AMSGrad ==3
90
0.6
OPT-AMSGrad 5=
OPT AMSGrad 1-10
85
AMSGrad
0.4
OPT-AMSGrad
80
OPT- AMSGrad r=5
0.2
75
OPT-AMSCrad r-10
Train Loss
Train Accuracy
0
70
20
40
60
80
100
20
40
60
80
100
# Epochs
# Epochs
0.6
95
CiFAR10+Res-18
CIFAR10+Res-18
Testing Accuracy (%)
AMSCrad
Testing Loss
OPT AMSGrad 1=3
90
0.5
OPT-AMSGrad 5=
OPT AMSGrad 1=10
85
AMSGrad OPT-A AET-AMSGrad r=3
0.4
80
OPT-AMSCrad 5
OPT AMSGrad r=10
0.3
Test Loss
Test Accuracy
75
20
40
60
80
100
20
40
60
80
100
# Epochs
Epochs
Figure 7: CIFAR 10 Res-18 18. We compare OPTIMITIICAMISGRAD (for 3, 5, 10) with AMS-
GRAD in terms of training (cross-entropy) loss, training accuracy, testing loss, and testing accuracy. The choice does not have significant impact on learning performance. While appears that 5 is good choice, the results for 3 do not differ much.
17

---

Under review as a conference paper at ICLR 2020
2
75
CIFAR100+Res-18
CIFAR100+Res-18
1.8
AMSGrad
Training Accuracy
70
Training Loss
OPT-AMSCrad r=
65
1.6
OPT-AMSGrad
60
1.4
OPT-AMS AMSGrad r=10
AMSGrad
55
OPT AMSGrad r=3
1.2
50
OPT--MMSrad r=5
OPT-AMSGrad r=10
45
Train Loss
Train Accuracy
0.8
40
20
40
60
80
100
20
40
60
80
100
# Epochs
# Epochs
70
CIFAR100+Res-18
CIFAR100+Res Res-18 18
Testing Accuracy
65
Testing Loss
1.8
AMSGrad
OPT-AMSGrad r=3
60
OPT-AMSGrad r
1.6
OPT AMSGrad 1=10
55
AMSGrad
OPT AMSGrad r-3
50
MSST-d ==5
1.4
OPT- MPP--AMSrrad r=10
45
Test Loss
Test Accuracy
1.2
40
40
60
80
100
20
60
80
100
Epochs
Epochs
Res-18. We compare PETTMISTIC-AMSGRROOO (for 3, 5, 10) with AMSGRAD in terms of training (cross-entropy) loss, training accuracy, testing loss, and testing accuracy. Again, the choice of r does affect the results too much.
Figure 8: CIFAR 100
0.5
100
Train Loss
Training Accuracy (%)
AMSGrad
MNIST-Image + CNN
Training Loss
0.4
APT--MMGrad I=3
OPT-AMSGrad 5=
0.3
OPT AMSGrad r= 10
AMSGrad
0.2
90
OPT-AMSGrad r=3
OPT-AMSGrad r=
0.1
OPT-AMSGrad 1=10
MNIST-Image + CNN
Train Accuracy
0
85
2
3
4
5
10
2
5
# Epochs
Epochs
0.6
96
MNIST-Image CNN
Testing Accuracy (%)
94
MNIST-Image CNN
Testing Loss
0.5
AMSGrad
92
OPTT-MMGraad r 3
90
OPT- AMSGrad r=5
0.4
OPT-AMSGrad r=10
88
AMSGrad
OPT-AMSGrad 3
86
OPT AMSGrad
0.3
84
OPT-AMSGrad 1=10
82
Test Loss
Test Accuracy
0.2
1
2
3
4
5
6
7
8
9
10
1
4
5
6
7
8
10
# Epochs
# Epochs
Figure 9: MNIST-back-image noisy dataset + a four-layer convolutional neural network.
18


Reviews:
[{"review_id": "r1xxZUGRKB", "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": "This paper studies an optimistic variant of AMSGrad algorithm, where an estimate of the future gradient is incorporated into the optimization problem. The main claim is that when we have good enough (distance from the ground truth is small) estimate of the unknown gradient, the proposed algorithm will enjoy lower regret. Theoretical results are provided and experiments are conducted to compare the proposed algorithm with baselines. The idea seems to be not very novel since the optimistic optimization techniques are borrowed directly from the online optimization field, while it is still interesting to see this kind of work and to see its comparison with existing algorithms in experiments. However, the comparison seems to be not fair both in theory and experiments.\n\nIn the second paragraph of Section 2.1, you use $m_t$ to denote an estimate of the loss function. But later (In the third equation) you use $m_t$ to denote the guess of gradient vector. The notation is reloaded without any description, which makes the presentation confusing.\n\nIn addition, at the end of this paragraph, you mentioned that even when $m_t$ is far away from $g_t$, the regret of an optimistic algorithm is just a constant factor of non-optimistic one. This seems not rigorous since it is true only when the divergence of $m_t$ from $g_t$ is in constant order.\n\nCan you explain why in line 8 of Algorithm 2, you use $w_{t-½}$ to update $w_{t+1}$ instead of $w_{t}$? A discussion about these choices should be added to the description of algorithm.\n\nIn the first equation on page 5, the second term on the R.H.S. of the first equation misses a factor of $1/2$. Moreover, the second equation should be inequality.\n\nIn the comparison of equation (2) and (3), I think it should be pointed out that when the gradient has a sparse structure, the regret of the optimistic-AMSGrad in (2) seems to be worse than that of the original AMSGrad.\n\nThe optimistic algorithm seems to cost more computation in order to estimate the unknown gradient in advance. In the experiment part, you used the last few iterations to estimate the guess of gradient in the next step. But it seems that the comparison with $r=3,5,10$ is not consistent in many plots since I expected a larger $r$ will lead to more accurate estimate.\n\nThe experiment results seem to be not convincing. In particular, in Fig. 1,2 and others, the training loss of AMSGrad is far away from zero, which implies that the algorithm is not fully optimized. Therefore, it is hard to draw any meaningful conclusion from the current experiments.\n\nIn footnote 1, “had been known” -> “had known”\n\n====after rebuttal\nThe authors did not provide satisfying response neither submit any revision to address the questions. I will keep my rating. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of 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": "Bkl-NUGTtB", "reviewer": "AnonReviewer3", "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:\n\n\nThis work proposed a new variant of AMSGrad called Optimistic-AMSGrad, which makes use of the ideas from Optimistic Online learning. The authors showed that Optimistic-AMSGrad enjoys lower regret compared with AMSgrad in online learning. Experiment results backup their theory. \n\nPros:\n\nThis work proposed a new variant of AMSGrad called Optimistic-AMSGrad. In the paper the authors showed that by predicting the future gradient using m_t, the regret of Optimistic-AMSGrad can be lowered from \\sum |g_t| to \\sum |g_t - m_t|, which improves AMSGrad directly. The authors also gave a practical way to compute m_t based on history information with the underlying assumption on input x_t. The authors provided detailed experiment results to backup their theory.  \n\nCons:\n\n- There is no discussion about the choice of parameters. From equation 2, Corollary 1, it seems that to set \\beta_2 = 1 achieves the best regret, which implies that to keep v_t unchanged achieves the best result. That sounds a bit strange because it suggests that the coordinate correction is useless. I recommend the authors to add some explanation for their corollary here. \n- The intuition behind Algorithm 3 should be demonstrated more clear. Right now I do not understand how the correlation between x_t affects the prediction of m_t. The authors should add more explanation in Section 3.\n- The experiment results are not well aligned with theoretical results, since the authors considered convex loss in their proof, while the optimization on neural network is a highly non-convex task. I suggest the authors add some simple convex examples to demonstrate the superiority of Optimistic-AMSGrad. \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": "B1xqSC6atS", "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 an online optimization method called Optimistic-AMSGrad, which combines two existing methods: (i) AMSGrad (Reddi et al 2018) and (ii) optimistic online learning where the prediction step is done with the extrapolation algorithm by Scieur et al 2016. The authors do a good job of presenting the method (by introducing the background in proper order), the paper seems self-contained and cites the relevant literature. The regret analysis of the proposed algorithm is provided, where the obtained regret can be smaller than AMSGrad depending on whether or not the guess of the gradient and the gradient are close.\n\nIn my opinion the boundedness assumption (footnote 2) is quite important here, and should be mentioned in the main text. \n\nIt is not clear how the different ways of accelerations combined in this method interact when the guess is not good. In other words, if the guess is not good this method could be slower then AMSGrad. Moreover, AMSGrad has stability property allowed from the ratio between 1st and 2nd moment estimate. In Optimistic-AMSGrad if m_t is bad, obtaining next w_{t+1} (line 9) would include ratio between outdated/bad 1st mom. estimate and new 2nd-moment estimate. In short, the method’s stability and outperformance might rely on the selection of the algorithm for gradient prediction.\n\nIn my understanding, extragradient has clear advantages in games, as if considering simple bilinear examples it is the only method that converges. However, for a single objective, its advantages are not clear to me (after reading the paper). Thus, I think it would be useful if the authors could provide comparison over *wall clock time* as well as long-run comparisons when the compared methods converge (it would be interesting to see if Optimistic-AMSGrad obtains better final train/test accuracy?). In many of the experiments where Opt-AMSGrad outperforms, the accuracy of the baseline still goes up--whereas the latter is computationally cheaper, so it is not clear from the provided results why a practitioner should use this method.\nMoreover, the experimental results would be much more convincing if the authors do multiple runs using different seeds and present mean and standard deviation of the methods.\nIn the context of games, using more computationally demanding optimizers makes sense as training is unstable. In this case, after reading the paper, it is not clear to me what is the problem that the proposed method solves (or its advantages). Indeed, its advantage depends on how good the guess of g_{t+1} is. However, the extra-computation cost to obtain a good guess needs to be justified, or proven empirically that gets better performances faster (wall-clock time), or final ones.\n\nIn summary: (i)  the paper is well-presented and provides hyperparameter sensitivity results; (ii) the paper is very interesting, but (imo) it should leave clearer message why one should use this method; (iii) the proposed method has tighter regret, but only in some (data-dependent) cases and combines existing methods, limiting novelty. Hence, given the pros and cons, I am not confident recommending acceptance, and I think improved experimental results (error bars & wall-clock, see above) would make the results more significant.\n\n\n--- Minor ---\n- Alg.2: maybe add input hyperparameter r to optimistic-AMSGrad and a line between lines 8-9 that calls function which obtains the guess m_{t+1} (r should be passed to it). It would make it more clear that your algorithm has parameter r (sec. D.2)\n- I could be wrong, but in my opinion, using \\theta as first moment est. is slightly confusing, as it is normally used to denote parameters; similarly, the authors could use hat/prime on top of a variable to denote the ‘guess’ of that same variable, making it easier to follow.\n- maybe add init of \\theta_0 in alg1&2\n- if I am correct amsgrad also does bias correction of the initial values of 1st and 2nd moment estimates; if that’s the case it could be useful adding a note that this is omitted for clarity if a reader implements it\n- pg2: we just would like -> we would like\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: The paper introduces a variant of AMSGrad ("Optimistic-AMSGrad"), which integrates an estimate of the future gradient into the optimization problem. While the method is interesting, reviewers agree that novelty is on the low side. The motivation of the approach should also be clarified. The experimental section should be made stronger; in particular, reporting convincing wall-clock running time advantages is critical for validating the viability of the proposed approach. 


Decision: Reject