Batch Normalization (BN) has become a cornerstone of deep learning across diverse architectures, appearing to help optimization as well as generalization. While the idea makes intuitive sense, theoretical analysis of its effectiveness has been lacking. Here theoretical support is provided for one of its conjectured properties, namely, the ability to allow gradient descent to succeed with less tuning of learning rates. It is shown that even if we fix the learning rate of scale-invariant parameters (e.g., weights of each layer with BN) to a constant (say, 0.3), gradient descent still approaches a stationary point (i.e., a solution where gradient is zero) in the rate of T^{−1/2} in T iterations, asymptotically matching the best bound for gradient descent with well-tuned learning rates. A similar result with convergence rate T^{−1/4} is also shown for stochastic gradient descent. Batch Normalization (abbreviated as BatchNorm or BN) (Ioffe & Szegedy, 2015) is one of the most important innovation in deep learning, widely used in modern neural network architectures such as ResNet BID8 , Inception (Szegedy et al., 2017) , and DenseNet (Huang et al., 2017) . It also inspired a series of other normalization methods (Ulyanov et al., 2016; BID0 Ioffe, 2017; Wu & He, 2018) .BatchNorm consists of standardizing the output of each layer to have zero mean and unit variance. For a single neuron, if x 1 , . . . , x B is the original outputs in a mini-batch, then it adds a BatchNorm layer which modifies the outputs to DISPLAYFORM0 where µ = i=1 (x i − µ) 2 are the mean and variance within the minibatch, and γ, β are two learnable parameters. BN appears to stabilize and speed up training, and improve generalization. The inventors suggested (Ioffe & Szegedy, 2015) that these benefits derive from the following:1. By stabilizing layer outputs it reduces a phenomenon called Internal Covariate Shift, whereby the training of a higher layer is continuously undermined or undone by changes in the distribution of its inputs due to parameter changes in previous layers., 2. Making the weights invariant to scaling, appears to reduce the dependence of training on the scale of parameters and enables us to use a higher learning rate;3. By implictly regularizing the model it improves generalization.But these three benefits are not fully understood in theory. Understanding generalization for deep models remains an open problem (with or without BN). Furthermore, in demonstration that intuition can sometimes mislead, recent experimental results suggest that BN does not reduce internal covariate shift either (Santurkar et al., 2018) , and the authors of that study suggest that the true explanation for BN's effectiveness may lie in a smoothening effect (i.e., lowering of the Hessian norm) on the objective. Another recent paper (Kohler et al., 2018) tries to quantify the benefits of BN for simple machine learning problems such as regression but does not analyze deep models.Provable quantification of Effect 2 (learning rates). Our study consists of quantifying the effect of BN on learning rates. Ioffe & Szegedy (2015) observed that without BatchNorm, a large learning rate leads to a rapid growth of the parameter scale. Introducing BatchNorm usually stabilizes the growth of weights and appears to implicitly tune the learning rate so that the effective learning rate adapts during the course of the algorithm. They explained this intuitively as follows . After BN the output of a neuron z = BN(w x) is unaffected when the weight w is scaled, i.e., for any scalar c > 0, BN(w x) = BN((cw) x).Taking derivatives one finds that the gradient at cw equals to the gradient at w multiplied by a factor 1/c. Thus, even though the scale of weight parameters of a linear layer proceeding a BatchNorm no longer means anything to the function represented by the neural network, their growth has an effect of reducing the learning rate.Our paper considers the following question: Can we rigorously capture the above intuitive behavior? Theoretical analyses of speed of gradient descent algorithms in nonconvex settings study the number of iterations required for convergence to a stationary point (i.e., where gradient vanishes). But they need to assume that the learning rate has been set (magically) to a small enough number determined by the smoothness constant of the loss function -which in practice are of course unknown. With this tuned learning rate, the norm of the gradient reduces asymptotically as T −1/2 in T iterations. In case of stochastic gradient descent, the reduction is like T −1/4 . Thus a potential way to quantify the rate-tuning behavior of BN would be to show that even when the learning rate is fixed to a suitable constant, say 0.1, from the start, after introducing BN the convergence to stationary point is asymptotically just as fast (essentially) as it would be with a hand-tuned learning rate required by earlier analyses. The current paper rigorously establishes such auto-tuning behavior of BN (See below for an important clarification about scale-invariance).We note that a recent paper (Wu et al., 2018) introduced a new algorithm WNgrad that is motivated by BN and provably has the above auto-tuning behavior as well. That paper did not establish such behavior for BN itself, but it was a clear inspiration for our analysis of BN.Scale-invariant and scale-variant parameters. The intuition of Ioffe & Szegedy (2015) applies for all scale-invariant parameters, but the actual algorithm also involves other parameters such as γ and β whose scale does matter. Our analysis partitions the parameters in the neural networks into two groups W (scale-invariant) and g (scale-variant). The first group, W = {w (1) , . . . , w (m) }, consists of all the parameters whose scales does not affect the loss, i.e., scaling w (i) to cw (i) for any c > 0 does not change the loss (see Definition 2.1 for a formal definition); the second group, g, consists of all other parameters that are not scale-invariant. In a feedforward neural network with BN added at each layer, the layer weights are all scale-invariant. This is also true for BN with p normalization strategies (Santurkar et al., 2018 ; Hoffer et al., 2018) and other normalization layers, such as Weight Normalization (Salimans & Kingma, 2016) , Layer Normalization BID0 ), Group Normalization (Wu & He, 2018 ) (see Table 1 in BID0 for a summary). In this paper, we studied how scale-invariance in neural networks with BN helps optimization, and showed that (stochastic) gradient descent can achieve the asymptotic best convergence rate without tuning learning rates for scale-invariant parameters. Our analysis suggests that scale-invariance in nerual networks introduced by BN reduces the efforts for tuning learning rate to fit the training data.However, our analysis only applies to smooth loss functions. In modern neural networks, ReLU or Leaky ReLU are often used, which makes the loss non-smooth. It would have more implications by showing similar results in non-smooth settings. Also, we only considered gradient descent in this paper. It can be shown that if we perform (stochastic) gradient descent with momentum, the norm of scale-invariant parameters will also be monotone increasing. It would be interesting to use it to show similar convergence results for more gradient methods.
We give a theoretical analysis of the ability of batch normalization to automatically tune learning rates, in the context of finding stationary points for a deep learning objective.
{"src": "scitldr-AIC_train", "paper_id": "rkxQ-nA9FX"}