PowerSGD: Powered Stochastic Gradient Descent Methods for Accelerated Non-Convex Optimization
Authors: Jun Liu
Beitong Zhou
Weigao Sun
Ruijuan Chen
Claire J. Tomlin
Ye Yuan
Venue:  (2020)
Keywords: stochastic gradient descent
non-convex optimization
powerball function
acceleration

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

Under review as a conference paper at ICLR 2020
POWERED STOCHASTIC GRADIENT DESCENT METHODS FOR ACCELERATED NON-CONVEX OPTIMIZATION
POWEREDSGD:
Anonymous authors Paper under double-blind review
ABSTRACT
We propose 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 stochastic gradient to a certain power 7 E [0, 1] elementwise during iterations and introduces only one additional parameter, namely, the power exponent y (when y = 1, PoweredSGD reduces to SGD). We further pro- pose PoweredSGD with momentum, which term PoweredSGDM, and provide convergence rate analysis on both PoweredSGD and PoweredSGDM methods. Ex- periments conducted 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 generaliza- tion ability with SGD, and improved robustness to hyper-parameter selection and vanishing gradients. PoweredSGD essentially a gradient modifier via nonlinear transformation. As such, it is orthogonal and complementary to other techniques for accelerating gradient-based optimization.
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 195T) the first widely used method in this field. iteratively updates the parameters of model by moving them in the direction of the negative gradient of the objective evaluated on a mini- batih 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.
adaptive method has been demonstrated to be worse than the non-adaptive ones. Adaptive methods (like AdaGrad, R.MPProp 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.] (017). 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 variant of Adam called AMSGrad, hoping solve this problem. The authors provide theoretical guarantee of convergence but only illustrate its better performance the generalization ability of AMSGrad on test data is found to be similar that of Adam, and considerable performance gap still exists between AMSGrad and SGD (Keskar & Socher 2017 17) Chen al., 2018). Indeed, the optimizer 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).
Despite the popularity of Adam, its generalization performance
training data. However,
Related Works: SGD, as the first efficient stochastic optimizer for training deep networks, iteratively updates the parameters of model by moving them in the direction of the negative gradient of the

---

Under review as a conference paper at ICLR 2020
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 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 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 al. 201T) when the gradients are sparse. However, will also lead 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 R.SProp 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-basee optimization to continuous dynamic system theory has received much attention (Yuan et al.) 2016; Mazumdar & Ratlifi 2018). While the proposed optimizer excels at improving initial training, it is completely complementary
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 modify the gradient terms via nonlinear function called the Powerball function by the authors of Yuan et al. 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 BBrnsttii 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 y is set to 0. We also point out that despite the name resemblance, the power PowerSign optimizer proposed in Bello et al. 2017) is conditional scaling of the gradient, whereas the proposed PoweredSGI optimizer applies a component-wist trasformation to the gradient.
Contributions: Inspired by the Powerball method in Yuan al. (0166), this paper uses Powerball- based 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 7) 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 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 y = 1) provide the currently best convergence bounds for SGD and SGDM 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.
The remainder of the paper is organized as below. Section 2 proposes the PoweredSGD and PoweredSGDM algorithms. Section B providess 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
Outline:
2

---

Under review as a conference paper at ICLR 2020
Given vector IR", denote its i-th coordinate by a; we use ||]]| to denote its 2-norm (Euclidean norm) and ||l|p to denote its p-norm for 2 1. Given two vectors a, E IR, we use a- b denote their inner product. We denote by [[|] the expectation with respect the underlying probability space.
Notation:
ALGORIHTM
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 Pow an extension of PoweredSGID to include a momentum term. We shall prove in Section 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 DNN with free parameters can be formulated as unconstrained optimization problem
min
f(x).
(1)
xE3*
where f()) :R" - R is 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 X2 E IR" at step in the opposite direction of a stochastic gradient g(x, Š1) (where & denotes random variable), which is calculated on r-th mini-bater of train dataset. The update rule of SGD for solving problem is
X++1 = - 5r),
starting from an arbitrary initial point X1, where a is known as the learning rate at step In the rest of the article, let & gxx, 5 for the sake of notation. We then introduce nonlinear transformation Gy(z) = sign(z)) named as the Powerball function where sign(z) returns the sign of z, or 0 if For any vector parameter y IR is introduced to adjust the mechanism and intensity of the Powerball function.
(z) the Powerball function Gy(z) applied to all elements of z.
Applying the Powerball function the stochastic gradient term in the update rule 2 gives the proposed PoweredSGD algorithm:
Xy+1 = - (y))))))
(3)
where y E [0, 1] is an additional parameter. Clearly, when y= 1, we obtain the vanilla SGD (2. The detailed pseudo-code of the proposed PoweredSGD is presented in Algorithm 1.
A Algorihhm I PowerSGD
Algorithm 2 PowerSGDM
I: Inpul: xi, { // 7 E [0,1]
Inpul: X1, Vi, {a 1/ B (0, 1), re (0.10
2: for to do
2: for I = 1 to do
3: 8: -=
3: 144 ßv, (07(8:))
1+11 Oy(z))
X;+1 = 1/+1
5: end for
5: end for
2.2 POWEREDSGDM
The momentum trick inspired by physical processes Polyak 1964): Nesterov (9833 has been
successfully combined with SGD give SGDM, which almost always gives hetter convergence on train deep networks. We hereby follow this line to propose the PoweredSGD with Momentum (PoweredSGDM)) whose update rule is
11+1 Bv, (
x = x; + 1/+1-
Clearly, when B = O, PowerSDGM (4 reduces to PoweredSGD PoweredSGDM is detailed in Algorithm
Pseudo-code the proposed
3

---

Under review as a conference paper at ICLR 2020
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 I. 0 such that [ V s -||x- for all x, IR".
We then assume that stochastic first-order black-box oracle is accessible as a noisy estimate of the gradient of f at any point x E RR,, 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:
(xg =f(xxx
5 VreR"
(5)
where & 2 0 is constant.
We will be working with a mini-batch size in the proposed PoweredSGD and PoweredSGDM. Let be the mini-bated size at the r-th iteration and the corresponding mini-bate batch stochastic gradient be given by the average of n, calls to the above oracle. Then by Assumption 3.2 we can show that El[lg (((x))) < 6² /n, for all i 2 1. In other words, we can reduce variance by choosing 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 = (independent of particular step f) can lead to
1|| T
(((())
-
Φ²
E
11
llitt
I
1-
2 8)
where E E (0,1),
p=
1+ T-y for any y 1) and for 1
The proof of Theorem 3.1 can found in the Supplementary Material
A.2
The proposed PoweredSGD and PoweredSGDM have the potential to outperform popular stochastic optimizers by allowing the additional parameter y that can be tuned for different training cases, and they always reduce other optimizers when setting y=
Remark 3.1
We leave E (0,1) to be free parameter the bound provide trade-offs between bounds given by the curvature L and stochasticity &. If & = O, we can choose E -+ 0 and recover the convergence bound for PoweredGD (see Supplementary Material A.II
Remark 3.2
The above theorem provides a sharp estimate of the convergence of PoweredSGD the following sense. When y 1, the convergence bound reduces the best known convergence rate for SGD. Note that, because of the choice of batch size, it requires 2 gradient evaluations in T iterations. So the convergence rate is effectively O(1 /TT/ This the best known rate of convergence for SGD attain
Remark 3.3
Ge et al. (2015). When & (i.e., exact gradients are used and B, 1), PoweredSGD convergence in the order OL1/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 Supple- mentary Material B.2 due the space limit.
4

---

Under review as a conference paper at ICLR 2020
Theorem 3.2 Suppose that Assumptions 3.7 and 3.2 hold. Let T be the number of iterations. For any E (0, PoweredSGDM (4) with an adaptive learning rate and mini-batch size B, = T (independent a particular step 1) can lead to
2|1
(
1
6²
E
Σ
& Ility
I T
2E(1 - E) 1-B +
T
1-
where E (0,1), p= H for any EE [0,1) and p= for y=
Remark 3.4 Convergence analysis of stochastic momentum methods for non-convex optinization 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 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, and offers very concise upper bounds in terms the constants. The upper bound continuously interpolates the convergence rate for varying in [0. 1] and B varying in [0, 1). The key technical result that made the results of Theorems 3.1 and 3.2 possible Lemma B.1 in the Supplementary Material, which provide tight estimate of accumulated momentum terms. We also note that the convergence rates for Y E (0, I) 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) is assumed for the convergence results to hold. This is consistent with the convergence analysis in Bernstein el al. (2078) for the special case y 0. We assume this because it enables us to put analysis of PoweredGD and PoweredSGD in unified framework so that we can obtain tighter bounds. In the stochastic setting, similar Remark 3.3, we note that our proof requires 22 gradient calls in T iterations and hence the effective convergence rate is O(1/VT), 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 mainly composed of two parts: (I) the convergence and generalization experiments and (2) the Powerball feature experiments. The setup for each experiment is detailed Table | In the first part, we present empirical study of different deep neural network architectures to how the proposed methods behave in terms 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 times from randomly initializations and the average results are shown. The settings of hyper-parameters of 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) The proposed PoweredSGI and PoweredSGDM methods exhibit better convergence than other adaptive methods such 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.
Architectures in generalization and convergence experiments can found at the following links: (I) ResNet-50 and DenseNet-12 121 on CIFAR-10:
com/ kuangliu/
pytorch-cifar (2) ResNext-29 29 and WideResNet on CIFAR- 100: https: https::/github com./
junyuseu/pyroorc--ciaa-aaaa lo (3) ResNet50 on ImageNet: https: thu.. com/
5

---

Under review as a conference paper at ICLR 2020
Experiments
Datasets
Architecture
ReaNet-50 Ho 2016
CIFAR- Krizhevsky Hinton
2009
DenseNet- rarprong
2017
Convergence and Generalization
ResNext-29 (16x64d) Xie et al.
2017
Experiments
CIFAR-104 Krizhevsky Hinton
2009
WidcResNet (deptl=26, k=10] Zagmuyko Komodakis
2016
ImageNei Russakvvky et 2015
ResNet-50[He al. 2016]
Powerball Feature Experiments
MNIST 1 LeCun
1998
13-Layer Fully Connected Neural Network
Table 1: Summaries of the models and datasets in experiments.
4.1
TUNING
Since the initial learning rate has a large impact on the performances of optimizers, we implement a logarithmically-spacee grid search strategy around the default learning rate for each optimization method, and leave the other Hyper-parametern to their default settings.
SGDM: The default learning rate for SGDM is 0.01. We tune the learning rate on logarithmic scale from (1,0.1, 0.01, 1, 0.0001 The momentum value in all experiments is set to default value 0.9.
PoweredSGD, PoweredSGDMM The learning rates for PoweredSGD and PoweredSGDM are chosen from the same range 0,1.0100 GDM also 0.9. Note that y 1 in Powerball function corresponds to the SGD or SGDM. Based on extensive experiments, we empirically tnne y from (0.5,0.6,0.7,008,,00
0.0001) as SGDM. The momentum value for PoweredS-
AdaGrad: The learning rates for AdaGrad are (1e-1,5e-2, 1e--2,1ee-2,550 1e-2, 1e-3) and we choose for the initial accumulator value.
RMSprop, Adam: Both have the default learning rate 1e-3 and their learning rates are searched from (le-2,5e-3, 1e-3,5e-4, le-4). The parameters ß1. B2 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, would try the learning rate between the best learning rate and its closest neighbor. For example, if we tried learning rates (le-2, 3e-3, 1e-3,5e-4, le-4) and le-4 was best performing, would try the learning rate 2e-4 to if performance improved. We iteratively update the learning rate until performance could not be improved any more. For all experiments, we used mini-batch size of 128.
4.2 EXPERIMENTS: CONVERGENCE AND GENERALIZATION
Fig. I shows the learning curves of three experiments we have conducted observe the performance of PoweredSGD and PoweredSGDM in comparison with other widely-used optimization methods.
ResNet-50 on CIFAR-10: We trained ResNet-50 model on CIFAR-10 and our results are shown in Fig. a and Fig. [b). We ran each experiment for fixed budget of 160 epochs and reduced the learning rate by a factor of 10 after every 60 epochs Wilson et al. (017).
As the figure shows, the adaptive methods converged fast and appeared to be performing better than the non-adaptive method SGDM as expected. 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 final best overall test accuracy of 94.75%. The PoweredSGD and PoweredSGDM achieved test accuracies of 17% and 94. 13% respectively, which are slightly worse than SGDM. The best adaptive method, Adam, achieved a test accuracy of 93.38%.
WideResNet on CIFAR-100, Next, we conducted experiments on the CIFAR-100 100 dataset using WideResNet model. The fixed budget here is 120 epochs and the learning rate reduces by a factor of 10 after every 60 epochs. The results are shown in Fig. [e) and Fig. ff).
The performance of the PoweredSGD and PoweredSGDM are still promising in both the train set and test set. PoweredSGD. PoweredSGDM and AdaGrad had the fastest initial progress. In the test set, PoweredSGID and PoweredSGDM had much better test accuracy than all other adaptive methods.

---

Under review as a conference paper at ICLR 2020
Adam
RMSSprp
AdaGrad
SGDM
PowerSGD
PowerSGDM
100
95
PowerSGDM: 94.13-
PowerSGD: 84.17
Train Accuracy
96
Test Aocuracy
90
AdeGrad: 91
Adam: 53.30
85
90
RMSpprpp: 92.99
85
75
SGDM: 94.75
80
0
50
100
150
50
100
150
Epoch
Epoch
(a) ResNet-50 CIFAR10 (Train)
(b) ResNet-50 CIFAR10 (Test)
100
95
PowerSGDM: 94
PowerSGD: 94,
Train Acciracy %
95
Test Accurady
90
Adam 93.5
AdaGradi 92.16
RMSprop: 93.43
85
SGDM: 95 05.07
75
80
70
50
100
150
50
100
150
Epoch
Epoch
(c) DenseNet-121 CIFAR10 (Train)
(d) DenseNet- 121 CIFAR10 (Test)
100
80
PowerSGDM 78.10
95
Test Accuracy %
PowerSGD: 76.29
Train Accuracy
70
Adam: 74.35
90
AdaGrad: 74.05
60
RMSprap: 73.71
80
76.78
75
50
20
40
80
80
100
120
40
60
80
100
120
Epoch
Epoch
(e) WideResNet CIFAR100 (Train)
In WideResNet CIFAR100 (Test)
100
PowerSGOM: 77.73
PowerBGD: 77.74
Train Accuracy %
Adam: 77.05
Test Aecuracy
70
AdaGred:
90
55
SGDM: 79 12
AMSprap: 78.84
40
60
100
120
40
60
100
120
Epoch
Epoch
(g) ResNeXt CIFAR100 (Train)
(h) ResNeXt CIFAR100 (Test)
80
PowerSGDM: 73.96
Train Accuracy %
PowerSGD: 73.71
70
Test TestAcoas Accuracy
70
Adam: 72.71
60
AdaGrad: 68.98
50
RMSprop: 72.44
S3DM: 78.27
40
50
0
20
40
60
80
100
120
0
20
40
60
80
100
120
Epoch
Epoch
ResNet-50 ImageNet (Train)
( ResNet-50 ImageNet (Test)
Figure 1: Train and test accuracy for different models and datasets. The annotations indicate the best overall test accuracy for each optimization method. The y values in five experiments are 0.8,0.8, 0.8, 0.8, 0.7,0.8 0.8 for PoweredSGD and 0.8, 0.8, 0.8, 0.8, 0.7 for PoweredSGDM, respectively.
7

---

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 hest adaptive methods, still Adam, achieved test accuracy of 74.35% and had much larger gap of 2.5% in performance compared to SGDM.
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. ii) and Fig. T 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. 76.27%, PoweredSGID and PoweredSGIMM gave the results of 73.71% and 73.96%, which were better than those of adaptive methods.
ResNet-50 on ImageNet:
Additional experiments (DenseNet-121 on CIFAR-10 and ResNeXt on CIFAR100) are shown in Fig. (k)) We observed similar results as in the other experiments.
4.3 EXPERIMENTS: FEATURES OF POWEREDSGD
SGD
PowerBeD
Grddette mnee
70
1011
Epoch
Esoch
Train and PowerBOD
(8) The 1-Norm of Gradients SGD and PowerSGD in the Flast Layer
Figure 2: (a) Train accuracy comparison between SGD (learning rate 0.1) and PoweredSGD (learning rate = 0.1, y= 0.4) on the 13-layer fully- uull--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.
To validate this, conduct experiments on the MNIST dataset by using 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 98.91% after few epochs. We further compare the l-norm of stochastic gradient vector in the first layer for both SGD and PoweredSGD. It 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
CONCLUSION
In this paper, a Powerball function is introduced basic technique to improve SGD and SGDM for deep neural network training. Their convergence rates have been proved in the non-convex opti- mization 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 empiri- cally 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.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Irwan Bello, Barret Zoph, Vijay Vasudevan, and Quoc V Le. Neural optimizer search with reinforce- ment learning, In Proceedings the 34th International Conference on Machine Learning-Von Vollue 70, pp. 459-468. JMLR. org, 2017.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Arizzadenesheli, and Anima Anandkumar, signSGD: Compressed optimisation for non-convex problems. arXiv preprint arXiv:1802.04444. 2018.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of class of Adam-type algorithms for non-convex optimization. arXiv preprint arXiv: 180xiv:8000.00 02940, 2 2018.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and
stochastic optimization. Journal of Machine Learning Research, 12(ul):2121-2159 2011.
Cong Fang, Zhouchen Lin, and Tong Zhang. Sharp analysis for nonconvex SGD escaping from saddle points. arXiv preprint arKiv: 0ttiv:9902.000 /902.00277 2019.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points-online stochastic gradient for tensor decomposition. In Conference on Learning Theory, pp. 797-842, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700-4708, 2017.
Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I Jordan. Stochastic gradient descent escapes saddle points efficiently. arXiv preprint arXiv: wxXiv:190..0481/ 2019.
Nitish Shirish Keskar and Richard Socher. Improving generalization performance by switching from Adam to SGD. arXiv preprint arXiv: 2017.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. Proceedings of the 3rd International Conference on Learning Representations, 2015.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 (6(17):22782222, 1998.
Iya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint arXiv:1608.03000 2016.
Liangchen Luo, Wenhao Huang, Zeng, Zaiqing Nie, and Xu Sun. Learning personalized end-to-end goal-oriented dialog. arXiv preprint arXiv: 181 1.4604, 2018
Eric Mazumdar and Lillian J. Ratliff. On the convergence of gradient-based learning in continuous games. arXiv preprint arXiv: 100iv::80440055 804405464, 2018
Yurii E Nesterov. A method for solving the convex programming problem with convergence rate o(1/k)). In Dokl. akad. nauk Sssr, volume 269, pp. 543-547, 1983.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. USSR
Computational Mathematics and Mathematical Physics, 4(5):1-17, 1964.
Ning Qian, On the momentum term in gradient descent learning algorithms. Neural networks, 12(1): 145-151, 1999.
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. In International Conference on Learning Representations, 2018.
Herbert Robbins and Sutton Monro. stochastic approximation method. The Annals of Mathematical Statistics, 22(3):400-44) 407, 1951.

---

Under review as a conference paper at ICLR 2020
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115(3):211-22)) 2015.
Leslie N. Smith. No more pesky learning rate guessing games. CoRR, abs/1506.01186, 2015, URL http:://axia org/ /a////b////// abs/1506.00 011866
Leslie N Smith and Nicholay Topin. Super-convergence: Very fast training of neural networks using large learning rates. In Artificial Intelligence and Machine Learning for Multi-Domain Operations Applications, volume 11 11006, pp. 1100612. International Society for Optics and Photonics, 2019.
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-RMSProp: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26-31, 2012.
Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Advances in Neural Information Processing Systems, pp. 4148 4158, 2017.
Yuxin Wu and Kaiming He. Group normalization. Proceedings of the European Conference on Computer Vision (ECCV), pp. 3-19, 2018.
Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual transformations for deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1492-1500, 2017.
Yan Yan, Tianbao Yang, Zhe Li, Qihang Lin, and Yi Yang. unified analysis of stochastic momentum methods for deep learning. arXiv preprint arXiv: 10396, 2018.
Ye Yuan, Mu Li, Jun Liu, and Claire J Tomlin. On the Powerball method for optimization. arXiv preprint urXiv:1605 0004011421, 2016.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint 165.016605.07146. 2016.
10

---

Under review as a conference paper at ICLR 2020
SUPPLEMENTARY MATERIAL
A CONVERGENCE ANALYSIS OF POWEREDSGD AND POWEREDSGDM
A.1 CONVERGENCE OF POWEREDGD
The authors of Yuan et al. 6 proposed the so-called Powerball accelerated gradient descent algorithm, which was updated as follows,
Xp+1 = (V(()x
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.7 holds. The PoweredGD scheme 6 can lead to
T
2Li|ZIpp
Σ
T (f(x))-))
T
where T is the number of iterations and 1+Y for any y E (0, and p = 0o for y y= T-y for
Proof: Denote by x" the minimizer and f" fxx"). Then, by the L-Lipschitz continuity of V and
(6.
f(++1) S [xx) ( - xx)
|1+ - x
L + - (vV((()))
(1)x))
(( L((((s(x)) > 0 (this holds if xx). Then
Let a
f(x+1) fx()
(V((a)) 21
(8)
By Hölder's inequality, for y (0, 1) and with p p= T-y and q 2 we have
1+%
1+%
[o(V{(()))1
Σ (V))(x))
14y ((
s |||| Σ (V))(())
It follows that
f(x+1) < f(x) (V)(x)) o (v
o V (x:
E (V
$ f(x)
21 1
(E" (V))
= f(x) 21 1|
1
(7))
1
f(x) 21. 1
which, by a telescoping sum, gives
1 T Σ (
|| T
((T < 2L||1|1 (((x))-(*)
T
where 1 is vector with entries all given by 1. It is easy to see that the estimate is also valid for y= with p and for y 0. The proof is complete.
11

---

Under review as a conference paper at ICLR 2020
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 (x(x) be the gradient of f at E R Suppose that we use the average of calls to the stochastic gradient oracle, denoted by g(x, 5) (i = 1, m), to estimate fx()). By Assumption 3.2 we have
g(x, Si)
E
fx)
E
(x( v[(0]]
1
8²
E
| 5.) [x())
(mo²
where in the second equality we used the fact that gxx, {i) (i (i= 1,.., m) are drawn independently and all give unbiased estimate of (x) (provided by Assumption 3.2
Now we are ready to present the proof of Theorem
PROOF OF THEOREM 3.1
Proof: By the L-Lipschitz continuity of ff and
(
(x x,) + L
f(x+1) $
|
-x 12
2
1.
f(x) - vVf(x) (g:) (
L
f(x)) ugg a(g) + マ
o(8))
Let a a(o))) L) O. Then
(())())) f(x+1) S f(xx 2 | a (g. vf(x)) (g)))
Fix any iteration number T>> 1 and let E (0, to be chosen. We can estimate
8r (gr)
a a vf(x)) (g)))
(g: vf(x)) (g:))
()))
|g. (8.)
lgr (f()))llo()))l
())
& (gr))
l|g. vx(x)]l
(g))
1
(gr (g.))
2/.
where the last inequality followed from the elementary inequality 2ab εa² + jb² for any positive real number and real numbers a, b. Substituting this into (9) gives
(x++1 {x(x)
le (Rr |||
+ + | (x;))1
(10)
21.
By the same argument in the proof for Theorem A.I
we can derive
(x*+1 {((z) - أ ||
II
2h llg, 222
Taking conditional expectation from both sizes gives
E[((++1) [x))) <
-- B I1 y + 1
ILE o?
02 -_ Ellle: [4 1 2LeT
S
12

---

Under review as a conference paper at ICLR 2020
where of is the variance of the r-th stochastic gradient approximation computed using the chosen mini-batch size B, = T. which therefore satisfies of Σ 6² performing telescoping sum give
r. Taking expectation from both sides and
L 1=1
& litt7
201 (
|| T8(1-2) 0².
T
The proof is complete.
B CONVERGENCE ANALYSIS OF POWEREDSGDM
B. CONVERGENCE OF POWEREDGDM
We first analyze the deterministic version of PoweredSGDM (denoted by PoweredGDM), The update rule for PoweredGDM is
V++1 = Bv, - (x;))xx)))
(11)
x,+1 Vr+1+
where B E 1) is momentum constant and vo 0. Clearly, when B = 0, the scheme also reduces PoweredGD.
Theorem B.1 Suppose that Assumption 3.1 holds. For any B E 1), the PoweredGIDM scheme 11 with an adaptive learning rate can lead to
T
2L 1| 1+B
IV
(f(x)) - T 1-B
T
1+Y where T is the number of iterations and p = T-y for any y E [0, 1) and p = 0o y y=
Proof: Let =x, + 1 v. It can be verified that the PoweredGDM scheme satisfies
04
2+1 24 1 [(V[(x)))
(12)
1/+1 Bv, (V((x)))
By the L-Lipschitz continuity of f and 12
f(z++1) < f(z) + +f Vf(z))
(3r41 - 2) + 2 |1,5++1 2112
f(z) a Vf(z) [VV
L of
2 (1 - B) ([((())))
0
f(z)
fx(x) o(V[(x)))
- -V
L af
+ 2 (1 - 2)²
|0 [[(((x))))
(13)
We can estimate
T-B B (Vf()) ((V(()) S 2(1
a
+/ (14)
8 VVV
where & > 0 is to be chosen. By the L-Lipschitz continuity of V
B
B²
[Vf()) - vf(x)) < = x1| 12
v, 2
1
(1- B) 1/2
(15)
Lemma B.1 For T we have
r Σ
1
r
11 <
Σ
of
([(v(()))1
(1 B)
13

---

Under review as a conference paper at ICLR 2020
Proof: It is easy to show by induction that, for r 2 I.
Σ B -
oo(((x)))
V1
Indeed, we have = 0 and V/2 -
Suppose that the above holds for 2 1. Then
V/+1 = Bv, -a-oo(()==((=
1-----la - (aoo(ia())) -BaV)(()) = -BaVV/))
Σ Bir tao
Hence
Σ
| = Σ | Σ B (v((())))
H
Σ
B
[o((((()))
T
$ Σ
B
Σ Bi-1-1 [[](((
B
(x)x)
Σ
B
B
1=+1
Σ af
[o(Vf())))
B)
By Lemma B.1 inequalities
14 15 and telescoping sum on
13 we get
f f(af()) S
04 Vf(x) (V(()))((Vf((())
β
e2
Σ af d((l(((((())))
+
2(1 (01-BBs
2E(1 - B)
2(1 B)
(1-8² LB
is clear that
would minimize the bound on the right-hand side (among different choices
of E 0) and give
LB (1 (1-B)² B)3 2(1 - B)2
T Σ a (((lo((((x)1
f(af(=)) s - 1 1- Σ a (VV((x) +
+
For any B E [0, 1), we can choose a
oV (1-B)2
(( T+p so that the bound reduces to
1-B (VS(x, (V(()))(VV((()))) (VV((x)))
f-)
21(1+B)
[V(V(x)))
which immediately gives the bound in the theorem by noting 2 =
B.2 CONVERGENCE POWEREDSGDM (PROOF OF THEOREM 3.2
Proof: The proof is built on that for Theorem B.1 With 2 = + T-B v. it can be verified that the
PoweredSGDM scheme satisfies
o(g))
2+11
(16)
Pr+1 = Bv, a (
14

---

Under review as a conference paper at ICLR 2020
By the L-Lipschitz continuity of f and (4)
f(z+1) S f(z)) + Vf(z)) [2++] - 2) + 1 zil2
f(z)
vf(z) ( +
2 (1 B) [|
1- B
a
f(z)
81 (
1 1- - -f(x)
-
1 -B
+ 1- B
a
(gr vf(x)) (g))
of
B)² (
(17)
Similar to the proof of Theorem B.1 we can estimate
B (Vf(a))V((x)))-00) o(g))
ا -
(18)
where & > is to be chosen. By the L-Lipschitz continuity of Vf.
B B
B²
Vf(²) V <12 - x 2 1.21
v1 12
1.2
(1 - B)2 11,.
(19)
Similar to Lemma B.1
we obtain
Σ ||
Σ of
(z))))
(20)
(1 - B)
/=1
We can also bound
& B
(g+ V((x)) (g:) S 1 B
||:: - (/(x +
1+B
of (1)
(21)
LE(1 B)
(1 (1-B) B)3
where E 8>0 O. By inequalities (88 and telescoping sum on 17 we get
fr f--f(ee f((1) s s-1zp E agg (g)) +
Lg2222
1 + LE(1+0)
Σ of (g
[1-0}3
(1-
(1-B)²
(1-B}>
1-B
Σ 11g, - vV(x)
Setting El and choosing 0 ((()
(1-B)2 LB
(1-8)²
lead to
[
1+.
f f f())
s -
(L-BXLL- Σ
(x-
+ 2L((I E' 1lsr 2.
20(1+B)
|
which, by taking expectation from both sides and by the argument in the proof for Theorem A.I. leads to
- f(a))) (1-B) 8) (1 (B)
02 2Le(1 + B)
E
Σ 8
-
+
which immediately gives the bound in the theorem by noting X1.
Remark B.1 Clearly, Theorem 3.2 exactly reduces to Theorem B. when ô 0 and - 0. Moreover, when B 0, Theorem 3.2 reduces exactly Theorem 3.1 This in a sense shows that estimates are sharp.
B.3 ESTIMATES OF TRUE GRADIENTS VS ESTIMATES OF STOCHASTIC GRADIENTS
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 gi. We now show that this is without loss of generality in view of Assumption 3.2
When 1, we have
E |g y Ellgg
E Ella
Vf = Ellle Vf(x +
15

---

Under review as a conference paper at ICLR 2020
where in the last equality, we used Assumption 3.2 This would imply
E| | )I)
Ellls Vf =
When y E [0, 1), by the equivalence of norm in R", there exist positive constants Cy and Dy such that
Cy||ж||2 = | Dyl1x|12
for x E R". Hence
Ellls Ii CyEllls v/
- C,Blll& VV(()))) +
+
2 - -VS(x))) Dy
which implies that
Dr Br l C
E [
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 gradient- based 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 y chosen from 0.3, 0.4,0.5, 0.7,0. 0.8, 0.9, 1.0) and learning rate n chosen from {1.0,0.1 0, 0,0.0.0..000000 When y= 1.0, the PoweredSGD becomes the vanilla SGD. The architecture network depth which ranges from 12 to 15 with ReLU as the activation function is shown in Table 2 visualized using heatmaps in Fig.
The results
Hidden neurons
Input layer
784 > 256
Hidde layers (x 10/11/12/13)
256 > 256
Output layer
256 10
Table 2: The architecture of MLP in vanishing gradient experiments.
As we can observe in the visualisation, when the network depth is more than 13 layers, increasing or decreasing the learning 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 y 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 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, may also help alleviate the exploding gradient problem. This gives another interesting direction for future research.
16

---

Under review as a conference paper at ICLR 2020
10
10
0.8
0.6
109
0.4
0.2
9.99)/9 (9)
10
10
8
10
10
10
10
Figure 3: The amplification effects of Powerball function with different and different gradient sizes. The amplification ratio is larger when the gradient size closer O.
12-laerrMPP
13-Layer
p-0.
7=0.9
Y=0.7
7=0
7-0.5
0.4
Y#0.4
V-0.3
0.2
ym8.
P-0
Y-0
n- 1.0
n-0.1
0.00
6-0.001
6=1.0
0-
--01
n- 0.001
Layer
15
1.0
Y=1.
Y- 0.8
7-0.8
Y 0.6
7-0.6
0.5
7=5.5
7=0.4
0.3
V+0.3
y-82
y= 0.1
V=011
Figure 4: We trained deep networks using PoweredSGD with different hyper-parameter settings. dark block indicates that PoweredSGD with specific setting succeeded in training the network within 25 epochs, while light block indicates that PoweredSGD (or SGD) failed to train. It is clear that by tuning the hyper-parameter y, PoweredSGI can train networks deeper than that by SGD.
17

---

Under review as a conference paper at ICLR 2020
D IMPROVED ROBUSTNESS TO HYPER-PARAMETE SELECTION
The Powerball function is nonlinear function with tunable Hyper-parameter applied to gradients, which is introduced to accelerate optimization. To test robustness different y, we trained ResNet- 50 and DenseNet- 121 on the CIFAR-10 dataset with PoweredSGD and SGDM. The parameter y chosen from {0, 00..1,0.23 (1.0,0.1, 0.1,1 0.01, 0.000.00000,
0.4,000,00... 0.5,0 5,,.6,0.7,000 0.7, 0.9, 1.0] and the learning rate is chosen from 0.001), J. The PoweredSGD becomes the vanilla SGD when y= The maximum test
accuracy is recorded and the results are visualized in Fig. 5
Although the y that gets the best test accuracy depends the choice of learning rates, can observe that can be selected within wide range from 0.5 to 1.0 without much loss in test accuracy. Moreover, the Powerball function with hyper-parameter y could help regularize the performance while the learning rate decreases. For example, when 7 = 0.001 and y 0.6, PoweredSGD get the best test accuracy of 90.06% compared with 79.87% accuracy of SGD.
We also compare the convergence performance of different choice in Fig. The training loss is recorded when training ResNet-50 on CIFAR-10 dataset. As the initial learning rate decreases, the range from which the typer-paramesl
y can be selected to accelerate training becomes wider. As practical guide, y = 0.8 seems proper setting in most cases. again observed that the choice of y in the range of 0.4-0.8 seems to provide improved robustness to the change of learning rates.
CIFAR-10 ResNet:50
DenseNet-121
10.00
83.93
89.35
91.95
Y=
10.00
87.52
93.22
10,00
88.41
91.85
93.38
10.00
91.29
91.86
93.81
83.86
91.54
92.52
93.28
87.12
92.01
93.37
93.84
-75
75
0.3
89.72
92.53
92.94
93.46
91.58
93.24
94.20
93.65
0-4.4
92.46
93.29
93.86
92.59
0.44
93.36
93.77
94.13
92.77
G.5
93.58
93.73
93.76
91.40
0.5.5
94.04
94.13
93.99
91.64
0.6
94.12
94.07
93.51
90.06
0-6
94.35
94.37
93.87
90.16
y
Vm
94.12
92.69
85.63
95.06
86.24
94.58
94.11
91.97
83.46
-30
94.91
94.80
92.44
84.13
-30
y=3.0
94.89
94.16
90.67
79.87
95.27
94.36
91.46
80.14
SGOM
26.57
94,96
94.27
90.77
SGOM
68.
65.
95.13
94.73
91.42
9.0.1
9000.0
Figure 5: Effects of different y on accuracy. We show the best Top-1 accuracy on CIFAR-10 dataset of ResNet-50 and DenseNet121 trained with PoweredSGD, Although the best choice of depends on learning rates, the selections can be quite robust considering the test accuracy.
E COMBINING POWEREDSGD WITH LEARNING RATE SCHEDULES
the main part of the paper, we demonstrated through multiple experiments that PoweredSGD can achieve faster initial training. In this section we demonstrate that PoweredSGD as a gradient modifier orthogonal and complementary to other techniques for improved learning.
The learning rate is the most important paree-prramtter to tune for deep neural networks. Motivated by recent advancement in designing learning rate schedules such as CLR policies (Smith) 2015) and SGDR (Loshchilov & Hutter 2016), we conducted some preliminary experiments combining learning rate schedules with PoweredSGD to improve its performance. The results are shown in Fig.
The selected learning rate schedule warm restarts introduced in (Loshchilov & Hutter 2016)..
which reset the learning rate the initial value after cycle of decaying the learning rate with
18

---

Under review as a conference paper at ICLR 2020
(a) Train Loss of PowerSGD (y 0.1)
(b) Train Loss of PowerSGD (q 0.01)
105
10
10
109
Itain Loos
10
0.66
101
0.6
1.0
10"1
Epoch
Epoch
Figure 6: Effects of different y on convergence. We show the best train loss CIFAR-10 dataset of ResNet-50 trained with PoweredSGD. While the which achieves the best convergence performance closely related the choice of learning rates, y chosen in the range of 0.4-0.6 seem provide better robustness to change of learning rates.
cosine annealing for each batch. In Fig. 7 SGD with momentum combined with warm restarts policy is named as SGDR. Similarly, PoweredSGDR indicates PoweredSGD combined with warm restarts policy. The hyper-parameter setting is To = 10 and m'ul = 2 for warm restarts. We test their performance CIFAR-10 -10 dataset with ResNet-50.
The results showed that the learning rate policy can improve both the convergence and test accuracy of PoweredSGD. Indeed, PoweredSGDDR achieved the lowest training error compared with SGDM and SGDR. The test accuracy for PoweredSGDR was also improved from the 94. 12% accuracy of PoweredSGID to 94.64%. The results demonstrate that the nonlinear transformation of gradients given by the Powerball function is orthogonal and complementary to existing methods. As such, its combination with other techniques could potentially further improve the performance.
(o) Train Loss Comparisons
10
10
SGDM
PowerSGD
SGDR
PowerSGDR
10"1
80
120
160
Epoch
(b) Test Accuracy Comparisons
98
PowerSGD! 94,12
Ttoll Accucec
85
SGDM
75
PowerBGDR: 94.64
PowerSGD
SGDA
70.
SGDM: 94.96
SCDRL 94.95
PowerSGDR
Epoch
Figure 7: Train loss and test accuracy for SGDR and PoweredSGDR, Learning rate schedules also help accelerate training of PoweredSGID and improve the test performance.
19

---

Under review as a conference paper at ICLR 2020
F COMPARISONS WITH VANILLA SGD AND SGDM
In this section, we compare PoweredSGD with the vanilla SGD and SGDM to show that how a simple Powerball functiin can boost the performance. The first four experiments in Section 4.2 are conducted for comparisons. The results are shown in Figure 8 below, in which the hyper-parameters that lead the best test accuracy are chosen and can found in Table 3
SGD
36DM
PowerBBD
100
PowerBOD 94.17
Trai Accuracy %
Test Accurscy
88
180
0
50
100
150
50
100
150
Epoch
Epoch
ResNet-50 CIFAR1D (Train)
ResNet-50 CIFAR10 (Test)
100
Train Accurasy
95
Test Accurasy
880 95
90
80
SODM:
85
76
70
100
150
100
150
Epoch
Epoch
(c) DenseNet-121 CIFAR10 (Train)
(d) DenseNet- CIFARIO (Test)
80
Trein Acourasy %
96
Accurscy
75
P0
BODW 78.73
80
85
80
80
SCD: 08
80
55
Epoch
Epoch
(e) WideFResNet CIFAR100 (Train)
(1) WideResNNtt CIFAR100 (Test)
PowerSCID: 77.73
Train Accuracy
Acourccy
86
300M 79.12
0
60
80
100
120
60
80
100
120
Epoch
Epoch
(a) ResNeXt CIFAR100 (Train)
(h) ResNeXt CIFAR100 (Test)
Figure 8: Train and test accuracy for SGD, SGDM and PowerSGD. The annotations indicate the best overall test accuracy for each optimization method.
SGD
SGDM
PowerSGD
ResNer-50 CIFARIO 17 n- I.0
1 0.1
1) 0=0.1,y= 0.8
DenseNet-121 CIFARIO
17 0.6
1=0.08
0=0.1,y 0.8
WideResNet+ CIFAR100
11 1==066 0.6
11 101.11
1=0.1, 0.8
R CIFARI00
1= I.0
17 = =00.08
11=011, =00.1,y= 0.7
Table 3: Hyper-parameter settings for experiments shown Figure
20


Reviews:
[{"review_id": "SkgOb3BRKH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes PowerSGD for improving SGD to train deep neural networks. The main idea is to raise the stochastic gradient to a certain power. Convergence analysis and experimental results on CIFAR-10/CIFAR-100/Imagenet and classical CNN architectures are given. \n\nOverall, this is a clearly-written paper with comprehensive experiments. My major concern is whether the results are significant enough to deserve acceptance. The proposed method PowerSGD is an extension of the method in Yuan et al. (extended to handle stochastic gradient and momentum). I am not sure how novel the convergence analysis for PowerSGD is, and it would be nice if the authors could discuss technical challenges they overcome in the introduction. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1gTSur19S", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nOverall 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:\n• 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).\n• 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\nmin_β (1/N)Σ_n (y_n – x_n • β)^2\nwith the minibatch gradient estimator computed over randomly chosen minibatches B:\n\\hat g = (1/|B|) Σ_{n \\in B} x_n (y_n – x_n • β).\nAs 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 \ndeal, just that it's not an improvement over Yan et al.'s result.\n\nThat aside, this seems like good work that could have a significant impact on practice.\n\nA couple of other minor points:\n• 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.\n• Not all of the arrows in Figure 1 are pointing to the right lines.\n• In the abstract, it might be good to clarify that the exponentiation is elementwise.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BkxI2ZwqYS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper investigates an SGD variant (PowerSGD) where the stochastic gradient is raised to a power of $\\gamma \\in [0,1]$.  The authors introduce PowerSGD and PowerSGD with momentum (PowerSGDM). The theoretical proof of  the convergence is given and experimental results show that the proposed algorithm converges faster than some of the existing popular adaptive SGD techniques.  Intuitively, the proposed PowerSGD can boost the gradient (since $\\gamma \\in [0,1]$) so it may be helpful for the gradient of the lower layers of a deep network which may be hit by the vanishing gradient issue. This may give rise to a faster convergence.   So overall the idea makes sense but I have the following concerns. \n\n1. The major issue I have with this paper is Theorem 3.1 on the ergodic convergence rate of the proposed PowerSGD.  At the first glance, it is $O(\\frac{1}{T})$ which is faster than the conventional SGD convergence rate $O(\\frac{1}{\\sqrt{T}})$.  But after a closer look, this rate is obtained by a very strong assumption on the batch size $B_{t}=T$.  In other words, when the number of iterations is large, the batch size will be large too.  I consider this assumption unrealistic.  Given that $T$ is typically very large (it is iterations, not epochs),  it will require a huge batch size, probably close to the whole training set. In this case, it is basically a GD, not SGD any more. That's why the rate is $O(\\frac{1}{T})$, which is the convergence rate of GD.   I would like to see a convergence proof where the batch size $B_{t}$ is treated as a small constant like other SGD proofs assume.  Actually in the experiments the authors never use an increasing batch size. Instead, a constant batch size 128 is used. Therefore,  the faster convergence demonstrated in the experiments can not be explained by Theorem 3.1 or Theorem 3.2. \n\n2. There are numerous inaccuracies in the proof given the supplementary material.  For instance, in Eq.7,  $\\nabla f(x) \\sigma(\\nabla f(x))$  should be $\\nabla f(x)^{T} \\sigma(\\nabla f(x))$   The random variable $\\xi_{t}$ should be a scalar on training samples, not a vector, etc..  The authors should clean it up. \n\n3. It would be helpful to show the $\\gamma$ value on each experiment with different tasks. It would be good to know how $\\gamma$ varies across tasks. \n\n4. I think in the comparative experiments, the plain SGD should be added as another reference algorithm. \n\n5. The term \"PowerSGD\" seems to have been used by other papers. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: After reading the author's rebuttal, the reviewers still think that this is an incremental work, and the theory and experiments .are inconsistent. The authors are encouraged to consider the the reivewer's comments to improve the paper.
Decision: Reject