Title: OPTIMISTIC ADAPTIVE ACCELERATION FOR OPTI-MIZATION

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.

1. INTRODUCTION:

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.

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 ∈ R d , u/v represents element-wise division, u 2 represents element-wise square, √ u represents element-wise square-root. We denote g 1:T [i] as the sum of the i th element of T vectors g 1 , g 2 , . . . , g T ∈ R d .

2.1. A BRIEF REVIEW OF ONLINE LEARNING AND OPTIMISTIC ONLINE LEARNING:

The standard setup of online learning is that, in each round t, an online learner selects an action w t ∈ K ⊆ R d , then the learner observes t (•) and suffers loss t (w t ) after the learner commits the action. The goal of the learner is minimizing the regret,

Regret T ({w t }) := T t=1 t (w t ) - 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 m t (•) of the loss function t (•) before playing an action w t . Then, the learner should exploit the guess m t (•) to choose an action w t since m t (•) 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

w t = arg min w∈K w, L t-1 + 1 η R(w),

where η is a parameter, R(•) is a 1-strongly convex function with respect to a norm ( • ) on the constraint set K, and L t-1 := t-1 s=1 g s is the cumulative sum of gradient vectors of the loss functions (i.e., g s := ∇ s (w s ) ) up to but not including t. FTRL has regret at most O( T t=1 g t * ). On the other hand, OPTIMISTIC-FTRL (Syrgkanis et al. (2015) ) has the update

w t = arg min w∈K w, L t-1 + m t + 1 η R(w),

where m t is the learner's guess of the gradient vector g t := ∇ t (w t ). Under the assumption that loss functions are convex, the regret of OPTIMISTIC-FTRL is at most O( T t=1 g t -m t * ), which can be much smaller than the regret of FTRL if m t is close to g t . Consequently, OPTIMISTIC-FTRL can achieve better performance than FTRL. On the other hand, if m t is far from g t , 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 m t . At the moment, we just would like to use this example of FTRL to emphasize the importance of leveraging a good guess m t for updating w t , 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.

2.2. ADAM AND AMSGRAD:

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 Σ t s=1 g s [j] 2 , where g s [j] is the j th element of the gradient vector g s 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 Algorithm 1 AMSGRAD (Reddi et al. (2018)) 1: Required: parameter β1, β2, and ηt. 2: Init: w1 ∈ K ⊆ R d and v0 = v0 = 1 ∈ R d . 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)g 2 t . 7: vt = max(vt-1, vt). 8: wt+1 = wt -ηt θ t √ vt

. (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., vt = v t for ADAM) while AMSGRAD adds the operation to guarantee a non-increasing learning rate, ηt √ vt , which helps for the convergence (i.e., average regret Regret T T → 0). For the parameters of AMSGRAD, it is suggested that β 1 = 0.9 and β 2 = 0.99.

3. OPTIMISTIC-AMSGRAD:

Algorithm 2 OPTIMISTIC-AMSGRAD 1: Required: parameter β1, β2, , and ηt. 2: Init:

w1 = w -1/2 ∈ K ⊆ R d and v0 = v0 = 1 ∈ R d . 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:

vt = max(vt-1, vt). 8:

w t+ 1 2 = ΠK w t-1 2 -ηt θ t √ vt

. 9:

wt+1 = ΠK w t+ 1 2 -ηt+1 h t+1 √ vt

, 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 g t := ∇ t (w t ) at w t (line 4), then it maintains an exponential moving average of θ t ∈ R d (line 5) and v t ∈ R d (line 6), which is followed by the max operation to obtain vt ∈ R d (line 7). The learner also updates an auxiliary variable w t+ 1 2 ∈ K (line 8). It uses the auxiliary variable to update and commit w t+1 (line 9), which exploits the guess m t+1 of g t+1 to get w t+1 . As the learner's action set is

K ⊆ R d , 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. 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 m t = 0. Furthermore, if K = R d (unconstrained case), one might want to combine line 8 and line 9 and get a single line as

w t+1 = w t-1 2 -η t θt √ vt -η t+1 ht+1 √ vt

. Yet, based on this expression, we see that w t+1 is updated from w t-1 2 instead of w t . 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.

3.1. THEORETICAL ANALYSIS OF OPTIMISTIC-AMSGRAD:

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/2 x for a PSD matrix H 1/2 t := diag{v t } 1/2

, where diag{v t } represents the diagonal matrix whose i th diagonal element is vt [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 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 + 1 2 u -v 2 ψt for any point u, v. A consequence of 1-strongly convexity of ψ t (•) is that B ψt (u, v) ≥ 1 2 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).

EQUATION

where g t := ∇ t (w t ) and η min := min t η t . The result holds for any benchmark w * ∈ K and any step size sequence {η t }.

Corollary 1. Suppose that v t is always monotone increasing (i.e., vt = v t , ∀t). Then,

Regret T ≤ 1 ηmin D 2 ∞ d i=1 {(1 -β 2 ) T s=1 β T -s 2 (g s [i] -m s [i]) 2 } 1/2 + B ψ 1 (w * ,w 1/2 ) η1 + T t=1 ηt 2 g t -m t 2 ψ * t-1

.

(2)

We should compare the bound of (2)3 with that of AMSGRAD (Reddi et al. ( 2018)), which is

EQUATION

where the result was obtained by setting the step size η t = η/ √ t. Notice that vt 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 g t and m t are close, the first term in (2) would be smaller than

√ T 2η(1-β1) D 2 ∞ d i=1 vT [i] 2 of (3).

Now let us switch to the second term in ( 2) and (3), we see that

B ψ 1 (w * ,w 1/2 ) η1

D ∞ in (2), while 0 in (3). For the last term in (2), we have

T t=1 ηt 2 g t -m t 2 ψ * t-1 = T -1 t=1 η t 2 g t -m t 2 ψ * t-1 + η T d i=1 (g T [i] -m T [i]) 2 v T -1 [i] = T -1 t=1 η t 2 g t -m t 2 ψ * t-1 + η d i=1 (g T [i] -m T [i]) 2 T (1 -β 2 ) T -1 s=1 β T -1-s 2 (g s [i] -m s [i]) 2 ≤η d i=1 T t=1 (g t [i] -m t [i]) 2 t (1 -β 2 ) t-1 s=1 β t-1-s 2 (g s [i] -m s [i]) 2 .

To interpret the bound, let us make a rough approximation such that

t-1 s=1 β t-1-s 2 (g s [i] -m s [i]) 2 (g t [i] -m t [i]) 2 .

We can then further obtain an upper-bound as

T t=1 η t 2 g t -m t 2 ψ * t-1 η √ 1 -β d i=1 T t=1 |g t [i] -m t [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 g t and m t 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 m t is available.

4. PREDICTING m t:

From the analysis in the previous section, we know that whether OPTIMISTIC-AMSGRAD converges faster than its counterpart depends on how m t is chosen. In OPTIMISTIC-ONLINE LEARNING, m t is usually set to m t = g t-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 {x t } ∈ R d has a linear relation

EQUATION

and A ∈ R d×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

EQUATION

where e t is a second order term satisfying e t 2 = O( x t-1 -x * 2 2 ) and A ∈ R d×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) ). For OPTIMISTIC-AMSGRAD, we use Algorithm 3 to get m t+1 . The following describes the procedure.

• Call Algorithm 3 with input being a sequence of some past r + 1 iterates, {w t , w t-1 , w t-2 , . . . , w t-r }, where r is a parameter.

• Set ŵt+1 := Σ r-1 i=0 c i w t-r+i from the output of Algorithm 3.

• Output m t+1 := ∇f ( ŵt+1 ).

That is, the latest r iterates are the input to Algorithm 3. The prediction of the gradient m t+1 is by computing a mini-batch stochastic gradient at the output, namely at ŵ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).

5. EXPERIMENTS:

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 ŵt+1 by the extrapolation method, we construct the guess of the next gradient m t+1 by computing a mini-batch of stochastic gradient of the negative log likelihood loss 6 at ŵt+1 (instead of the gradient of the cross entropy loss at t+1 ). The slight modification leads to a better performance. 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 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.

6. CONCLUSION:

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 ( 

[T ] E[ ∇f (w t ) 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 m t is close to g t . 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 w t+1 = arg min w∈K ( t s=1 g s ) w + m t+1 w + r 0:t (w), where r 0: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 r 0:T (w * ) + T t=1 g t -m t (t) * for any benchmark w * ∈ K. We see that if one selects r 0:t (w) := w, diag{v t } 1/2 w 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: w 1 ∈ K. 3: for t = 1 to T do 4:

Get mini-batch stochastic gradient vector g t ∈ R d at w t . 5:

θ t = β 1 θ t-1 + (1 -β 1 )g t . 6: v t = β 2 v t-1 + (1 -β 2 )g 2 t .

7:

w t+1 = Π k [w t -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 {w t } T t=1 , {w t-1 2 } 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 v t and the gradient g t 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) 

B PROOF OF THEOREM 1:

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/2 x for a PSD matrix H 1/2 t := diag{v t } 1/2 , where diag{v t } represents the diagonal matrix whose i th diagonal element is vt [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 + 1 2 u -v 2 ψt for any point u, v. A consequence of 1-strongly convexity of ψ t (•) is that B ψt (u, v) ≥ 1 2 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

EQUATION

as the sequence {v t } is non-decreasing. Therefore, Regret T (13),( 14),( 15)

≤ 1 ηmin D 2 ∞ d i=1 v1/2 T [i] + B ψ 1 (w * ,w 1/2 ) η1 + T t=1 ηt 2 g t -m t 2 ψ * t-1

.

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 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(r 3 ), 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 + r 3 . 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. Get mini-batch stochastic gradient vector g t ∈ R d at w t .

5:

θ t = β 1 θ t-1 + (1 -β 1 )g t .

6:

v t = β 2 v t-1 + (1 -β 2 )g 2 t .

7:

vt = max(v t-1 , v t ).

8:

w t+1 = Π k [w t -2η t θt √ vt + η t θt-1 √ vt-1

].

9: end for

Here we also compare OPTIMISTIC-AMSGRAD with another baseline, which we called OPTIMISTIC-ADAM+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 vt = max(v t-1 , v t ) 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. 

:

Imagine 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.

The 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.

The following conclusion in general holds for (1), when vt may not be monotone-increasing. For brevity, we only consider the case that vt = vt, as vT has a clean expression in this case.

MNIST-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.5 Specifically, we use a neural net model defined on the tutorial page https://github.com/pytorch/ examples/blob/master/mnist/main.py.6 Assume a K classification problem. Denote the values on the output layer ŷi ∈ R K for a sample i with true label yi ∈ [K], its negative log likelihood loss is defined as -ŷi[yi]. See function nll loss in PyTorch for details.

Note 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

developed the second-order tree-split formulation for boosted trees. Also see(Li (2018)) for comparisons with new kernel methods.

Figures and Tables:

Chiang et al. (2012);Rakhlin & Sridharan (2013a;b);Syrgkanis et al. (2015)). (line 9)

REGULARIZED APPROXIMATE MINIMAL POLYNOMIAL EXTRAPOLATION (RMPE) (Scieur et al. (2016)) 1: Input: sequence {xs ∈ R d } s=r s=0 , parameter λ > 0. 2: Compute matrix U = [x1 -x0, . . . , xr -xr-1] ∈ R d×r . 3: Obtain z by solving (U U + λI)z = 1. 4: Get c = z/(z 1). 5: Output: Σ r-1 i=0 cixi, the approximation of the fixed point x * .

Figure 1: CIFAR 10 + Res-18. We compare OPTIMISTIC-AMSGRAD 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-AMSGRAD noticeably improves AMSGRAD in all four measures.

Figure 2: CIFAR 100 + Res-18. We compare OPTIMISTIC-AMSGRAD with AMSGRAD in terms of training (cross-entropy) loss, training accuracy, testing loss, and testing accuracy.

Figure 3: MNIST-back-image + CNN. We compare OPTIMISTIC-AMSGRAD with AMSGRAD in terms of training (cross-entropy) loss, training accuracy, testing loss, and testing accuracy.

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)).

COMPARISON WITH MODIFIED OPTIMISTIC-ADAM (DASKALAKIS ET AL. (2018))Algorithm 5 OPTIMISTIC-ADAM+v t .1: Required: parameter β 1 , β 2 , and η t . 2: Init: w 1 ∈ K and v0 = v 0 = 1 ∈ R d . 3: for t = 1 to T do 4:

Figure 4: CIFAR 10 + Res-18. We compare three methods: OPTIMISTIC-AMSGRAD, AMSGRAD, and OPTIMISTIC-ADAM+v t , in terms of training (cross-entropy) loss, training accuracy, testing loss, and testing accuracy. We observe that OPTIMISTIC-AMSGRAD consistently improves the two baselines.

Figure 5: CIFAR 100 + Res-18. We compare three methods: OPTIMISTIC-AMSGRAD, AMSGRAD, and OPTIMISTIC-ADAM+v t , in terms of training (cross-entropy) loss, training accuracy, testing loss, and testing accuracy.

Figure 6: MNIST-back-image noisy dataset + a four-layer convolutional neural network.

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. NeurIPS, 2018. Matthew D. Zeiler. Adadelta: An adaptive learning rate method. arXiv:1212.5701, 2012. Dongruo Zhou, Yiqi Tang, Ziyan Yang, Yuan Cao, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. arXiv:1808.05671, 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. arXiv:1808.03408, 2018.

Table content: <table/>

Peer review (iclr2020):
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. In my opinion the boundedness assumption (footnote 2) is quite important here, and should be mentioned in the main text. It 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. In 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. Moreover, 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. In 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. In 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. --- Minor --- - 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) - I could be wrong, but in my opinion, using 	heta 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. - maybe add init of 	heta_0 in alg1&2 - 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 - pg2: we just would like -> we would like