Super-Convergence: Very Fast Training of Neural Networks Using Large Learning Rates — part 1/3
Cleaned-text code points [0, 15808). Bibliography omitted here; source.md includes it.
# Super-Convergence: Very Fast Training of Neural Networks Using Large Learning Rates
###### Abstract
In this paper, we describe a phenomenon, which we named “super-convergence”, where neural networks can be trained an order of magnitude faster than with standard training methods. The existence of super-convergence is relevant to understanding why deep networks generalize well. One of the key elements of super-convergence is training with one learning rate cycle and a large maximum learning rate. A primary insight that allows super-convergence training is that large learning rates regularize the training, hence requiring a reduction of all other forms of regularization in order to preserve an optimal regularization balance. We also derive a simplification of the Hessian Free optimization method to compute an estimate of the optimal learning rate. Experiments demonstrate super-convergence for Cifar-10/100, MNIST and Imagenet datasets, and resnet, wide-resnet, densenet, and inception architectures. In addition, we show that super-convergence provides a greater boost in performance relative to standard training when the amount of labeled training data is limited. The architectures to replicate this work will be made available upon publication.
## 1 Introduction
While deep neural networks have achieved amazing successes in a range of applications, understanding why stochastic gradient descent (SGD) works so well remains an open and active area of research. Specifically, we show that, for certain hyper-parameter values, using very large learning rates with the cyclical learning rate (CLR) method ( Smith, 2015 ; Smith, 2017 ) can speed up training by as much as an order of magnitude. We named this phenomenon “super-convergence.” In addition to the practical value of super-convergence training, this paper provides empirical support and theoretical insights to the active discussions in the literature on stochastic gradient descent (SGD) and understanding generalization.
Figure 1(a) provides a comparison of test accuracies from a super-convergence example and the result of a typical (piecewise constant) training regime for Cifar-10, both using a 56 layer residual network architecture. Piecewise constant training reaches a peak accuracy of 91.2% after approximately 80,000 iterations, while the super-convergence method reaches a higher accuracy (92.4%) after only 10,000 iterations. Note that the training accuracy curve for super-convergence is quite different than the characteristic accuracy curve (i.e., increasing, then plateau for each learning rate value). Figure 1(b) shows the results for a range of CLR stepsize values, where training of one cycle reached a learning rate of 3. This modified learning rate schedule achieves a higher final test accuracy (92.1%) than typical training (91.2%) after only 6,000 iterations. In addition, as the total number of iterations increases from 2,000 to 20,000, the final accuracy improves from 89.7% to 92.7%.
The contributions of this paper include: 1. Systematically investigates a new training methodology with improved speed and performance.
2. Demonstrates that large learning rates regularize training and other forms of regularization must be reduced to maintain an optimal balance of regularization.
3. Derives a simplification of the second order, Hessian-free optimization method to estimate optimal learning rates which demonstrates that large learning rates find wide, flat minima.
4. Demonstrates that the effects of super-convergence are increasingly dramatic when less labeled training data is available.
## 2 Background
In this paper, when we refer to a typical, standard, or a piecewise-constant training regime, it means the practice of using a global learning rate, (i.e., ≈ 0.1 \approx 0.1 ), for many epochs, until the test accuracy plateaus, and then continuing to train with a learning rate decreased by a factor of 0.1 0.1 . This process of reducing the learning rate and continuing to train is often repeated two or three times.
There exists extensive literature on stochastic gradient descent (SGD) (see Goodfellow et al. (2016) and Bottou (2012) ) which is relevant to this work. Also, there exists a significant amount of literature on the loss function topology of deep networks (see Chaudhari et al. (2016) for a review of the literature). Our use of large learning rate values is in contrast to suggestions in the literature of a maximum learning rate value Bottou et al. (2016) . Methods for adaptive learning rates have also been an active area of research. This paper uses a simplification of the second order Hessian-Free optimization ( Martens, 2010 ) to estimate optimal values for the learning rate. In addition, we utilize some of the techniques described in Schaul et al. (2013) and Gulcehre et al. (2017) . Also, we show that adaptive learning rate methods such as Nesterov momentum ( Sutskever et al., 2013 ; Nesterov, 1983 ) , AdaDelta ( Duchi et al., 2011 ) , AdaGrad ( Zeiler, 2012 ) , and Adam ( Kingma and Ba, 2014 ) do not use sufficiently large learning rates when they are effective nor do they lead to super-convergence. A warmup learning rate strategy ( He et al., 2016 ; Goyal et al., 2017 ) could be considered a discretization of CLR, which was also recently suggested in ( Jastrzębski et al., 2017 ) . We note that Loshchilov and Hutter (2016) subsequently proposed a similar method to CLR, which they call SGDR. The SGDR method uses a sawtooth pattern with a cosine followed by a jump back up to the original value. Our experiments show that it is not possible to observe the super-convergence phenomenon when using their pattern.
Our work is intertwined with several active lines of research in the deep learning research community, including a lively discussion on stochastic gradient descent (SGD) and understanding why solutions generalize so well, research on SGD and the importance of noise for generalization, and the generalization gap between small and large mini-batches. We defer our discussion of these lines of research to the Supplemental materials where we can compare to our empirical results and theoretical insights.
## 3 Super-convergence
In this work, we use cyclical learning rates (CLR) and the learning rate range test (LR range test) which were first introduced by Smith (2015) and later published in Smith (2017) . To use CLR, one specifies minimum and maximum learning rate boundaries and a stepsize. The stepsize is the number of iterations used for each step and a cycle consists of two such steps – one in which the learning rate increases and the other in which it decreases. Smith (2015) recommended the simplest method, which is letting the learning rate change linearly (on the other hand, Jastrzębski et al. (2017) suggest discrete jumps). Please note that the philosophy behind CLR is a combination of curriculum learning ( Bengio et al., 2009 ) and simulated annealing ( Aarts and Korst, 1988 ) , both of which have a long history of use in deep learning.
The LR range test can be used to determine if super-convergence is possible for an architecture. In the LR range test, training starts with a zero or very small learning rate which is slowly increased linearly throughout a pre-training run. This provides information on how well the network can be trained over a range of learning rates. Figure 2(a) shows a typical curve from a LR range test, where the test accuracy has a distinct peak. 1 1 1 Figure reproduced from Smith (2017) with permission. When starting with a small learning rate, the network begins to converge and, as the learning rate increases, it eventually becomes too large and causes the training/test accuracy to decrease. The learning rate at this peak is the largest value to use as the maximum learning rate bound when using CLR. The minimum learning rate can be chosen by dividing the maximum by a factor of 3 or 4. The optimal initial learning rate for a typical (piecewise constant) training regime usually falls between these minimum and maximum values.
If one runs the LR range test for Cifar-10 on a 56 layer residual networks, one obtains the curves shown in Figure 2(b) . Please note that learning rate values up to 3.0 were tested, which is an order of magnitude lager than typical values of the learning rate. The test accuracy remains consistently high over this unusual range of large learning rates. This unusual behavior motivated our experimentation with much higher learning rates, and we believe that such behavior during a LR range test is indicative of potential for super-convergence. The three curves in this figure are for runs with a maximum number of iterations of 5,000, 20,000, and 100,000, which shows independence between the number of iterations and the results.
Here we suggest a slight modification of cyclical learning rate policy for super-convergence; always use one cycle that is smaller than the total number of iterations/epochs and allow the learning rate to decrease several orders of magnitude less than the initial learning rate for the remaining iterations. We named this learning rate policy “1cycle” and in our experiments this policy allows an improvement in the accuracy.
This paper shows that super-convergence traning can be applied universally and provides guidance on why, when and where this is possible. Specifically, there are many forms of regularization, such as large learning rates, small batch sizes, weight decay, and dropout ( Srivastava et al., 2014 ) . Practitioners must balance the various forms of regularization for each dataset and architecture in order to obtain good performance. The general principle is: the amount of regularization must be balanced for each dataset and architecture. Recognition of this principle permits general use of super-convergence. Reducing other forms of regularization and regularizing with very large learning rates makes training significantly more efficient.
## 4 Estimating optimal learning rates
Gradient or steepest descent is an optimization method that uses the slope as computed by the derivative to move in the direction of greatest negative gradient to iteratively update a variable. That is, given an initial point x 0 x_{0} , gradient descent proposes the next point to be: x = x 0 − ϵ ▽ x f ( x ) x=x_{0}-\epsilon\bigtriangledown_{x}f(x) (1) where ϵ \epsilon is the step size or learning rate . If we denote the parameters in a neural network (i.e., weights) as θ ∈ R N \theta\in R^{N} and f ( θ ) f(\theta) is the loss function, we can apply gradient descent to learn the weights of a network; i.e., with input x x , a solution y y , and non-linearity σ \sigma : y = f ( θ ) = σ ( W l σ ( W l − 1 σ ( W l − 2 … σ ( W 0 x + b 0 ) … + b l ) CLOSE CLOSE y=f(\theta)=\sigma(W_{l}\sigma(W_{l-1}\sigma(W_{l-2}...\sigma(W_{0}x+b_{0})...+b_{l}) (2) where W l ∈ θ W_{l}\in\theta are the weights for layer l l and b l ∈ θ b_{l}\in\theta are biases for layer l l .
The Hessian-free optimization method ( Martens, 2010 ) suggests a second order solution that utilizes the slope information contained in the second derivative (i.e., the derivative of the gradient ▽ θ f ( θ ) \bigtriangledown_{\theta}f(\theta) ). From Martens (2010) , the main idea of the second order Newton’s method is that the loss function can be locally approximated by the quadratic as: f ( θ ) ≈ f ( θ 0 ) + ( θ − θ 0 ) T ▽ θ f ( θ 0 ) + 1 2 ( θ − θ 0 ) T H ( θ − θ 0 ) f(\theta)\approx f(\theta_{0})+(\theta-\theta_{0})^{T}\bigtriangledown_{\theta}f(\theta_{0})+\frac{1}{2}(\theta-\theta_{0})^{T}H(\theta-\theta_{0}) (3) where H H is the Hessian, or the second derivative matrix of f ( θ 0 ) f(\theta_{0}) . Writing Equation 1 to update the parameters at iteration i i as: θ i + 1 = θ i − ϵ ▽ θ f ( θ i ) \theta_{i+1}=\theta_{i}-\epsilon\bigtriangledown_{\theta}f(\theta_{i}) (4) allows Equation 3 to be re-written as: f ( θ i − ϵ ▽ θ f ( θ i ) ) ≈ f ( θ i ) + ( θ i + 1 − θ i ) T ▽ θ f ( θ i ) + 1 2 ( θ i + 1 − θ i ) T H ( θ i + 1 − θ i ) f(\theta_{i}-\epsilon\bigtriangledown_{\theta}f(\theta_{i}))\approx f(\theta_{i})+(\theta_{i+1}-\theta_{i})^{T}\bigtriangledown_{\theta}f(\theta_{i})+\frac{1}{2}(\theta_{i+1}-\theta_{i})^{T}H(\theta_{i+1}-\theta_{i}) (5)
In general it is not feasible to compute the Hessian matrix, which has Ω ( N 2 ) \Omega(N^{2}) elements, where N N is the number of parameters in the network, but it is unnecessary to compute the full Hessian. The Hessian expresses the curvature in all directions in a high dimensional space, but the only relevant curvature direction is in the direction of steepest descent that SGD will traverse. This concept is contained within Hessian-free optimization, as Martens (2010) suggests a finite difference approach for obtaining an estimate of the Hessian from two gradients: H ( θ ) = lim δ → 0 ▽ f ( θ + δ ) − ▽ f ( θ ) δ H(\theta)=\lim_{\delta\to 0}\frac{\bigtriangledown f(\theta+\delta)-\bigtriangledown f(\theta)}{\delta} (6) where δ \delta should be in the direction of the steepest descent. The AdaSecant method ( Gulcehre et al., 2014 ; Gulcehre et al., 2017 ) builds an adaptive learning rate method based on this finite difference approximation as: ϵ ∗ ≈ θ i + 1 − θ i ▽ f ( θ i + 1 ) − ▽ f ( θ i ) \epsilon^{*}\approx\frac{\theta_{i+1}-\theta_{i}}{\bigtriangledown f(\theta_{i+1})-\bigtriangledown f(\theta_{i})} (7) where ϵ ∗ \epsilon^{*} represents the optimal learning rate for each of the neurons. Utilizing Equation 4 , we rewrite Equation 7 in terms of the differences between the weights from three sequential iterations as: ϵ ∗ = ϵ θ i + 1 − θ i 2 θ i + 1 − θ i − θ i + 2 \epsilon^{*}=\epsilon~~\frac{\theta_{i+1}-\theta_{i}}{2\theta_{i+1}-\theta_{i}-\theta_{i+2}} (8) where ϵ \epsilon on the right hand side is the learning rate value actually used in the calculations to update the weights. Equation 8 is an expression for an adaptive learning rate for each weight update. We borrow the method in Schaul et al. (2013) to obtain an estimate of the global learning rate from the weight specific rates by summing over the numerator and denominator, with one minor difference. In Schaul et al. (2013) their expression is squared, leading to positive values – therefore we sum the absolute values of each quantity to maintain positivity (using the square root of the sum of squares of the numerator and denominator of Equation 8 leads to similar results).
For illustrative purposes, we computed the optimal learning rates from the weights of every iteration using Equation 8 for two runs: first when the learning rate was a constant value of 0.1 0.1 and second with CLR in the range of 0.1 − 3 0.1-3 with a stepsize of 5,000 iterations. Since the computed learning rate exhibited rapid variations, we computed a moving average of the estimated learning rate as L R = α ϵ ∗ + ( 1 − α ) L R LR=\alpha\epsilon^{*}+(1-\alpha)LR with α = 0.1 \alpha=0.1 and the results are shown in Figure 3(a) for the first 300 iterations. This curve qualitatively shows that the optimal learning rates should be in the range of 2 to 6 for this architecture. In Figure 3(b) , we used the weights as computed every 10 iterations and ran the learning rate estimation for 10,000 iterations. An interesting divergence happens here: when keeping the learning rate constant, the learning rate estimate initially spikes to a value of about 3 but then drops down near 0.2 0.2 . On the other hand, the learning rate estimate using CLR remains high until the end where it settles down to a value of about 0.5 0.5 . The large learning rates indicated by these Figures is caused by small values of our Hessian approximation and small values of the Hessian implies that SGD is finding flat and wide local minima.