Year: 2018

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.

text: 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.

heading: 1 INTRODUCTION
text: 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’
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 ≤ βp2 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.

heading: 2 PROBLEM SETUP
text: 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
1v is not tracked but just computed and used at each iteration.
scalars by lower-case letters, vectors by bold lower-case letters, and matrices by bold upper-case letters. Following convention, we denote the lp (p ≥ 1) norm of a vector x ∈ Rd by ‖x‖p = ( ∑d i=1 |xi|p)1/p. As p → ∞, the l∞ norm takes a special form ‖x‖∞ = maxdi=1 |xi|. We let g1:t,i = [g1,i, g2,i, · · · , gt,i], where gt,i is the ith element of a vector gt ∈ Rd. We use E[·] to denote the expectation operation. Given two sequences {at} and {bt}, the notation at = O(bt) indicates that the magnitude of at is proportional to that of bt for t ≥ 0. Formally, we reconsider solving the stochastic smooth nonconvex optimization studied in (Ghadimi & Lan (2013; 2016); Zhou et al. (2018))
min x∈Rd
f(x) = Eξ [f(x; ξ)] , (1)
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 ft(x; ξt), where ξt is a realization of ξ. Solving (1) is asymptotically equivalent to addressing the following optimization
lim T→∞ min x∈Rd T∑ t=1 ft(x; ξt). (2)
We will consider both the two formulations (1) and (2) in the reminder of the paper.

heading: 3 GENERALIZED ADAPTIVE MOMENT ESTIMATION (GAME)
text: 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 v̂t at iteration t is computed as
vt = β2vt−1 +(1− β2)g2t (3) v̂t = max(vt, v̂t−1). (4)
It is seen from (3)-(4) that vt is a function of the squared gradients {g2j }tj=1 while v̂t tracks the maximum values of {vj}tj=1 up to iteration t. From a high level perspective, it feels redundant to keep both vt and v̂t 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̂ −pt at iteration t in AMSGrad, where p ∈ [0, 12 ]. One can easily show that p = 0 corresponds to SGD while p = 12 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, 12 ], 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 l2 norm to lp 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 v̂t at iteration t is computed as
vt = β2v̂t−1 +(1− β2)|gt|q (5) v̂t = max(vt, v̂t−1), (6)
where q > 0 is our newly introduced parameter and |gt|q denotes element-wise qth power of |gt|. It is clear from (5)-(6) that vt 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 {vt}. 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 = 12 for Game to make a fair comparison w.r.t. AMSGrad . In this case, one can easily show that v̂t 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 αtV̂ − 12 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.

heading: 4 CONVERGENCE ANALYSIS FOR GAME
text: 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.

heading: 4.1 ANALYSIS FOR CONVEX OPTIMIZATION
text: Formally, we define the cost regret up to iteration T as
RT = T∑ t=1 [ft(xt; ξt)− ft(x∗T ; ξt)] , (7)
where x∗T = arg min ∑T t=1 ft(x) denotes the optimal solution within the iteration range [1, T ], and xt 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 RT and then quantify its convergence behaviour as T increases.
Next we present our convergence analysis: Lemma 1. Let (β1, β2) ∈ [0, 1), β1t ≤ β1, pq < 2 and p, q > 0, and αt = α/ √ t. Then the quantity∑T
t=1 αt [ ‖V̂ −p/2t mt‖22 ] of Game is upper bounded by
T∑ t=1 αt [ ‖V̂ −p/2t mt‖22 ] ≤ α √ 1 + log T (1− β1)2(1− β2)p  d∑ i=1  T∑ j=1 |gj,i|2(2−pq) 1/2  . (8) 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 ≤ β2p2 , where p is the parameter of PAdam.
Theorem 1 (convex). Suppose {ft} 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 ‖∇ft(x; ξt)‖∞ ≤ G∞ for all t ≤ T and distance between any xt generated by Game and x∗T is bounded, i.e., ‖xm − x∗T ‖∞ ≤ D∞. Then we have the following bound on the regret
RT ≤ D2∞ √ T
α(1− β1) d∑ i=1 v̂pT,i + D2∞ 2(1− β1) T∑ t=1 d∑ i=1 β1tv̂ p t,i αt
+ α √ 1 + log T
(1− β1)3(1− β2)p  d∑ i=1  T∑ j=1 |gj,i|2(2−pq) 1/2  (9)
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
RT ≤ D2∞ √ T
α(1− β1) d∑ i=1 v̂ 1/2 T,i + D2∞ 2(1− β1) T∑ t=1 d∑ i=1 β1tv̂ p t,i αt + α √ 1 + log T (1− β1)3( √ 1− β2 [ d∑ i=1 ‖g1:T,i‖2 ] .(10)
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.

heading: 4.2 ANALYSIS FOR SMOOTH NONCONVEX OPTIMIZATION
text: Differently from the analysis for convex optimization, we will consider gradient expectation for nonconvex case. To simplify study later on, we choose the output xout from {xt}Tt=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 xT 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 ∈ Rd, we have
|f(x)− f(y) + 〈∇f(y),x− y〉| ≤ L 2 ‖x− y‖22. (11)
Furthermore, f(x) is lower bounded, i.e., infx 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 tE [ ‖V̂ −pt mt‖22 ] and ∑T t=1 α 2 tE [ ‖V̂ −pt gt‖22 ] 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 r ∈ [2pq − 1, 1]. Assuming ‖∇ft(x; ξt)‖∞ ≤ G∞ for all t ≤ T , we then have
T∑ t=1 α2tE [ ‖V̂ −pt mt‖22 ] ≤ α 2 1G (1+r−2pq) ∞ T (1+r)/2 (1− β2)2p E [ d∑ i=1 (‖g1:T,i‖2)(1−r) ]
(12)
T∑ t=1 α2tE [ ‖V̂ −pt gt‖22 ] ≤ α 2 1T pq (1− β2)2p E [ d∑ i=1 (‖|g1:T,i‖2)2(1−pq) ] . (13)
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 ‖∇ft(x; ξt)‖∞ ≤ G∞ for all t ≤ T and Assumption 1 holds. The output xout of Game satisfies
E [ ‖∇f(xout)‖22 ] ≤ M1 T − 1 + M2d T − 1 + M3T pq T − 1 E ( d∑ i=1 (‖g1:T,i‖2)2(1−pq) )
+ M4T
(1+r)/2
T − 1 E ( d∑ i=1 (‖g1:T,i‖2)1−r ) T ≥ 2, (14)
where
M1 = G pq ∞∆f/α1 (15)
M2 = G2+pq∞ ‖v̂
−p 1 ‖1
d(1− β1) + G2∞ (1− β2)p
(16)
M3 = 2LGpq∞α1 (1− β2)2p
(17)
M4 = 4LG1+r−pq∞ α1
(1− β2)2p
( β1
1− β1
)2 (18)
where ∆f = f(x1)− infx 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 {g1:T,i|i = 1, . . . , d} while the last two are contributed by the inequalities derived in Lemma 2. All the four scalar parameters Mi, 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 = 12 and r = 2pq − 1 in Theorem 2, the upper bound of E [ ‖∇f(xout)‖22 ] then takes the form of
E [ ‖∇f(xout)‖22 ] ≤ M1
(T − 1)α1 + M2d T − 1 +
(M3 +M4)α1 √ T
T − 1 E ( d∑ i=1 ‖g1:T,i‖2 ) T ≥ 2. (19)
As summarized in Table 1, It is immediate that the upper bound in (19) is proportional to O(d/T + GT / √ T ), where GT = E (∑d i=1 ‖g1:T,i‖2 ) . As reflected in Table 1, the upper bound also holds for PAdam even though the iteration procedure (3)-(4) of PAdam is different from (5)-(6) of Game.
We are now in a position to study under what conditions Game would converge. It is not difficult to conclude that when GT is of order GT = O((dT )s) where s < 12 , (19) tends to converge with
Table 2-5 for the detailed CNN architectures in Appendix D).
the speed O(d/T + ds/T 1/2−s). We note that in Duchi et al. (2011)), the assumption GT √ 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 GT = O((dT )s) is slightly stronger than GT √ dT as in practice, the dimension d could be larger than T when training large-scale neural networks.

heading: 5 EXPERIMENTAL RESULTS
text: 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-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.

heading: 6 CONCLUSIONS AND FUTURE WORKS
text: 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.
2This parameter value p = 0.125 was suggested by the authors of (Chen & Gu (2018)). 3It is found that αt = 0.001 is not stable when applying AMSGrad to train the CNNs in this case.

heading: A PROOF OF LEMMA 1
text: Before formally presenting the proof, we first introduce a lemma below: Lemma 3. Let v̂t be defined as in Game and q > 0. Then each component v̂t,i is lower bounded by v̂t,i ≥ (1− β2)|gt,i|q , i = 1, . . . , d.
Proof. The proof follows directly from the computation v̂t,i = max(v̂t−1,i, β2v̂t−1,i+(1−β2)|gt,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 αtE [ ‖V̂ −p/2t mt‖22 ] can be upper bounded by
αt [ ‖V̂ −p/2t mt‖22 ] = αt
[ d∑ i=1 m2t,i v̂pt,i ]
= αt [ d∑ i=1 1 v̂pt,i (∑t j=1 (1− β1j) ∏t−j k=1 β1(t−k+1)gj,i )2] (a) ≤ αt
[ d∑ i=1 1 v̂pt,i (∑t j=1 βt−j1 gj,i )2] (b) ≤ αt
[ d∑ i=1 1 v̂pt,i (∑t j=1 βt−j1 )(∑t j=1 βt−j1 |gj,i|2 )]
(c) ≤ αt 1− β1 [ d∑ i=1 1 v̂pt,i (∑t j=1 βt−j1 |gj,i|2 )]
(d) ≤ αt 1− β1  d∑ i=1 t∑ j=1 1 v̂pj,i βt−j1 |gj,i|2  (e) ≤ αt (1− β1)(1− β2)p  d∑ i=1 t∑ j=1 βt−j1 |gj,i|(2−pq)  (20)
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 v̂ p t,i ≥ v̂ p j,i for all j ≤ t, and step (e) uses the results in Lemma 3.
Next taking the summation of (20) over t = 1 to t = T produces T∑ t=1 αt [ ‖V̂ −p/2t mt‖22 ]
≤ 1 (1− β1)(1− β2)p  T∑ t=1 d∑ i=1 t∑ j=1 αtβ t−j 1 |gj,i|(2−pq)  (a)
≤ α (1− β1)(1− β2)p  d∑ i=1 T∑ j=1 |gj,i|(2−pq) T∑ t=j βt−j1√ t  ≤ α
(1− β1)(1− β2)p  d∑ i=1 T∑ j=1 1√ j |gj,i|(2−pq) T∑ t=j βt−j1 
(b) ≤ α (1− β1)2(1− β2)p  d∑ i=1 T∑ j=1 1√ j |gj,i|(2−pq)  (c) ≤ α (1− β1)2(1− β2)p  d∑ i=1  T∑ j=1 |gj,i|2(2−pq) 1/2 T∑ j=1 1 j 1/2 
(d) ≤ α √ 1 + log T
(1− β1)2(1− β2)p  d∑ i=1  T∑ j=1 |gj,i|2(2−pq) 1/2  (21) where step (a) uses αt = α/ √ t, step (b) uses ∑T t=j β t−j 1 < 1/(1 − β1), step (c) follows from
Cauchy-Schwarz inequality, and step (d) uses ∑T t=1 1/t ≤ (1 + log T ). The proof is complete.

heading: B PROOF OF LEMMA 2
text: We first consider the summation ∑T t=1 α 2 tE [ ‖V̂ −pt mt‖22 ] . Each quantity α2tE [ ‖V̂ −pt mt‖22 ] can be upper bounded by
α2tE [ ‖V̂ −pt mt‖22 ] = α2tE [ d∑ i=1 m2t,i v̂2pt,i ]
= α2tE [ d∑ i=1 1 v̂2pt,i (∑t j=1 (1− β1)βt−j1 gj,i )2]
(a) ≤ α2t (1− β1)2E [ d∑ i=1 1 v̂2pt,i (∑t j=1 βt−j1 |gj,i|(1+r−2pq) )(∑t j=1 βt−j1 |gj,i|(1−r+2pq) )] (b) ≤ α2t (1− β1)2E [ d∑ i=1 1 v̂2pt,i (∑t j=1 βt−j1 G (1+r−2pq) ∞ )(∑t j=1 βt−j1 |gj,i|(1−r+2pq) )]
(c) ≤ α2t (1− β1)G(1+r−2pq)∞ E [ d∑ i=1 1 v̂2pt,i (∑t j=1 βt−j1 |gj,i|(1−r+2pq) )]
(d) ≤ α2t (1− β1)G(1+r−2pq)∞ E  d∑ i=1 t∑ j=1 1 v̂2pj,i βt−j1 |gj,i|(1−r+2pq)  (e)
≤ α 2 t (1− β1)G
(1+r−2pq) ∞
(1− β2)2p E  d∑ i=1 t∑ j=1 βt−j1 |gj,i|(1−r)  (22)
where step (a) uses Cauchy-Schwarz inequality and the property that 2pq − 1 ≤ r ≤ 1 and pq ≤ 1, step (b) uses |gj,i| ≤ ‖gj‖∞ ≤ G∞, step (c) uses ∑t j=1 β t−j 1 ≤ 1/(1−β1), step (d) uses v̂ 2p t,i ≥ v̂ 2p 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
T∑ t=1 α2tE [ ‖V̂ −pt mt‖22 ]
≤ (1− β1)G (1+r−2pq) ∞
(1− β2)2p E  T∑ t=1 d∑ i=1 t∑ j=1 α2tβ t−j 1 |gj,i|(1−r)  (23)
(a) ≤ α 2 1(1− β1)G
(1+r−2pq) ∞
(1− β2)2p E  d∑ i=1 T∑ j=1 |gj,i|(1−r) T∑ t=j βt−j1  (b)
≤ α 2 1G
(1+r−2pq) ∞
(1− β2)2p E  d∑ i=1 T∑ j=1 |gj,i|(1−r) 
(c) ≤ α 2 1G
(1+r−2pq) ∞
(1− β2)2p E  d∑ i=1  T∑ j=1 |gj,i|2 (1−r)/2 T (1+r)/2 = α21G (1+r−2pq) ∞ T (1+r)/2
(1− β2)2p E [ d∑ i=1 (‖g1:T,i‖2)(1−r) ]
where step (a) uses the property that aj ≤ aj−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).
The quantity ∑T t=1 α 2 tE [ ‖V̂ −pt gt‖22 ] in (13) can be upper bounded as
T∑ t=1 α2tE [ ‖V̂ −pt gt‖22 ] =
T∑ t=1 α2tE [ d∑ i=1 g2t,i v̂2pt,i ] (a)
≤ T∑ t=1 α21E [ d∑ i=1 g2t,i (1− β2)2p|gt,i|2pq ]
(b) = α21 (1− β2)2p E  d∑ i=1 T∑ j=1 |gj,i|2−2pq 
(c) ≤ α 2 1
(1− β2)2p E  d∑ i=1  T∑ j=1 |gj,i|2 1−pq T pq = α21T pq
(1− β2)2p E [ d∑ i=1 (‖|g1:T,i‖2)2(1−pq) ]
where step (a) uses the property that aj ≤ aj−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).

heading: C PROOF OF THEOREM 2
text: 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 x0 = x1 and for each t ≥ 1
zt = xt + β1
1− β1 (xt − xt−1) =
1
1− β1 xt − β1 1− β1 xt−1, (24)
where z1 = x1 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 {xj}Tj=0 directly, we tackle {zj}Tj=1 as in the literature. In (Zhou et al. (2018)) and (Chen et al. (2018)), the authors provided a general upper bound for f(zt+1)− f(zt), which also holds for Game. We now summarize their result in a lemma below:
Lemma 4. Suppose the sequence {zj}Tj=1 is as defined in (24). Then under Assumption 1, the quantity f(zt+1)− f(zt) is upper bounded by
f(z2)− f(z1) ≤−∇f(x1)Tα1V̂ −p1 g1 + 2L‖α1V̂ −p 1 g1‖22 (25)
f(zt+1)− f(zt) ≤−∇f(xt)Tαt−1V̂ −pt−1gt + 1
1− β1 G2∞(‖αt−1v̂ −p t−1‖1 − ‖αtv̂ −p t ‖1)
+ 2L‖αtV̂ −pt gt‖22 + 4L (
β1 1− β1
)2 ‖xt − xt−1‖22 t ≥ 2. (26)
With Lemma 4, we are ready to present the proof for Theorem 2. Firstly, taking expectation on both sides of (25) produces
E[f(z2)− f(z1)] ≤ E [ −∇f(x1)Tα1V̂ −p1 g1 + 2L‖α1V̂ −p 1 g1‖22 ] ≤ E [ dα1‖∇f(x1)‖∞ · ‖V̂ −p1 g1‖∞ + 2L‖α1V̂ −p 1 g1‖22
] (a)
≤ E [
dα1 (1− β2)p
‖∇f(x1)‖∞ · ‖|g|1−pq‖∞ + 2L‖α1V̂ −p1 g1‖22 ]
(b) ≤ E [ dα1G 2−pq ∞
(1− β2)p + 2L‖α1V̂ −p1 g1‖22
] , (27)
where step (a) uses V̂1 = (1− β2)|g1|q and pq < 1, and step (b) uses ‖∇ft(x; ξt)‖∞ ≤ G∞. Next by rearranging terms and taking expectation in (26), we have
E [ f(zt+1) +
G2∞ 1− β1
‖αtv̂−pt ‖1 − ( f(zt) +
G2∞ 1− β1
‖αt−1v̂−pt−1‖1 )]
≤ E [ −∇f(xt)tαt−1V̂ −pt−1gt + 2L‖αtV̂ −p t gt‖22 + 4L ( β1
1− β1
)2 ‖xt−1 − xt‖22 ] (a) = −∇f(xt)tαt−1V̂ −pt−1∇f(xt) + E [ 2L‖αtV̂ −pt gt‖22 + 4L ( β1
1− β1
)2 ‖αt−1V̂ −pt−1mt−1‖22 ] (b) ≤ −αt−1‖∇f(xt)‖22(Gpq∞)−1 + E [ 2L‖αtV̂ −pt gt‖22 + 4L ( β1
1− β1
)2 ‖αt−1V̂ −pt−1mt−1‖22 ] , (28)
where step (a) uses the property that E[gt] = ∇f(xt), and step (b) uses the inequality ‖v̂t−1‖∞ ≤ Gq∞ which can be derived from ‖∇ft(x; ξt)‖∞ ≤ G∞, t ≥ 1. Taking the summation of (27)-(28) over t = 1 to T produces
(Gpq∞) −1 T∑ t=2 αt−1E‖∇f(xt)‖22
≤ E [ f(z1) + G2∞‖α1v̂ −p 1 ‖1
1− β1 + dα1G
2−pq ∞ (1− β2)p − ( f(zT+1) + G2∞ 1− β1 ‖αT v̂−pT ‖1 )]
+ 2L T∑ t=1 E [ ‖αtV̂ −pt gt‖22 ] + 4L ( β1 1− β1 )2 T∑ t=2 E [ ‖αt−1V̂ −pt−1mt−1‖22 ] (a) ≤ E [ ∆f + G2∞‖α1v̂ −p 1 ‖1
1− β1 + dα1G
2−pq ∞
(1− β2)p
] + 2L
T∑ t=1 E [ ‖αtV̂ −pt gt‖22 ] + 4L ( β1
1− β1 )2 T∑ t=1 E [ ‖αtV̂ −pt mt‖22 ] , (29)
where step (a) uses the inequality ∆f = f(x1)− infx f(x) ≥ f(x1)− f(zT+1) and z1 = x1.
Finally, substituting (12)-(13) into (29) produces
E‖∇f(xout)‖22
= 1∑T
t=2 αt−1 T∑ t=2 αt−1E‖∇f(xt)‖22
≤ G pq ∞∑T
t=2 αt−1 E
[ ∆f + G2∞‖α1v̂ −p 1 ‖1
1− β1 + dα1G
2−pq ∞
(1− β2)p
]
+ 2LGpq∞∑T t=2 αt−1 α21T pq (1− β2)2p E ( d∑ i=1 (‖g1:T,i‖2)2(1−pq) )
+ 4LGpq∞∑T t=2 αt−1
( β1
1− β1
)2 α21G (1+r−2pq) ∞ T (1+r)/2
(1− β2)2p E ( d∑ i=1 (‖g1:T,i‖2)1−r )
(a) =
Gpq∞∆f
(T − 1)α1 +
1
T − 1
( G2+pq∞ ‖v̂ −p 1 ‖1
1− β1 + dG2∞ (1− β2)p
)
+ T pq T − 1 · 2LG pq ∞α1 (1− β2)2p E ( d∑ i=1 (‖g1: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 (‖g1:T,i‖2)1−r )
= M1 T − 1 + M2d T − 1 + M3T
pq
T − 1 E ( d∑ i=1 (‖g1:T,i‖2)2(1−pq) )
+ M4T
(1+r)/2
T − 1 E ( d∑ i=1 (‖g1:T,i‖2)1−r ) ,
where step (a) uses the property αt = α1 for all t ≥ 2, and {Ml}4l=1 are given by (15)-(18). The proof is complete.

heading: D CNN ARCHITECTURES IN EXPERIMENTS
text: 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.

Review summaries:
The authors proposed a generalized adaptive moment estimation method(Game). Compared to the existing methods AMSGrad and PAdam, the new method Game tracks only two parameters in iteration and hence saves memory. Besides, they introduced a additional tuning parameter $q$ to track the q-th moment of the gradient and allow more flexibility. The authors also provided the theoretical convergence analysis of Game for convex optimization and smooth nonconvex optimization. Their experiment shows Game may produce better performance than AMSGrad and PAdam with a little bit sacrifice of convergence speed. Game is a promising alternative method for training large-scale neural network.