Title: ADA+: A GENERIC FRAMEWORK WITH MORE ADAP-TIVE EXPLICIT ADJUSTMENT FOR LEARNING RATE Anonymous

Abstract: Although adaptive algorithms have achieved significant success in training deep neural networks with faster training speed, they tend to have poor generalization performance compared to SGD WITH MOMENTUM(SGDM). One of the state-of-the-art algorithms, PADAM, is proposed to close the generalization gap of adaptive methods while lacking an internal explanation. This work proposes a general framework, in which we use an explicit function Φ(•) as an adjustment to the actual step size, and present a more adaptive specific form ADAPLUS(ADA+). Based on this framework, we analyze various behaviors brought by different types of Φ(•), such as a constant function in SGDM, a linear function in ADAM, a concave function in PADAM and a concave function with offset term in ADAPLUS. Empirically, we conduct experiments on classic benchmarks both in CNN and RNN architectures and achieve better performance(even than SGDM). The code is anonymously provided in https: //anonfiles.com/daV7Ed6enb/AdaPlus_zip.

1. INTRODUCTION:

First-order optimization algorithms play a significant role in training deep neural networks. One of the dominant methods is SGD (Robbins & Monro, 1951) , which updates parameters in a very concise form. SGD WITH MOMENTUM (Polyak, 1964 ) is a momentum-based improvement of SGD that combines raw gradients to reduce the interference of noise gradients and has proved itself to be an efficient first-order optimization algorithm. Besides, adaptive variants of SGD, such as ADA-GRAD (Duchi et al., 2011) , RMSPROP (Tieleman & Hinton, 2012) , ADAM (Kingma & Ba, 2015) , have recently emerged and achieved success due to their convenient and fast automatic learning rate adjustment mechanisms. However, since ADAM is indicated not to converge in certain instances, AMSGRAD (Reddi et al., 2018) suggests maintaining a non-increasing step size by a maximum historical term, so as to deal with the non-convergence problem.

On the one hand, adaptive methods are widely applied due to their quicker convergence at an early stage. However, there remain potential perils of adaptivity (Wilson et al., 2017) , which suggest worse performance than the fine-tuned SGD/SGDM. Therefore, many architectures in the field of computer vision, such as VGGNet (Simonyan & Zisserman, 2015) , ResNet (He et al., 2016) , DenseNet (Huang et al., 2017) , and natural language processing tasks (Klein et al., 2017) , would be inclined to choose SGD-like algorithms to act as an optimizer. On the other hand, the 'small learning rate dilemma' (Chen & Gu, 2018) is also a challenge for adaptive methods, that is, it is difficult to apply the well-worked learning rate decaying strategy in SGD to adaptive gradient methods. With better performance, the PADAM algorithm (Chen & Gu, 2018) is proposed to solve this problem. However, the motivation of this partially adaptive momentum fails to explain the intrinsic implication of doing grid search for the power p of the second-order moment estimation, along with the relationship between the desired learning rate and the partially adaptive term.

In this work, we first propose an adaptive adjustment function, which is a map based on historical gradient information to adjust the actual step size, and a framework that can explain the above phenomenon explicitly. Through our analysis of this function, which combines the SGD-like algorithm with the ADAM-like algorithm, we further explain the different behaviors of different algorithms. Moreover, we propose a brief but efficient specific form, called ADAPLUS(ADA+), with better adaptability to cope with the aforementioned challenges effectively. Empirically, we conduct experiments on popular models and tasks both in CNN and RNN architectures with ADAPLUS. Comparing favorably to SGD-like approaches, it gains faster convergence, reduced oscillation and better performance. Compared with ADAM-like methods, it can adapt to a variable learning rate schedule, thus achieving significant improvement in performance in complex deep neural network architectures.

2. PRELIMINARIES AND MOTIVATIONS:



2.1. NOTATIONS:

As is generally agreed, we use lowercase letters a for scalars, lowercase bold letters a for vectors, and uppercase bold letters A for matrices. Then, we set θ t ∈ R d as a parameter vector of a sequence in d-dimensional space, and use the scalar θ t,i to represent the i-th elements in vector θ t . The set of all positive definite d×d matrices is denoted by S d + . Besides, operators are defined as following. For vectors a and b in the same dimension, we use √ a to donate element-wise squares, a/b to donate element-wise divisions. These notations are the same for matrices. For a given matrix A ∈ S d + and a vector b ∈ R d , we use Π X ,A (b) as a projection operator which means arg min a∈X A 1/2 (a -b) , where X is a convex set which has a bounded diameter D

∞ , i.e., a -b ∞ ≤ D ∞ , ∀ a, b ∈ X .

Additionally, with a mild abuse of the notation of norms, we represent the L p norm formation of an exponential moving average (EMA) of g t like this:

g t p v 1 p t = [β p 2 v t-1 + (1 -β p 2 ) |g t | p ] 1 p = (1 -β p 2 ) t i=1 β p(t-i) 2 • |g i | p 1 p (2.1)

2.2. MOTIVATIONS:

As is described in Figure 1 , for optimizers, we treat their adjustment term of α t as a mapping from g t p to the actual adjustment value, i.e.,

θ t+1 = θ t - α t Φ( g t p ) • m t (2.2)

To avoid confusion, we call α t the learning rate, which is a parameter that needs tuning and applying a decaying schedule. Apart from that, αt Φ( gt p ) is called the actual step size. In this section, we summarize popular first-order stochastic optimization algorithms into the following four categories: Figure 1 : Different choices for Φ( g t p ), changing from Adam to SGD. We propose a specific function Φ( g t p )

g t p + ∆, which is shown above.

• Type I SGDM (Constant function):

θ t+1 = θ t - α t 1 • m t , i.e., Φ( g t p ) = 1. (2.3)

It can be seen from the formula in SGD WITH MOMENTUM(SGDM)that the actual step size of each update equals to α t , which is applied without adaptive adjustments. The high learning rate in an early stage makes the loss function fluctuate significantly on the surface, and its learning speed is not as fast as adaptive optimization algorithms and their variants. • Type II ADAM (Linear function):

θ t+1 = θ t - α t g t 2 • m t , i.e., Φ( g t 2 ) = g t 2 .

(2.4)

Extremes of the learning rate (Wilson et al., 2017) in ADAM-like algorithms have brought many issues. As is shown in Figure 1 , when the gradient is very large, the function value grows greatly in a linear rate, which leads to a rapid decrease in the step size; on the other hand, once the gradient is extremely small (ie, when the norm of EMA of g t approaches to 0), Φ( g t p ) = g t p is very close to 0, which makes it more than essential to select a much smaller learning rate(a few orders of magnitude smaller than SGDM) to get a reasonable actual step size. However, the much smaller initial learning rate makes ADAM-like algorithms not flexible enough to adapt to the various learning rate schedule. Although their early convergence is faster, the final performance tends to be poor due to the small actual step size in the final stage. A proposed solution, ADAMW (Loshchilov & Hutter, 2019) , trying to change the way the weight attenuation is updated, achieves a better generalization performance, but there still remains a gap between adaptive methods and SGD-like methods.

• Type III PADAM (Concave function):

θ t+1 = θ t - α t g t p 2

• m t , i.e., Φ( g t 2 ) = 4 g t 2 .

(2.5) Note that the p here means partial rather than L p norm, its default setting is1 4

1 . PADAM has achieved superior performance (Chen & Gu, 2018) in computer vision experiments, but this algorithm only introduces a new hyper-parameter p and does grid searches for it without realizing the essential reason for its improvement relative to ADAM. The internal cause is that a concave function is applied rather than the linear function in ADAM. Once ε is extremely small and g t 2 ∈ (0, ε), the mapping value of Φ(•) would be much larger in PADAM than in ADAM; therefore, PADAM can adapt to larger learning rate α t , thus flexibly adapting to the variable learning rate scheme.

• Type IV ADAPLUS(ADA+) (Concave function with offset):

θ t+1 = θ t - α t g t 1 + ∆ • m t , i.e., Φ( g t 1 ) = g t 1 + ∆. (2.6)

In ADAPLUS, we extend the concave function by introducing an offset ∆ and present a default setting as above. This form of Φ(•) not only directly inherits advantages of PADAM, as is depicted in Figure 1 , but also makes a better guarantee for larger learning rates. The offset ∆ makes sure that Φ(•) can altogether avoid the extreme situation. Even when g t 1 → 0, a more extensive learning rate α t is allowed. Besides, when g t 1 is relatively large, we can also adaptively constrain the updates and achieve 'naturally annealing' like ADAM, but more moderately. Thus, we reckon that the proposed algorithm has better adaptive performance than both ADAM-like and SGD-like algorithms, which is why we call it ADAPLUS(ADA+). So far, we may surprisingly notice that this offset ∆ is the ε that we used to apply in optimizers indeed. Nevertheless, the previous ε is only used to avoid dividing by zero to keep the numerical stability. In fact, through our analysis above, the design of offset ∆ can effectively avoid the occurrence of extreme step sizes, thus saliently improving adaptivity and performance.

We present a default setting as above, due to its excellent performance and concise form; however, there would be more elegant forms remaining for us to explore in the future. For instance, we can replace the square function with log(•) or tanh(•) and so on, or tune it into a p-th power function to apply a PADAM-like grid search.

3. THE PROPOSED FRAMEWORK AND METHOD:



3.1. GENERIC FRAMEWORK:

As is shown in Section 2.2, we propose a generic framework that includes SGD-like and ADAM-like algorithms. With the adaptive adjustment function Φ( g t p ) to combine algorithms in an organized way, behavioral characteristics of different algorithms can be explicitly observed.

Algorithm 1 GENERIC FRAMEWORK Input: θ 1 ∈ X ; learning rate {α t } T t=1 ; momentum parameters {β 1t } T t=1 , β 2 ; L p norm parameter p; function for step estimation Φ(•). 1: Set m 0 = 0, v 0 = 0, v 0 = 0 2: for t = 1 to T do 3: g t = ∇f t (x t ) 4: m t = β 1t m t-1 + (1 -β 1t )g t 5: v t = β 2 v t-1 + (1 -β 2 )|g t | p 6: v t = max ( v t-1 , v t ) 7:

// Depending on whether AMSGrad is desired, the previous line can be optionally annotated.

8:

θ t+1 = Π X ,diag Φ -1 ( v 1/p t ) θ t -αt Φ( v 1/p t )

• m t 9: end for 10: // We omit the bias-correction terms and other misc for clarity.

According to our analysis, different settings of the adaptive adjustment function Φ( g t p ) will lead to different behaviors of the algorithm, such as Φ( g t p ) = 1 for SGDM and Φ( g t p ) = g t p for ADAM. In practice, we can selectively decide whether or not to open AMSGRAD according to the actual situation. We will present a specific algorithm that has a concise form and demonstrates superior performance in Section 5.

3.2. SPECIFIC FORMATION FOR ADAPLUS:

Algorithm 2 ADAPLUS Input: θ 1 ∈ X ; learning rate {α t } T t=1 ; momentum parameters {β 1t } T t=1 , β 2 ; offset term ∆. 1: Set m 0 = 0, v 0 = 0, v 0 = 0 2: for t = 1 to T do 3: g t = ∇f t (x t ) 4: m t = β 1t m t-1 + (1 -β 1t )g t 5: v t = β 2 v t-1 + (1 -β 2 )|g t | 6: v t = max ( v t-1 , v t ) 7:

// Depending on whether AMSGrad is desired, the previous line can be optionally annotated. 8:

θ t+1 = Π X ,diag( √ vt+∆) θ t -αt √ vt+∆ • m t 9:

end for 10: // We omit the bias-correction terms and other misc for clarity.

Here, we express the specific algorithm corresponding to the Type IV function mentioned in Section 2.2 as following. It is a special case of Algorithm 1.

θ t+1 = θ t - α t g t 1 + ∆ • m t , i.e., Φ( g t 1 ) = g t 1 + ∆. (3.1)

Two main contributions are made, including the concave function √

x and an offset term ∆, so the algorithm can avoid extreme actual step sizes and achieve superior empirical results.

4. CONVERGENCE ANALYSIS OF ADAPLUS:

In this section, we provide a convergence analysis based on a standard online convex optimization framework (Zinkevich, 2003) . For each time step t ∈ [T ], there are sequences of parameters {θ t } T t=1 and convex loss functions {f t } T t=1 . Let X be a bounded convex feasible set, which includes {θ t } T t=1 and the optimal solution θ * . The optimal solution θ * is defined to achieve empirical risk minimization(ERM), i.e., θ * = argmin θ∈X T t=1 f t (θ). We use regret R T to donate the entire difference between T t=1 f t (θ t ) and its minimum value, i.e.,

R T = T t=1 f t (θ t ) -min θ∈X T t=1 f t (θ) = T t=1 (f t (θ t ) -f t (θ * )) . (4.1)

With further assumption of bounded gradients, we establish convergence analysis of ADAPLUS to ensure the bound of regret as follows.

Theorem 1.

Let α t = α/ √ t, β 1 , β 2 ∈ (0, 1), γ = β 1 / √ β 2 ∈ (0, 1) and β 1t ≤ β 1 , ∀ t ∈ [T ]. Assume that the convex feasible set X has a bounded diameter D ∞ , i.e., ∀ x, y ∈ X , x -y ∞ ≤ D ∞ . Also, assume that loss functions f t (•) are convex and have bounded gradients, i.e., ∃ G ∞ > 0, ∀ θ ∈ X and t ∈ [T ], ∇f t (θ) ∞ ≤ G ∞ .

For θ t generated using the ADAPLUS (Algorithm 2), we have the following regret bound:

R T ≤ D 2 ∞ 2α (1 -β 1 ) d i=1 (v T,i + ∆) T + α (1 + β 1 ) √ 1 + log T (1 -β 1 ) 2 (1 -γ) √ 1 -β 2 d i=1 g 1:T,i 2 + D 2 ∞ 2 (1 -β 1 ) T t=1 d i=1 β 1t α t v t,i + ∆. (4.2)

This theorem leads directly to the following two corollaries. We will provide the proof of Theorem 1 and Corollary 1, 2 in Appendix A.

Corollary 1. Under the conditions in Theorem 1, and supposing β 1t = β 1 /t, β 1t ≥ 0, we have the following regret bound:

R T ≤ D 2 ∞ 2α (1 -β 1 ) d i=1 (v T,i + ∆) T + α (1 + β 1 ) √ 1 + log T (1 -β 1 ) 2 (1 -γ) √ 1 -β 2 d i=1 g 1:T,i 2 + β 1 dD 2 ∞ (1 + ρ) G ∞ 2α (1 -β 1 ) (1 -λ) 2 .

(4.3)

Corollary 2. Under the conditions in Corollary 1, we further have the following regret bound:

R T ≤ dD 2 ∞ (1 + ρ) G ∞ T 2α (1 -β 1 ) + α (1 + β 1 ) dG ∞ (1 + log T ) T (1 -β 1 ) 2 (1 -γ) √ 1 -β 2 + β 1 dD 2 ∞ (1 + ρ) G ∞ 2α (1 -β 1 ) (1 -λ) 2 . (4.4) which means R T = O( √ T ),

where O(•) donates the omission of logarithmic factors.

5. EXPERIMENTS:



5.1. EXPERIMANTAL SETTINGS:

In this section, we conduct full experiments on classical tasks both in CNN and RNN architectures, and compare ADAPLUS with popular algorithms, such as SGD/SGDM, ADAM and AMSGRAD to evaluate performance. Unless otherwise specified, ADAPLUS that we utilized in practice is based on the implementation of AMSGRAD, i.e., v t = max ( v t-1 , v t ) is applied, as is described in Algorithm 2. Overall experiments are summarized in Table 1 .

In the field of computer vision, we consider three different architectures on the standard CIFAR-10/100 dataset (Krizhevsky et al., 2009) . We use VGGNet-16 (Simonyan & Zisserman, 2015) , ResNet-50 (He et al., 2016) and DenseNet-121 (Huang et al., 2017) , where there was a clear distinction in the number of layers to better identify different behaviors of algorithms. We employ the fixed budget of 200 epochs and multiply the learning rates by 0.1 at 100th and 150th epochs. In the Neural Machine Translation experiment(?), we chose the learning rate attenuation scheme lu-ong234, which means after 2/3 num train steps, we start halving the learning rate for 4 times before finishing. Using the same parameter settings as the benchmark (Luong et al., 2017) , we run a total of 12000 steps on Titan XP.

For reproducibility, we provide the codes anonymously in https://anonfiles.com/ daV7Ed6enb/AdaPlus_zip and put full details of experiments in the Appendix C.

5.2. CONVOLUTIONAL NEURAL NETWORK ON CIFAR-10/100:

In this section, we train three different models with various numbers of layers to accurately compare the performance of optimizers. We also conducted experiments both on CIFAR-10 and CIFAR-100 to examine the impacts of complex tasks and different datasets on the behavior of optimizers. We report training loss and test accuracy in the following figures.

In general, we notice that in deep neural network architecture the final performance of SGDM is significantly better than ADAM and AMSGRAD, which shows issues in generalization of ADAMlike algorithms once again. Additionally, to our surprise, our approach ADAPLUS outperforms SGDM in the various models and tasks almost at all the time step (with significant differences or a bit similar). Summary of behaviors. Empirically, the behaviors of various algorithms match with what we analyze in Section 2.2. Primarily, ADAPLUS has similar behaviors to PADAM, showing faster convergence and less volatility than SGDM in the early stage. The results of PADAM and SGDM are mostly identical, sometimes SGDM wins while other times PADAM wins. However, ADAPLUS has achieved better performance than both of them due to the introduction of offset term ∆. In addition, both ADAM and AMSGRAD perform poorly in the end, although their early training losses decline rapidly and their convergence is faster.

Summary of performances. For VGGNet-16, ResNet-50 and DenseNet-121, ADAPLUS has achieved test accuracies of 0.26%, 0.46%, and 0.15% higher than SGDM in Cifar-10 tasks; while in Cifar-100 tasks, the gaps are about 1.18%, 1.62% and 0.54%. In terms of architectures, the most significant improvement of ADAPLUS incurs in ResNet-50, followed by VGGNet-16 and DenseNet-121. ADAPLUS has achieved an accuracy of about 80% in ResNet-50 on CIFAR-100, which is a significant improvement over SGDM. In terms of complexity of tasks, when the tasks are more complex, ADAPLUS can gain better promotions, since architectures have been improved more by ADAPLUS on CIFAR-100 than on CIFAR-10.

5.3. NEURAL MACHINE TRANSLATION:

In this section, we evaluate the performance of ADAPLUS in a classic NLP task Neural Machine Translation (NMT) (Klein et al., 2017) . Due to the particularity of NLP problems, adaptive optimization algorithms and their variants do not perform as well as SGD; therefore, many researchers prefer to use fine-tuned SGD (Wilson et al., 2017) .

OpenNMT has standard benchmarks with open source codes (Luong et al., 2017) , from which we select to conduct the IWSLT15 English-to-Vietnam task with the same settings as its benchmark.

Since there is no TensorFlow implementation for PADAM, we will not consider it but focus on the comparison of ADAPLUS with the state-of-the-art benchmark. As is generally agreed, standard SGD with lr = 1.0 can achieve the best average performance of 26.1 in the model with beam = 10. We apply ADAPLUS to the same task in this section. Besides, we experiment in the Vietnam-to-English task of 15k steps in Appendix D, using the same settings as ADASHIFT (Zhou et al., 2019) , which also yields better results than SGD.

Figure 4 shows that AMSGRAD's performance is worse than ADAM and that despite the fluctuations of ADAM are smaller, SGD performs indeed better. Therefore, we do not apply AMSGRAD in ADAPLUS, i.e., the sixth line of Algorithm 2 is annotated. Our NMT experiment further proves that ADAPLUS is more suitable for NLP problems with recurrent neural network model and sparse data set. As is shown in Figure 4 , ADAPLUS is almost always superior to all other methods. Finally, it has achieved the best BLEU slightly higher than SGD, as shown in Table 2 . 

6. FUTURE WORK:

Although we present a generic framework and an explicit algorithm with excellent performance, there would be more elegant forms remaining for us to explore in the future.

1. The choice of function Φ(•). For instance, we can replace the square function with log(•) or tanh(•) and so on. Also, the square function can be tuned into a p-th power function to apply a PADAM-like grid search. 2. The choice of L p Norm parameter p. Different L p Norm parameter can be tried to get better numerical performance.

7. CONCLUSION:

This work proposes a novel generic framework, in which we explicitly analyze different behaviors brought by various types of Φ(•), such as the constant function in SGDM, the linear function in ADAM, the concave function in PADAM and the concave function with offset term in ADAPLUS.

With better adaptivity as is demonstrated, ADAPLUS has achieved remarkable superior results in both CNN and RNN experiments. Our main contributions can be summarized as follows:

• A generic framework. Combining ADAM-like algorithms with SGD-like algorithms, the adaptive adjustment function Φ(•) suggests a generic framework we desired. • Explicit analysis of different algorithm behaviors by Φ(•). Based on the explicit analysis of Φ(•), we explain the different behaviors of different algorithms, which is a fundamental reason never mentioned before. • The proposal of a concave function with offset term. In ADAPLUS, we propose an offset term ∆, which can further avoid extreme actual step sizes based on the concave function and achieve superior performance.

A PROOF OF CONVERGENCE:

A.1 PROOF OF THEOREM 1

Proof. Since all f t (•) are convex, which means ∀ x, y ∈ X ,

f t (y) ≥ f t (x) + ∇f t (x) (y -x). (A.1)

Then, we have

R T = T t=1 (f t (θ t ) -f t (θ * )) ≤ T t=1 g t , θ t -θ * . (A.2)

Consider the explicit update formula in Algorithm 2, and use the notation

V t = diag ( v t ).

Here, we can get θ t+1 = Π X ,( Vt+∆)

1 2 θ t -α t ( V t + ∆) -1 2 • m t .

We use Q t V t + ∆ ∈ S d + to donate the matrix for simplification. Besides, we can find that Q t Φ( V t ) is the general formation in Algorithm 1, as long as it satisfies the requirement of being positive definite matrices, the following derivation suits as well.

For the definition of θ * , it holds that Π X ,Q (θ * ) = θ * , ∀θ * ∈ X . Using Lemma 1, we have

Q 1 2 t (θ t+1 -θ * ) 2 2 ≤ Q 1 2 t θ t -α t Q -1 t • m t -θ * 2 2 . (A.3)

Expanding the squared norm on the right side of the inequality and further expanding the momentum term, there is

Q 1 2 t (θ t+1 -θ * ) 2 2 ≤ Q 1 2 t (θ t -θ * ) 2 2 + α 2 t Q -1 2 t m t 2 2 -2α t m t , θ t -θ * = Q 1 2 t (θ t -θ * ) 2 2 + α 2 t Q -1 2 t m t 2 2 -2α t β 1t m t-1 + (1 -β 1t ) g t , θ t -θ * (A.4)

Rearranging the terms in the above inequality, the following first inequality holds,

g t , θ t -θ * ≤ 1 2α t (1 -β 1t ) Q 1 2 t (θ t -θ * ) 2 2 -Q 1 2 t (θ t+1 -θ * ) 2 2 + α t 2 (1 -β 1t ) • Q -1 2 t m t 2 2 - β 1t 1 -β 1t m t-1 , θ t -θ * ≤ 1 2α t (1 -β 1t ) Q 1 2 t (θ t -θ * ) 2 2 -Q 1 2 t (θ t+1 -θ * ) 2 2 + α t 2 (1 -β 1t ) • Q -1 2 t m t 2 2 + β 1t α t 2 (1 -β 1t ) • Q -1 2 t-1 m t-1 2 2 + β 1t 2α t (1 -β 1t ) Q 1 2 t-1 (θ t -θ * ) 2 2 . (A.5)

and the last inequality holds due to Cauchy-Schwarz and Young's inequality.

Combining (A.2) with (A.5), we have

T t=1 [f t (θ t ) -f t (θ * t )] ≤ T t=1 1 2α t (1 -β 1t ) Q 1 2 t (θ t -θ * ) 2 2 -Q 1 2 t (θ t+1 -θ * ) 2 2 + α t 2 (1 -β 1t ) • Q -1 2 t m t 2 2 + β 1t α t 2 (1 -β 1t ) • Q -1 2 t-1 m t-1 2 2 + β 1t 2α t (1 -β 1t ) Q 1 2 t-1 (θ t -θ * ) 2 2 .

(A.6) As is separately proven in Lemma 2, Lemma 3 and Lemma 4, we can further get the desired regret bound.

R T = T t=1 [f t (θ t ) -f t (θ * t )] ≤ D 2 ∞ 2α (1 -β 1 ) d i=1 (v T,i + ∆) T + α (1 + β 1 ) √ 1 + log T (1 -β 1 ) 2 (1 -γ) √ 1 -β 2 d i=1 g 1:T,i 2 + D 2 ∞ 2 (1 -β 1 ) T t=1 d i=1 β 1t α t v t,i + ∆ (A.7) A.2 PROOF OF COROLLARY 1

Proof.

Since we assume that β 1t = β 1 λ t , λ ∈ (0, 1), we have

D 2 ∞ 2 (1 -β 1 ) T t=1 d i=1 β 1t α t v t,i + ∆ = D 2 ∞ 2 (1 -β 1 ) T t=1 d i=1 β 1 λ t-1 α ( v t,i + ∆) t (A.8)

Besides, due to the definition of vt,i , we have

vt,i + ∆ = (1 -β 2 ) t j=1 β t-j 2 |g j,i | + ∆ ≤ (1 -β 2 )   t j=1 β t-j 2 |g j,i | + ∆ 1 -β 2   .

(A.9)

Since ∆ > 0 is a given constant, which is chosen to be relatively small enough, it always holds that ∃ ρ > 0, s.t., ∆ ≤ ρ • G ∞ . Then, we can further improve the result in (A.9),

∀ t ∈ [T ], vt,i + ∆ ≤ (1 -β 2 )   t j=1 β t-j 2   G ∞ + ρ • G ∞ ≤ (1 + ρ) G ∞ , (A.10) which leads to D 2 ∞ 2 (1 -β 1 ) T t=1 d i=1 β 1t α t v t,i + ∆ ≤ β 1 D 2 ∞ (1 + ρ) G ∞ 2α (1 -β 1 ) T t=1 d i=1 λ t-1 √ t ≤ β 1 dD 2 ∞ (1 + ρ) G ∞ 2α (1 -β 1 ) (1 -λ) 2 .

(A.11)

Under review as a conference paper at ICLR 2020 Submitting (A.11) into (A.7), we extend the conclusion in Theorem 1 to Corollary 1.

R T = T t=1 [f t (θ t ) -f t (θ * t )] ≤ D 2 ∞ 2α (1 -β 1 ) d i=1 (v T,i + ∆) T + α (1 + β 1 ) √ 1 + log T (1 -β 1 ) 2 (1 -γ) √ 1 -β 2 d i=1 g 1:T,i 2 + β 1 dD 2 ∞ (1 + ρ) G ∞ 2α (1 -β 1 ) (1 -λ) 2 (A.12) A.3 PROOF OF COROLLARY 2 Proof.

Primarily, as is proved in (A.10), it holds that

vT,i + ∆ ≤ (1 -β 2 )   T j=1 β T -j 2   G ∞ + ρ • G ∞ ≤ (1 + ρ) G ∞ .

(A.13) Thus, we have

D 2 ∞ √ T 2α (1 -β 1 ) d i=1 vT,i + ∆ ≤ D 2 ∞ √ T 2α (1 -β 1 ) d i=1 (1 + ρ) G ∞ = dD 2 ∞ (1 + ρ) G ∞ • T 2α (1 -β 1 ) (A.14)

Second, due to the property of convex functions and bounded gradients, we further have

d i=1 g 1:T,i 2 ≤ d i=1 T t=1 g 2 t,i ≤ dG ∞ √ T , (A.15)

Pluging (A.14) and (A.15) back into (A.12), we finally get the result of Corollary 2 

EQUATION

X ⊂ R d , suppose u 1 = arg min x∈X Q 1/2 (x -z 1 ) 2 and u 2 = arg min x∈X Q 1/2 (x -z 2 ) 2 then we have Q 1/2 (u 1 -u 2 ) 2 ≤ Q 1/2 (z 1 -z 2 ) 2 .

We will not provide the proof here, since it will be exactly the same as the reference and has been proved many times.

B.2 PROOF OF LEMMA 2:

Lemma 2. Under the conditions in Theorem 1, we have

T t=1 α t 2 (1 -β 1t ) Q -1 2 t m t 2 + β 1t Q -1 2 t-1 m t-1 2 ≤ α (1 + β 1 ) √ 1 + log T (1 -β 1 ) 2 (1 -γ) √ 1 -β 2 d i=1 g 1:T,i 2 .

Proof. Similar to (Reddi et al., 2018; Chen & Gu, 2018) , we first describe the upper bound of

T t=1 α t Q -1 2 t m t 2 = T t=1 d i=1 αt•m 2 t,i √ vt,i+∆

in the following derivation, since we use

Q t V t + ∆ ∈ S d + to donate the update rule. T t=1 α t Q -1 2 t m t 2 = T t=1 d i=1 α t • m 2 t,i v t,i + ∆ = T -1 t=1 d i=1 α t • m 2 t,i v t,i + ∆ + d i=1 α T • m 2 T,i v T,i + ∆ ≤ T -1 t=1 d i=1 α t • m 2 t,i v t,i + ∆ + d i=1 α T • m 2 T,i v T,i + ∆ = T -1 t=1 d i=1 α t • m 2 t,i v t,i + ∆ + α √ T d i=1 T j=1 (1 -β 1j ) β T -j 1 g j,i 2 (1 -β 2 ) T j=1 β T -j 2 |g j,i | + ∆ ≤ T -1 t=1 d i=1 α t • m 2 t,i v t,i + ∆ + α T (1 -β 2 ) d i=1 T j=1 β T -j 1 |g j,i | 1 2 T j=1 β T -j 1 |g j,i | 3 2 T j=1 β T -j 2 |g j,i | + ∆ 1-β2 (B.1)

These several equalities holds due to the update rule and definitions of α t , v t,i and m t,i . Also, the first inequality holds due to the definition of v t,i , while the second inequality holds due to

β 1t ≤ β 1 , ∀ t ∈ [T ] and Cauchy-Schwarz inequality. Since T j=1 β T -j 1 ≤ 1 1-β1 and f t (•) has bounded gradients, we have T t=1 α t Q -1 2 t m t 2 ≤ T -1 t=1 d i=1 α t • m 2 t,i v t,i + ∆ + α √ G ∞ (1 -β 1 ) T (1 -β 2 ) d i=1 T j=1 β T -j 1 |g j,i | 3 2 T j=1 β T -j 2 |g j,i | + ∆ 1-β2 ≤ T -1 t=1 d i=1 α t • m 2 t,i v t,i + ∆ + α √ G ∞ (1 -β 1 ) T (1 -β 2 ) d i=1 T j=1 β T -j 1 |g j,i | 3 2 T j=1 β T -j 2 |g j,i | ≤ T -1 t=1 d i=1 α t • m 2 t,i v t,i + ∆ + α √ G ∞ (1 -β 1 ) T (1 -β 2 ) T j=1 d i=1 β T -j 1 |g j,i | 3 2 β T -j 2 |g j,i | ≤ T -1 t=1 d i=1 α t • m 2 t,i v t,i + ∆ + α √ G ∞ (1 -β 1 ) T (1 -β 2 ) T j=1 d i=1 γ T -j |g j,i | , (B.2)

where the second inequality is indeed strictly less for ∆ > 0, the third inequality holds due to the property of concave function. At last, as is assumed, γ = β1 √ β2 ∈ (0, 1) is introduced.

Under review as a conference paper at ICLR 2020

We further expand

T -1 t=1 α t Q -1 2 t m t 2 = T -1 t=1 d i=1 αt•m 2 t,i √ vt,i+∆

in the same way, which leads to

T t=1 α t Q -1 2 t m t 2 ≤ α √ G ∞ (1 -β 1 ) √ 1 -β 2 T t=1 1 √ t t j=1 d i=1 γ t-j |g j,i | = α √ G ∞ (1 -β 1 ) √ 1 -β 2 d i=1 T t=1 |g t,i | √ t T j=t γ j-t ≤ α √ G ∞ (1 -β 1 ) √ 1 -β 2 d i=1 T t=1 |g t,i | (1 -γ) √ t = α √ G ∞ (1 -γ) (1 -β 1 ) √ 1 -β 2 d i=1 T t=1 |g t,i | √ t ≤ α √ G ∞ (1 -γ) (1 -β 1 ) √ 1 -β 2 d i=1 g 1:T,i 2 T t=1 1 t ≤ α G ∞ (1 + log T ) (1 -γ) (1 -β 1 ) √ 1 -β 2 d i=1 g 1:T,i 2 (B.3)

Similarly, with T j=t γ j-t ≤ 1 1-γ , the second inequality holds. The third inequality also holds by Cauchy-Schwarz inequality, while the last inequality holds due to the bound on harmonic sum:

T t=1 1 t ≤ 1 + log T .

Thus, we finally get 

T t=1 α t 2 (1 -β 1t ) Q -1 2 t m t 2 + β 1t Q -1 2 t-1 m t-1 2 ≤ α (1 + β 1 ) G ∞ (1 + log T ) 2 (1 -γ) (1 -β 1 ) 2 √ 1 -β 2 d i=1

1 2α t (1 -β 1t ) Q 1 2 t (θ t -θ * ) 2 2 -Q 1 2 t (θ t+1 -θ * ) 2 2 ≤ D 2 ∞ 2α (1 -β 1 ) d i=1

(v T,i + ∆) T .

Proof. Consider:

T t=1 Proof.

1 2α t (1 -β 1t ) Q 1 2 t (θ t -θ * ) 2 2 -Q 1 2 t (θ t+1 -θ * ) 2 2 ≤ T t=1 d i=1 vt,i + ∆ 2α t (1 -β 1 ) (θ t+1,i -θ * i ) 2 -(θ t,i -θ * i ) 2 = 1 2 (1 -β 1 ) d i=1 v1,i + ∆ (θ 1,i -θ * i ) 2 α 1 + T l=2 d i=1 vt,i + ∆ α t - vt-1,i + ∆ α t-1 (θ t,i -θ * i ) 2 ≤ D 2 ∞ 2 (1 -β 1 ) d i=1 v1,i + ∆ α 1 + T t=2 d i=1 vt,i + ∆ α t - vt-1,i + ∆ α t-1 = D 2 ∞ 2 (1 -β 1 ) d i=1 vT,i + ∆ α T = D 2 ∞ 2α (1 -β 1 )

Consider T t=1 β 1t 2α t (1 -β 1t ) Q 1 2 t-1 (θ t -θ * ) 2 2 ≤ T t=1 d i=1 β 1t • v t,i + ∆ 2α t (1 -β 1 ) (θ t,i -θ * i ) 2 ≤ D 2 ∞ 2 (1 -β 1 ) T t=1 d i=1 β 1t α t v t,i + ∆, (B.6)

where the first inequality is based on β 1t ≤ β 1 and the non-decreasing property of v t,i , and the second inequality is due to the definition of a bounded feasible set.

C EXPERIMENTAL SETTINGS:

C.1 CIFAR CLASSIFICATION

• β 1 and β 2 . We conduct experiments in (β 1 , β 2 ) = {(0.9, 0.99), (0.9, 0.999)}. For ADAM and AMSGRAD, we use (0.9, 0.99); while for SGDM, PADAM and ADAPLUS, we use (0.9, 0.999).

• Learning Rate. For ADAM and AMSGRAD, we do grid search in {0.001, 0.0001}. For SGDM, PADAM and ADAPLUS, we do grid search in {0.05, 0.1, 0.2, 0.3}, and most optimal results are using lr = 0.1. 

:

It is a bit different from the formation in(Chen & Gu,

2018), but actually the same.

Figures and Tables:

Figure 2: Training loss and test accuracy of different architectures on Cifar-10.

Figure 4: Training perplexity and test BLEU on NMT.

A.16) which means R T = O( √ T ), where O(•) donates the omission of logarithmic factors. Lemma 1 (McMahan & Streeter (2010); Reddi et al. (2018); Chen & Gu (2018)). For any Q ∈ S d + and convex feasible set

Lemma 3. Under the conditions in Theorem 1, we have T t=1

,i + ∆) T , (B.5) where the first inequality is based on β 1t ≤ β 1 , and the second inequality is due to the definition of a bounded feasible set. B.4 PROOF OF LEMMA 4 Lemma 4. Under the conditions in Theorem 1, we have

Figure 5: Training perplexity and test BLEU on NMT.

An Overview of Experiments.

Table content: <table><tr><td>Tasks</td><td>Architectures</td><td>Datasets</td><td>Framework</td></tr><tr><td/><td>VGGNet-16(Simonyan &amp; Zisserman, 2015)</td><td/><td/></tr><tr><td>CV</td><td>ResNet-50(He et al., 2016)</td><td>CIFAR-10/100</td><td>Torch</td></tr><tr><td/><td>DenseNet-121(Huang et al., 2017)</td><td/><td/></tr><tr><td>NLP</td><td>OpenNMT(Klein et al., 2017)</td><td>IWSLT15</td><td>Tensorflow</td></tr></table>

Best BLEU for 12k steps on IWSLT15 English-to-Vietnam.

Table content: <table><tr><td>Optimizer</td><td colspan="3">SGD ADAM AMSGRAD ADAPLUS</td></tr><tr><td colspan="2">Best BLEU 26.12 24.74</td><td>23.17</td><td>26.31</td></tr></table>

Best BLEU for 15k steps on IWSLT15 Vietnam-to-English.

Table content: <table><tr><td>Optimizer</td><td colspan="3">SGD ADAM AMSGRAD ADAPLUS</td></tr><tr><td colspan="2">Best BLEU 25.02 21.68</td><td>18.92</td><td>25.35</td></tr></table>

Peer review (iclr2020):
This work proposes a general framework for adaptive algorithms, and presents a specific form: ADAPLUS. In the theory part, this work gives convergence analysis of ADAPLUS. For experiments, this work analyzes several algorithm*s empirical performances including SGDM, ADAM, AMSGRAD, PADAM, ADAPLUS on CV and NLP tasks. 1. This paper*s analysis is not solid enough to support its claim. Since this paper gives a general framework and claims that offset term can achieve superior performance, it is better to give the convergence analysis of general algorithm in the framework and discuss the benefit of the offset term theoretically. Actually, the author gives almost the same theoretical result as ADAM type algorithms, from which I did not see the advantage of using ADAPLUS. 2. And the experiment shows that ADAPLUS performs on par with PADAM on CV task. I wonder why the authors did not give the experimental result of PADAM on NLP task? 3.The notation in this paper is quite confusing. In page 2 definition (2.1), v is a vector so the L^p norm of g is actually a vector. But in Figure on page 2, the paper treat it as a scalar and I cannot understand it without further explanation from the authors. Therefore, I think this work doesn*t make enough contribution and the novelty is not enough for ICLR standard.