Title: OPTIMISTIC ACCELERATION FOR OPTIMIZATION

Abstract: We consider new variants of optimization algorithms. Our algorithms are based on the observation that mini-batch of stochastic gradients in consecutive iterations do not change drastically and consequently may be predictable. Inspired by the similar setting in online learning literature called OPTI-MISTIC ONLINE LEARNING, we propose two new optimistic algorithms for AMSGrad and Adam, respectively, by exploiting the predictability of gradients. The new algorithms combine the idea of momentum method, adaptive gradient method, and algorithms in OPTIMISTIC ONLINE LEARNING, which leads to speed up in training deep neural nets in practice.

1. INTRODUCTION:

Nowadays deep learning has been shown to be very effective in several tasks, 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) ). Typically, the model parameters of a state-of-the-art deep neural net is very high-dimensional and the required training data is also in huge size. Therefore, fast algorithms are necessary for training a deep neural net. To achieve this, there are number of 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 combines two ideas: the idea of adaptivity in ADAGRAD (Duchi et al. (2011) ; McMahan & Streeter (2010) ) and the idea of momentum as NESTEROV'S METHOD (Nesterov (2004) ) or the 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. The update of ADAGRAD has a notable feature: the learning rate is different for different dimensions, 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 the Momentum 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) ) leverages these two ideas to get fast training for 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 (Chiang et al. (2012) ; Rakhlin & Sridharan (2013) ; Syrgkanis et al. (2015) ; Abernethy et al. (2018) ). OPTIMISTIC ONLINE LEARNING considers that a good guess of the loss function in the current round of online learning is available and plays an action by exploiting the good guess. By exploiting the guess, those algorithms in OPTIMISTIC ONLINE LEARNING have regret in the form of O( T t=1 g t -m t ), where g t is the gradient of loss function in round t and m t is the "guess" of g t before seeing the loss function in round t (i.e. before getting g t ). This kind of regret can be much smaller than O( √ T ) when one has a good guess m t of g t . We combine the OPTIMISTIC ONLINE LEARNING idea with the adaptivity and the momentum ideas to design new algorithms in training deep neural nets, which leads to NEW-OPTIMISTIC-AMSGRAD and NEW-OPTIMISTIC-ADAM. We also provide theoretical analysis of NEW-OPTIMISTIC-AMSGRAD. The proposed OPTIMISTIC-algorithms not only adapt to the informative dimensions and exhibit momentums but also take advantage of a good guess of the next gradient to facilitate acceleration. We evaluate our algorithms with (Kingma & Ba (2015) ), (Reddi et al. (2018) ) and (Daskalakis et al. (2018) ). Experiments show that our OPTIMISTIC-algorithms are faster than the baselines. We should explain that Daskalakis et al. (2018) proposed another version of optimistic algorithm for ADAM, which is referred to as ADAM-DISZ in this paper. We apply the idea of (Daskalakis et al. (2018) ) on AMSGRAD, which leads to AMSGRAD-DISZ. Both ADAM-DISZ and AMSGRAD-DISZ are used as baselines.

2. PRELIMINARIES:

Both AMSGRAD (Reddi et al. (2018) ) and ADAM (Kingma & Ba (2015) ) are actually ONLINE LEARNING algorithms. They use REGRET ANALYSIS to provide some theoretical guarantees of the algorithms. Since one can convert an online learning algorithm to an offline optimization algorithm by online-to-batch conversion (Cesa-Bianchi et al. (2004) ), one can design an offline optimization algorithm by designing and analyzing its counterpart in online learning. Therefore, we would like to give a brief review of ONLINE LEARNING and OPTIMISTIC-ONLINE LEARNING.

2.1. BRIEF REVIEW OF ONLINE LEARNING:

In the typical setting of online learning, there is a LEARNER playing an action and then receiving a loss function in each round t. Specifically, the learner plays an action w t ∈ K in round t, where w t is chosen in a compact and convex set K ⊆ R n , known as the DECISION SPACE. Then, the learner sees the LOSS FUNCTION t (•) and suffers loss t (w t ) for the choice. No distributional assumption is made on the loss functions sequence { 1 (•), 2 (•), . . . , T (•)} in ONLINE LEARNING. Namely, the loss functions can be adversarial. The goal of an online learner is minimizing its REGRET, which is

Regret T := T t=1 t (w t ) -min w∈K T t=1 t (w).

(1)

We can also define AVERAGE REGRET as Regret T :=

Regret T T

, which is REGRET divided by number of rounds T . In ONLINE LEARNING literature, NO-REGRET ALGORITHMS means online learning algorithms satisfying Regret T → 0 as T → ∞.

2.2. BRIEF REVIEW OF OPTIMISTIC ONLINE LEARNING:

In recent years, there is a branch of works in the paradigm of OPTIMISTIC ONLINE LEARNING (e.g. Chiang et al. (2012) ; Rakhlin & Sridharan (2013) ; Syrgkanis et al. (2015) ; Abernethy et al. (2018) ). The idea of OPTIMISTIC ONLINE LEARNING 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 . (Recall that the learner receives the loss function after the learner commits an action!) Then, the learner should exploit the guess m t (•) to choose an action w t , as m t (•) is close to the true loss function t (•).1 For example, (Syrgkanis et al. (2015) ) proposed an optimistic-variant of the so called FOLLOW-THE-REGULARIZED-LEADER (FTRL). The update rule of FTRL (see e.g. Hazan (2016) ) is

EQUATION

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

EQUATION

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 satisfies Regret T ≤ O( T t=1 g t -m t * ), which can be much smaller than O( √ T ) of FTRL if m t is close to g t . Consequently, OPTIMISTIC-FTRL will have much smaller regret than FTRL. On the other hand, if m t is far from g t , then the regret of OPTIMISTIC-FTRL would be a constant factor worse than that of FTRL without optimistic update. In the later section, we provide a way to get m t . Here, we just want to emphasize the importance of leveraging a good guess m t for updating w t to get a fast convergence rate (or equivalently, small regret). We also note that the works of OPTIMISTIC ONLINE LEARNING Chiang et al. (2012) ; Rakhlin & Sridharan (2013) ; Syrgkanis et al. (2015) ) has been shown to accelerate the convergence of some zero-sum games.

2.3. ADAM AND AMSGRAD:

ADAM (Kingma & Ba (2015) ) is a very popular algorithm for training deep nets. It combines the momentum idea Polyak (1964) with the idea of ADAGRAD (Duchi et al. (2011) ), which has individual learning rate for different dimensions. The 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 may 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) 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 = w t -η t θt √ vt

. (element-wise division) 9: end for Ba (2015)) proposes using a moving average of gradients (element-wise) divided by the root of the second moment of the moving average to update model parameter w (i.e. line 5,6 and line 8 of Algorithm 1). Yet, ADAM (Kingma & Ba (2015) ) fails at some online convex optmization 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 update of line 7. (Reddi et al. (2018) ) adds the step to guarantee a nonincreasing learning rate, ηt √ vt

. which helps for the convergence (i.e. average regret Regret T → 0.) For the parameters of AMSGRAD, it is suggested that β 1 = 0.9, β 2 = 0.99 and η t = η/ √ t for a number η.

3. NEW-OPTIMISTIC-AMSGRAD:

As mentioned in the introduction, Daskalakis et al. (2018) proposed one version of optimistic algorithm for ADAM, which is referred to as ADAM-DISZ in this paper. Daskalakis et al. (2018) did not propose an optimistic algorithm for AMSGRAD but such an extension is straightforward which is referred to as AMSGRAD-DISZ.

In this section, we propose a new algorithm for training deep nets: NEW-OPTIMISTIC-AMSGRAD, shown in Algorithm 2. NEW-OPTIMISTIC-AMSGRAD has an optimistic update, which is line 9 of Algorithm 2. It exploits the guess m t+1 of g t+1 to get w t+1 , since the vector h t+1 uses m t+1 . Notice that the gradient vector is computed at w t instead of w t-1 2 and the moving average of gradients is used to update w t+ 1 2 . One might want to combining line 8 and line 9 and getting a single line:

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

. From this, we see that w t+1 is updated from w t-1 2 instead of w t . Therefore, while NEW-OPTIMISTIC-AMSGRAD looks like just doing an additional update compared to AMSGRAD, the difference of update is subtle. We also want to emphasize that although the learning rate on line 9 contains 4 1-β1 factor. We suspect that it is due to the artifact of our theoretical analysis. In our experiments, the learning rate on line 9 does not have the factor of 4 1-β1 . That is, in practice, we implement line 9 as w t+1 = w t+ 1 2 -η t+1 ht+1 √ vt . We leave closing the gap between theory and practice as a future work.

We see that NEW-OPTIMISTIC-AMSGRAD inherits three properties

• Adaptive learning rate of each dimension as ADAGRAD (Duchi et al. (2011)) . (line 8) • 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 (Chiang et al. (2012) ; Rakhlin & Sridharan (2013) ; Syrgkanis et al. (2015) ; Abernethy et al. (2018) ).

(line 9)

The first property helps acceleration when the gradient has sparse structure. The second one is the well-recognized idea of momentum which can achieve acceleration. The last one, perhaps less known outside the ONLINE LEARNING community, can actually achieve acceleration when the prediction of the next gradient is good. We are going to elaborate this property in the later section where we give the theoretical analysis of NEW-OPTIMISTIC-AMSGRAD.

To obtain m t , we 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 method typically assumes that the sequence {x t } ∈ R d has a linear relation

EQUATION

) for an unknown matrix A ∈ R d×d (not necessarily symmetric). The goal is to use the last few iterates {x t } to estimate the fixed point x * on (4). (Scieur et al. (2016) ) adapt the classical extrapolation methods to the iterates/updates of Algorithm 2 NEW-OPTIMISTIC-AMSGRAD 1: Required: parameter β 1 , β 2 , and η t . 2: Init: w 1 . 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:

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

8:

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

. (element-wise division)

9:

w t+1 = w t+ 1 2 -η t+1 4 1-β1 ht+1 √ vt

, where

h t+1 := β 1 θ t-1 + (1 -β 1 )m t+1

and m t+1 is the guess of g t+1 . (In practice, use

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

.) 10: end for Algorithm 3 REGULARIZED APPROXIMATE MINIMAL POLYNOMIAL EXTRAPOLATION (RMPE) (Scieur et al. (2016) )

1: Input: some sequence {x s ∈ R d } s=r s=0 , parameter λ > 0 2: Compute matrix U = [x 1 -x 0 , . . . , x r -x r-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 c i x i , the approximation of the fixed point x * .

an optimization algorithm and propose an algorithm that produces a solution that is better than the last iterate of the underlying optimization algorithm in practice. The algorithm of (Scieur et al. ( 2016)) (shown in Algorithm 3) allows the iterates {x t } to be nonlinear

EQUATION

where e t is a second order term (namely, satisfying e t 2 = O( x t-1 -x * 2 2 ). Some theoretical guarantees regarding the distance between the output and x * is provided in (Scieur et al. (2016) ).

In NEW-OPTIMISTIC-AMSGRAD, we use Algorithm 3 to get m t . Specifically, m t is obtained by

• Call Algorithm 3 with input being a sequence of some past r + 1 gradients, {g t , g t-1 , g t-2 , . . . , g t-r } to obtain m t , where r is a parameter.

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

If the past few gradients can be modeled by ( 4) approximately, the extrapolation method should be expected to work well in predicting the gradient. In practice, it helps to achieve faster convergence.

NEW-OPTIMISTIC-ADAM By removing line 7 in Algorithm 2, the step of making monotone weighted second moment, we obtain an algorithm which we call it NEW-OPTIMISTIC-ADAM, as the resulting algorithm can be viewed as an OPTIMISTIC-variant of ADAM.

3.1. THEORETICAL ANALYSIS OF NEW-OPTIMISTIC-AMSGRAD:

We provide the regret analysis here. We denote the Mahalanobis norm • H = •, H• for some PSD matrix H. For the PSD matrix diag{v t }, where diag{v t } represents the diagonal matrix such that its i th diagonal element is vt [i] in Algorithm 2, we define the the corresponding Mahalanobis norm

• ψt := •, diag{v t } 1/2

• , where we use the notation ψ t to represent the matrix diag{v t } 1/2 . We can also define the the corresponding dual norm

• ψ * t := •, diag{v t } -1/2 • .

We assume that the model parameter w is in d-dimensional space. That is, w ∈ R d . Also, the analysis of NEW-OPTIMISTIC-AMSGRAD is for unconstrained optimization. Thus, we assume that the constraint K of the benchmark in the regret definition, min w∈K T t=1 t (w), is a finite norm ball that contains the optimal solutions to the underlying offline unconstrained optimization problem. Now we can conduct our analysis. First of all, we can decompose the regret as follows.

EQUATION

where the first inequality is by assuming that the loss function t (•) is convex and that we use the notation g t := ∇ t (w t ) which we adopt throughout the following proof for brevity.

Given the decomposition, let us analyze the first term

T t=1 w t-1 2 -w * , g t in (6). Lemma 1. Denote D ∞ = max t w t-1 2 -w * ∞ . We have that T t=1 w t-1 2 -w * , g t ≤ 1 2η T (1-β1) D 2 ∞ d i=1 vT [i] 2 + T t=1 ηt (1-β1) θ t 2 ψ * t + D 2 ∞ T t=1 d i=1 β1 vt[i] 1/2 2ηt(1-β1) .

Astute readers may realize that the bound in Lemma 1 is actually the bound of AMSGRAD. Indeed, since in online learning setting the loss vectors g t come adversarially, it does matter how g t is generated. Therefore, the regret of T t=1 w t-1 2 -w * , g t can be bounded in the same way as AMSGRAD. In Appendix B, we provide the detail proof of Lemma 1.

Now we switch to bound the other sums:

T t=1 w t -w t-1 2 , g t -h t + T t=1 w t -w t-1 2 , h t in (6). The proof is available in Appendix C. Lemma 2. T t=1 w t -w t-1 2 , g t -h t + T t=1 w t -w t-1 2 , h t ≤ T t=1 ηt 2 g t -h t 2 ( 1-β 1 8 ψt-1) * -3 2ηt w t - w t-1 2 2 1-β 1 8 ψt-1

.

Combining (6) and Lemma 1 and 2 leads to

EQUATION

Now we can conclude the following theorem. The proof is in Appendix D.

EQUATION

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

EQUATION

where η t = η/ √ t in their setting. We need to compare the last two terms in (8) with the last term in (9). We are going to show that, under certain conditions, the bound is smaller than that of AMSGRAD. Let us suppose that g t is close to m t so that

T t=1 2η t (1 -β 1 ) g t -m t 2 ψ *

t is much smaller than the last term of ( 8). Yet, the last term of ( 8 

EQUATION

) Assume that if each (gt[i] 2 -ht[i] 2 ) √ vt-1[i]

in the inner sum is bounded by a constant c, we will get

T t=1 O( 1 √ t ) = O( √ T ).

Yet, the denominator vt-1 is non-decreasing so that we can actually have a smaller bound. That is, in practice, vt-1 [i] might grow over time, and the growth rate is different for different dimension i. If vt-1 [i] in the denominator grows like O( √ t) then the last term is just O(log T ), which might be better than that of the last term on (9). One can also get a data dependent bound of the last term of (8). To summarize, when m t is close to g t , NEW-OPTIMISTIC-AMSGRAD can have a smaller regret (thus better convergence rate) than ADAM (Kingma & Ba ( 2015)) and AMSGRAD (Reddi et al. ( 2018)).

3.2. COMPARISON OF ADAM-DISZ IN DASKALAKIS ET AL. (2018):

Algorithm 4 ADAM-DISZ 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

We are aware of Algorithm 1 in Daskalakis et al. (2018) , which was also motivated by OPTIMISTIC ONLINE LEARN-ING 2 . For comparison, we replicate ADAM-DISZ in Algorithm 4. We are going to describe the differences of the algorithms and the differences of the contributions between our work and their work. First of all, by comparing NEW-OPTIMISTIC-AMSGRAD (Algorithm 2) or NEW-OPTIMISTIC-ADAM (Algorithm 2 without line 7) with ADAM-DISZ (Algorithm 4), we see that the updates are indeed different. The update cannot be written into the same form as our NEW-OPTIMISTIC-AMSGRAD (and vise versa). NEW-OPTIMISTIC-AMSGRAD (Algorithm 2) actually uses two interleaving sequences of updates {w t } T t=1 , {w t-1 2 } T t=1 , Also, Daskalakis et al. (2018) does not have any theoretical analysis of ADAM-DISZ. The theoretical analysis in Daskalakis et al. (2018) is for other algorithms. Second, the contributions are very different. Daskalakis et al. (2018) focus 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 (2013) ; Syrgkanis et al. (2015) ) showing that if both players use some kinds of OPTIMISTIC-update, then acceleration to the convergence of the minimax value of the game is possible. Daskalakis et al. (2018) was 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. Our work is about solving min x f (x) (e.g. empirical risk) quickly.

We also show that ADAM-DISZ suffers the non-convergence issue as ADAM. The proof is available in Appendix E.

Theorem 2. There exists a convex online learning problem such that ADAM-DISZ has nonzero average regret (i.e.

Regret T:

= o(T ))

One might wonder if the non-convergence issue can be avoided if one let the weighted second moment of ADAM-DISZ be monotone by adding the step vt = max(v t-1 , v t ) as AMSGRAD, which we call it AMSGRAD-DISZ.

Unfortunately, we are unable to prove if the step guarantees convergence or not.

4. EXPERIMENTS:

To demonstrate the effectiveness of our proposed method, we test its performance with various neural network architectures, including fully-connected neural networks, convolutional neural networks (CNN's) and recurrent neural networks (RNN's). The results illustrate that NEW-OPTIMISTIC-AMSGRAD is able to speed up the convergence of state-of-art AMSGRAD algorithm, making the learning process more efficient.

For AMSGRAD algorithm, we set the parameter β 1 and β 2 , respectively, to be 0.9 and 0.999, as recommended in Reddi et al. (2018) . We tune the learning rate η over a fine grid and report the results under best-tuned parameter setting. For NEW-OPTIMISTIC-AMSGRAD and AMSGRAD-DISZ, we use same β 1 , β 2 and learning rate as those for AMSGRAD to make a fair comparison of the enhancement brought by the optimistic step. We use the same weight initialization for all algorithms. The remaining tuning parameter of NEW-OPTIMISTIC-AMSGRAD is r, the number of previous gradients that we use to predict the next move. We conduct In the plots, "AMSGrad-Proposed" is the proposed NEW-OPTIMISIC-AMSGRAD.

On this dataset, we empirically observe obvious improvement of NEW-OPTIMISTIC-AMSGRAD in terms of both convergence speed and training loss. On the other hand, AMSGRAD-DISZ performs similarly to AMSGRAD in general.

4.2. CIFAR10 + CONVOLUTIONAL NEURAL NETWORKS (CNN):

Convolutional Neural Networks (CNN) have been widely studied and is important in various deep learning applications such as computer vision and natural language processing. We test the effectiveness of NEW-OPTIMISTIC-AMSGRAD in deep CNN's with dropout. We use the CIFAR10 dataset, which includes 60,000 images (50,000 for training and 10,000 for testing) of size 32 × 32 in 10 different classes. ALL-CNN architecture proposed in Springenberg et al. (2015) is implemented with two blocks of 3 × 3 convolutional filter, 3 × 3 convolutional layer with stride 2 and dropout layer with keep probability 0.5. Another block of 3 × 3, 1 × 1 convolutional layer and a 6 × 6 global averaging pooling is added before the output layer. We apply another dropout with keep probability 0.8 on the input layer. The cost function is multi-class cross entropy. The batch size is 128. The images are all whitened. The training loss is provided in figure 2 . The result shows that NEW-OPTIMISTIC-AMSGRAD accelerates the learning process significantly and gives lowest training cost after 10000 iterations. For this dataset, the performance of AMSGRAD-DISZ is worse than original AMSGRAD. 

4.3. IMDB + LONG-SHORT TERM MEMORY (LSTM):

As another important application of deep learning, natural language processing tasks often benefit from considering sequence dependency in the models. Recurrent Neural Networks (RNN's) achieves this goal by adding hidden state units that act as "memory". Long-Short Term Memory (LSTM) is the most popular structure in building RNN's. We use IMDB movie review dataset from Maas et al. (2011) to test the performance of NEW-OPTIMISTIC-AMSGRAD in RNN's under the circumstance of high data sparsity. IMDB is a binary classification dataset with 25000 training and test samples respectively. Our model includes a word embedding layer with 5000 input entries representing most frequent words in the dataset and each word is embedded into a 32 dimensional space. The output of embedding layer is passed to 100 LSTM units, which is then connected to 100 fully connected ReLu's before reaching the output layer. Binary cross-entropy loss is used and the batch size is 128. We provide the results in figure 3 . We observe a considerable improvement in convergence speed. In the first epoch, the result is more exciting. At epoch 0.5, NEW-OPTIMISTIC-AMSGRAD already achieves the training loss that vanilla AMSGRAD can produce with more than 1 epoch. The sample efficiency is significantly improved. On this dataset, AMSGRAD-DISZ performs less effectively and may be trapped in local minimum. We remark that in each iteration, only a small portion of gradients in embedding layer is non-zero. Thus, this experiment demonstrates that NEW-OPTIMISTIC-AMSGRAD could also perform well with sparse gradient. (See additional experiments in Appendix A.)

5. EXTENSIONS AND FUTURE WORK:

In this paper, we propose NEW-OPTIMISTIC-AMSGRAD, which combines optimistic learning and AMSGRAD to strengthen the learning process of optimization problems, in particular, deep neural networks. The idea of adding optimistic step can be easily extended to other optimization algorithms, e.g ADAM and ADAGRAD. We provide OPTIMISTIC-ADAGRAD algorithm and theoretical results in Appendix F. A potential direction based on this work is to improve the method for predicting next gradient. We expect that optimistic acceleration strategy could be widely used in various optimization problems.

A MORE EXPERIMENTAL RESULTS:



A.1 CHOOSING PARAMETER r:

In NEW-OPTIMISTIC-AMSGRAD, parameter r, the number of previous gradients used, may affect the performance dramatically. If we choose r too small (e.g r < 10), the optimistic updates will start at very early stage, but the information we collect from the past is limited. This may make our training process off-track at first several iterations. On the other hand, if r is chosen to be too large (e.g r >= 30), although we may get a better prediction of next gradient, the optimistic step will start late so NEW-OPTIMISTIC-AMSGRAD may miss great chances to improve the learning performance at early stages. Additionally, we need more room to store past gradients, hence the operational time will increase. The empirical impact of different r value is reported in figure 4 . We suggest 10 ≤ r ≤ 20 as an ideal range, and r = 15 tend to perform well in most training tasks. Actually, we may make the algorithm more flexible by "early start". For example, when we set r = 20, we can instead start adding optimistic step at iteration 10, and gradually increase the number of past gradients we use to predict next move from 10 to 20 in next 10 iterations. After iteration 21, we fix the moving window size for optimistic prediction as 20. This may bring enhancement to NEW-OPTIMISTIC-AMSGRAD because it can seek opportunities to accelerate learning in first several iterations, which is critical for indicating a better direction towards the minimum loss. In the plots, "ADAM-Proposed" is the proposed NEW-OPTIMISIC-ADAM.

B PROOF OF LEMMA 1

Lemma 1 Denote D ∞ = max t w t-1 2 -w * ∞ . T t=1 w t-1 2 -w * , g t ≤ 1 2η T (1-β1) D 2 ∞ d i=1 vT [i] 2 + T t=1 ηt (1-β1) θ t 2 ψ * t + D 2 ∞ T t=1 d i=1 β1 vt[i] 1/2 2ηt(1-β1) .

Proof. The proof of this lemma basically follows that of (Reddi et al. ( 2018)). We have that

EQUATION

By rearranging the terms above and summing it from t = 1, . . . , T ,

EQUATION

where the first inequality is due to Young's inequality and the second one is due to the constraint 0

< β 1 ≤ 1 so that ηt 2(1-β1) + β1ηt 2(1-β1) ≤ ηt (1-β1) .

Under review as a conference paper at ICLR 2019 Now we can bound

EQUATION

where the first inequality is due to (12).

Continue the analysis, we have

EQUATION

where the last equality is by telescoping sum.

C PROOF OF LEMMA 2:

Lemma 2

EQUATION

Therefore, we have that

EQUATION

where (a) is by Hölder's inequality and (b) is by Young's inequality.

D PROOF OF THEOREM 1:

Theorem 1 Denote γ

EQUATION

Proof. Recall that from (7), we show that

EQUATION

To proceed, let us analyze

EQUATION

and

EQUATION

where we use the update rule,

w t = w t-1 2 -η t 4 1-β1 ht √ vt-1

. Therefore, we have that

EQUATION

where the second inequality is due to that the sequence {v t [i]} is non-decreasing and the last equality is because

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

To summarize,

EQUATION

E PROOF OF THEOREM 2:

Theorem 2 There exists a convex online learning problem such that ADAM-DISZ has nonzero average regret (i.e.

= o(T ))

We basically follow the same setting as Theorem 1 of Reddi et al. (2018) . In each round, the loss function t (w) is linear and the learner's decision space is K = [-1, 1]

f t (w) = Cw , for t mod 3 = 1 -w , otherwise ,

where C ≥ 4. For this loss function sequences, the point w = -1 achieves the minimum regret, i.e. -1 = arg min w∈K T t=1 f t (w) when T → ∞. Consider the execution of ADAM-DISZ with 2018), the assumption of the initial point is without loss of generality. If the initial point is not 1, then one can translate the coordinate system to a new coordinate system so that the initial point is 1 and then choose the loss function sequences for the new coordinate system. Therefore, the base case x 1 = 1 is true. Now assume that for some t > 0, x 3t+1 = 1 and x s > 0 for all s ≤ 3t + 1. Observe that. ∇f t (w) = C , for t mod 3 = 1 -1 , otherwise ,

β 1 = 0, β 2 = 1 1+2C 2 , η t = η √ t with η < 1 3 √ 1 -β 2 . Notice that β 2 1 / √ β 2 < 1 in

According to the update of ADAM-DISZ

EQUATION

For ŵ3t+4 , let us first consider the case that ŵ3t+3 < 1 ŵ3t+4 = min( ŵ3t+3 , 1) + 2η

EQUATION

where (a) uses

β2C 2 +(1-β2) 3/2 = √ 1 -β 2 for the choice of β 2 = 1/(1 + 2C 2 ), (b) is because 1 - √ 3t+1 √

3t+2 is a decreasing function of t and has its largest value at t = 1 for any t > 0, which is 1 -( √ 4 √ 5 ) ≤ 0.12. To summarize, we have that w 3t+4 = 1. Now if it is the case that ŵ3t+3 ≥ 1 ŵ3t+4 = min( ŵ3t+3 , 1) + 2η

(3t + 3)(β 2 v 3t+2 + (1 -β 2 )) - η (3t + 3)(β 2 v 3t+1 + (1 -β 2 )) = 1 + 2η (3t + 3)(β 2 v 3t+2 + (1 -β 2 )) - η (3t + 3)(β 2 v 3t+1 + (1 -β 2 )) > 1 (26)

where the last inequality is because

EQUATION

To see this,

β 2 v 3t+2 + (1 -β 2 ) = β 2 (β 2 v 3t+1 + (1 -β 2 )) + (1 -β 2 ) = (β 2 2 )v 3t+1 + 1 -β 2 2 (28)

So, the above inequality is equivalent to

EQUATION

which is true. This means that w 3t+4 = 1. Therefore, we have completed the induction.

To summarize, we have 3t+1 (w 3t+1 ) + 3t+2 (w 3t+2 ) + 3t+3 (w 3t+3 ) -3t+1 (-1) -3t+2 (w -1 ) -3t+3 (-1) ≥ 2C -4. That is, for every 3 steps, the algorithms suffers regret at least 2C -4, this means that the regret over T rounds would be (2C -4)T /3, which is not sublinear to T . Now we have completed the proof. One may follow the analysis of Theorem 2 of Reddi et al. (2018) to generalize the result so that ADAM-DISZ does not converge for any β 1 , β 2 ∈ [0, 1) such that β 1 < √ β 2 .

F OPTIMISTIC-ADAGRAD:

The optimistic update step can also be extended to other algorithms as well. For example, based on ADAGRAD, we propose OPTIMISTIC-ADAGRAD by including the optimistic update step.

Algorithm 5 OPTIMISTIC-ADAGRAD (UNCONSTRAINED)

1: Required: parameter η.

2: Init: w 1 .

3: for t = 1 to T do 4:

Get current gradient g t at w t .

5::

w t+ 1 2 = w t- w t+1 = w t+ 1 2 -ηdiag(G t ) -1/2 m t+1 , where m t+1 is the guess of g t+1 . 7: end for F.1 ANALYSIS:

We provide the regret analysis here. Let us recall the notations and assumptions 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 the PSD matrix diag{v t }, where diag{v t } represents the diagonal matrix such that its i th diagonal element is vt [i] in Algorithm 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 is called the distance generating function. We can also define the associate dual norm as ψ * t (x) := x, diag{v t } -1/2 x . We assume that the model parameter w is in d-dimensional space. That is, w ∈ R d . It suffices to analyze Algorithm 6, which holds for any convex set K. The algorithm reduces to Algorithm 5 when K = R d . and that ψ t-1 (•) is 1-strongly convex with respect to • ψt-1 . To proceed, notice that, by definition of Bregman divergence, we also have B ψt+1 (w * , w t+ 1 2 ) -B ψt (w * , w t+ 1 2 ) = w * -w t+ 1 2 , diag(s t+1 -s t )(w * -w t+ 1 2 ) ≤ max i (w * [i] -w t+ 1 2 [i]) 2 s t+1 -s t 1 .

(36) and B ψt-1 (w t+ 1 2 , w t-1 2 ) -B ψt (w t+ 1 2 , w t-1 2 ) = w t+ 1 2 -w t-1 2 , diag(s t-1 -s t )(w t+ 1 2 -w t- 

One need to compare it with the bound of ADAGRAD Duchi et al. (2011) , which has regret3 

Regret T = O(max

EQUATION

We see that when m t predicts ∇f (w t ) very well, the last term is dominated by the second one. One can set η of OPTIMISTIC-ADAGRAD to be a large step size so that OPTIMISTIC-ADAGRAD has a smaller regret than ADAGRAD.

:

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 minimizes the regret.

We notice that the term NEW-OPTIMISTIC-ADAM was already used inDaskalakis et al. (2018) to describe their Algorithm 1 in the paper. To avoid confusion, let us still use NEW-OPTIMISTIC-ADAM to refer to Algorithm 2 without line 7 in this paper, while we use ADAM-DISZ to refer to their algorithm, where DISZ are the initials of the authors' last names of the paperDaskalakis et al. (2018).

The bound here is the result of optimizing over η of ADAGRAD.

Figures and Tables:

Figure 2: CIFAR10 c96-c96-c96-c192-c192-c192-c192-c192-c10 ConvNet with dropout. Left panel: training loss vs. number of iterations. Right panel: training loss in the first 5 epochs.

Figure3: Embedding-LSTM100-f100 RNN: on the left is the training loss against number of iterations. On the right is the plot for first 5 epochs.

Figure 4: The training performance on two datasets for different r values.

Figure 5: Training loss of NEW-OPTIMISTIC-ADAM. Left panel: MNIST-Back-Rand. Right panel: CIFAR10 (CNN).In the plots, "ADAM-Proposed" is the proposed NEW-OPTIMISIC-ADAM.

),

Table content: <table><tr><td>T t=1</td><td>ηt 2 g t -h t ( 1-β 1 8</td><td colspan="3">ψt-1)  *  , might be actually o(</td><td>√</td><td>T ) and consequently might also be smaller than the last term of</td></tr><tr><td colspan="3">(9). To see this, let us rewrite</td><td>T t=1</td><td colspan="2">ηt 2 g t -h t ( 1-β 1 8</td><td>ψt-1)</td></tr></table>

NEW-OPTIMISTIC-AMSGRAD with different values of r and observe similar performance (See Appendix A). Hence, we report r = 15 for all experiments for tidiness of plots. To follow previous works of Reddi et al. (2018) and Kingma & Ba (2015), we compare different methods on MNIST, CIFAR10 and IMDB datasets in our experiment. For MNIST, we use a noisy version named as MNIST-back-rand in Larochelle et al. (2007) to increase the training difficulty.

Table content: <table><tr><td/><td>0.8</td><td/><td/><td/><td/><td/><td/><td>1.2</td><td/><td/><td/><td/></tr><tr><td>Training Loss</td><td>0.4 0.6</td><td/><td/><td colspan="3">AMSGrad AMSGrad-DISZ AMSGrad-Proposed</td><td>Training Loss</td><td>0.7 0.8 0.9 1 1.1</td><td/><td/><td/><td colspan="2">AMSGrad AMSGrad-DISZ AMSGrad-Proposed</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td>0.6</td><td/><td/><td/><td/></tr><tr><td/><td>0.2</td><td>1</td><td>500</td><td>1000</td><td>1500</td><td>2000</td><td/><td>0.5</td><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td></tr><tr><td/><td/><td/><td/><td># Iterations</td><td/><td/><td/><td/><td/><td/><td colspan="2"># Epochs</td></tr></table>

this case, which satisfies the conditions ofKingma & Ba (2015).The goal is to show that for all t, w 3t+1 = 1, and w t > 0. Let us denote ŵt+1 := w t -2η t Assume the initial point is 1. As pointed it out by Reddi et al. (

Table content: <table><tr><td>θt √ v t</td><td>+ η t</td><td>θt-1 √ v t-1</td><td>and</td></tr><tr><td>w t+1 := Π k [ ŵt+1 ].</td><td/><td/><td/></tr></table>

1 2 -ηdiag(G t ) -1/2 g t

Table content: <table><tr><td>where diag(G t ) :=</td><td> </td><td>t s=1 g t [1] 2 0 0</td><td>0 0 s=1 g t [2] 2 0 0 t •</td><td> </td></tr><tr><td>6:</td><td/><td/><td/><td/></tr></table>

1 2 ) ≤ 0. (37)where the vector s t ∈ R d is defined as follows: its i th entry s t [i] iss t [i] := B ψt (w * , w t-1 2 ) -B ψt (w * , w t+ 1 2 ) + B ψt-1 (w t+ 1 2 , w t-1 2 ) -B ψt (w t+ 1 2 , w t-1 2 )For any learning rate η t := η, OPTIMISTIC-ADAGRAD (Algorithm 6) has regret

Table content: <table><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>t</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>g s [i] 2 .</td><td>(38)</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>s=1</td></tr><tr><td colspan="2">Now we have</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td colspan="3">Regret T ≤</td><td colspan="2">T t=1</td><td>η t 2</td><td colspan="5">∇f (w t ) -m t</td><td/><td>2 ψ  *  t-1</td></tr><tr><td>+</td><td>1 η t</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td>≤</td><td>1 η 1</td><td colspan="6">B ψ1 (w  T t=1</td><td colspan="2">η t 2</td><td colspan="4">∇f (w t ) -m t</td><td>2 ψ  *  t-1 +</td><td>T -1 t=1</td><td>η t 1</td><td>max</td><td>(39)</td></tr><tr><td>≤</td><td>1 η 1</td><td colspan="5">B ψ1 (w  *  , w 1/2 ) +</td><td colspan="2">1 η min</td><td colspan="3">max t≤T</td><td colspan="2">w  *  -w t-1 2</td><td>2 ∞</td><td>d i=1</td><td>g 1:T [i] 2 +</td><td>T t=1</td><td>η t 2</td><td>∇f (w t ) -m t</td><td>2 ψ  *  t-1 .</td></tr><tr><td colspan="13">Therefore, we conclude the following theorem.</td></tr><tr><td colspan="3">Theorem 3. Regret T ≤</td><td>1 η</td><td colspan="6">B ψ1 (w  *  , w 1/2 ) +</td><td>1 η</td><td colspan="2">max t≤T</td><td>w  *  -w t-1 2</td><td>2 ∞</td><td>d i=1</td><td>g 1:T [i] 2 +</td><td>T t=1</td><td>η 2</td><td>∇f (w t ) -m t</td><td>2 ψ  *  t-1</td></tr></table>

Peer review (iclr2019):
 This paper provides an interesting way to combine regularized approximate minimal polynomial extrapolation and optimistic methods. I like the idea and the experimental results look promising. However, I have some concerns: - I*m wondering if the comparison with the baseline is fair. Actually, one iteration of Optimistic-AMSGrad is more expensive than one iteration of AMSGrad since it requires to compute m_{t+1}. The authors should explain to what extend this computation is significantly cheaper that a backprop (if it actually is). - The discussion after Theorem 1 is not clear. To me it is not clear whether or not Optimistic-AMSGrad has a better Regret that AMSGrad: you did not compare the *sum* of the two additional term with the term with a (second line of (8) with second lien of (9)). Do you get a better regret that O(.sqrt{T}), a better constant ? Moreover you did not justify why it is reasonable to assume that each are bounded. - I*m also concerned about the definition of . Did you prove that this constant is not infinite ? (Reddi et al. 2018) proposed a projected version of their algorithm and did the analysis assuming that the constraints set was bounded. In your Algorithm 2 would you project in Line 8 and 9 or only on line 9 ? I think that the easiest fix would be to provide a projected version of your algorithm and to do your analysis with the standard assumption that the constraints set is bounded. - The description of Alg 2 is not clear. "Notice that the gradient vector is computed at w_t instead of w_{t−1/2}" why would it be ? in comparison to what ? "Also, w_{t+ 1/2} is updated from {w_{t− 1/2} instead of w_t." Same. The comments are made without any description of the algorithm, fact is, if the reader is not familiar with the algorithm (which is introduced in the following page) the whole paragraph is hard to catch. - Actually, Page 6 you explain how the optimistic step of Daskalikis et al. (2018) is unclear but you can merge the updates Lines 8 and 9 to (Plug line 8 in line 9 and then plug Line 9 at time t) to get a very similar update. If you look more closely at Daskalakis et al. 2018 their guess is . Finally you Theorem 2 is stated in a bit unfair way since you also require , moreover it seems that Theorem 2 is no longer true anymore if, as you says, you impose that the second moment of ADAM-DISZ is monotone adding the maximization step. - About the experiments, I do not understand why there is the number of iterations in the left plots and the number of epochs on the right plots. It makes the plots hard to compare. - You should compare your method to extragradient methods. To sum up, this paper introduce interesting results. The combination of (Scieur et al. 2016) and optimistic online learning is really promising and solid theoretical results are claimed. However, some points should be clarified (see my comments above). Especially, I think that the authors focused too much (sometimes being unfair in their discussion and propositions) on showing how their algorithm is better than (Daskalakis et al. 2018) whereas as they mentioned it "The goals are different." ADAM-DISZ is designed to optimize games and is similar to extragradient. It is know that extragradient methods are slower than gradient methods for single objective minimization because of the extrapolation step using a too conservative signal for single objective minimization. Some minor remarks: - Page One "NESTEROV*SMETHOD" - "which can be much smaller than .sqrt{T} of FTRL if one has a good guess." You could refer to Section 3 or something else because otherwise this sentence remains mysterious. What is a good guess (OR maybe you could say that standard "good" guesses are either the previous gradient or the average of the previous gradients) - "It combines the idea of ADAGRAD (Duchi et al. (2011)), which has individual learning rate for different dimensions." what is the other thing combined ? - Beginning of Sec 3.1 represent . ===== After Authors Response ===== As developed in my response "On assumption " to the reviewers, I think that the assumption that bounded is a critical issue. That is why I am moving down my grade.