Title: ADAMT: A STOCHASTIC OPTIMIZATION WITH TREND CORRECTION SCHEME

Abstract: Adam-typed optimizers, as a class of adaptive moment estimation methods with the exponential moving average scheme, have been successfully used in many applications of deep learning. Such methods are appealing for capability on largescale sparse datasets. On top of that, they are computationally efficient and insensitive to the hyper-parameter settings. In this paper, we present a new framework for adapting Adam-typed methods, namely AdamT. Instead of applying a simple exponential weighted average, AdamT also includes the trend information when updating the parameters with the adaptive step size and gradients. The newly added term is expected to efficiently capture the non-horizontal moving patterns on the cost surface, and thus converge more rapidly. We show empirically the importance of the trend component, where AdamT outperforms the conventional Adam method constantly in both convex and non-convex settings.

1. INTRODUCTION:

Employing first order optimization methods, such as stochastic gradient descent (SGD), is a key of solving large-scale problems. The classic gradient descent algorithm is widely used to update the model parameters, denoted by x,

x t+1 = x t -η∇f (x t ),

(1) where the gradient is denoted by ∇f (x t ) and the step size by η. While the method has shown its efficiency for many contemporary tasks, the adaptive variants of SGD outperform the vanilla SGD methods on their rapid training time. Specifically, the step size η is substituted by an adaptive step size η/ √ v t , and v t is generated from the squared gradient [∇f (x t )] 2 .

Several variants of the popular adaptive optimizers can be summarized into such common format. These optimizers share gradients calculation and parameters updating functions, but specify different moving average schemes for calculating the parameter-wise adaptive learning rate v t . For example, AdaGrad (Duchi et al., 2011) takes the arithmetic average of historical squared gradients [∇f (x t )] 2 . Compared with the conventional momentum method, it adapts the learning rate to each parameter to suit the sparse data structure, and thus gains a rapid convergence speed (Ruder, 2016) . Later, Tieleman & Hinton (2012) proposed RMSProp to reduce the aggressiveness of the decay rate in AdaGrad. The method modifies v t to the exponentially decayed squared gradients. Similar implementations could also be found in ADADELTA (Zeiler, 2012) . Instead of the squared gradients, the method applies squared parameter updates to define the adaptive learning rate. As a result, each update guarantees the same hypothetical units as the parameter. Later, Adam (Kingma & Ba, 2015) modifies RMSProp with the idea from momentum methods (Qian, 1999) . Except for the second moment moving average, the new rule also replaces the gradient ∇f (x t ) at the end of the Equation (1) to the first-moment estimation. The method has practically shown its superiority regarding the converge speed and memory requirement. While the aforementioned methods are the most famous frameworks, there are also many variants for each of them. The examples include NAdam (Dozat, 2016) , AMSGrad (Reddi et al., 2018) and Adafom (Chen et al., 2019) .

So far, the adaptive methods with exponential moving average gradients have gained great attention with huge success in many deep learning tasks. However, it remains unsolved whether the simple exponential smoothing results or the level information is sufficient in capturing the landscape of the cost surface. When clear upward or downward pattern could be recognized within the moving routine, it is suggested to add a trend term on top of the single level information.

In this paper, we modify the Adam rule with trend-corrected exponential smoothing schemes, namely AdamT, to obtain the local minima with a faster speed. To the best of our knowledge, our research is the first to apply the trend-corrected features on gradients scaling and parameters updating. It shall be emphasized that our framework is universally implementable for all adaptive update methods that apply the exponential average term, including but not restricted to ADADELTA, RM-SProp, AdaMAX and other well-recognized methods. For the sake of conciseness, in this specific paper, we focus on Adam regarding rule modification and performance comparison.

Our contributions in this paper could be summarized in three-fold:

1. We propose the notion of trend corrected exponential smoothing to modify the conventional application of exponential moving average in optimizers with adaptive gradients.

Our AdamT method collaborates the trend information into the update rule of Adam.

2. We show the conditions for the method to converge in convex settings. The regret bound is in consistent to Adam at O( √ T ).

3. We demonstrate AdamT's convergence in both convex and non-convex settings. The performance is compared with Adam, where AdamT shows clear superiority on both the training set and the test set, especially for non-convex problems.

For the remainder of the paper, we present the fundamental idea of Adam and Holt's linear methods in Section 2. In Section 3 and 4, we detail the update rules and experimental analysis, respectively. In addition, Section 5 reviews recent developments of Adam-typed optimizers. While many of them focus more on non-convex optimizations, there is a potential to incorporate our methods with such frameworks and this extension is expected for future settings.

2. PRELIMINARY:



2.1. ADAPTIVE METHODS WITH EXPONENTIAL MOVING AVERAGES:

For adaptive gradient methods, we apply the update rule at step t + 1

x t+1 = x t - η √ vt + mt .

where m t is the gradient updates, and conventionally it is defined as the last gradient value ∇f (x t ).

To prevent zero division, a smoothing term is included on the denominator.

In this paper, we focus our analysis and modifications on Adam. The method was initially proposed by Kingma & Ba (2015) , and quickly becomes one of the most popular optimizers in the last few years. The adaptive step size is accelerated from the previous square gradients

EQUATION

)

In terms of the gradient m t , Adam takes the exponentially weighted average of all previous gradients instead of solely relying on the last gradient ∇f t

EQUATION

While the two moment estimates from Equations ( 2) & (3) could potentially counteract towards zero, the series mt and vt are considered for bias-correction. Formally, the rules are defined as:

mt = m t 1 -β t 1 ; vt = v t 1 -β t 2 .

2.2. TREND CORRECTED EXPONENTIAL SMOOTHING:

The idea of extracting a smoothed new point from all the previous information is called the exponential weighted moving average. Holt (2004) extended the method by including the trend behaviours within the series, namely trend corrected exponential smoothing or Holt's linear method. Consider a time series {y t } for t = 1, 2, .... Our target is to find the smoothing results at step t. We denote the smoothing result as y t+1|t . Holt's linear method formulates the conditional forecasting by summing two smoothing equations up

y t+1|t = t + b t t = β( t-1 + b t-1 ) + (1 -β)y t b t = γb t-1 + (1 -γ)( t -t-1 ).

For a new estimation, we first update the level term t with the weighted average of the last observation y t and its estimation y t|t-1 . The trend term b t is updated simultaneously as the weighted average of the estimated trend tt-1 and its previous estimation b t-1 . The smoothing parameters for the level and the trend are denoted as α and β. Both values could be selected between 0 and 1.

Gardner Jr & McKenzie (1985) also suggested adding a damping factor φ, so that

y t+1|t = t + φb t t = β( t-1 + φb t-1 ) + (1 -β)y t b t = γφb t-1 + (1 -γ)( t -t-1 ).

The damped method is identical to Holt's Linear method with φ = 1, and is the same as simple exponential moving average method with φ = 0. When φ is positive, the parameter could be used to control the significance of the trend component.

The damped trend methods are considerably popular for forecasting tasks (Hyndman & Athanasopoulos, 2018) . Such methods inherent both level and trend information from historical series, while stay flexible enough to adjust the influence of the trend term via φ. On top of that, involving the damped factor could to some extend reduce the volatility of the smoothed line.

3. METHODOLOGY:

We introduce our proposed algorithm AdamT, which is based on Adam (Kingma & Ba, 2015) with added Holt's linear trend information for both of the first moment estimate and the second raw moment estimate. Specifically, we use trend-corrected exponential weighted moving averages in the final parameter update step instead of the level-only estimates used in Adam.

3.1. ALGORITHM:

Consider the gradient of a stochastic objective function f (x) evaluated at T iterations as a time series {∇f (x t )} for t = 1, 2, . . . , T . According to the Holt's linear trend method illustrated in Section 2.2, we write two series { m t } and {b m t } as the exponential weighted moving averages which estimate the level and trend information of the first moment ∇f (x t ):

m t = β 1 m t-1 + (1 -β 1 )∇f (x t ) b m t = γ 1 φ 1 b m t-1 + (1 -γ 1 )( m t -m t-1 ) m t = m t + φ 1 b m t

where β 1 , γ 1 and φ 1 have the same functionality as explained in Section 2.2 and these are regarded as hyperparameters in our algorithm. Equation (3.1) combines the level and the trend information of first moment, which will be used for calculating the final update rule and the trend-corrected level estimates. The procedures for the second raw moment ∇f (x t ) • ∇f (x t ) is analogous:

v t = β 2 v t-1 + (1 -β 2 )∇f (x t ) • ∇f (x t ) b v t = γ 2 φ 2 b v t-1 + (1 -γ 2 )( v t -v t-1 ) v t = v t + φ 2 b v t

where the operation "•" denotes an element-wise multiplication. The hyperparameters β 2 , γ 2 and φ 2 here share the same corresponding meanings as before. The moving averages { v t } and {b v t } estimate the level and trend of the second raw moment respectively. The term v t combines these two information, which will be used in the calculations of final update rule and trend-corrected level estimates of the second raw moment.

In our algorithm, we set the initial values of the series

{ m t }, { v t }, {b m t } and {b v t } to be zero vectors, so that m 0 = v 0 = b m 0 = b v 0 = 0.

The series {m t } and {v t }, as a result, are also initialized as zero vectors. As observed in Kingma & Ba (2015) , the exponential weighted moving averages could bias towards zero, especially during the early training stage. We perform the bias correction for the two level estimates { m t } and { v t } by following Kingma & Ba (2015) . For the two trend estimates {b m t } and {b v t }, we correct the bias in a different way by taking into account the effect of damping parameters (φ 1 , φ 2 ). Thus, the bias-corrected version of the series {m t } and {v t } can be written as:

mt = m t 1 -β t 1 + (1 -γ 1 φ 1 )b m t (1 -γ 1 )(1 -(γ 1 φ 1 ) t ) vt = v t 1 -β t 2 + (1 -γ 2 φ 2 )b v t (1 -γ 2 )(1 -(γ 2 φ 2 ) t )

The justification for the two bias-corrected trend estimates is provided in Appendix A. Similar to Adam, we consider the adaptive update rule with the bias-corrected first moment estimate and the second raw moment estimate:

x t+1 = x t - η |v t | + mt (4)

where is a positive tiny number added in the denominator to avoid zero-division case. Please note that the series { mt } and {v t } in AdamT are different from that of Adam. The two series are trend-corrected (also bias-corrected) estimates of both moments.

The direction of the effective step ∆ t = η • mt / |v t | (with = 0) in the parameter space depends on the joint effect of the first moment level and trend estimates. In the update rule (4), we only care about the magnitude of vt by taking the absolute value and thus the ratio mt / |v t | can be seen as a signal-to-noise ratio. Note that the effective step ∆ t in our algorithm is also invariant to the scale of the gradients. Specifically, re-scaling the gradients ∇f (x t ) with a factor c will scale m t and b m t by a factor c, and will scale v t and b v t by a factor c 2 . This results in scaling mt and vt by a factor c and c 2 respectively, and finally cancel out in the parameter update rule

(c • mt )/( |c 2 • vt |) = mt / |v t |.

Note that our proposed method AdamT has two extra computational steps, that is Equations (3.1) & (3.1). However, the computational complexity of these two steps is almost linear in time. Therefore, we can conclude that AdamT yields a superior performance compared with Adam (the results will be shown in the experiment section) with a minimal additional computational cost.

In our algorithm, we set the hyperparameters β 1 , γ 1 , β 2 , γ 2 according to the suggestion in Kingma & Ba (2015) . The smoothing parameters for the first moment estimates are set to 0.9, that is β 1 = γ 1 = 0.9, while the smoothing parameters for the second raw moment estimates are set to 0.999, that is β 2 = γ 2 = 0.999. We empirically find that the good default values of the two damping parameters can be set to φ 1 = φ 2 = 0.5. The pseudo-code of our AdamT is provided in Algorithm 1.

3.2. REGRET BOUND:

We present the key results of convergence analysis for AdamT in this section and the details is presented in Appendix B. Theorem 3.1. Assume that the objective function f t has bounded gradients, that is

∇f t (x) 2 ≤ G, ∇f t (x) ∞ ≤ G ∞ for all x ∈ R d . Assume that the distance between any x t produced by AdamT is bounded, that is x n -x m 2 ≤ D, x m -x n ∞ ≤ D ∞ for any m, n ∈ {1, 2, . . . , T }, and β 1 , γ 1 , β 2 , γ 2 ∈ [0, 1), φ 1 , φ 2 ∈ [0, 1]. AdamT achieves the following guarantee for all T ≥ 1 R(T ) ≤ D 2 ∞ 2η(1 -β 1 ) d i=1 T vT,i + 1 2 [β 1 (1 -β 1 )(1 + φ 1 (1 -γ 1 )) 2 ]G 2 ∞ + D 2 ∞ 2(1 -γ 1 φ 1 ) 3 (1 -β 1 )((1 -γ 1 )(1 -(γ 1 φ 1 ) T )) 2 + η 2(1 -β 1 ) (2 -β 1 ) 2 √ 2 -β 2 d i=1 g 1:T,i 2 + dD 2 2 (1 -γ 1 )β 1 + 1 -γ 1 φ 1 2(1 -γ 1 )(1 -β 1 ) .

This result implies that AdamT has O( √ T ) regret bound given that

d i=1 g 1:T,i 2 ≤ dG ∞ √ T and d i=1

T vT,i ≤ dCG ∞ √ T for some positive constant C. Hence, we can prove that the average regret of AdamT converges, Algorithm 1 AdamT. The Adam optimizer modified with Holt's Linear Trend method. Empirically suggested default values for the hyperparameters are β 1 = γ 1 = 0.9, β 2 = γ 2 = 0.999, φ 1 = φ 2 = 0.5, η = 0.0001. All of the operations on vectors are element-wise.

1: Require: η: Learning rate 2: Require: b v 0 ← 0: Initial second raw moment trend estimate 10: for t = 1, 2, . . . , T do 11:

β 1 , γ 1 , β 2 , γ 2 ∈ [0,

m t ← β 1 m t-1 + (1 -β 1 )∇f (x t ) 12: b m t ← γ 1 φ 1 b m t-1 + (1 -γ 1 )( m t -m t-1 ) 13: v t ← β 2 v t-1 + (1 -β 2 )∇f (x t ) • ∇f (x t ) 14: b v t ← γ 2 φ 2 b v t-1 + (1 -γ 2 )( v t -v t-1 ) 15: mt ← m t /(1 -β t 1 ) + [(1 -γ 1 φ 1 )b m t ]/[(1 -γ 1 )(1 -(γ 1 φ 1 ) t )] 16: vt ← v t /(1 -β t 2 ) + [(1 -γ 2 φ 2 )b v t ]/[(1 -γ 2 )(1 -(γ 2 φ 2 ) t )]

17: 

x t+1 ← x t -η mt /( |v t | + ) = 1e

4. EXPERIMENTS:

We evaluate the proposed algorithm AdamT on both convex and non-convex real-world optimization problems with several popular types of machine learning models. The models we considered in the experiments include logistic regression which has a well-known convex loss surface, and different neural network models, including feedforward neural networks, convolutional neural networks and variational autoencoder. Neural Networks with non-linear activation function typically have an inherent non-convex loss surface which is more challenging for an optimization method.

We compare our method with Adam (Kingma & Ba, 2015) and demonstrate the effectiveness of the trend information of the gradients infused in AdamT. The experiment results show that our method has a converge faster to reach a better minimum point than Adam. The observation evidences that the added trend information effectively helps AdamT to better capture the landscape of loss surface.

In the following experiments, we prepare the same set of initial values for the models, so that the initial model losses (the loss value at epoch = 0) are identical for all the optimization methods.

In terms of the hyperparameters, all the smoothing parameters (β 1 , β 2 in Adam and β 1 , β 2 , γ 1 , γ 2 in AdamT) are set at their corresponding default values which are provided in Algorithm 1. The damping factors (φ 1 , φ 2 ) and the learning rate η are tuned through a dense grid search to produce the best results for both of the optimizers. All the experiments and optimizers are written in PyTorch.

4.1. LOGISTIC REGRESSION FOR FASHION-MNIST:

We first evaluate AdamT on the logistic regression for multi-class classification problem with Fashion-MNIST dataset (Xiao et al., 2017) which is a MNIST-like dataset of fashion products. The dataset has 60, 000 training samples and 10, 000 testing samples. Each of them has 28 × 28 pixels. Each of the samples is classified into one of the 10 fashion products. The cross-entropy loss The results are reported in Figure 1 . Since the superiority of our method over Adam is relatively small in this experiment, the plot of loss value against epoch cannot visualize the difference. Instead, we plot the loss difference of the two optimizers, which is (Loss Adam -Loss AdamT ) against training epoch. The difference above zero reflect the advantage of AdamT. Figure 1 indicates that AdamT converges faster at the early training stage and constantly outperforms Adam during the rest of the training phase, though the advantage is relatively small in this experiment. The AdamT gives a similar (slightly better) performance on the test dataset as Adam. The loss surface of logistic regression is convex and well-behaved so that the trend information of AdamT cannot further provide much useful information for optimization, which results in a small advantage in this experiment.

4.2. FEEDFORWARD NEURAL NETWORKS FOR SVHN:

To investigate the performance on non-convex objective functions, we conduct the experiment with feedforward neural networks on The Street View House Numbers (SVHN) dataset (Netzer et al., 2011) for a digit classification problem. We pre-process this RGB image dataset into grayscale for dimension reduction by taking the average across the channels for each pixel in the image. The samples are 32 × 32 grayscale images. The neural network used in this experiment has two fullyconnected hidden layers, each of which has 1, 400 hidden units and ReLU activation function is used for the two hidden layers. We use softmax cross-entropy loss function for training the model.

To evaluate the performance of the optimizers in noisy settings, we apply a stochastic regularization method in the model for a separate experiment. Specifically, we include two dropout layers (Srivastava et al., 2014) , where one is applied between the two hidden layers and the other one is used before the output layer. The dropout probability is set to 0.5 for both of the two dropout layers. In the experiments, we use a constant learning rate η and minibatch training with size set to 128.

We examine the training and test loss of the models with and without dropout layers for the two optimizers. According to Figure 2 , we find that AdamT outperforms Adam significantly. In terms of the training process, AdamT yields a faster convergence and reaches a better position than Adam for the models, both with and without dropout layers. The superior performance of AdamT is also shown in the test phase, which demonstrates that AdamT also has a better generalization ability than Adam. For the model without dropout, our method performs on a par with Adam on the test dataset. Comparing to logistic regression, the loss surface in this experiment becomes complex and non-convex. The trend estimates of the gradients from AdamT can provide more meaningful information of the landscape of the loss surface, and it encourages a better performance on AdamT.

4.3. CONVOLUTIONAL NEURAL NETWORKS FOR CIFAR-10:

Convolutional neural network (CNN) is the main workhorse for Computer Vision tasks. We train a CNN model on standard CIFAR-10 dataset for a multi-class classification task. The dataset contains 2018), which has the following architecture. There are 2 stages of alternating convolution and max pooling layers. Each convolution layer has 64 channels and kernel size 5 × 5 with stride 1. Each max pooling layer is applied with a kernel size of 2 × 2. After that, there is a fully-connected layer with 600 hidden units and a dropout probability 0.5 followed by the output layer with 10 units. We use ReLU for the activation function and softmax cross-entropy for the loss function. The model is trained with a tuned constant learning rate and minibatch size 128 same as the previous experiments.

The experiment results are reported in Figure 3 . We can observe that the proposed AdamT clearly excels Adam on the training loss, and this superiority translates into a more significant advantage of AdamT on the test loss, which again demonstrates a better generalization ability.

4.4. DEEP GENERATIVE MODELS FOR MNIST:

Variational Autoencoder (VAE) (Kingma & Welling, 2014; Rezende et al., 2014) is one of the most popular deep generative models for density estimation and image generation. In this experiment, we train a VAE model on the standard MNIST dataset which contains 60, 000 training samples and 10, 000 test samples. Each sample is one 28 × 28 black-and-white image of the handwritten digit. The VAE model used in this experiment exactly matches the architecture presented in Kingma & Welling (2014): Gaussian encoder and Bernoulli decoder, both of which are implemented by feedforward neural networks with single hidden layer and there are 500 hidden units in each hidden layer. We employ the hyperbolic tangent activation function for the model and set the dimensionality of the latent space as 20. We use the constant learning rate and set the minibatch size to 150. We examine the Evidence Lower Bound (ELBO) of the training and testing phases for the two optimizers' performance assessment. See Figure 4 for the experiment results. Due to the issue of different scales, we plot the difference between the ELBOs produced by the two optimizers. Similar to the first experiment, we plot the difference value (ELBO Adam -ELBO AdamT ) against the epoch for training and testing. We observe that our AdamT has a much faster convergence at the early stage of training than Adam and constantly excels Adam during the rest of the training phase. The superior performance of AdamT in this experiment also translates into a clear advantage in the testing phase.

5. RELATED WORKS:

We consider the class of adaptive moment estimation methods with exponential moving average scheme as Adam-type learning algorithms. The fundamental idea was proposed in Kingma & Ba (2015) and quickly extended to many variants. Some examples include AdaMax (Kingma & Ba, 2015) , Nadam (Dozat, 2016) and AdamW (Loshchilov & Hutter, 2019) .

Despite the efficiency in practice, the conventional Adam-type methods fail to guarantee global convergences. Reddi et al. (2018) discussed the problematic short-term memory of the gradients. For the convex settings, they proposed AMSGrad that promises a global optimization with a comparable performance. Except for some other recent studies for convex optimization (Xu et al., 2017; Chen et al., 2018; Levy et al., 2018) , several works developed optimization methods for non-convex problems. Padam (Chen & Gu, 2018; Zhou et al., 2018) introduces a partial adaptive parameter p to interpolate between SGD with momentum and Adam so that adjacent learning rates could decrease smoothly. AdaUSM (Zou & Shen, 2018) appends the idea of unified momentum for non-decreasing sequence of weights. AdaFom (Chen et al., 2019) obtains first-order stationary by taking simple average on the second moment estimation. More conditions for pursuing global convergence were summarized in Zou et al. (2019) , basing on the currently successful variants.

6. DISCUSSION AND CONCLUSION:

In this work, we have modified the scheme to calculate the adaptive step size from exponential moving average to trend-corrected exponential smoothing. Empirical results demonstrate that our method, AdamT, works well in practice and constantly beats the baseline method Adam.

We leave some potentials for future developments. First, although we focused primarily on ADAM for theoretical and experimental analysis, we believe that similar ideas could also extend to other adaptive gradient methods, such as RMSProp (Tieleman & Hinton, 2012) and AMSGrad (Reddi et al., 2018) . Also, this work, the same as the original ADAM method, relies on the theoretical assumption of convex problems settings. We have demonstrated its computational ability on the non-convex settings, and it is possible to extend the theoretical framework to non-convex scenarios. Some potential candidates in the latest research are listed in Section 5.

A BIAS CORRECTION OF THE TREND ESTIMATES:

To conduct the bias correction for the two trend estimates {b m t } and {b v t }, we have to take into account the effect of the corresponding damping factors. Here, we give the justification for the trend estimate {b m t } and the procedures for {b v t } is analogous. Note that we can write the trend estimate b m t into the following compact summation form:

b m t = γ 1 φ 1 b m t-1 + (1 -γ 1 )( m t -m t-1 ) = (1 -γ 1 ) t i=1 (γ 1 φ 1 ) t-i ( m i -m i-1 )

To find how the expectation of the trend estimates b m t relates to the expectation of the difference between the level estimates at successive timesteps ( m t -m t-1 ), we take the expectation for both sides of the above equation:

E[b m t ] = E[(1 -γ 1 ) t i=1 (γ 1 φ 1 ) t-i ( m i -m i-1 )] = (1 -γ 1 ) t i=1 (γ 1 φ 1 ) t-i E[( m i -m i-1 )] = E[( m t -m t-1 )](1 -γ 1 ) t i=1 (γ 1 φ 1 ) t-i + ζ

where ζ can be considered as a small constant, since the factor (γ 1 φ 1 ) t-i will be tiny if the associated expectation

E[( m i -m i-1 )] is too far away in the past in the case that E[( m i -m i-1 )] is non-stationary. If E[( m i -m i-1 )

] is stationary, the constant ζ will be zero. To further simplify the above equation, we apply the formula for the sum of geometric sequence:

E[b m t ] = E[( m t -m t-1 )](1 -γ 1 ) 1 -(γ 1 φ 1 ) t 1 -γ 1 φ 1 + ζ

This suggests that we can use the term (1 -γ 1 )[1 -(γ 1 φ 1 ) t ]/[1 -γ 1 φ 1 ] to correct the bias and close the discrepancy between the above two expectations at the presence of the damping factor φ 1 .

B PROOF OF REGRET BOUND B.1 BACKGROUNDS:

We investigate the convergence of AdamT with regret minimization by following Zinkevich (2003) . Formally, the regret is defined as the difference between total cost and that of best point in hindsight

R(T ) = T t=1 [f t (x t ) -f t (x * )],

where f (x t ) is the convex function with arguments x t at iteration t and x * denotes the optimal set of the parameters. For the sake of clarity, we denote f (x t ) as f t .

For a vanishing average regret, Jensen's inequality implies that the average decision f (x T ) converges to f (x * ). In other words,

f (x T ) -f (x * ) ≤ 1 T T t=1 [f (x t ) -f (x * )] = regret T .

Below we list essential theorems and lemmas. Definition B.1 (Convexity). Let K ⊆ R d be a bounded convex and compact set in Euclidean space. A function f :

K → R is convex if for any x, y ∈ K ∀α ∈ [0, 1], f (αx + (1 -α)y) ≤ αf (x) + (1 -α)f (y).

We denote by D an upper bound on the diameter of K, then x, y ∈ K, x -y ≤ D Definition B.2 (Subgradient). The set of all subgradients of a function f at x, denoted ∂f (x), is the set of all vectors u such that f (y) ≥ f (x) + u (y -x)

Suppose f is differentiable, for any existing gradient ∇f (x), we have ∇f (x) ∈ ∂f (x) and ∀y ∈ K

f (y) ≥ f (x) + ∇f (x) (y -x).

We denote G ≥ 0 and upper bound on the norm of the subgradients of f over K, i.e., ∇f (x) ≤ G for all x ∈ K. In other words, the function f is Lipschitz continuous with parameter G, that is, for all

x, y ∈ K |f (x) -f (y)| ≤ G x -y

Below are the three core lemmas that applied in proving the regret bound. Lemma B.3 (Kingma & Ba (2015) ). We define ∇f 1:t,i ∈ R t as the vector at the i th dimension of the gradients over all iterations till t, ∇f 1:

t,i = [∇f 1,i , ∇f 2,i , ..., ∇f t,i ]. With ∇f t (x t ) 2 ≤ G, ∇f t (x t ) ∞ ≤ G ∞ we have T t=1 ∇f 2 t,i t ≤ 2G ∞ ∇f 1:T,i 2 Lemma B.4. For β 1 , γ 1 , β 2 , γ 2 ∈ [0, 1) and φ 1 , φ 2 ∈ [0, 1] the series { mt,i } and {v t,i } has the following summation form mt,i ≤ (1 -β 1 ) 1 -β t 1 + (1 -γ 1 φ 1 )(1 -β 1 ) (1 -(γ 1 φ 1 ) t ) t i=1 ∇f i . vt,i ≤ (1 -β 2 ) 1 -β t 2 + (1 -γ 2 φ 2 )(1 -β 2 ) (1 -(γ 2 φ 2 ) t ) t i=1 ∇f 2 i .

Proof. We start from mt,i . It can be shown that

m t-1 = m t-1 + φ 1 b m t-1 m t = (1 -β 1 )∇f t + β 1 l m t-1 + β 1 φ 1 b m t-1 b m t = (1 -β 1 )(1 -γ 1 )∇f t -(1 -β 1 )(1 -γ 1 )l m t-1 -((1 -β 1 )(1 -γ 1 ) -φ 1 )b m t-1

Substitute m t,i and b m t,i , we have

mt,i = 1 1 -β t 1 m t,i + (1 -γ 1 φ 1 ) (1 -γ 1 )(1 -(γ 1 φ 1 ) t ) b m t,i = (1 -β 1 ) 1 -β t 1 + (1 -γ 1 φ 1 )(1 -β 1 ) (1 -(γ 1 φ 1 ) t ) ∇f t,i + (1 -β 1 ) 1 -β t 1 (β 1 (1 + φ 1 )) + (1 -γ 1 φ 1 )(1 -β 1 ) (1 -(γ 1 φ 1 ) t ) (φ 1 -(1 -β 1 )(2 -γ 1 )) ∇f t-1,i + (1 -β 1 ) 1 -β t 1 (β 1 ((β 1 -φ 1 (1 -β 1 )(1 -γ 1 )) + φ 1 )(β 1 -φ 1 + (1 -β 1 )(1 -γ 1 ))) + (1 -γ 1 φ 1 )(1 -β 1 ) (1 -(γ 1 φ 1 ) t ) (β 1 (1 -β 1 )(φ 1 (γ 1 -1) -1) -(φ 1 -(1 -β 1 )(2 -γ 1 ))((1 -β 1 )(1 -γ 1 ) -φ 1 ))) ∇f t-2,i + • • • ≤ (1 -β 1 ) 1 -β t 1 + (1 -γ 1 φ 1 )(1 -β 1 ) (1 -(γ 1 φ 1 ) t ) t k=1 ∇f k,i

Similarly for vt , we have

vt,i ≤ (1 -β 2 ) 1 -β t 2 + (1 -γ 2 φ 2 )(1 -β 2 ) (1 -(γ 2 φ 2 ) t ) t k=1 ∇f 2 k,i .

B.2 PROOF OF REGRET BOUND:

Theorem B.5. Assume that the objective function f t has bounded gradients, that is ∇f

t (x) 2 ≤ G, ∇f t (x) ∞ ≤ G ∞ for all x ∈ R d .

We further assume that the distance between any x t produced by AdamT is bounded, that is

x n -x m 2 ≤ D, x m -x n ∞ ≤ D ∞ for any m, n ∈ {1, 2, . . . , T }, and β 1 , γ 1 , β 2 , γ 2 ∈ [0, 1), φ 1 , φ 2 ∈ [0, 1]. The proposed AdamT achieves the following guarantee for all T ≥ 1 R(T ) ≤ D 2 ∞ 2η(1 -β 1 ) d i=1 T vT,i + 1 2 [β 1 (1 -β 1 )(1 + φ 1 (1 -γ 1 )) 2 ]G 2 ∞ + 2(1 -γ 1 φ 1 ) 3 (1 -β 1 )((1 -γ 1 )(1 -(γ 1 φ 1 ) T )) 2 D 2 ∞ + η 2(1 -β 1 ) (2 -β 1 ) 2 √ 2 -β 2 d i=1 g 1:T,i 2 + dD 2 2 (1 -γ 1 )β 1 + 1 -γ 1 φ 1 2(1 -γ 1 )(1 -β 1 )

Proof. According to Theorem B.2, for any convex function f t and x * ∈ K, we have

f t (x t ) -f t (x * ) ≤ ∇f t (x t ) (x t -x * )

which implies the regret upper bound

R(T ) = T t=1 f t (x t ) - T t=1 f t (x * ) ≤ T t=1 ∇f t (x t -x * ).

From the update rules in Algorithm,

x t+1 = x t - η t √ vt mt = x t - η t √ vt m t 1 -β t 1 + (1 -γ 1 φ 1 )b m t (1 -γ 1 )(1 -(γ 1 φ 1 ) t ) = x t - η t √ vt β 1 ( m t-1 + φ 1 b m t-1 ) 1 -β t 1 + (1 -β 1 )∇f t (x t ) 1 -β t 1 + (1 -γ 1 φ 1 )b m t (1 -γ 1 )(1 -(γ 1 φ 1 ) t ) .

Consider the i th dimension of the parameter vector at time t

(x t+1,i -x * i ) 2 =(x t,i - η t vt,i mt,i -x * i ) 2 =(x t,i -x * i ) 2 -2η t mt,i vt,i (x t,i -x * i ) + η 2 t ( mt,i vt,i ) 2 =(x t,i -x * i ) 2 - 2η t √ vt β 1 ( m t-1 + φ 1 b m t-1 ) 1 -β t 1 + (1 -β 1 )∇f t (x t ) 1 -β t 1 + (1 -γ 1 φ 1 )b m t (1 -γ 1 )(1 -(γ 1 φ 1 ) t ) (x t,i -x * i ) + η 2 t ( mt,i vt,i ) 2

Under review as a conference paper at ICLR 2020 Rearrange the equation above will get

EQUATION

For any β 1 ≤ 1 and (1 -

β t 1 ) ≤ 1, we can get ∇f t,i (x t,i -x * i ) ≤ √ vt 2η t (1 -β 1 ) (x t,i -x * i ) 2 -(x t+1,i -x * i ) 2 + β 1 ( m t-1 + φ 1 b m t-1 ) 1 -β 1 (x * i -x t,i ) + (1 -γ 1 φ 1 )b m t (1 -β 1 )(1 -γ 1 )(1 -(γ 1 φ 1 ) t ) (x * i -x t,i ) + η t m2 t,i

2(1 -β 1 ) vt,i .

Applying Young's inequality on the second and the third term yields

β 1 ( m t-1 + φ 1 b m t-1 ) 1 -β 1 (x * i -x t,i ) = β 1 (1 -β 1 ) (x * i -x t,i ) β 1 (1 -β 1 ) ( m t-1 + φ 1 b m t-1 ) ≤ β 1 2(1 -β 1 ) (x * i -x t,i ) 2 + β 1 2(1 -β 1 ) ( m t-1 + φ 1 b m t-1 ) 2 , (1 -γ 1 φ 1 )b m t (1 -β 1 )(1 -γ 1 )(1 -(γ 1 φ 1 ) t ) (x * i -x t,i ) = 1 -γ 1 φ 1 (1 -β 1 )(1 -γ 1 ) (x * i -x t,i ) φ 1 (1 -β 1 ) b m t (1 -γ t 1 ) ≤ 1 -γ 1 φ 1 2(1 -β 1 )(1 -γ 1 ) (x * i -x t,i ) 2 + 1 -γ 1 φ 1 2(1 -β 1 )(1 -γ 1 ) b m t (1 -γ t 1 )

2

The regret bound can be derived by taking summation across all the dimensions for i = 1, 2, . . . , d and the convex functions for t = 1, 2, . . . , T .

R(T ):

≤ d i=1 T t=1 ∇f t,i (x t,i -x * i ) ≤ d i=1 1 2η(1 -β 1 ) (x 1,i -x * i ) 2 v1,i + d i=1 T t=2 1 2(1 -β 1 ) (x t,i -x * i ) 2 vt,i η - vt-1,i η t-1 P 1 + T t=1 1 2(1 -β 1 ) β 1 ( m t-1 + φ 1 b m t-1 ) 2 + (1 -γ 1 φ 1 )((1 -γ 1 φ 1 )(b m t )) 2 ((1 -γ 1 )(1 -(γ 1 φ 1 ) T )) 2 P 2 + d i=1 T t=1 η 2(1 -β 1 ) m2 t,i vt,i P 3 + T t=1 1 2(1 -β 1 ) β 1 + 1 -γ 1 φ 1 1 -γ 1 (x * i -x t,i ) 2 P 4

According to the assumptions x t -x * 2 ≤ D, x m -x n ∞ ≤ D ∞ for any m, n ∈ 1, 2, . . . , T , the above four parts in the inequality can be further upper bounded as follows respectively:

P 1 = d i=1 1 2η(1 -β 1 ) (x 1,i -x * i ) 2 v1,i + d i=1 T t=2 1 2(1 -β 1 ) (x t,i -x * i ) 2 vt,i η t - vt-1,i ≤ D 2 ∞ 2η(1 -β 1 ) d i=1

T vT,i

P 2 = T t=1 1 2(1 -β 1 ) β 1 ( m t-1 + φ 1 b m t-1 ) 2 + (1 -γ 1 φ 1 )((1 -γ 1 φ 1 )(b m t )) 2 ((1 -γ 1 )(1 -(γ 1 φ 1 ) T )) 2 = T t=1 β 1 2(1 -β 1 ) ( m t-1 + φ 1 b m t-1 ) 2 + T t=1 1 2(1 -β 1 ) (1 -γ 1 φ 1 )((1 -γ 1 φ 1 )(b m t )) 2 ((1 -γ 1 )(1 -(γ 1 φ 1 ) T )) 2 ≤ 1 2 (β 1 (1 -β 1 )(1 + φ 1 (1 -γ 1 )) 2 ) T t=1 ∇f 2 t-1 + (1 -γ 1 φ 1 ) 3 2(1 -β 1 )((1 -γ 1 )(1 -(γ 1 φ 1 ) T )) 2 T t=1 (b m t ) 2 ≤ 1 2 (β 1 (1 -β 1 )(1 + φ 1 (1 -γ 1 )) 2 )G 2 ∞ + 2(1 -γ 1 φ 1 ) 3 (1 -β 1 )((1 -γ 1 )(1 -(γ 1 φ 1 ) T )) 2 D 2 ∞ P 3 = d i=1 T t=1 η 2(1 -β 1 ) m2 t,i vt,i ≤ η 2(1 -β 1 ) (2 -β 1 ) 2 √ 2 -β 2 d i=1 g 1:T,i 2 P 4 = d i=1 T t=1 1 2(1 -β 1 ) β 1 + 1 -γ 1 φ 1 1 -γ 1 (x * i -x t,i ) 2 ≤ (1 -γ 1 )β 1 + 1 -γ 1 φ 1 2(1 -γ 1 )(1 -β 1 ) d i=1 D 2 2 = dD 2 2 (1 -γ 1 )β 1 + 1 -γ 1 φ 1 2(1 -γ 1 )(1 -β 1 )

Hence, the final regret upper bound can be written as:

R(T ) ≤ D 2 ∞ 2η(1 -β 1 ) d i=1 T vT,i + 1 2 [β 1 (1 -β 1 )(1 + φ 1 (1 -γ 1 )) 2 ]G 2 ∞ + 2(1 -γ 1 φ 1 ) 3 (1 -β 1 )((1 -γ 1 )(1 -(γ 1 φ 1 ) T )) 2 D 2 ∞ + η 2(1 -β 1 ) (2 -β 1 ) 2 √ 2 -β 2 d i=1 g 1:T,i 2 + dD 2 2 (1 -γ 1 )β 1 + 1 -γ 1 φ 1 2(1 -γ 1 )(1 -β 1 )

:



Figures and Tables:

1): Smoothing hyperparameters 3: Require: φ 1 , φ 2 ∈ [0, 1]: Damping hyperparameters 4: Require: f (x): Noisy objective function with parameters x 5: Initialize: x 1 : Initial parameter values 6: m 0 ← 0: Initial first moment level estimate 7: v 0 ← 0: Initial second raw moment level estimate 8: b m 0 ← 0: Initial first moment trend estimate 9:

-8 18: end for 19: return x t Corollary 3.1.1. By following the assumptions in Theorem 3.1, for all T ≥ 1 AdamT achieves R(T ) T = O 1 √ T This result follows immediately from Theorem 3.1 and thus lim T →∞ R(T ) T = 0.

Figure 1: Training loss difference (left) and test loss difference (right) of the logistic regression on Fashion-MNIST dataset for classification task.

Figure 2: Training loss (left) and test loss (right) of the feedforward neural network on SVHN dataset for a classification problem. The model architecture is fc1400-fc1400.

Figure 4: Training ELBO difference (left) and test ELBO difference (right) of the variational autoencoder on MNIST dataset.

Peer review (iclr2020):
Overall I think there is a room for this paper to improve. I expect to see more comprehensive experiments for comparing Adam and AdamT. The authors applied AdamT to four different tasks and compared training and testing loss difference. Are the models used in these tasks state-of-the-art? I did not see a discussion about whether parameters (including learning rate) are tuned for the best results for each optimization method. Also it is hard to visualize the difference in a figure (e.g. Figure 3) to claim whether it is significant. I would suggest using more quantitative measures. More details: - label all equations - second paragraph on page 3: *are denoted as alpha and _x0008_eta* --> gamma and _x0008_eta? - *Equation 3.1*: which equation? - FIg. 1: Has the author tried different learning rates for Adam? I wonder whether the faster convergence speed by the proposed trend estimation can be achieved by a larger learning rate - Fig. 3: The testing loss for Adam+Dropout and AdamT+Dropout does not seem to be significant. Is the loss smoothed or averaged across different runs to remove randomness? Can the authors apply AdamT to the state-of-the-art model for CIFAR-10 and can still show advantages?