Title: POWEREDSGD: POWERED STOCHASTIC GRADIENT DESCENT METHODS FOR ACCELERATED NON-CONVEX OPTIMIZATION

Abstract: We propose a novel technique for improving the stochastic gradient descent (SGD) method to train deep networks, which we term PoweredSGD. The proposed Pow-eredSGD method simply raises the stochastic gradient to a certain power γ ∈ [0, 1] elementwise during iterations and introduces only one additional parameter, namely, the power exponent γ (when γ = 1, PoweredSGD reduces to SGD). We further propose PoweredSGD with momentum, which we term PoweredSGDM, and provide convergence rate analysis on both PoweredSGD and PoweredSGDM methods. Experiments are conducted on popular deep learning models and benchmark datasets. Empirical results show that the proposed PoweredSGD and PoweredSGDM obtain faster initial training speed than adaptive gradient methods, comparable generalization ability with SGD, and improved robustness to hyper-parameter selection and vanishing gradients. PoweredSGD is essentially a gradient modifier via a nonlinear transformation. As such, it is orthogonal and complementary to other techniques for accelerating gradient-based optimization.

1. INTRODUCTION:

Stochastic optimization as an essential part of deep learning has received much attention from both the research and industry communities. High-dimensional parameter spaces and stochastic objective functions make the training of deep neural network (DNN) extremely challenging. Stochastic gradient descent (SGD) (Robbins & Monro, 1951) is the first widely used method in this field. It iteratively updates the parameters of a model by moving them in the direction of the negative gradient of the objective evaluated on a mini-batch. Based on SGD, other stochastic optimization algorithms, e.g., SGD with Momentum (SGDM) (Qian, 1999) , AdaGrad (Duchi et al., 2011) , RMSProp (Tieleman & Hinton, 2012) , Adam (Kingma & Ba, 2015) are proposed to train DNN more efficiently.

Despite the popularity of Adam, its generalization performance as an adaptive method has been demonstrated to be worse than the non-adaptive ones. Adaptive methods (like AdaGrad, RMSProp and Adam) often obtain faster convergence rates in the initial iterations of training process. Their performance, however, quickly plateaus on the testing data (Wilson et al., 2017) . In Reddi et al. (2018) , the authors provided a convex optimization example to demonstrate that the exponential moving average technique can cause non-convergence in the RMSProp and Adam, and they proposed a variant of Adam called AMSGrad, hoping to solve this problem. The authors provide a theoretical guarantee of convergence but only illustrate its better performance on training data. However, the generalization ability of AMSGrad on test data is found to be similar to that of Adam, and a considerable performance gap still exists between AMSGrad and SGD (Keskar & Socher, 2017; Chen et al., 2018) . Indeed, the optimizer is chosen as SGD (or with Momentum) in several recent state-of-the-art works in natural language processing and computer vision (Luo et al., 2018; Wu & He, 2018) , where in these instances SGD does perform better than adaptive methods. Despite the practical success of SGD, obtaining sharp convergence results in the non-convex setting for SGD to efficiently escape saddle points (i.e., convergence to second-order stationary points) remains a topic of active research (Jin et al., 2019; Fang et al., 2019) .

Related Works: SGD, as the first efficient stochastic optimizer for training deep networks, iteratively updates the parameters of a model by moving them in the direction of the negative gradient of the objective function evaluated on a mini-batch. SGDM brings a Momentum term from the physical perspective, which obtains faster convergence speed than SGD. The Momentum idea can be seen as a particular case of exponential moving average (EMA). Then the adaptive learning rate (ALR) technique is widely adopted but also disputed in deep learning, which is first introduced by AdaGrad. Contrast to the SGD, AdaGrad updates the parameters according to the square roots of the sum of squared coordinates in all the past gradients. AdaGrad can potentially lead to huge gains in terms of convergence (Duchi et al., 2011) when the gradients are sparse. However, it will also lead to rapid learning rate decay when the gradients are dense. RMSProp, which first appeared in an unpublished work (Tieleman & Hinton, 2012) , was proposed to handle the aggressive, rapidly decreasing learning rate in AdaGrad. It computes the exponential moving average of the past squared gradients, instead of computing the sum of the squares of all the past gradients in AdaGrad. The idea of AdaGrad and RMSProp propelled another representative algorithm: Adam, which updates the weights according to the mean divided by the root mean square of recent gradients, and has achieved enormous success. Recently, research to link discrete gradient-based optimization to continuous dynamic system theory has received much attention (Yuan et al., 2016; Mazumdar & Ratliff, 2018) . While the proposed optimizer excels at improving initial training, it is completely complementary to the use of learning rate schedules (Smith & Topin, 2019; Loshchilov & Hutter, 2016) . We will explore how to combine learning rate schedules with the PoweredSGD optimizer in future work.

While other popular techniques focus on modifying the learning rates and/or adopting momentum terms in the iterations, we propose to modify the gradient terms via a nonlinear function called the Powerball function by the authors of Yuan et al. (2016) . In Yuan et al. (2016) , the authors presented the basic idea of applying the Powerball function in gradient descent methods. In this paper, we 1) systematically present the methods for stochastic optimization with and without momentum; 2) provide convergence proofs; 3) include experiments using popular deep learning models and benchmark datasets. Another related work was presented in Bernstein et al. (2018) , where the authors presented a version of stochastic gradient descent which uses only the signs of gradients. This essentially corresponds to the special case of PoweredSGD (or PoweredSGDM) when the power exponential γ is set to 0. We also point out that despite the name resemblance, the power PowerSign optimizer proposed in Bello et al. (2017) is a conditional scaling of the gradient, whereas the proposed PoweredSGD optimizer applies a component-wise trasformation to the gradient.

Contributions::

Inspired by the Powerball method in Yuan et al. (2016) , this paper uses Powerballbased stochastic optimizers for the training of deep networks. In particular, we make the following major contributions:

1. We propose the PoweredSGD, which is the first systematic application of the Powerball function technique in stochastic optimization. PoweredSGD simply applies the Powerball function (with only one additional parameter γ) on the stochastic gradient term in SGD. Hence, it is easy to implement and requires no extra memory. We also propose the Pow-eredSGDM as a variant of PoweredSGD with momentum to further improve its convergence and generalization abilities. 2. We have proved the convergence rates of the proposed PoweredSGD and PoweredSGDM. It has been shown that both the proposed PoweredSGD and PoweredSGDM attain the best known rates of convergence for SGD and SGDM on non-convex functions. In fact, to the knowledge of the authors, the bounds we proved for SGD and SGDM (as special cases of PoweredSGD and PoweredSGDM when γ = 1) provide the currently best convergence bounds for SGD and SGDM in the non-convex setting in terms of both the constants and rates of convergence (see, e.g. Yan et al. (2018) ). 3. Experimental studies are conducted on multiple popular deep learning tasks and benchmark datasets. The results empirically demonstrate that our methods gain faster convergence rate especially in the early train process compared with the adaptive gradient methods. Meanwhile, the proposed methods show comparable generalization ability compared with SGD and SGDM.

Outline: The remainder of the paper is organized as below. Section 2 proposes the PoweredSGD and PoweredSGDM algorithms. Section 3 provides convergence results of the proposed algorithms for non-convex optimization. Section 4 gives the experiment results of the proposed algorithms on a variety of models and datasets to empirically demonstrate their superiority to other optimizers. Finally, conclusions are drawn in section 5.

Notation: Given a vector a ∈ R n , we denote its i-th coordinate by a i ; we use a to denote its 2-norm (Euclidean norm) and a p to denote its p-norm for p ≥ 1. Given two vectors a, b ∈ R n , we use a • b to denote their inner product. We denote by E[•] the expectation with respect to the underlying probability space.

2. ALGORITHMS:

In this section, we present the main algorithms proposed in this paper: PoweredSGD and PoweredS-GDM. PoweredSGD combines the Powerball function technique with stochastic gradient descent, and PoweredSGDM is an extension of PoweredSGD to include a momentum term. We shall prove in Section 3 that both methods converge and attain at least the best known rates of convergence for SGD and SGDM on non-convex functions, and demonstrate in Section 4 the advantages of using PoweredSGD and PoweredSGDM compared to other popular stochastic optimizers for train deep networks.

2.1. POWEREDSGD:

Train a DNN with n free parameters can be formulated as an unconstrained optimization problem

EQUATION

where f (•) : R n → R is a function bounded from below. SGD proved itself an efficient and effective solution for high-dimensional optimization problems. It optimizes f by iteratively updating the parameter vector x t ∈ R n at step t, in the opposite direction of a stochastic gradient g(x t , ξ t ) (where ξ t denotes a random variable), which is calculated on t-th mini-batch of train dataset. The update rule of SGD for solving problem (1) is

EQUATION

starting from an arbitrary initial point x 1 , where α t is known as the learning rate at step t. In the rest of the article, let g t = g(x t , ξ t ) for the sake of notation. We then introduce a nonlinear transformation σ γ (z) = sign(z)|z| γ named as the Powerball function where sign(z) returns the sign of z, or 0 if z = 0. For any vector z = (z 1 , . . . , z n ) T , the Powerball function σ γ (z) is applied to all elements of z. A parameter γ ∈ R is introduced to adjust the mechanism and intensity of the Powerball function.

Applying the Powerball function to the stochastic gradient term in the update rule (2) gives the proposed PoweredSGD algorithm:

EQUATION

where γ ∈ [0, 1] is an additional parameter. Clearly, when γ = 1, we obtain the vanilla SGD (2). The detailed pseudo-code of the proposed PoweredSGD is presented in Algorithm 1.

2.2. POWEREDSGDM:

The momentum trick inspired by physical processes Polyak (1964); Nesterov (1983) has been successfully combined with SGD to give SGDM, which almost always gives better convergence rates on train deep networks. We hereby follow this line to propose the PoweredSGD with Momentum (PoweredSGDM), whose update rule is

EQUATION

Clearly, when β = 0, PowerSDGM (4) reduces to PoweredSGD (3). Pseudo-code of the proposed PoweredSGDM is detailed in Algorithm 2.

3. CONVERGENCE ANALYSIS:

In this section, we present convergence results of PoweredGD and PoweredSGDM in the non-convex setting. We start with some standard technical assumptions. First, we assume that the gradient of the objective function f is L-Lipschitz.

Assumption 3.1 There exists some

L > 0 such that |∇ f (x) -∇ f (y)| ≤ L x -y , for all x, y ∈ R n .

We then assume that a stochastic first-order black-box oracle is accessible as a noisy estimate of the gradient of f at any point x ∈ R n , and the variance of the noise is bounded.

Assumption 3.2 The stochastic gradient oracle gives independent and unbiased estimate of the gradient and satisfies:

EQUATION

where σ ≥ 0 is a constant.

We will be working with a mini-batch size in the proposed PoweredSGD and PoweredSGDM. Let n t be the mini-batch size at the t-th iteration and the corresponding mini-batch stochastic gradient be given by the average of n t calls to the above oracle. Then by Assumption 3.2 we can show that

E[ g t -∇ f (x t ) 2 ] ≤ σ 2 /n t for all t ≥ 1.

In other words, we can reduce variance by choosing a larger mini-batch size (see Supplementary Material A.2).

3.1. CONVERGENCE ANALYSIS OF POWEREDSGD:

We now state the main convergence result for the proposed PoweredSGD.

Theorem 3.1 Suppose that Assumptions 3.1 and 3.2 hold. Let T be the number of iterations. PoweredSGD (3) with an adaptive learning rate and mini-batch size B t = T (independent of a particular step t) can lead to

E 1 T T ∑ k=1 g t 2 1+γ ≤ 2 1 p T L( f (x 1 ) -f ) 1 -ε + σ 2 2ε(1 -ε)

,

where ε ∈ (0, 1), p = 1+γ 1-γ for any γ ∈ [0, 1) and p = ∞ for γ = 1.

The proof of Theorem 3.1 can be found in the Supplementary Material A.2.

Remark 3.1 The proposed PoweredSGD and PoweredSGDM have the potential to outperform popular stochastic optimizers by allowing the additional parameter γ that can be tuned for different training cases, and they always reduce to other optimizers when setting γ = 1.

Remark 3.2 We leave ε ∈ (0, 1) to be a free parameter in the bound to provide trade-offs between bounds given by the curvature L and stochasticity σ . If σ = 0, we can choose ε → 0 and recover the convergence bound for PoweredGD (see Supplementary Material A.1).

Remark 3.3:

The above theorem provides a sharp estimate of the convergence of PoweredSGD in the following sense. When γ = 1, the convergence bound reduces to the best known convergence rate for SGD. Note that, because of the choice of batch size, it requires T 2 gradient evaluations in T iterations. So the convergence rate is effectively O(1/ √ T ). This is the best known rate of convergence for SGD Ge et al. (2015) . When σ = 0 (i.e., exact gradients are used and B t = 1), PoweredSGD can attain convergence in the order O(1/T ), which is consistent with the convergence rate of gradient descent.

3.2. CONVERGENCE ANALYSIS OF POWEREDSGDM:

We now present convergence analysis for PoweredSGDM. The proof is again included in the Supplementary Material B.2 due to the space limit.

Theorem 3.2 Suppose that Assumptions 3.1 and 3.2 hold. Let T be the number of iterations. For any β ∈ [0, 1), PoweredSGDM (4) with an adaptive learning rate and mini-batch size B t = T (independent of a particular step t) can lead to

E 1 T T ∑ t=1 g t 2 1+γ ≤ 2 1 p T L( f (x 1 ) -f ) 1 -ε 1 + β 1 -β + σ 2 2ε(1 -ε)

,

where ε ∈ (0, 1), p = 1+γ 1-γ for any γ ∈ [0, 1) and p = ∞ for γ = 1.

Remark 3.4 Convergence analysis of stochastic momentum methods for non-convex optimization is an important but under-explored topic. While our results on convergence analysis do not improve the rate of convergence for stochastic momentum methods in a non-convex setting, it does match the currently best known rate of convergence (Yan et al., 2018; Bernstein et al., 2018) in special cases (γ = 0, 1) and offers very concise upper bounds in terms of the constants. The upper bound continuously interpolates the convergence rate for γ varying in [0, 1] and β varying in [0, 1). The key technical result that made the results of Theorems 3.1 and 3.2 possible is Lemma B.1 in the Supplementary Material, which provide a tight estimate of accumulated momentum terms. We also note that the convergence rates for γ ∈ (0, 1) are entirely new and not reported elsewhere before.

Even for the special case of γ = 0, 1, our proof differs from that of (Yan et al., 2018; Bernstein et al., 2018) and seems more transparent.

Remark 3.5 A large mini-batch (B t = T ) is assumed for the convergence results to hold. This is consistent with the convergence analysis in Bernstein et al. (2018) for the special case γ = 0. We assume this because it enables us to put analysis of PoweredGD and PoweredSGD in a unified framework so that we can obtain tighter bounds. In the stochastic setting, similar to Remark 3.3, we note that our proof requires T 2 gradient calls in T iterations and hence the effective convergence rate is O(1/ √ T ), which is consistent with the known rate of convergence for SGD (Ge et al., 2015) .

4. EXPERIMENTS:

The propose of this section is to demonstrate the efficiency and effectiveness of the proposed Pow-eredSGD and PoweredSGDM algorithms. We conduct experiments of different model architectures on datasets in comparison with widely used optimization methods including the non-adaptive method SGDM and three popular adaptive methods: AdaGrad, RMSprop and Adam. This section is mainly composed of two parts: (1) the convergence and generalization experiments and (2) the Powerball feature experiments. The setup for each experiment is detailed in Table 1 1 . In the first part, we present empirical study of different deep neural network architectures to see how the proposed methods behave in terms of convergence speed and generalization. In the second part, the experiments are conducted to explore the potential features of PoweredSGD and PoweredSGDM.

To ensure stability and reproducibility, we conduct each experiment at least 5 times from randomly initializations and the average results are shown. The settings of hyper-parameters of a specific optimization method that can achieve the best performance on the test set are chosen for comparisons. When two settings achieve similar test performance, the setting which converges faster is adopted.

We can have the following findings from our experiments: (1) Since the initial learning rate has a large impact on the performances of optimizers, we implement a logarithmically-spaced grid search strategy around the default learning rate for each optimization method, and leave the other hyper-parameters to their default settings.

SGDM::

The default learning rate for SGDM is 0.01. We tune the learning rate on a logarithmic scale from {1, 0.1, 0.01, 0.001, 0.0001}. The momentum value in all experiments is set to default value 0.9.

PoweredSGD, PoweredSGDM: The learning rates for PoweredSGD and PoweredSGDM are chosen from the same range {1, 0.1, 0.01, 0.001, 0.0001} as SGDM. The momentum value for PoweredS-GDM is also 0.9. Note that γ = 1 in Powerball function corresponds to the SGD or SGDM. Based on extensive experiments, we empirically tune γ from {0.5, 0.6, 0.7, 0.8, 0.9}.

AdaGrad: The learning rates for AdaGrad are {1e-1, 5e-2, 1e-2, 5e-3, 1e-3} and we choose 0 for the initial accumulator value.

RMSprop, Adam: Both have the default learning rate 1e-3 and their learning rates are searched from {1e-2, 5e-3, 1e-3, 5e-4, 1e-4}. The parameters β 1 , β 2 and the perturbation value ε are set to default.

As previous findings Wilson et al. (2017) show, adaptive methods generalize worse than non-adaptive methods and carefully tuning the initial learning rate yields significant improvements for them. To better compare with adaptive methods, once we have found the value that was best performing in adaptive methods, we would try the learning rate between the best learning rate and its closest neighbor. For example, if we tried learning rates {1e-2, 5e-3, 1e-3, 5e-4, 1e-4} and 1e-4 was best performing, we would try the learning rate 2e-4 to see if performance was improved. We iteratively update the learning rate until performance could not be improved any more. For all experiments, we used a mini-batch size of 128. As the figure shows, the adaptive methods converged fast and appeared to be performing better than the non-adaptive method SGDM as expected. During the training process, the stochastic gradients in early layers can be extremely small due to the chain rule, and this can even completely stop the networks from being trained. Our proposed PoweredSGD method can relieve the phenomenon of gradient vanishing by effectively rescaling the stochastic gradient vectors.

4.2. EXPERIMENTS: CONVERGENCE AND GENERALIZATION:

To validate this, we conduct experiments on the MNIST dataset by using a 13-layer fully-connected neural network with ReLU activation functions. The SGD and proposed PoweredSGD are compared in terms of train accuracy and 1-norm of gradient vector. As can be observed in Fig. 2 , SGD completely cannot train such a deep network and its train accuracy remained below 11.24%. By contrast, the train accuracy of PoweredSGD grows quickly to 98.91% after few epochs. We further compare the 1-norm of stochastic gradient vector in the first layer for both SGD and PoweredSGD. It is clear that the Powerball function amplifies the stochastic gradients and helps relieve the gradient vanishing phenomenon. We have included more experimental results on gradient vanishing in the Supplementary Material C.

5. CONCLUSION:

In this paper, a Powerball function is introduced as a basic technique to improve SGD and SGDM for deep neural network training. Their convergence rates have been proved in the non-convex optimization settings. We discussed the choice of an important hyper-parameter γ in the Supplementary Material E from an empirical point of view. The experiments on different neural network models and benchmark datasets have demonstrated that the proposed PoweredSGD and PoweredSGDM empirically obtain faster training speed than adaptive gradient methods and good if not better generalization ability compared with SGD. We also show that PoweredSGD can help alleviate gradient vanishing.

The authors of Yuan et al. (2016) then provided insights from finite convergence properties of ODEs models for Powerball variants of gradient descent algorithms and presented empirical observations of convergence acceleration of Powerball methods. Nonetheless, they did not provide any convergence results for their algorithms. In fact, they highlighted the convergence analysis of their algorithms as open theoretical questions. In this paper, we are going to analyze stochastic variants of Powerball methods in the non-convex setting. We start with the analysis of PoweredGD (powered gradient descent) in ( 6).

Theorem A.1 Suppose that Assumption 3.1 holds. The PoweredGD scheme (6) can lead to

1 T T ∑ t=1 ∇ f (x t )) 2 1+γ ≤ 2L 1 p T ( f (x 1 ) -f ),

where T is the number of iterations and p = 1+γ 1-γ for any γ ∈ [0, 1) and p = ∞ for γ = 1.

Proof: Denote by x the minimizer and f = f (x ). Then, by the L-Lipschitz continuity of ∇ f and (6),

EQUATION

EQUATION

)

By Hölder's inequality, for γ ∈ (0, 1) and with p = 1+γ 1-γ and q = 1+γ 2γ , we have

σ (∇ f (x t )) 2 = n ∑ i=1 |(∇ f ) i (x t )| 2γ ≤ ( n ∑ i=1 1 p ) 1 p ( n ∑ i=1 (|(∇ f ) i (x t )| 2γ ) q ) 1 q ≤ 1 p ( n ∑ i=1 |(∇ f ) i (x t )| 1+γ ) 2γ 1+γ .

It follows that

f (x t+1 ) ≤ f (x t ) - (∇ f (x t ) • σ (∇ f (x t ))) 2 2L σ (∇ f (x t )) 2 ≤ f (x t ) - (∑ n i=1 |(∇ f ) i (x t )| 1+γ ) 2 2L 1 p (∑ n i=1 |(∇ f ) i (x t )| 1+γ ) 2γ 1+γ = f (x t ) - 1 2L 1 p ( n ∑ i=1 |(∇ f ) i (x t )| 1+γ ) 2 1+γ = f (x t ) - 1 2L 1 p ∇ f (x t ) 2 1+γ ,

which, by a telescoping sum, gives

1 T T ∑ t=1 ∇ f (x t ) 2 1+γ ≤ 2L 1 p T ( f (x 1 ) -f (x T +1 )) ≤ 2L 1 p T ( f (x 1 ) -f ),

where 1 is vector with entries all given by 1. It is easy to see that the estimate is also valid for γ = 1 with p = ∞ and for γ = 0. The proof is complete.

A.2 CONVERGENCE OF POWEREDSGD (PROOF OF THEOREM 3.1):

To analyze the convergence of PoweredSGD, we need some preliminary on the relation between mini-batch size and variance reduction of SGD.

VARIANCE REDUCTION BY A LARGER MINI-BATCH SIZE:

Let ∇ f (x) be the gradient of f at x ∈ R n . Suppose that we use the average of m calls to the stochastic gradient oracle, denoted by g(x, ξ i )

(i = 1, • • • , m), to estimate ∇ f (x)

. By Assumption 3.2, we have

E ∑ m i=1 g(x, ξ i ) m -∇ f (x) 2 = 1 m E 1 m m ∑ i=1 [g(x, ξ i ) -∇ f (x)] 2 = 1 m E 1 m m ∑ i=1 g(x, ξ i ) -∇ f (x) 2 = 1 m 1 m (m σ 2 ) = σ 2 m ,

where in the second equality we used the fact that g(x, ξ i )

(i = 1, • • • , m)

are drawn independently and all give unbiased estimate of ∇ f (x) (provided by Assumption 3.2).

Now we are ready to present the proof of Theorem 3.1.

PROOF OF THEOREM 3.1

Proof: By the L-Lipschitz continuity of ∇ f and (6),

EQUATION

Fix any iteration number T > 1 and let ε ∈ (0, 1) to be chosen. We can estimate

α t (g t -∇ f (x t )) • σ (g t ) = g t • σ (g t ) L σ (g t ) 2 (g t -∇ f (x t )) • σ (g t ) ≤ |g t • σ (g t )| L σ (g t ) 2 g t -∇ f (x t ) σ (g t ) = |g t • σ (g t )| L σ (g t ) g t -∇ f (x t ) ≤ 1 2L ε (g t • σ (g t )) 2 σ (g t ) 2 + 1 ε g t -∇ f (x t ) 2 ,

where the last inequality followed from the elementary inequality 2ab ≤ εa 2 + 1 ε b 2 for any positive real number ε and real numbers a, b. Substituting this into (9) gives

EQUATION

)

By the same argument in the proof for Theorem A.1, we can derive

f (x t+1 ) ≤ f (x t ) -1-ε 2L 1 p g t 2 1+γ + 1 2Lε g t -∇ f (x t ) 2 .

Taking conditional expectation from both sizes gives

E[ f (x t+1 ) -f (x t ) | x t ] ≤ -1-ε 2L 1 p E[ g t 2 1+γ ] + 1 2Lε σ 2 t ≤ -1-ε 2L 1 p E[ g t 2 1+γ ] + σ 2 2LεT ,

where σ 2 t is the variance of the t-th stochastic gradient approximation computed using the chosen mini-batch size B t = T , which therefore satisfies σ 2 t ≤ σ 2

T . Taking expectation from both sides and performing a telescoping sum give

E 1 T T ∑ t=1 g t 2 1+γ ≤ 2L 1 p T (1-ε) ( f (x 1 ) -f ) + 1 p T ε(1-ε) σ 2 .

The proof is complete.

B CONVERGENCE ANALYSIS OF POWEREDSGDM B.1 CONVERGENCE OF POWEREDGDM:

We first analyze the deterministic version of PoweredSGDM (denoted by PoweredGDM). The update rule for PoweredGDM is

EQUATION

where β ∈ [0, 1) is a momentum constant and v 0 = 0. Clearly, when β = 0, the scheme also reduces to PoweredGD.

Theorem B.1 Suppose that Assumption 3.1 holds. For any β ∈ [0, 1), the PoweredGDM scheme ( 11) with an adaptive learning rate can lead to

1 T T ∑ t=1 ∇ f (x t ) 2 1+γ ≤ 2L 1 p T 1 + β 1 -β ( f (x 1 ) -f ),

where T is the number of iterations and p = 1+γ 1-γ for any γ ∈ [0, 1) and p = ∞ for γ = 1.

Proof: Let z t = x t + β 1-β v t . It can be verified that the PoweredGDM scheme satisfies

EQUATION

By the L-Lipschitz continuity of ∇ f and (12),

EQUATION

)

We can estimate

EQUATION

)

where ε > 0 is to be chosen. By the L-Lipschitz continuity of ∇ f ,

EQUATION

) Lemma B.1 For T ≥ 1, we have T ∑ t=1 v t 2 ≤ 1 (1 -β ) 2 T ∑ t=1 α 2 t σ (∇ f (x t )) 2 .

Proof: It is easy to show by induction that, for t ≥ 1,

v t = - t-1 ∑ i=1 β t-i-1 α i σ (∇ f (x i )).

Indeed, we have v 1 = 0 and v 2 = -α 1 σ (∇ f (x 1 )). Suppose that the above holds for t ≥ 1. Then

v t+1 = β v t -β α t σ (∇ f (x t )) = β - t-1 ∑ i=1 β t-i-1 α i σ (∇ f (x i )) -β α t ∇ f (x t ) = - t ∑ i=1 β (t+1)-i-1 α i σ (∇ f (x i )). Hence T ∑ t=1 v t 2 = T ∑ t=1 - t-1 ∑ i=1 β t-i-1 α i σ (∇ f (x i )) 2 ≤ T ∑ t=1 t-1 ∑ i=1 β t-i-1 α i σ (∇ f (x i )) 2 ≤ T ∑ t=1 t-1 ∑ i=1 β t-i-1 t-1 ∑ i=1 β t-i-1 α i σ (∇ f (x i )) 2 ≤ 1 1 -β T ∑ t=1 t-1 ∑ i=1 β t-i-1 α i σ (∇ f (x i )) 2 = 1 1 -β T ∑ i=1 α i σ (∇ f (x i )) 2 T ∑ t=i+1 β t-i-1 ≤ 1 (1 -β ) 2 T ∑ t=1 α 2 t σ (∇ f (x t )) 2 .

By Lemma B.1, inequalities ( 14), ( 15), and a telescoping sum on (13), we get

f -f (z 1 ) ≤ - 1 1 -β T ∑ t=1 α t ∇ f (x t ) • σ (∇ f (x t )) + εL 2 β 2 2(1 -β ) 5 + 1 2ε(1 -β ) + L 2(1 -β ) 2 T ∑ t=1 α 2 t σ (∇ f (x t )) 2 . It is clear that ε = (1-β ) 2

Lβ would minimize the bound on the right-hand side (among different choices of ε > 0) and give

f -f (z 1 ) ≤ - 1 1 -β T ∑ t=1 α t ∇ f (x t ) • σ (∇ f (x t )) + Lβ (1 -β ) 3 + L 2(1 -β ) 2 T ∑ t=1 α 2 t σ (∇ f (x t )) 2 .

For any β ∈ [0, 1), we can choose

α t = ∇ f (x t )•σ (∇ f (x t )) L σ (∇ f (x t )) 2 (1-β ) 2

1+β so that the bound reduces to

f -f (z 1 ) ≤ - 1 -β 2L(1 + β ) T ∑ t=1 (∇ f (x t ) • σ (∇ f (x t ))) 2 σ (∇ f (x t )) 2 ,

which immediately gives the bound in the theorem by noting z 1 = x 1 .

B.2 CONVERGENCE OF POWEREDSGDM (PROOF OF THEOREM 3.2):

Proof: The proof is built on that for Theorem B.1. With z t = x t + β 1-β v t , it can be verified that the PoweredSGDM scheme satisfies

EQUATION

By the L-Lipschitz continuity of ∇ f and (4),

EQUATION

)

Similar to the proof of Theorem B.1, we can estimate

EQUATION

)

where ε 1 > 0 is to be chosen. By the L-Lipschitz continuity of ∇ f ,

EQUATION

)

Similar to Lemma B.1, we obtain

EQUATION

)

We can also bound

EQUATION

where ε > 0. By inequalities ( 18)-( 21), and a telescoping sum on (17), we get

f -f (z 1 ) ≤ -1 1-β ∑ T t=1 α t g t • σ (g t ) + 1 2 ε 1 L 2 β 2 (1-β ) 5 + 1 ε 1 (1-β ) + L (1-β ) 2 + Lε(1+β ) (1-β ) 3 ∑ T t=1 α 2 t σ (g t ) 2 + 1-β 2Lε(1+β ) ∑ T t=1 g t -∇ f (x t ) 2 . Setting ε 1 = (1-β ) 2 Lβ and choosing α t = g t •σ (g t ) L σ (g t ) 2 (1-β ) 2 1+β lead to f -f (z 1 ) ≤ -(1-β )(1-ε) 2L(1+β ) ∑ T t=1 (g t •σ (g t )) 2 σ (g t ) 2 + 1-β 2Lε(1+β ) ∑ T t=1 g t -∇ f (x t ) 2 .

which, by taking expectation from both sides and by the same argument in the proof for Theorem A.1, leads to

f -f (z 1 ) ≤ - (1 -β )(1 -ε) 2L 1 p (1 + β ) E T ∑ t=1 g t 2 1+γ + σ 2 (1 -β ) 2Lε(1 + β ) ,

which immediately gives the bound in the theorem by noting z 1 = x 1 .

Remark B.1 Clearly, Theorem 3.2 exactly reduces to Theorem B.1 when σ = 0 and ε → 0. Moreover, when β = 0, Theorem 3.2 reduces exactly to Theorem 3.1. This in a sense shows that our estimates are sharp.

B.3 ESTIMATES OF TRUE GRADIENTS VS ESTIMATES OF STOCHASTIC GRADIENTS:

A careful reader will notice that in Theorems 3.1 and 3.2, our estimates of convergence rates for PoweredSGD and PoweredSGDM, respectively, are in terms of the stochastic gradients g t . We now show that this is without loss of generality in view of Assumption 3.2.

When γ = 1, we have

E[ g t 2 1+γ ] = E[ g t 2 2 ] = E[ g t -∇ f (x t ) + ∇ f (x t ) 2 2 ] = E[ g t -∇ f (x t ) 2 2 ] + E[ ∇ f (x t ) 2 2 ],

where in the last equality, we used Assumption 3.2. This would imply

E[ ∇ f (x t ) 2 2 ] ≤ E[ g t 2 1+γ ] -E[ g t -∇ f (x t ) 2 2 ] ≤ E[ g t 2 1+γ

].

When γ ∈ [0, 1), by the equivalence of norm in R n , there exist positive constants C γ and D γ such that

C γ x 2 2 ≤ x 2 1+γ ≤ D γ x 2 2 ,

for all x ∈ R n . Hence

E[ g t 2 1+γ ] ≥ C γ E[ g t 2 2 ] = C γ E[ g t -∇ f (x t ) + ∇ f (x t ) 2 2 ] = C γ E[ g t -∇ f (x t ) 2 2 ] +C γ E[ ∇ f (x t ) 2 2 ] ≥ C γ E[ g t -∇ f (x t ) 2 2 ] + C γ D γ E[ ∇ f (x t ) 2 1+γ ],

which implies that

E[ ∇ f (x t ) 2 1+γ ] ≤ D γ C γ E[ g t 2 1+γ

].

In other words, the estimates are equivalent (modulo a constant factor). We prefer the versions in Theorems 3.1 and 3.2, because the bounds are more elegant.

C POWEREDSGD HELPS ALLEVIATE THE VANISHING GRADIENT PROBLEM:

The vanishing gradient problem is quite common when training deep neural networks using gradientbased methods and backpropagation. The gradients can become too small for updating the weight values. Eventually, this may stop the networks from further training. The Powerball function can help amplify the gradients especially when they approach zero. We visualized the amplification effects of Powerball function in Fig. 3 . Thus, the attributes of PoweredSGD can help alleviate the vanishing gradient problem to some extent. We investigated the actual performance of PoweredSGD and SGD when dealing with very deep networks.

We trained deep networks on the MNIST dataset using PoweredSGD with γ chosen from {0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0} and learning rate η chosen from {1.0, 0.1, 0.01, 0.001}. When γ = 1.0, the PoweredSGD becomes the vanilla SGD. The architecture of network depth which ranges from 12 to 15 with ReLU as the activation function is shown in Table 2 . The results are visualized using heatmaps in Fig. 4 . As we can observe in the visualisation, when the network depth is more than 13 layers, increasing or decreasing the learning rate of SGD could not solve the vanishing gradient problem. For PoweredSGD, the usage of the Powerball function enables it to amplify the gradients and thus allows to further train deep networks with proper γ settings. This confirms our hypothesis that PoweredSGD helps alleviate the vanishing gradient problem to some extent. We also note that, when the network increases to 15 layers, both SGD and PoweredSGD could not train the network further. We speculate that this is due to the ratio of amplified gradients to the original gradients becomes too large (see Fig. 3 ) and a much smaller learning rate is needed (this is also consistent with the change of theoretical learning rates suggested in the convergence proofs as the gradient size decreases). Since PoweredSGD is essentially a gradient modifier, it would also be interesting to see how to combine it with other techniques for dealing with the vanishing gradient problem. Since PoweredSGD also reduces the gradient when the gradient size is large, it may also help alleviate the exploding gradient problem. This gives another interesting direction for future research.

Hidden neurons:



:

Architectures in generalization and convergence experiments can be found at the following links: (1) ResNet-50 and DenseNet-121 on CIFAR-10: https://github.com/kuangliu/ pytorch-cifar; (2) ResNext-29 and WideResNet on CIFAR-100: https://github.com/ junyuseu/pytorch-cifar-models; (3) ResNet50 on ImageNet: https://github.com/ pytorch/examples/tree/master/imagenet

Figures and Tables:

Fig. 1 shows the learning curves of three experiments we have conducted to observe the performance of PoweredSGD and PoweredSGDM in comparison with other widely-used optimization methods. ResNet-50 on CIFAR-10: We trained a ResNet-50 model on CIFAR-10 and our results are shown in Fig. 1(a) and Fig. 1(b). We ran each experiment for a fixed budget of 160 epochs and reduced the learning rate by a factor of 10 after every 60 epochs Wilson et al. (2017).

Figure 2: (a) Train accuracy comparison between SGD (learning rate = 0.1) and PoweredSGD (learning rate = 0.1, γ = 0.4) on the 13-layer fully-connected neural network. The arrows annotate the accuracy values of both methods after 20 epochs. (b) The 1-norm of stochastic gradients of SGD and PoweredSGD in the first layer of the fully-connected neural network at every epoch. Gradient Vanishing: In deep learning, the phenomenon of gradient vanishing poses difficulties in training very deep neural networks by SGD.During the training process, the stochastic gradients in early layers can be extremely small due to the chain rule, and this can even completely stop the networks from being trained. Our proposed PoweredSGD method can relieve the phenomenon of gradient vanishing by effectively rescaling the stochastic gradient vectors.

The proposed PoweredSGD and PoweredSGDM methods exhibit better convergence rate than other adaptive methods such as Adam and RMSprop. (2) Our proposed methods achieve better generalization performance than adaptive methods although slightly worse than SGDM. (3) The Powerball function can help relieve the gradient vanishing phenomenon. Summaries of the models and datasets in our experiments.

Table content: <table><tr><td>Experiments</td><td>Datasets</td><td>Architecture</td></tr><tr><td/><td>CIFAR-10 Krizhevsky &amp; Hinton (2009)</td><td>ResNet-50 He et al. (2016) DenseNet-121 Huang et al. (2017)</td></tr><tr><td>Convergence and Generalization Experiments</td><td>CIFAR-100 Krizhevsky &amp; Hinton (2009)</td><td>ResNext-29 (16x64d) Xie et al. (2017) WideResNet (depth=26, k=10) Zagoruyko &amp; Komodakis (2016)</td></tr><tr><td/><td>ImageNet Russakovsky et al. (2015)</td><td>ResNet-50 He et al. (2016)</td></tr><tr><td colspan="2">Powerball Feature Experiments MNIST LeCun et al. (1998)</td><td>13-Layer Fully-Connected Neural Network</td></tr><tr><td colspan="2">4.1 HYPER-PARAMETER TUNING</td><td/></tr></table>

For PoweredSGD and PoweredSGDM, we observed the same tendency in convergence rate as AdaGrad, which outperformed Adam and RMSprop. For the test performance, adaptive methods and our proposed methods still outperform SGDM in the early stage. SGDM achieved a final best overall test accuracy of 94.75%. The PoweredSGD and PoweredSGDM achieved test accuracies of 94.17% and 94.13% respectively, which are slightly worse than SGDM. The best adaptive method, Adam, achieved a test accuracy of 93.38%.

Table content: <table/>

Under review as a conference paper at ICLR 2020 SGDM surpassed PoweredSGD and PoweredSGDM by epoch 60 when the learning rate decayed. SGDM had the best test accuracy of 76.78%, while PoweredSGD and PoweredSGDM achieved accuracies of 76.29% and 76.10%, respectively, with approximately 0.5% gap in test performance compared with SGDM. The best adaptive methods, still Adam, achieved test accuracy of 74.35% and had much larger gap of 2.5% in performance compared to SGDM.ResNet-50 on ImageNet: Finally, we conducted experiments on the ImageNet dataset using ResNet-50 model. The fixed budget here is 120 epochs and the learning rate reduces by a factor of 10 after every 30 epochs. The results are shown in Fig.1(i) and Fig.1(j). We observed that PoweredSGD and PoweredSGDM gave better convergence rates than adaptive methods while AdaGrad quickly plateaus due to too many parameter updates. For test set, we can notice that although SGDM achieved the best test accuracy of 76.27%, PoweredSGD and PoweredSGDM gave the results of 73.71% and 73.96%, which were better than those of adaptive methods.

Table content: <table><tr><td>(g) ResNeXt CIFAR100 (Train)</td><td>(h) ResNeXt CIFAR100 (Test)</td></tr><tr><td/><td>PowerSGDM: 73.96</td></tr><tr><td/><td>PowerSGD: 73.71</td></tr><tr><td/><td>Adam: 72.71</td></tr><tr><td/><td>AdaGrad: 68.98</td></tr><tr><td/><td>RMSprop: 72.44</td></tr><tr><td/><td>SGDM: 76.27</td></tr><tr><td>(i) ResNet-50 ImageNet (Train)</td><td>(j) ResNet-50 ImageNet (Test)</td></tr></table>

The architecture of MLP in vanishing gradient experiments.

Table content: <table><tr><td>Input layer</td><td>784 → 256</td></tr><tr><td colspan="2">Hidde layers (×10/11/12/13) 256 → 256</td></tr><tr><td>Output layer</td><td>256 → 10</td></tr></table>

Peer review (iclr2020):
This paper proposes, analyzes, and empirically evaluates PowerSGD (and a version with momentum), a simple adjustment to standard SGD algorithms that alleviates issues caused by poorly scaled gradients in SGD. The rates in the theoretical analysis are competitive with those for standard SGD, and the empirical results argue that PowerSGD algorithms are competitive with widely used adaptive methods such as Adam and RMSProp, suggesting that PowerSGD may be a useful addition to the armory of adaptive SGD algorithms. Overall I recommend acceptance of this paper, although I think there may be a couple of places where the authors overclaim a bit on the theoretical side. Specifically: • The convergence analysis assumes a batch size equal to T, the number of steps of PowerSGD. This implies that the amount of work (in FLOPs) done by the algorithm (at least the version being analyzed) is quadratic in T, which makes the convergence rates a bit misleading. If one reframes the convergence rate in terms of FLOPs U=T^2 instead of iterations, then the convergence rate drops from 1/T to 1/sqrt(U), which undermines the claim in remark 3.4 that this analysis is superior to that of Yan et al. (2018). • In Remark 3.4.3, the authors claim that another point of difference between their results and Yan et al.*s (2018) is that Yan et al. assume bounded gradients, an assumption that is not satisfied for e.g., mean squared error (MSE). But a very similar assumption is hidden in the bounded-gradient-variance assumption Assumption 3.2; for example, Assumption 3.2 is clearly not satisfied by the least-squares regression problem min_? (1/N)?_n (y_n – x_n • ?)^2 with the minibatch gradient estimator computed over randomly chosen minibatches B: hat g = (1/|B|) ?_{n in B} x_n (y_n – x_n • ?). As the norm of ? goes to infinity, so does the expected norm of the error of hat g. I*m not saying this is a particularly big deal, just that it*s not an improvement over Yan et al.*s result. That aside, this seems like good work that could have a significant impact on practice. A couple of other minor points: • It looks like neither the experiments nor Theorem 3.2 show any benefit to PowerSGDM over PowerSGD. It would be nice to see some discussion (or at least speculation) on why that is. • Not all of the arrows in Figure 1 are pointing to the right lines. • In the abstract, it might be good to clarify that the exponentiation is elementwise.