Year: 2019

Abstract:
This paper considers a new variant of AMSGrad called Optimistic-AMSGrad. AMSGrad (Reddi et al. (2018)) 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.

heading: 1 INTRODUCTION
text: Nowadays deep learning has been very successful in numerous applications, from robotics (e.g., Levine et al. (2017)), computer vision (e.g., He et al. (2016); Goodfellow et al. (2014)), reinforcement learning (e.g., Mnih et al. (2013)), to natural language processing (e.g., Graves et al. (2013)). A common goal in these applications is learning quickly. It becomes a 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 as AMSGRAD (Reddi et al. (2018)), ADAM (Kingma & Ba (2015)), RMSPROP (Tieleman & Hinton (2012)), ADADELTA (Zeiler (2012)), and NADAM (Dozat (2016)), etc.
All the prevalent algorithms for training deep nets mentioned above combine two ideas: the idea of adaptivity from ADAGRAD (Duchi et al. (2011); McMahan & Streeter (2010)) and the idea of momentum from NESTEROV’S METHOD (Nesterov (2004)) or HEAVY BALL method (Polyak (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 a notable feature: the effective learning rate is different for each dimension, depending on the magnitude of gradient in each dimension, which might help in exploiting the geometry of data and leading to a better update. On the other hand, NESTEROV’S METHOD or HEAVY BALL Method (Polyak (1964)) is an accelerated optimization algorithm whose update not only depends on the current iterate and current gradient but also depends on the past gradients (i.e., momentum). State-of-the-art 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. (2015); Abernethy et al. (2018)). OPTIMISTIC ONLINE LEARNING considers that a 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 a theoretical analysis of OPTIMISTIC-AMSGRAD. The proposed 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 OPTIMISTIC-AMSGRAD improves AMSGRAD in terms of various measures: training loss, testing loss, and classification accuracy on training/testing data over epochs.

heading: 2 PRELIMINARIES
text: 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 optimization (Kingma & Ba (2015); Reddi et al. (2018)). For any vector u, v ∈ Rd, u/v represents element-wise division, u2 represents element-wise square, √ u represents element-wise square-root. We denote g1:T [i] as the sum of the ith element of T vectors g1, g2, . . . , gT ∈ Rd.

heading: 2.1 A BRIEF REVIEW OF ONLINE LEARNING AND OPTIMISTIC ONLINE LEARNING
text: The standard setup of online learning is that, in each round t, an online learner selects an action wt ∈ K ⊆ Rd, then the learner observes `t(·) and suffers loss `t(wt) after the learner commits the action. The goal of the learner is minimizing the regret,
RegretT ({wt}) := ∑T t=1 `t(wt)− ∑T t=1 `t(w ∗),
which is the cumulative loss of the learner minus the cumulative loss of some benchmark w∗ ∈ K. The idea of OPTIMISTIC ONLINE LEARNING (e.g., Chiang et al. (2012); Rakhlin & Sridharan (2013a;b); Syrgkanis et al. (2015); Abernethy et al. (2018)) is as follows. Suppose that, in each round t, the learner has a good guess mt(·) of the loss function `t(·) before playing an action wt. Then, the learner should exploit the guess mt(·) to choose an action wt since mt(·) is close to the true loss function `t(·). 1 For example, Syrgkanis et al. (2015) proposes an optimistic-variant of FOLLOW-THE-REGULARIZED-LEADER (FTRL). FTRL (see e.g. Hazan (2016)) is an online learning algorithm whose update is
wt = arg minw∈K〈w,Lt−1〉+ 1ηR(w),
where η is a parameter, R(·) is a 1-strongly convex function with respect to a norm (‖ · ‖) on the constraint setK, and Lt−1 := ∑t−1 s=1 gs is the cumulative sum of gradient vectors of the loss functions
(i.e., gs := ∇`s(ws) ) up to but not including t. FTRL has regret at most O( √∑T
t=1 ‖gt‖∗). On the other hand, OPTIMISTIC-FTRL (Syrgkanis et al. (2015)) has the update
wt = arg minw∈K〈w,Lt−1 +mt〉+ 1ηR(w),
where mt is the learner’s guess of the gradient vector gt := ∇`t(wt). Under the assumption that loss functions are convex, the regret of OPTIMISTIC-FTRL is at most O( √∑T t=1 ‖gt −mt‖∗), which can be much smaller than the regret of FTRL if mt is close to gt. Consequently, OPTIMISTIC-FTRL can achieve better performance than FTRL. On the other hand, if mt is far from gt, then the regret of OPTIMISTIC-FTRL would be only a constant factor worse than that of its non-optimistic counterpart.
In Section 4, we will provide a strategy to obtain mt. At the moment, we just would like to use this example of FTRL to emphasize the importance of leveraging a good guess mt 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-AMSGRAD and AMSGRAD.

heading: 2.2 ADAM AND AMSGRAD
text: ADAM (Kingma & Ba (2015)) is a popular algorithm for training deep nets. It combines the momentum idea (Polyak (1964)) with the idea of ADAGRAD (Duchi et al. (2011)), which has effective different learning rates for different dimensions. The effective learning rate of ADAGRAD in iteration t for a dimension j is proportional to the inverse of √ Σts=1gs[j]
2, where gs[j] is the jth element of the gradient vector gs in time s. This adaptive learning rate might help for accelerating the convergence when the gradient vector is sparse (Duchi et al. (2011)). 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 8 of Algorithm 1). Yet, ADAM (Kingma & Ba (2015)) fails at
1Imagine that if the learner would had been known `t(·) before committing its action, then it would exploit the knowledge to determine its action and consequently minimizes the regret.
Algorithm 1 AMSGRAD (Reddi et al. (2018)) 1: Required: parameter β1, β2, and ηt. 2: Init: w1 ∈ K ⊆ Rd and v̂0 = v0 = 1 ∈ Rd. 3: for t = 1 to T do 4: Get mini-batch stochastic gradient vector gt at wt. 5: θt = β1θt−1 + (1− β1)gt. 6: vt = β2vt−1 + (1− β2)g2t . 7: v̂t = max(v̂t−1, vt). 8: wt+1 = wt − ηt θt√
v̂t . (element-wise division)
9: end for
some online convex optimization problems. AMSGRAD (Reddi et al. (2018)) fixes the issue. The algorithm of AMSGRAD is shown in Algorithm 1. The difference between ADAM and AMSGRAD lies on line 7 of Algorithm 1. ADAM does not have the max operation on line 7 (i.e., v̂t = vt for ADAM) while AMSGRAD adds the operation to guarantee a non-increasing learning rate, ηt√
v̂t , which
helps for the convergence (i.e., average regret RegretTT → 0). For the parameters of AMSGRAD, it is suggested that β1 = 0.9 and β2 = 0.99.

heading: 3 OPTIMISTIC-AMSGRAD
text: Algorithm 2 OPTIMISTIC-AMSGRAD 1: Required: parameter β1, β2, , and ηt. 2: Init: w1 = w−1/2 ∈ K ⊆ Rd and v̂0 = v0 = 1 ∈ Rd. 3: for t = 1 to T do 4: Get mini-batch stochastic gradient vector gt at wt. 5: θt = β1θt−1 + (1− β1)gt. 6: vt = β2vt−1 + (1− β2)(gt −mt)2. 7: v̂t = max(v̂t−1, vt). 8: wt+ 1
2 = ΠK
[ wt− 1
2 − ηt θt√v̂t
] .
9: wt+1 = ΠK [ wt+ 1 2 − ηt+1 ht+1√v̂t ] , where ht+1 := β1θt−1 + (1− β1)mt+1
and mt+1 is the guess of gt+1. 10: end for
We propose a new optimization algorithm, OPTIMISTIC-AMSGRAD, shown in Algorithm 2. In each iteration, the learner computes a gradient vector gt := ∇`t(wt) at wt (line 4), then it maintains an exponential moving average of θt ∈ Rd (line 5) and vt ∈ Rd (line 6), which is followed by the max operation to obtain v̂t ∈ Rd (line 7). The learner also updates an auxiliary variable wt+ 12 ∈ K (line 8). It uses the auxiliary variable to update and commit wt+1 (line 9), which exploits the guess mt+1 of gt+1 to get wt+1. As the learner’s action set is K ⊆ Rd, we adopt the notation ΠK[·] for the projection to K if needed. We see that OPTIMISTIC-AMSGRAD has three properties:
• Adaptive learning rate of each dimension as ADAGRAD (Duchi et al. (2011)). (line 6, line 8 and line 9) • Exponentially moving average of the past gradients as NESTEROV’S METHOD (Nesterov
(2004)) and the HEAVY-BALL method (Polyak (1964)). (line 5) • Optimistic update that exploits a good guess of the next gradient vector as optimistic online
learning algorithms (e.g. Chiang et al. (2012); Rakhlin & Sridharan (2013a;b); Syrgkanis et al. (2015)). (line 9)
The first property helps for acceleration when the gradient has a sparse structure. The second one is from the well-recognized idea of momentum which can also help for acceleration. The last one, perhaps less known outside the ONLINE LEARNING community, can actually lead to acceleration when the prediction of the next gradient is good. This property will be elaborated in the following subsection in which we provide the theoretical analysis of OPTIMISTIC-AMSGRAD.
Observe that the proposed algorithm does not reduce to AMSGRAD when mt = 0. Furthermore, if K = Rd (unconstrained case), one might want to combine line 8 and line 9 and get a single line as wt+1 = wt− 12 − ηt θt√ v̂t − ηt+1 ht+1√v̂t . Yet, based on this expression, we see that wt+1 is updated from wt− 12 instead of wt. Therefore, while OPTIMISTIC-AMSGRAD looks like just doing an additional update compared to AMSGRAD, 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.

heading: 3.1 THEORETICAL ANALYSIS OF OPTIMISTIC-AMSGRAD
text: We provide the regret analysis here. To begin with, let us introduce some notations first. We denote the Mahalanobis norm ‖ · ‖H := √ 〈·, H·〉 for some PSD matrix H . We let ψt(x) := 〈x, diag{v̂t}1/2x〉 for a PSD matrix H1/2t := diag{v̂t}1/2, where diag{v̂t} represents the diagonal matrix whose ith diagonal element is v̂t[i] in Algorithm 2. We define its corresponding Mahalanobis norm ‖ · ‖ψt := √ 〈·, diag{v̂t}1/2·〉, where we slightly abuse the notation ψt to represent the PSD matrix H1/2t := diag{v̂t}1/2. Consequently, ψt(·) is 1-strongly convex with respect to the norm ‖ ·‖ψt := √ 〈·, diag{v̂t}1/2·〉. Namely, ψt(·) satisfies ψt(u) ≥ ψt(v)+ 〈ψt(v), u−v〉+ 12‖u−v‖ 2 ψt for any point u, v. A consequence of 1-strongly convexity of ψt(·) is that Bψt(u, v) ≥ 12‖u− v‖ 2 ψt
, where the Bregman divergence Bψt(u, v) is defined as Bψt(u, v) := ψt(u)−ψt(v)−〈ψt(v), u− v〉 with ψt(·) as the distance generating function. We can also define the corresponding dual norm ‖ · ‖ψ∗t := √ 〈·, diag{v̂t}−1/2·〉.
We prove the following result regarding to the regret in the convex loss setting. The proof is available in Appendix B. For simplicity, we analyze the case when β1 = 0. One might extend our analysis to more general setting β1 = [0, 1).
Theorem 1. Let β1 = 0. Assume that K has bounded diameter D∞ 2. Suppose that the learner incurs a sequence of convex loss functions {`t(·)}. OPTIMISTIC-AMSGRAD (Algorithm 2) has regret
RegretT ≤ 1ηminD 2 ∞ ∑d i=1 v̂ 1/2 T [i] + Bψ1 (w ∗,w1/2) η1 + ∑T t=1 ηt 2 ‖gt −mt‖ 2 ψ∗t−1 , (1)
where gt := ∇`t(wt) and ηmin := mint ηt. The result holds for any benchmark w∗ ∈ K and any step size sequence {ηt}.
Corollary 1. Suppose that vt is always monotone increasing (i.e., v̂t = vt,∀t). Then, RegretT ≤ 1ηminD 2 ∞ ∑d i=1{(1− β2) ∑T s=1 β T−s 2 (gs[i]−ms[i])2}1/2
+ Bψ1 (w
∗,w1/2) η1 + ∑T t=1 ηt 2 ‖gt −mt‖ 2 ψ∗t−1 . (2)
We should compare the bound of (2) 3 with that of AMSGRAD (Reddi et al. (2018)), which is
RegretT ≤ √ T 2η(1−β1)D 2 ∞ ∑d i=1 v̂T [i] 2 +D2∞ ∑T t=1 ∑d i=1 β1v̂t[i] 1/2 2ηt(1−β1)
+ η √ 1+log T
(1−β1)2(1−γ) √ 1−β2 ∑d i=1 ‖g1:T [i]‖2,
(3)
where the result was obtained by setting the step size ηt = η/ √ t. Notice that v̂t in (3) is the one
in Algorithm 1 (AMSGRAD). For fair comparison, let us set ηt = η/ √ t in (2) so that η1 = η and
ηmin = η/ √ T and also let us set β1 = 0 in (3) so that their parameters have the same values as ours in the analysis. By comparing the first term in (2) and (3), we clearly see that if gt and mt are close, the first term in (2) would be smaller than √ T 2η(1−β1)D 2 ∞ ∑d i=1 v̂T [i] 2 of (3).
2The boundedness assumption also appears in the previous works (Reddi et al. (2018); Kingma & Ba (2015)). It seems to be necessary in regret analysis. If the boundedness assumption is lifted, then one might construct a scenario such that the benchmark is w∗ =∞ and the learner’s regret is infinite.
3The following conclusion in general holds for (1), when vt may not be monotone-increasing. For brevity, we only consider the case that v̂t = vt, as v̂T has a clean expression in this case.
Now let us switch to the second term in (2) and (3), we see that Bψ1 (w ∗,w1/2)
η1 ' D∞ in (2), while 0
in (3). For the last term in (2), we have∑T t=1 ηt 2 ‖gt −mt‖ 2 ψ∗t−1
= T−1∑ t=1 ηt 2 ‖gt −mt‖2ψ∗t−1 + ηT d∑ i=1 (gT [i]−mT [i])2√ vT−1[i]
= T−1∑ t=1 ηt 2 ‖gt −mt‖2ψ∗t−1 + η d∑ i=1 (gT [i]−mT [i])2√ T ( (1− β2) ∑T−1 s=1 β T−1−s 2 (gs[i]−ms[i])2
) ≤η
d∑ i=1 T∑ t=1 (gt[i]−mt[i])2√ t ( (1− β2) ∑t−1 s=1 β t−1−s 2 (gs[i]−ms[i])2
) . To interpret the bound, let us make a rough approximation such that
t−1∑ s=1 βt−1−s2 (gs[i]−ms[i])2 ' (gt[i]−mt[i])2.
We can then further obtain an upper-bound as
T∑ t=1 ηt 2 ‖gt −mt‖2ψ∗t−1 / η√ 1− β d∑ i=1 T∑ t=1 |gt[i]−mt[i]|√ t ≤ η √ 1 + log T√ 1− β d∑ i=1 ‖(g −m)1:T [i]‖2,
where the last inequality is due to Cauchy-Schwarz. The bound means that when gt and mt 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 D∞) is likely to be dominated by the other terms, the proposed algorithm improves AMSGRAD when the good guess mt is available.
4 PREDICTING mt
From the analysis in the previous section, we know that whether OPTIMISTIC-AMSGRAD converges faster than its counterpart depends on how mt is chosen. In OPTIMISTIC-ONLINE LEARNING, mt is usually set to mt = gt−1, i.e., using the previous gradient as a guess of the next one. The choice can accelerate the convergence to an equilibrium in some two-player zero-sum games (Rakhlin & Sridharan (2013a;b); Syrgkanis et al. (2015); Daskalakis et al. (2018)), in which each player uses an optimistic online 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 (2013)). Some classical works include Anderson acceleration (Walker & Ni. (2011)), minimal polynomial extrapolation (Cabay & Jackson (1976)), reduced rank extrapolation (Eddy (1979)). These methods typically assume that the sequence {xt} ∈ Rd has a linear relation
xt = A(xt−1 − x∗) + x∗, (4)
and A ∈ Rd×d is an unknown, not necessarily symmetric, 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 {xt} ∈ Rd satisfies xt − x∗ = A(xt−1 − x∗) + et, (5) where et is a second order term satisfying ‖et‖2 = O(‖xt−1 − x∗‖22) and A ∈ Rd×d is an unknown matrix. The extrapolation algorithm we used is shown in Algorithm 3. Some theoretical guarantees regarding the distance between the output and x∗ are provided in (Scieur et al. (2016)).
Algorithm 3 REGULARIZED APPROXIMATE MINIMAL POLYNOMIAL EXTRAPOLATION (RMPE) (Scieur et al. (2016))
1: Input: sequence {xs ∈ Rd}s=rs=0, parameter λ > 0. 2: Compute matrix U = [x1 − x0, . . . , xr − xr−1] ∈ Rd×r . 3: Obtain z by solving (U>U + λI)z = 1. 4: Get c = z/(z>1). 5: Output: Σr−1i=0 cixi, the approximation of the fixed point x ∗.
For OPTIMISTIC-AMSGRAD, we use Algorithm 3 to get mt+1. The following describes the procedure.
• Call Algorithm 3 with input being a sequence of some past r + 1 iterates, {wt, wt−1, wt−2, . . . , wt−r}, where r is a parameter.
• Set ŵt+1 := Σr−1i=0 ciwt−r+i from the output of Algorithm 3.
• Output mt+1 := ∇̂f(ŵt+1).
That is, the latest r iterates are the input to Algorithm 3. The prediction of the gradient mt+1 is by computing a mini-batch stochastic gradient at the output, namely at ŵt+1, 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.
Remark: The work (Scieur et al. (2016)) leverages its extrapolation algorithm to post-process the trajectory of gradient descent and obtains a point that is closer to an optimal point. In contrast, we use the extrapolation algorithm on the fly to accelerate the convergence (of OPTIMISTIC-AMSGRAD).

heading: 5 EXPERIMENTS
text: Datasets and neural nets: The experiments were conducted on CIFAR10 and CIFAR100 datasets, and a noisy variant of MNIST dataset (MNIST-back-Image (Larochelle et al. (2007)) 4). We train Res-18 (He et al. (2016)) for CIFAR10 and CIFAR100 datasets and a four-layer convolutional neural net 5 for the noisy MNIST dataset.
In all the experiments described in the following of this section, we use the following hyperparameters:
• Step size η = 0.001. • β1 = 0.9, β2 = 0.99. • Number of training samples in each batch: batch size = 64. • (Optimistic-AMSGrad) Number of previous iterates stored for gradient prediction: r = 5
(i.e., r = 5 means the latest five iterates are stored for gradient prediction).
As these are classification tasks, we use the cross entropy loss for training the neural nets. For training on CIFAR 10 and CIFAR 100, after getting the guess of the next iterate ŵt+1 by the extrapolation method, we construct the guess of the next gradient mt+1 by computing a mini-batch of stochastic gradient of the negative log likelihood loss 6 at ŵt+1 (instead of the gradient of the cross entropy loss at t+1). The slight modification leads to a better performance.
4MNIST-back-image takes random patches from a black and white as noisy background. The dataset has 12,000 training samples and 50,000 test samples.
5Specifically, we use a neural net model defined on the tutorial page https://github.com/pytorch/ examples/blob/master/mnist/main.py.
6Assume a K classification problem. Denote the values on the output layer ŷi ∈ RK for a sample i with true label yi ∈ [K], its negative log likelihood loss is defined as −ŷi[yi]. See function nll loss in PyTorch for details.
Results: Figure 1 shows the result on CIFAR10+Res-18 and Figure 2 shows the result on CIFAR100+Res-18. Figure 3 shows the result on MNIST-back-img dataset.7 From the results
7Note that our results on MNIST-back-image actually improved those reported in (Larochelle et al. (2007)), which did not use convolutional nets. The test accuracy is now comparable to that reported in (Li (2010)) which
shown on the figures, it is clear that OPTIMISTIC-AMSGRAD 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-AMSGRAD finds a better point that generalize well than AMSGRAD. In Appendix D.2, we report OPTIMISTIC-AMSGRAD with different values of the parameters r. We find that the algorithm performance is not sensitive the choice of r.
Comparisons with related works. In Appendix A, we provide a 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 (Mohri & Yang (2016)) and OPTIMISTIC-ADAM (Daskalakis et al. (2018)). Moreover, in Section D.1, we provide the experimental results for the comparison to a modified version of OPTIMISTIC-ADAM.

heading: 6 CONCLUSION
text: We propose OPTIMISTIC-AMSGRAD that combines the ideas of optimistic online learning and AMSGRAD to accelerate optimization. For training deep neural networks, OPTIMISTIC-AMSGRAD significantly improves AMSGRAD in terms of various performance measures in 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-AMSGRAD not only minimizes the training loss faster but it can also find a point that generalizes better than the baselines. As the success of OPTIMISTIC-AMSGRAD relies on a good guess of the next gradient, future work includes improving predicting gradients. Exploring the possibility of 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 see (Li (2018)) for comparisons with new kernel methods.

heading: A COMPARISON TO RELATED WORKS
text: A.1 COMPARISON TO SOME NON-CONVEX OPTIMIZATION WORKS
Recently, Zaheer et al. (2018); Chen et al. (2019a); Ward et al. (2019); Zhou et al. (2018); Zou & Shen (2018); Li & Orabona. (2019) provide some theoretical analysis of ADAM-type algorithms when applying them to smooth nonconvex optimization problems. For example, Chen et al. (2019a) provide a bound, which is mint∈[T ] E[‖∇f(wt)‖2] = O(log T/ √ T ). Yet, this data independent bound does not show an advantage over standard stochastic gradient descent. Similar concerns appear in other papers.
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-AMSGRAD to nonconvex optimization, one can follow the approach of (Agarwal et al. (2019)) or (Chen et al. (2019b)). 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-AMSGRAD as the base algorithm in their methods will immediately lead to a variant of OPTIMISTIC-AMSGRAD that enjoys some guarantee on nonconvex optimization. The variant can outperform the ones instantiated by other ADAM-type algorithms when the gradient prediction mt is close to gt. We omit the details since this is a straightforward application.
A.2 COMPARISON TO MOHRI & YANG (2016)
Mohri & Yang (2016) proposes AO-FTRL, which has the update of the form wt+1 = arg minw∈K( ∑t s=1 gs)
>w +m>t+1w + r0:t(w), where r0:t(·) is a 1-strongly convex loss function with respect to some norm ‖ · ‖(t) that may be different for different iteration t. Data dependent regret bound was provided in the paper, which is r0:T (w∗) + ∑T t=1 ‖gt−mt‖(t)∗ for any benchmark
w∗ ∈ K. We see that if one selects r0:t(w) := 〈w, diag{v̂t}1/2w〉 and ‖ · ‖(t) := √ 〈·, diag{v̂t}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. (2018) proposed one version of optimistic algorithm for ADAM, which is called OPTIMISTIC-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. (2014))), while the proposed algorithm in this paper is designed to accelerate optimization (e.g., solving empirical risk minimization quickly). Daskalakis et al. (2018) focused on 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
Algorithm 4 OPTIMISTIC-ADAM (Daskalakis et al. (2018)) 1: Required: parameter β1, β2, and ηt. 2: Init: w1 ∈ K. 3: for t = 1 to T do 4: Get mini-batch stochastic gradient vector gt ∈ Rd at wt. 5: θt = β1θt−1 + (1− β1)gt. 6: vt = β2vt−1 + (1− β2)g2t . 7: wt+1 = Πk[wt − 2ηt θt√vt + ηt θt−1√ vt−1
]. 8: end for
(2013a;b); Syrgkanis et al. (2015)) showing that if both players use some kinds of OPTIMISTICupdate, then accelerating the convergence to the equilibrium of the game is possible. Daskalakis et al. (2018) were inspired by these related works and showed that OPTIMISTIC-MIRROR-DESCENT can avoid the cycle behavior in a 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-ADAM in Algorithm 4. OPTIMISTIC-ADAM in Algorithm 4 uses the previous gradient as the guess of the next gradient. Yet, the update cannot be written into the same form as our OPTIMISTIC-AMSGRAD (and vise versa). OPTIMISTIC-AMSGRAD (Algorithm 2) actually uses two interleaving sequences of updates {wt}Tt=1, {wt− 12 } T t=1. The design and motivation of both algorithms are different.
A.4 OTHER WORKS ABOUT ADAPTIVE GRADIENT METHODS
There has been a spate of research in improving adaptive gradient methods from different respects. Anil et al. (2019) develop a method to reduce memory overheads in adaptive gradient methods like ADAGRAD and ADAM. Zhou et al. (2019) propose decorrelation between the second moment term vt and the gradient gt by temporal shifting to deal with the non-convergence 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 a 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 a new variant of ADAM by including a 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)).

heading: B PROOF OF THEOREM 1
text: We provide the regret analysis here. To begin with, let us introduce some notations first. We denote the Mahalanobis norm ‖ · ‖H = √ 〈·, H·〉 for some PSD matrix H . We let ψt(x) := 〈x, diag{v̂t}1/2x〉 for a PSD matrix H1/2t := diag{v̂t}1/2, where diag{v̂t} represents the diagonal matrix whose ith diagonal element is v̂t[i] in Algorithm 2. We define its corresponding Mahalanobis norm ‖ · ‖ψt := √ 〈·, diag{v̂t}1/2·〉, where we abuse the notation ψt to represent the PSD matrix H 1/2 t := diag{v̂t}1/2. Consequently, ψt(·) is 1-strongly convex with respect to the norm ‖ · ‖ψt :=√ 〈·, diag{v̂t}1/2·〉. Namely, ψt(·) satisfies ψt(u) ≥ ψt(v) + 〈ψt(v), u− v〉+ 12‖u− v‖ 2 ψt
for any point u, v. A consequence of 1-strongly convexity of ψt(·) is that Bψt(u, v) ≥ 12‖u− v‖ 2 ψt
, where the Bregman divergence Bψt(u, v) is defined as Bψt(u, v) := ψt(u)− ψt(v)− 〈ψt(v), u− v〉 and ψt(·) serves as the distance generating function of the Bregman divergence. We can also define the the corresponding dual norm ‖ · ‖ψ∗t := √ 〈·, diag{v̂t}−1/2·〉.
Proof. [of Theorem 1] By regret decomposition, we have that
RegretT := T∑ t=1 `t(wt)− min w∈K T∑ t=1 `t(w)
≤ ∑T t=1〈wt − w∗,∇`t(wt)〉
= ∑T t=1〈wt − wt+ 12 , gt −mt〉+ 〈wt − wt+ 12 ,mt〉+ 〈wt+ 12 − w ∗, gt〉,
(6)
where we denote gt := ∇`t(wt). Recall the notation ψt(x) and the Bregman divergence Bψt(u, v) we defined in the beginning of this section. For β1 = 0, we can rewrite the update on line 8 of (Algorithm 2) as
wt+ 12 = arg minw∈K ηt〈w, gt〉+Bψt(w,wt− 12 ), (7)
and rewrite the update on line 9 of (Algorithm 2) as
wt+1 = arg minw∈K ηt+1〈w,mt+1〉+Bψt(w,wt+ 12 ). (8)
Now we are going to exploit a useful inequality (which appears in e.g., Tseng (2008)); for any update of the form ŵ = arg minw∈K〈w, θ〉+Bψ(w, v), it holds that
〈ŵ − u, θ〉 ≤ Bψ(u, v)−Bψ(u, ŵ)−Bψ(ŵ, v), (9)
for any u ∈ K. By using (9) for (8), we have
〈wt − wt+ 12 ,mt〉 ≤ 1
ηt
( Bψt−1(wt+ 12 , wt− 1 2 )−Bψt−1(wt+ 12 , wt)−Bψt−1(wt, wt− 12 ) ) , (10)
and, by using (9) for (7), we have
〈wt+ 12 − w ∗,gt〉 ≤
1
ηt
( Bψt(w ∗, wt− 12 )−Bψt(w ∗, wt+ 12 )−Bψt(wt+ 12 , wt− 12 ) ) . (11)
So, by (6), (10), and (11), we obtain
RegretT (6) ≤ ∑T t=1〈wt − wt+ 12 , gt −mt〉+ 〈wt − wt+ 12 ,mt〉+ 〈wt+ 12 − w
∗, gt〉 (10),(11)
≤ ∑T t=1 ‖wt − wt+ 12 ‖ψt−1‖gt −mt‖ψ∗t−1
+ 1ηt ( Bψt−1(wt+ 12 , wt− 1 2 )−Bψt−1(wt+ 12 , wt)−Bψt−1(wt, wt− 12 ) +Bψt(w ∗, wt− 12 )−Bψt(w ∗, wt+ 12 )−Bψt(wt+ 12 , wt− 12 ) ) ,
(12)
which is further bounded by
(a) ≤ ∑T t=1{ 1 2ηt ‖wt − wt+ 12 ‖ 2 ψt−1 + ηt2 ‖gt −mt‖ 2 ψ∗t−1 + 1ηt ( Bψt−1(wt+ 12 , wt− 1 2 )− 12‖wt+ 12 − wt‖ 2 ψt−1 −Bψt−1(wt, wt− 12 ) +Bψt(w ∗, wt− 12 )−Bψt(w ∗, wt+ 12 )−Bψt(wt+ 12 , wt− 12 ) ) }
≤ ∑T t=1{ ηt 2 ‖gt −mt‖ψ∗t−1 + 1 ηt ( Bψt(w ∗, wt− 12 )−Bψt(w ∗, wt+ 12 )
+Bψt−1(wt+ 12 , wt− 1 2 )−Bψt(wt+ 12 , wt− 12 )
) },
(13) where (a) is because ‖wt − wt+ 12 ‖ψt−1‖gt −mt‖ψ∗t−1 = infβ>0 1 2β ‖wt − wt+ 12 ‖ 2 ψt−1
+ β2 ‖gt − mt‖2ψ∗t−1 by Young’s inequality and that ψt−1(·) is 1-strongly convex with respect to ‖ · ‖ψt−1 .
To proceed, notice that
Bψt+1(w ∗, wt+ 12 )−Bψt(w ∗, wt+ 12 ) = 〈w ∗ − wt+ 12 , diag(v̂ 1/2 t+1 − v̂ 1/2 t )(w ∗ − wt+ 12 )〉
≤ (maxi(w∗[i]− wt+ 12 [i]) 2) · ( ∑d i=1 v̂ 1/2 t+1[i]− v̂ 1/2 t [i])
(14)
and Bψt−1(wt+ 12 , wt− 1 2 )−Bψt(wt+ 12 , wt− 12 )
= 〈wt+ 12 − wt− 12 , diag(v̂ 1/2 t−1 − v̂ 1/2 t )(wt+ 12 − wt− 12 )〉 ≤ 0,
(15)
as the sequence {v̂t} is non-decreasing. Therefore,
RegretT (13),(14),(15) ≤ 1ηminD 2 ∞ ∑d i=1 v̂ 1/2 T [i] + Bψ1 (w ∗,w1/2) η1 + ∑T t=1 ηt 2 ‖gt −mt‖ 2 ψ∗t−1 .

heading: C DISCUSSION OF ITERATION COST OF OPTIMISTIC-AMSGRAD
text: We observe that the iteration cost (i.e., actual running time per iteration) of our implementation of OPTIMISTIC-AMSGRAD is roughly two 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 to r × d, since the matrix U only changes one column at a time. (b) The step of solving the linear system. The cost of this step is O(r3), which is negligible as the linear system is very small (5-by-5 if r = 5). (c) The step that outputs an estimated gradient as a weighted average of previous gradients. The cost of this step is r × d. So, the computational overhead is 2rd+ r3. Yet, we notice that step (a) and (c) is parallelizable.
Memory usage: Our algorithm needs a storage of past r gradients to get an estimated gradient. Though it seems quite demanding compared to the standard AMSGrad, it is relatively cheap compared to Natural gradient method (e.g., Martens & Grosse (2015)), as Natural gradient method needs to store some matrix inverse.

heading: D MORE EXPERIMENTS
text: D.1 A COMPARISON WITH MODIFIED OPTIMISTIC-ADAM (DASKALAKIS ET AL. (2018))
Algorithm 5 OPTIMISTIC-ADAM+v̂t. 1: Required: parameter β1, β2, and ηt. 2: Init: w1 ∈ K and v̂0 = v0 = 1 ∈ Rd. 3: for t = 1 to T do 4: Get mini-batch stochastic gradient vector gt ∈ Rd at wt. 5: θt = β1θt−1 + (1− β1)gt. 6: vt = β2vt−1 + (1− β2)g2t . 7: v̂t = max(v̂t−1, vt). 8: wt+1 = Πk[wt − 2ηt θt√v̂t + ηt θt−1√ v̂t−1 ].
9: end for
Here we also compare OPTIMISTIC-AMSGRAD with another baseline, which we called OPTIMISTICADAM+v̂t as shown in Algorithm 5. OPTIMISTIC-ADAM+v̂t is OPTIMISTIC-ADAM (Algorithm 4) of (Daskalakis et al. (2018)) with the additional max operation v̂t = max(v̂t−1, vt) to guarantee that the weighted second moment is monotone increasing. Figure 4, 5, and 6 show the results. We observe that our method dominates the other two methods.
D.2 CHOICE OF DIFFERENT r VALUES
Recall that our proposed algorithm has the parameter r in addition to the step size η that governs the use of past information. Figure 7, 8, and 9 compare the performance under different values or 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, it appears that r = 5 is a good choice, although the results for r = 3 do not differ much.

Review summaries:
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.

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.