References: Y. Yuan, M.Li, J. Liu and C. Tomlin, “On the Powerball Method: Variants of DescentMethods for Accelerated Optimization,” in IEEE Control Systems Letters, vol. 3, no. 3, pp. 601-606, 2019.

This article introduces the IJCAI-2020 paper "pbSGD: Powered Stochastic Gradient Descent Methods for Accelerated Non-Convex Optimization", which was completed by Huazhong University of Science and Technology, University of Waterloo and the University of California, Berkeley.

is the | Sun Weigao

edit | 这是口

paper address: https://www.ijcai.org/Proceedings/2020/0451.pdf

Open source address: https://github.com/HAIRLAB/pbSGD

1

Preface

Training of deep learning is more difficult than traditional optimization due to the existence of high-dimensional function space and random objective functions. Stochastic Gradient Descent is the first method widely used in the field of deep learning to optimize training. It calculates the target loss of small batches of data and iteratively updates model parameters in the direction of negative gradients. At present, many optimization methods for more efficient training of neural networks have been derived based on SGD methods.

In this paper, we propose a new SGD-based optimization method (pbSGD) for training neural networks.

is different from the current mainstream idea (adaptive learning rate or momentum method). In previous work [1], the author of this paper proposed a new method to accelerate the convergence of by leveraging the intuitive expression of the finite time stability of ODE. This method, called Powerball, is obtained by simply adding the power coefficient γ∈[0,1) to the gradients in various gradient-based optimization methods. Essentially, the Powerball method can be regarded as the fastest descent method relative to the p-norm, where p = 1 + 1/γ. Here, an intuitive explanation of the Powerball function instead of other nonlinear functions is that on the one hand, polynomials with exponential (power) operators in mathematics can be used to approximate any nonlinear functions. Therefore, the authors use the power coefficient as variable parameters to create the Powerball function. On the other hand, because the power coefficient γ∈[0,1), according to the principle of the power function, it is not difficult to find that by introducing power coefficients acting on the gradient, the phenomenon of gradient disappearance can be effectively improved.

is very difficult for deriving the convergence of discrete time models (optimization algorithms) over a finite time. It is this point that prompts the authors in [1] to propose continuous time models of optimization methods and analyze their convergence over finite time. In addition, [1] points out that for a given optimization problem, how to choose the optimal γ is theoretically open. It is well known that initial iteration is crucial for a given computational constraint when it comes to large-scale optimization problems. To this end, several types of deformations of Powerball methods have also been developed in [1], which are empirically superior to standard optimization methods, especially in the initial iteration. Experiments based on multiple actual data sets in [1] show that the proposed method in this paper can increase the convergence speed of the (stochastic) gradient descent method and the L-BFGS method by 10 times.

Specifically, based on the basic idea of applying Powerball functions in gradient descent method proposed by the author in [1], this article generalizes it to the SGD situation, and obtains a simple and general method to improve the training efficiency of deep neural networks. In pbSGD, the Powerball function acts on the stochastic gradient term in SGD, and its mechanism of action is consistent with that in [1]. This method performs a simple power function transformation on the stochastic gradient during the iteration process to improve the performance of the SGD method by introducing only one extra hyperparameter, namely the power exponent term. We further propose pbSGD, i.e. pbSGDM, which combines momentum (momentum), and give a theoretical analysis of convergence of the two methods.

experiments show that the proposed pbSGD and pdSGDM methods can achieve faster convergence speed compared to other adaptive gradient methods and similar generalization effects to the SGD method. At the same time, this method can maintain the advantages of the method in [1], mainly including training acceleration during initial iteration, the robustness of algorithm performance to hyperparameters, and effectively improving the gradient vanishing problem.

2

Research background

stochastic optimization is a very important part of deep learning research.Based on the SGD method, many other optimization methods that can effectively train deep neural networks have been proposed in recent years, such as SGD with Momentum (SGDM), RMSProp and Adam, etc. that combine momentum. Adaptive algorithms (such as AdaGrad, RMSProp, Adam) usually have good convergence performance in the early stage. However, recent studies have shown that adaptive algorithms tend to converge to local minimum values during optimization, and have poor generalization performance on the test set. Therefore, many studies in computer vision and natural language processing still use SGD for training networks. On the other hand, compared with the adaptive method SGD, there is some lack in convergence speed. Therefore, how to make SGD effectively escape the saddle point under non-convex conditions and achieve better convergence effects has become a hot research field. There are currently two main design ideas for

: momentum method and adaptive learning rate. SGDM introduces a momentum term from a physical perspective and achieves a faster convergence effect than SGD in practical applications. Momentum can be regarded as a special case of exponential sliding average. Adaptive algorithms usually adopt the idea of adaptive learning rate, and dynamically modify the learning rate by accumulating historical second-order and first-order gradient information. It was first applied to the AdaGrad method. Adam combines AdaGrad and RMSProp algorithms and becomes one of the most commonly used optimizers at present.

is different from the current mainstream idea (adaptive learning rate or momentum method). We propose a new method, using the Powerball function to perform nonlinear transformation of gradient terms to improve the performance of SGD in non-convex cases, namely the pbSGD method. The main contributions of this article are as follows:

1. We propose a simple and easy-to-use optimization method pbSGD based on SGD, giving a pbSGD variant that combines momentum, namely pbSGDM.

2. We conducted a detailed experimental comparison on multiple data sets and tasks. The experimental results show that the method proposed in this paper can achieve better convergence speed than adaptive algorithms in the early stage of training, and at the same time, the generalization effect of SGD and SGDM in the test set is similar.

3. We provide a theoretical analysis of the convergence speed of pbSGD and pbSGDM under non-convex conditions.

3

algorithm introduction

We here give the ideas and derivation of the two algorithms proposed. Among them, pbSGD combines Powerball optimization method with the traditional stochastic gradient descent method, and pbSGDM is an extension of pbSGD after the momentum term was introduced.

1, pbSGD

Training a DNN network with n free parameters can be modeled as an unconstrained optimization problem:

Here f is a function with lower bounds, and SGD has been proven to be an effective and efficient solution to high-dimensional optimization problems. It optimizes f by iteratively updating the parameter vector, which is performed in the opposite direction of the stochastic gradient g. The stochastic gradient here is calculated from the t-th small batch of the training dataset. The parameter update strategy of SGD is as follows:

Now, we introduce a novel nonlinear function:

and call it the Powerball function. Here sign refers to a symbolic function. If z is a vector, the Powerball function will act on each element of z. The parameter gamma here is a new parameter introduced by the Powerball function to adjust the mechanism and strength of the Powerball function.

Here, we apply the Powerball function to the stochastic gradient term of SGD, as shown below:

and get the new pbSGD optimization algorithm.

2, pbSGDM

momentum technology is an inspiration taken from physical processes and has been successfully applied to SGDM and in most cases it can obtain better training results for neural networks. We also propose the momentum acceleration form of pbSGD, that is, pbSGDM. The parameter update rules are:

. The two algorithms proposed in this paper, and their pseudo-codes can be summarized as follows:

4

Experimental comparison

On three public data sets CIFAR-10, CIFAR-100 and ImageNet, we use several different models to compare the convergence speed and generalization effect of the algorithm. Among them, CIFAR-10 is used to train models ResNet-50 and DenseNet-121, CIFAR-100 is used to train ResNet-29 and WideResNet, and ImageNet is used to train ResNet-50.In addition, we built a 13-layer fully connected neural network to verify the ability of pbSGD to mitigate gradient vanishing.

1, convergence and generalization comparison experiments

We completed seven different comparison experiments on three data sets. The optimizers used for comparison include SGDM, pbSGD, pbSGDM, AdaGrad, RMSProp and Adam. We found the best learning rate through grid search in the range of 1.0~1e-4. Each learning rate is averaged five times to avoid random errors. Other hyperparameters remain the default value, and the settings of parameters in the experiment are consistent with other papers. The figure below shows the training curves of each optimizer under different experiments under the best learning rate. The arrows indicate the best accuracy on the test set. The experimental results are as follows:

From the experimental results, we can see that the pbSGD algorithm obtained by adding the Powerball function is faster in the early convergence than the adaptive algorithms (AdaGrad, RMSProp and Adam) without accumulating historical gradient information. The performance on the CIFAR-10 and CIFAR-100 test sets is almost the same as SGD, and the performance of pbSGDM and pbSGD are similar. pbSGD still shows a good convergence speed on the ImageNet dataset, but we noticed that the gap between generalization performance and SGD is widening. We guess that adaptive algorithms and pbSGD have changed the gradient distribution, resulting in bad results on larger datasets.

2, gradient vanishing

Powerball function introduces the gradient vector rescaling, so the problem of gradient vanishing can also be alleviated in deep neural networks. We designed a 13-layer fully connected network, with the activation function selected as ReLU, and used SGD and pbSGD to train respectively, and the learning rate is still selected by grid search. Through experiments, we found that SGD cannot train this network structure, and pbSGD can train the model normally after scaling the gradient vector.

3, robustness improvement

In the experiment, we found that the introduction of hyperparameter gamma can not only accelerate convergence, but also improve the robustness of the accuracy and convergence of the test set. (pbSGD becomes SGD algorithm when gamma=1.0)

1) Improve the robustness of learning rate to accuracy

hyperparameter gamma can standardize the performance of test set when setting the learning rate is small. For example, when learning rate eta=1e-3 and gamma=0.6, the accuracy of pbSGD's test set is 90.06%, while the accuracy of SGD is 79.87%.

2) Improve the robustness of learning rate to convergence

hyperparameter gamma can also improve the robustness of learning rate to convergence. When the learning rate setting is not appropriate, pbSGD can still achieve better convergence performance.

4. Combined with the learning rate strategy

pbSGD only changes the gradient terms, so it can be well combined with other optimization methods to further improve the overall performance. We chose restart's learning rate strategy for comparison experiments. From the results, we can see that pbSGD, which combines the learning rate strategy, achieved better results.

5. Robustness of batch size

Increasing batch size can increase the amount of calculation at each iteration and accelerate the training process. However, changing the distribution characteristics of the gradient will also lead to deterioration in generalization performance. We used comparative experiments at different sizes to explore the robustness of pbSGD to batch size. From the experiment, we can see that the increase in batch size causes the generalization performance of SGD to rapidly decrease, and the impact on pbSGD is relatively small. The introduction of Powerball function improves the robustness of SGD for batch size.

Summary

In this article, we propose a simple but practical method to improve the performance of SGD and SGDM methods. Experimental results prove that this method can effectively accelerate the convergence of the model in training, improve the robustness of hyperparameter selection, and alleviate the problem of gradient disappearance. In addition, this method can be well complementary to other methods, such as learning rate strategies, to further improve the performance of the optimizer.

References:

[1] Y. Yuan, M.Li, J. Liu and C. Tomlin, "On the Powerball Method: Variants of DescentMethods for Accelerated Optimization," in IEEE Control Systems Letters,vol. 3, no. 3, pp. 601-606, 2019.

Recruitment Hire

AI Technology Comment Hope to be able to recruit Science and Technology Editor/Reporter

Office Location: Beijing/Shenzhen

Position: Mainly tracking academic hot spots and interviews with people

Work content:

1, Pay attention to hot events in the academic field and follow up and report in a timely manner;

2, interview scholars or R&D personnel in the field of artificial intelligence;