Title: GENERALIZED ADAPTIVE MOMENT ESTIMATION

Abstract: Adaptive gradient methods have experienced great success in training deep neural networks (DNNs). The basic idea of the methods is to track and properly make use of the first and/or second moments of the gradient for model-parameter updates over iterations for the purpose of removing the need for manual interference. In this work, we propose a new adaptive gradient method, referred to as generalized adaptive moment estimation (Game). From a high level perspective, the new method introduces two more parameters w.r.t. AMSGrad (S. J. Reddi & Kumar ( 2018)) and one more parameter w.r.t. PAdam (Chen & Gu (2018)) to enlarge the parameterselection space for performance enhancement while reducing the memory cost per iteration compared to AMSGrad and PAdam. The saved memory space amounts to the number of model parameters, which is significant for large-scale DNNs. Our motivation for introducing additional parameters in Game is to provide algorithmic flexibility to facilitate a reduction of the performance gap between training and validation datasets when training a DNN. Convergence analysis is provided for applying Game to solve both convex optimization and smooth nonconvex optimization. Empirical studies for training four convolutional neural networks over MNIST and CIFAR10 show that under proper parameter selection, Game produces promising validation performance as compared to AMSGrad and PAdam.

1. INTRODUCTION:

Stochastic gradient descent (SGD) and its variants have become the mainstream training methods in machine learning (ML) due to its simplicity and effectiveness. In general, SGD is known to work reasonably well regardless of their problem structure if the learning rate is set properly in a dynamical manner over training iterations. Intuitively speaking, if optimization problems admit certain structural properties (e.g., gradients magnitudes not balanced across the parameter set), advanced gradient descent methods exploiting the structural properties would be likely to boost optimization performance. In 2011, Duchi et al. firstly proposed to track the second moment of gradients and then scale each gradient coordinate using the tracked information before updating the model parameters, which is referred to as AdaGrad (Duchi et al. (2011) ). From a conceptual point of view, AdaGrad adaptively adjusts "individual learning rates" for all the model parameters, allowing for the parameters to be updated on a roughly equal scale. It is found that AdaGrad converges significantly faster than SGD when the gradients are sparse. Its performance deteriorates when the gradients are dense due to a rapid decay of the learning rates.

Since the pioneering work of AdaGrad, various adaptive gradient methods have been proposed on tracking and using the first and/or second moment of the gradients for effective parameter updates. The methods include, for example, RMSProp (Tieleman & Hinton (2012) ), Adam (Kingma & Ba (2017) ), and NAdam (Dozat (2016) ). The main difference of the above methods from AdaGrad is that the first and/or second moment of the gradients are tracked via exponential moving averaging to enhance the importance of the most recent gradients.

Despite the wide usage of Adam in ML community, Reddit et al. have recently shown that the method does not even converge for a class of specially constructed convex functions (S. J. Reddi & Kumar (2018) ) due to the non-monotonicity of the "individual learning rates" being multiplied to the gradients. To fix the convergence issue of Adam, the authors proposed a so-called AMSGrad method by additionally tracking the maximum value of the second moment of gradients over iterations (i.e., vector v of Alg. 1 in Table 1 ). Later on, Chen and Guo generalized AMSGrad by introducing one free parameter (i.e., p of Alg. 2 in Table 1 ), referred to as PAdam (Chen & Gu (2018) ). The authors' Input: x1, {αt}, {β1t}, β2 Input: x1, {αt}, {β1t}, β2 Init.: m0 ← 0, v0 ← 0, v0 ← 0 Init.: m0 ← 0, v0 ← 0, v0 ← 0 Init.: m0 ← 0, v0 ← 0 for t = 1 to T do for t = 1 to T do for t = 1 to T do gt = ∇xf (xt; ξt) gt = ∇xf (xt; ξt) gt = ∇xf (xt; ξt) (vt, vt-1) vt = max(vt, vt-1) vt = max(vt, vt-1)

mt = β1tmt-1 + (1 -β1t)gt mt = β1tmt-1 + (1 -β1t)gt mt = β1tmt-1 + (1 -β1t)gt vt = β2vt-1 + (1 -β2)g 2 t vt = β2vt-1 + (1 -β2)g 2 t vt = β2 vt-1 + (1 -β2)|gt| q vt = max

xt+1 ← xt -αt V -1/2 t mt xt+1 ← xt -αt V -p t mt xt+1 ← xt -αt V -p t mt

end for end for end for Comparison of analysis results for smooth nonconvex optimization (Zhou et al. (2018) ) :

O d T + G T √ T ; β1 < β 1 2 2 , p = 1 4 new results : O d T + G T √ T when p = 1/4 new results : O d T + G T √ T when pq = 1/2 Notations: Vt = diag(vt); GT = E d i=1 g1:T,i 2 ; d : dimension of x

primary motivation is to improve the generalization performance by tuning the parameter. Both AMSGrad and PAdam require additional memory in comparison to Adam for storing v.

While machine learning has seen rapid advances in algorithm development, theoretical convergence analysis has also made remarkable progress recently. The work of (Zhou et al. (2018) ) extends the original analysis for PAdam in (Chen & Gu (2018) ) from convex optimization to smooth nonconvex optimization. In another recent article (Chen et al. (2018) ), the authors also considered smooth nonconvex optimization and provided convergence analysis for a class of Adam-related algorithms including AMSGrad and Adam. The convergence bounds developed in the above two articles differ in their analysis approach and step-size selection. From a high level point of view, analysis on nonconvex optimization is highly valuable in practice as training deep neural networks (DNNs) is well known to be a nonconvex optimization problem. An improved convergence analysis on existing algorithms would provide insights on designing more advanced adaptive gradient methods.

In this paper, we make two main contributions. Firstly, we propose a new adaptive gradient method named generalized adaptive moment estimation (Game). As shown in Table 1 , Game tracks only two variables (m, v)1 over iterations as compared to AMSGrad and PAdam, which track three variables (m, v, v) . We emphasize that since the dimension of v is the same as the number of model parameters, the memory saved by Game can be remarkable for modern large-scale neural networks, which usually have millions of parameters. Furthermore, Game introduces two parameters (i.e., (p, q) of Alg. 3 in Table 1 ) in comparison to PAdam which introduces one parameter (i.e., p of Alg. 2 in Table 1 ) to further enhance its flexibility. The parameter q enables Game to track information of the qth moment of gradient magnitude rather than only the second moment of the gradients. By doing so, the parameter provides one more degree of freedom for the method to balance the tradeoff between convergence speed on training data and generalization ability on validation data.

Secondly, in our theoretical convergence analysis for Game, we manage to remove the condition on the relationship between β 1 and β 2 while β 1 ≤ β 2 and β 1 ≤ β p 2 are required in (S. J. Reddi & Kumar (2018)) for AMSGrad and (Zhou et al. (2018) ) for PAdam, respectively. We provide convergence analysis for both convex optimization and smooth nonconvex optimization. The results for nonconvex case are briefly summarized in Table 1 with the analysis results from (Zhou et al. (2018) ) as a reference. Finally, our experimental results on training four convolutional neural networks (CNNs) for MNIST and CIFAR10 suggest that with a proper setup of (p, q), Game produces promising validation performance in comparison to AMSGrad and PAdam.

2. PROBLEM SETUP:

Before introducing the problem, we describe the notation used in the paper, which are basically in line with that of (S. J. Reddi & Kumar (2018) ) and (Chen & Gu (2018) ) for consistency. We denote scalars by lower-case letters, vectors by bold lower-case letters, and matrices by bold upper-case letters. Following convention, we denote the l p (p ≥ 1) norm of a vector x ∈ R d by x p = (

d i=1 |x i | p ) 1/p . As p → ∞, the l ∞ norm takes a special form x ∞ = max d i=1 |x i |. We let g 1:t,i = [g 1,i , g 2,i , • • • , g t,i

], where g t,i is the ith element of a vector g t ∈ R d . We use E[•] to denote the expectation operation. Given two sequences {a t } and {b t }, the notation a t = O(b t ) indicates that the magnitude of a t is proportional to that of b t for t ≥ 0.

Formally, we reconsider solving the stochastic smooth nonconvex optimization studied in (Ghadimi & Lan (2013; 2016) ; Zhou et al. (2018) )

EQUATION

where x represents the parameters of a model in a vector form and ξ is a random variable. Due to randomness of ξ, one can only obtain an unbiased noisy gradient ∇f (x; ξ), satisfying ∇f

(x) = E ξ [∇f (x; ξ)].

In practice, the variable ξ often represents the random mini-batch state. For the above situation, we denote the function realization at iteration t as f t (x; ξ t ), where ξ t is a realization of ξ.

Solving (1) is asymptotically equivalent to addressing the following optimization

lim T →∞ min x∈R d T t=1 f t (x; ξ t ).

(2)

We will consider both the two formulations (1) and (2) in the reminder of the paper.

3. GENERALIZED ADAPTIVE MOMENT ESTIMATION (GAME):

In this section, we present our new adaptive gradient method for solving (1). Our algorithm Game is motivated by making two observations about AMSGrad and PAdam in Table 1 . Firstly, both the two methods have to track the parameter v in addition to v. In particular, the parameter vt at iteration t is computed as

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

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

(4)

It is seen from ( 3)-(4) that v t is a function of the squared gradients {g 2 j } t j=1 while vt tracks the maximum values of {v j } t j=1 up to iteration t. From a high level perspective, it feels redundant to keep both v t and vt in AMSGrad and PAdam as both parameters are related to the second moment of the gradients. One natural question is if it is sufficient to keep only one parameter about the second moment of the gradients without sacrificing convergence speed. Less memory usage is always desirable in designing an algorithm for simplicity and applicability.

Secondly, it is clear from Table 1 that PAdam is designed by replacing the diagonal matrix V -1 2 t with V -p t at iteration t in AMSGrad, where p ∈ [0, 1 2 ]. One can easily show that p = 0 corresponds to SGD while p = 1 2 leads to AMSGrad. The parameter p establishes a smooth connection between SGD and AMSGrad, allowing the resulting method PAdam to carry the advantages of both methods. The empirical study in (Chen & Gu (2018) ) suggests that when p is properly chosen in the range [0, 1 2 ], PAdam shows better generalization performance than AMSGrad, which is as expected due to the fact SGD usually produces good generalization performance. To summarize, the above technique of introducing an additional parameter to an existing algorithm adds one more degree of freedom to enhance its applicability. One can find many examples in applied mathematics that use similar techniques for knowledge expansion. For instance, the extension from l 2 norm to l p norm and generalization from Cauchy-Schwarz inequality to Hölder's inequality.

Based on the above two observations, we propose a new adaptive gradient method named Game as summarized in Table 1 . Basically, the new method only tracks two parameters (m, v) , where vt at iteration t is computed as

EQUATION

where q > 0 is our newly introduced parameter and |g t | q denotes element-wise qth power of |g t |. It is clear from ( 5)-( 6) that v t is only a temporary parameter at iteration t and is not required to be stored in the memory for next iteration. Therefore, it is safe to say that Game saves roughly 33 percent memory per iteration as compared to AMSGrad and PAdam by removing the need for tracking {v t }.

We now study the impact of saved memory by Game when training large-scale neural networks. Note that the dimension of v is actually the number of model parameters. That is, Game manages to save a memory space which is equivalent to the size of the neural network to be trained. It is known that state-of-the-art neural networks for challenging tasks (e.g., ImageNet competition (Russakovsky et al. (2015) )) tend to be extremely deep and consist of millions of parameters (Simonyan & Zisserman (2016) ). When applying Game to train those large-scale networks, the memory saved by the new training method becomes remarkable with AMSGrad as a reference.

Next we let q = 2 and p = 1 2 for Game to make a fair comparison w.r.t. AMSGrad . In this case, one can easily show that vt in ( 6) is either greater than or equal to the one in (4). As a result, Game would always have either equal or smaller effective learning rate α t V -1 2 t than AMSGrad. The above property implies that Game is more conservative than AMSGrad and PAdam due to the update reformulation ( 5)-( 6). If needed, one can adjust the parameters {α t } to larger values to make Game more aggressive.

Finally we consider the new scalar parameter q introduced in (5). From an algebraic point of view, introduction of parameter q allows v in ( 5)-( 6) to track information of the qth moment of the gradient magnitude over iterations. As q decreases, small gradients would be amplified while large gradients would be suppressed, leading to a decreasing dynamic range of v. When q → 0, it is not difficult to show that Game approaches SGD. Therefore, the parameter q has a similar effect as the parameter p of PAdam. We point out that when β 2 > 0, we cannot merge p and q into one parameter via certain reformulation of the updating expressions of Game. That is, p and q play different roles in Game. Our purpose of introducing q in addition to p is to enlarge the parameter-selection space of Game and improve generalization performance with proper parameter setup.

4. CONVERGENCE ANALYSIS FOR GAME:

In this section, we analyze the convergence of Game for both convex optimization and smooth nonconvex optimization. The cost regret will be studied for the convex case while gradient expectation will be considered for the nonconvex case, which represents two different analysis approaches.

4.1. ANALYSIS FOR CONVEX OPTIMIZATION:

Formally, we define the cost regret up to iteration T as

EQUATION

where x * T = arg min T t=1 f t (x) denotes the optimal solution within the iteration range [1, T ], and x t is a causal estimate of x * T at iteration t as obtained by following Game in Table 1 . Our objective is to derive an upper bound of R T and then quantify its convergence behaviour as T increases.

Next we present our convergence analysis:

EQUATION

)

Proof. See Appendix A for proof.

Remark 1. We emphasize that there is a major difference between the upper bound expression in (8) and those derived in (S. J. Reddi & Kumar (2018)) and (Chen & Gu (2018) ) for analyzing AMSGrad and PAdam. That is the new upper bound does not put any restriction on the relationship between β 1 and β 2 for (8) to hold while in the above two articles, it is required that β 1 ≤ β 2p 2 , where p is the parameter of PAdam.

Theorem 1 (convex). Suppose {f t } are close, proper and convex functions (Sawaragi et al. (1985) ). Let β 1 , β 2 ∈ [0, 1), β 1t ≤ β 1 , pq < 2 and p, q > 0, and α t = α/ √ t. Assume ∇f t (x; ξ t ) ∞ ≤ G ∞ for all t ≤ T and distance between any x t generated by Game and x * T is bounded, i.e., x m -x * T ∞ ≤ D ∞ . Then we have the following bound on the regret

EQUATION

Based on Lemma 1, one can easily derive the upper bound expression (9) by following the derivation steps for Theorem 4 in (S. J. Reddi & Kumar ( 2018)). When pq = 1 and p = 1/2, (9) can be simplified as

EQUATION

)

One can see that no constraint is imposed between the relationship of β 1 and β 2 for the upper bound to hold. We have conducted empirical studies and found that both AMSGrad and Game converge even when β 2 < β 1 .

4.2. ANALYSIS FOR SMOOTH NONCONVEX OPTIMIZATION:

Differently from the analysis for convex optimization, we will consider gradient expectation for nonconvex case. To simplify study later on, we choose the output x out from {x t } T t=2 with probability α t-1 /( T -1 j=1 α j ), which is in line with the definition in (Zhou et al. (2018) ). In practice, it is natural to take the most recent estimate x T at last iteration T as output.

We now introduce the L-smooth assumption needed for analysis:

Assumption 1 (L-smooth). f (x) = E ξ f (x; ξ) is L-smooth: for any x, y ∈ R d , we have |f (x) -f (y) + ∇f (y), x -y | ≤ L 2 x -y 2 2 . (11) Furthermore, f (x) is lower bounded, i.e., inf x f (x) > -∞.

The above smooth assumption is standard for nonconvex optimization. It essentially requires the object function f changes smoothly in the parameter space. See (Zhou et al. (2018) ; Chen et al. ( 2018)) for employing the assumption in their analysis.

We now present our convergence analysis in two steps. Firstly, we provide upper bounds for the two quantities

T t=1 α 2 t E V -p t m t 2 2 and T t=1 α 2 t E V -p t g t 2 2

in a lemma below. We then show the main result in a theorem, which are derived based on the lemma. Lemma 2. Let β 1 , β 2 ∈ [0, 1), pq ≤ 1 and p, q > 0, the step sizes α j ≤ α j-1 for all j > 1, and

EQUATION

T t=1

EQUATION

)

Proof. See Appendix B for proof.

We note that a scalar parameter r ∈ [2pq -1, 1] is introduced in the upper bound expression of Lemma 2. As will be discussed in Corollary 1 later on, the parameter r provides a freedom to tune the expression (12) and merge with other expressions for simplicity. Remark 2. Again the two upper bounds ( 12)-( 13) do not require any constraint on the relationship of β 1 and β 2 , which is consistent with the results in Lemma 1.

Theorem 2 (nonconvex). Let β 1 , β 2 ∈ [0, 1), pq < 1 and p, q > 0, the step sizes α t = α 1 for all t > 1, and r ∈ [2pq -1, 1]. Assume ∇f t (x; ξ t ) ∞ ≤ G ∞ for all t ≤ T and Assumption 1 holds.

The output x out of Game satisfies

EQUATION

)

where

EQUATION

EQUATION

M 4 = 4LG 1+r-pq ∞ α 1 (1 -β 2 ) 2p β 1 1 -β 1 2 (18) where ∆f = f (x 1 ) -inf x f (x).

Proof. See Appendix C for proof.

It is clear from Theorem 2 that the two parameters p and q have to satisfy certain conditions. That is p, q > 0 and pq < 1. The conditions suggest if one parameter is chosen large, the other one should be set small to avoid divergence. In practice, it is found that Game also converges when pq = 1. This leaves us an open question on how to elaborate the convergence analysis to cover the special case of pq = 1 for Game.

We now study the upper bound on the right hand side of ( 14). The expression includes four quantities, where the first two quantities are independent of the gradients {g 1:T,i |i = 1, . . . , d} while the last two are contributed by the inequalities derived in Lemma 2. All the four scalar parameters M i , i = 1, . . . , 4, are independent of iteration number T . The convergence of Game can be established if one can show that the upper bound expression approaches to zero as T increases.

In the following, we simplify the upper bound expression in ( 14) by specifying pq and r with particular values and then study its convergence behaviour. Corollary 1. Let pq = 1 2 and r = 2pq -1 in Theorem 2, the upper bound of E ∇f (x out ) 2 2 then takes the form of

EQUATION

)

As summarized in the speed O(d/T + d s /T 1/2-s ). We note that in Duchi et al. (2011) ), the assumption G T √ dT was used for analyzing AdaGrad, which was later on employed for convergence analysis of other adaptive gradient methods (see (Zhou et al. (2018) ) and (S. J. Reddi & Kumar (2018)) for example).

The assumption G T = O((dT ) s ) is slightly stronger than G T

√:

dT as in practice, the dimension d could be larger than T when training large-scale neural networks.

5. EXPERIMENTAL RESULTS:

In the experiment, we evaluated the effectiveness of AMSGrad, PAdam and Game for training convolutional neural networks (CNNs). The classification problems on the two datasets MNIST and CIFAR10 were considered. To alleviate overfitting, each of the two datasets was augmented with additional training data (e.g., shifting images vertically and/or horizontally, and image flipping for CIFAR10). In brief, we tested four CNNs: the 1st one consists of four layers for MNIST using the activation function SERLU (Zhang & Li (2018) ), the 2nd consists of 8 layers for CIFAR10 using SERLU, and the 3rd and 4th have the same structure as the 2nd one but using ELU (Clevert et al. (2016) ) and ReLU (Nair & Hinton (2010)) , respectively. More detailed information of the four CNNs can be found in Table 2 -5 of Appendix D.

We first consider the CNN training for MNIST using SERLU. The shared parameters among the three methods include (α t , β 1 , β 2 ) = (0.001, 0.9, 0.999), which was recommended in (Kingma & Ba (2017) ) for Adam. On the other hand, the special parameters include p = 0.125 for PAdam2 and (p, q) = (0.5, 1) for Game. The setup (p, q) = (0.5, 1) was found empirically to be more effective than other tested values. It is worth noting that q = 1 indicates that Game tracks information of the gradient magnitude rather than the second moment of gradients.

Next we study the CNN training for CIFAR10 using SERLU, ELU and ReLU. As the three neural networks (see Table 3 4 5 ) are deeper than that for MNIST, we employed shift-dropout for SERLU and dropout for ELU and ReLU to combat overfitting, respectively. The parameter setup is slightly different from the one for MNIST. In particular, the shared parameters among the three methods include (β 1 , β 2 ) = (0.9, 0.999) and dropout rate of 0.2. Special parameters include α t = 0.0001 for AMSGrad,3 (α t , p) = (0.001, 0.125) for PAdam, and (α t , p, q) = (0.001, 0.5, 1) for Game.

The convergence results for training the four CNNs are demonstrated in Figure 1 . It is seen that Game produces better generalization performance (on validation datasets) than AMSGrad in subplot (a) and (c) -(d) while in the same three subplots, AMSGrad exhibits the fastest convergence speed over training data. The two methods have roughly the same convergence performance in subplot (b), suggesting that selection of activation functions also affects the convergence behaviours. It is observed that SERLU performs slightly better than ELU and ReLU in terms of validation loss. In all the four subplots, PAdam converges slightly slower due to the fact the a small value p = 0.125 is selected as compared to p = 0.5 of AMSGrad.

To briefly summarize, the above convergence results suggest that Game produces promising generalization performance in comparison to AMSGrad and PAdam on validation datasets. The nice convergence behaviour of Game might be because the method tracks the 1st moment of gradient magnitude by setting q = 1. As a result, Game achieves better validation performance by slightly sacrificing convergence speed on training dataset. If one also takes into account of memory usage (see Table 1 ), it is clear that Game is simpler to implement and requires less memory resource, rendering Game an advantage over AMSGrad and PAdam.

6. CONCLUSIONS AND FUTURE WORKS:

In this paper, we have proposed a new adaptive gradient method termed as Game. The new method only needs to track two parameters (m, v) in comparison to AMSGrad and PAdam, which track three parameters (m, v, v), thus requiring only two-thirds of memory w.r.t. the two methods. The saved memory scales along with the number of model parameters, which becomes significant when training large-scale neural networks. Furthermore, Game introduces one additional parameter q, allowing the method to track information of the qth moment of the gradient magnitude, while AMSGrad and PAdam only consider tracking the 2nd moment of gradients. The freedom of tuning parameter q makes Game more flexible. Theoretical convergence analysis is provided for applying Game to solve both convex and smooth nonconvex optimization. Experimental results on MNIST and CIFAR10 demonstrate that Game produces promising generalization performance in comparison to AMSGrad and PAdam. Given that Game demands only two-thirds of memory in implementation, we conclude that the new method is a promising candidate for training large-scale neural networks.

APPENDIX A PROOF OF LEMMA 1:

Before formally presenting the proof, we first introduce a lemma below: Lemma 3. Let vt be defined as in Game and q > 0. Then each component vt,i is lower bounded by

vt,i ≥ (1 -β 2 )|g t,i | q , i = 1, . . . , d.

Proof. The proof follows directly from the computation vt,i = max(v t-1,i , β 2 vt-1,i +(1-β 2 )|g t,i | q ) as summarized in Table 1 for Game.

With Lemma 3, we are ready to describe the proof for Lemma 1. Firstly, the quantity

EQUATION

2 can be upper bounded by

EQUATION

EQUATION

where step (a) uses

β 1t ≤ β 1 < 1, step (b) uses Cauchy-Schwarz inequality, step (c) uses t j=1 β t-j 1 ≤ 1/(1 -β 1 ), step (d) uses vp t,i ≥ vp j,i

for all j ≤ t, and step (e) uses the results in Lemma 3.

Next taking the summation of (20

EQUATION

where step (a) B PROOF OF LEMMA 2

EQUATION

We first consider the summation

EQUATION

2 can be upper bounded by

EQUATION

)

where step (a) uses Cauchy-Schwarz inequality and the property that 2pq -1 ≤ r ≤ 1 and pq ≤ 1,

step (b) uses |g j,i | ≤ g j ∞ ≤ G ∞ , step (c) uses t j=1 β t-j 1 ≤ 1/(1-β 1 ), step (d) uses v2p t,i ≥ v2p j,i

for all j ≤ t, and step (e) uses the results in Lemma 3.

Taking the summation of ( 22) over t = 1 to t = T produces

EQUATION

) (a) ≤ α 2 1 (1 -β 1 )G (1+r-2pq) ∞ (1 -β 2 ) 2p E   d i=1 T j=1 |g j,i | (1-r) T t=j β t-j 1   (b) ≤ α 2 1 G (1+r-2pq) ∞ (1 -β 2 ) 2p E   d i=1 T j=1 |g j,i | (1-r)   (c) ≤ α 2 1 G (1+r-2pq) ∞ (1 -β 2 ) 2p E    d i=1   T j=1 |g j,i | 2   (1-r)/2    T (1+r)/2 = α 2 1 G (1+r-2pq) ∞ T (1+r)/2 (1 -β 2 ) 2p E d i=1 ( g 1:T,i 2 ) (1-r)

where step (a) uses the property that a j ≤ a j-1 for all j > 1, step (b) uses

T t=j β t-j 1 < 1/(1 -β 1

), and step (c) follows from Holder's inequality. The proof is complete for (12). 13) can be upper bounded as

The quantity:

T t=1 α 2 t E V -p t g t 2 2 in (

EQUATION

≤ T t=1 α 2 1 E d i=1 g 2 t,i (1 -β 2 ) 2p |g t,i | 2pq (b) = α 2 1 (1 -β 2 ) 2p E   d i=1 T j=1 |g j,i | 2-2pq   (c) ≤ α 2 1 (1 -β 2 ) 2p E    d i=1   T j=1 |g j,i | 2   1-pq    T pq = α 2 1 T pq (1 -β 2 ) 2p E d i=1 ( |g 1:T,i 2 ) 2(1-pq)

where step (a) uses the property that a j ≤ a j-1 for all j > 1 and the results in Lemma 3, step (b) uses pq < 1, p, q > 0, and step (c) -(d) follow from Holder's inequality. The proof is complete for (13).

C PROOF OF THEOREM 2:

In brief, we use the technique of parameter transformation proposed in (Yang et al. (2016) ) to study Game for solving stochastic nonconvex optimization. In particular, we let x 0 = x 1 and for each t ≥ 1

EQUATION

where z 1 = x 1 for the special case t = 1. We note that the technique has also been employed in (Zhou et al. (2018) ) and (Chen et al. (2018) ) for analyzing PAdam and a class of Adam-type methods. Instead of considering {x j } T j=0 directly, we tackle {z j } T j=1 as in the literature. In (Zhou et al. (2018) ) and (Chen et al. (2018) ), the authors provided a general upper bound for f (z t+1 ) -f (z t ), which also holds for Game. We now summarize their result in a lemma below: Lemma 4. Suppose the sequence {z j } T j=1 is as defined in (24). Then under Assumption 1, the quantity f

EQUATION

)

With Lemma 4, we are ready to present the proof for Theorem 2. Firstly, taking expectation on both sides of ( 25) produces

EQUATION

where step (a) uses V1 = (1 -β 2 )|g 1 | q and pq < 1, and step (b)

uses ∇f t (x; ξ t ) ∞ ≤ G ∞ .

Next by rearranging terms and taking expectation in (26), we have

EQUATION

where step (a) uses the property that E[g t ] = ∇f (x t ), and step (b) uses the inequality vt-1 ∞ ≤ G q ∞ which can be derived from ∇f t (x; ξ t ) ∞ ≤ G ∞ , t ≥ 1. Taking the summation of ( 27)-( 28

EQUATION

where step (a) uses the inequality ∆f = f (x 1 ) -inf x f (x) ≥ f (x 1 ) -f (z T +1 ) and z 1 = x 1 .

Finally, substituting ( 12)-( 13) into ( 29) produces

E ∇f (x out ) 2 2 = 1 T t=2 α t-1 T t=2 α t-1 E ∇f (x t ) 2 2 ≤ G pq ∞ T t=2 α t-1 E ∆f + G 2 ∞ α 1 v-p 1 1 1 -β 1 + dα 1 G 2-pq ∞ (1 -β 2 ) p + 2LG pq ∞ T t=2 α t-1 α 2 1 T pq (1 -β 2 ) 2p E d i=1 ( g 1:T,i 2 ) 2(1-pq) + 4LG pq ∞ T t=2 α t-1 β 1 1 -β 1 2 α 2 1 G (1+r-2pq) ∞ T (1+r)/2 (1 -β 2 ) 2p E d i=1

( g 1:T,i 2 )

1-r (a) = G pq ∞ ∆f (T -1)α 1 + 1 T -1 G 2+pq ∞ v-p 1 1 1 -β 1 + dG 2 ∞ (1 -β 2 ) p + T pq T -1 • 2LG pq ∞ α 1 (1 -β 2 ) 2p E d i=1 ( g 1:T,i 2 ) 2(1-pq) + T (1+r)/2 T -1 • 4LG 1+r-pq ∞ α 1 (1 -β 2 ) 2p β 1 1 -β 1 2 E d i=1 ( g 1:T,i 2 ) 1-r = M 1 T -1 + M 2 d T -1 + M 3 T pq T -1 E d i=1

( g 1:T,i 2 )

2(1-pq)

+ M 4 T (1+r)/2 T -1 E d i=1

( g 1:T,i 2 ) 1-r , where step (a) uses the property α t = α 1 for all t ≥ 2, and {M l } 4 l=1 are given by ( 15)-( 18). The proof is complete.

D CNN ARCHITECTURES IN EXPERIMENTS:

Remark 3. The full name of SERLU in Table 3 is so called scaled exponentially-regularized linear unit. Furthermore, the shift-dropout in Table 3 is designed specifically for SERLU, which includes dropout as a special case. 

:

v is not tracked but just computed and used at each iteration.

This parameter value p = 0.125 was suggested by the authors of(Chen & Gu (2018)).

It is found that αt = 0.001 is not stable when applying AMSGrad to train the CNNs in this case.

Figures and Tables:

Figure 1: Performance comparison of PAdam, AMSGrad, and Game for training four CNNs (see Table 2-5 for the detailed CNN architectures in Appendix D).

c) follows from Cauchy-Schwarz inequality, and step (d) uses T t=1 1/t ≤ (1 + log T ). The proof is complete.

Comparison of three adaptive gradient methods

Table content: <table><tr><td>Alg. 1: AMSGrad</td><td>Alg. 2: PAdam</td><td>Alg. 3: Game</td></tr><tr><td>Input: x1, {αt}, {β1t}, β2</td><td/><td/></tr></table>

CNN for MNIST using SERLU

Table content: <table><tr><td>Layer 1</td><td>conv.: 3 × 3@32 (SERLU)</td></tr><tr><td>Layer 2</td><td>conv.: 3 × 3@64 (SERLU) max-pooling</td></tr><tr><td>Layer 3</td><td>dense: 512 neurons (SERLU)</td></tr><tr><td>Layer 4</td><td>dense + softmax</td></tr></table>

Peer review (iclr2019):
 Pros: 1. The algorithm saves about 1/3 memory consumption compared with AMSGrad. 2. The authors give the proof that the generalized algorithms have the same convergence rate with weaker assumptions. Cons: 1. All the experiments are based on CNN. There are no results based on modern deep neural networks such as Residual Nets and Dense Nets, where it is obvious to see Adam suffers from poor generalization. 2. Algorithms like SGD with momentum and Adam should be included for comparison. 3. This framework introduces two more hyper-parameters p and q, which makes it more difficult for practitioners to tune. Although this framework has proven convergence in both convex and non-convex smooth cases, the experimental evidence is limited. In addition, the proof strategy is not novel enough, Theorem 1 is similar to Theorem 4 in AMSGrad paper and Theorem 2 is similar to Theorem 3.3 in Zhou et al*s paper.