In Machine learning, how does normalization help in convergence of gradient descent?

Question

I have read in an article that normalization helps gradient descent to converge faster in machine learning. But I cannot understand why is that.

Any idea?

Answer 1

Rescaling is preconditioning

Steepest descent can take steps that oscillate wildly away from the optimum, even if the function is strongly convex or even quadratic.

Consider $f(x)=x_1^2 + 25x_2^2$. This is convex because it is a quadratic with positive coefficients. By inspection, we can see that it has a global minimum at $x=[0,0]^\top$. It has gradient $$ \nabla f(x)= \begin{bmatrix} 2x_1 \\ 50x_2 \end{bmatrix} $$

With a learning rate of $\alpha=0.035$, and initial guess $x^{(0)}=[0.5, 0.5]^\top,$ we have the gradient update

$$ x^{(1)} =x^{(0)}-\alpha \nabla f\left(x^{(0)}\right) $$

which exhibits this wildly oscillating progress towards the minimum.

Each step is wildly oscillating because the function is much steeper in the $x_2$ direction than the $x_1$ direction. Because of this fact, we can infer that the gradient is not always, or even usually, pointing toward the minimum. This is a general property of gradient descent when the eigenvalues of the Hessian $\nabla^2 f(x)$ are on dissimilar scales. Progress is slow in directions corresponding to the eigenvectors with the smallest corresponding eigenvalues, and fastest in the directions with the largest eigenvalues. It is this property, in combination with the choice of learning rate, that determines how quickly gradient descent progresses.

The direct path to the minimum would be to move "diagonally" instead of in this fashion which is strongly dominated by vertical oscillations. However, gradient descent only has information about local steepness, so it "doesn't know" that strategy would be more efficient, and it is subject to the vagaries of the Hessian having eigenvalues on different scales.

Rescaling the input data changes the Hessian matrix to be spherical. In turn, this means that steepest descent can move more directly towards the minimum instead of sharply oscillating.

Rescaling prevents early saturation

If you're using sigmoidal (logistic, tanh, softmax, etc.) activations, then these have flat gradients for inputs above a certain size. This implies that if the product of the network inputs and the initial weights is too small, the units will immediately be saturated and the gradients will be tiny. Scaling inputs to reasonable ranges and using small values for initial weights can ameliorate this and allow learning to proceed more quickly.

• Effect of rescaling of inputs on loss for a simple neural network

A common method is to scale the data to have 0 mean and unit variance. But there are other methods, such as min-max scaling (very common for tasks like MNIST), or computing Winsorized means and standard deviations (which might be better if your data contains very large outliers). The particular choice of a scaling method is usually unimportant as long as it provides preconditioning and prevents early saturation of units.

• Neural Networks input data normalization and centering

More Reading

In "Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift", Sergey Ioffe and Christian Szegedy write

It has been long known (LeCun et al., 1998b; Wiesler & Ney, 2011) that the network training converges faster if its inputs are whitened – i.e., linearly transformed to have zero means and unit variances, and decorrelated.

So you might also find that the network gets better results if you decorrelate the inputs in addition to applying zero mean and unit variances.

Following the citations provides more description and context.

• LeCun, Y., Bottou, L., Orr, G., and Muller, K. "Efficient backprop." In Orr, G. and K., Muller (eds.), Neural Networks: Tricks of the trade. Springer, 1998b.

• Wiesler, Simon and Ney, Hermann. "A convergence analysis of log-linear training." In Shawe-Taylor, J., Zemel, R.S., Bartlett, P., Pereira, F.C.N., and Weinberger, K.Q. (eds.), Advances in Neural Information Processing Systems 24, pp. 657–665, Granada, Spain, December 2011

• This answer borrows this example and figure from Neural Networks Design (2nd Ed.) Chapter 9 by Martin T. Hagan, Howard B. Demuth, Mark Hudson Beale, Orlando De Jesús.

Answer 2

Gradient descent pushes you towards the steepest direction. If there is scale difference between dimensions, your level curves will typically look like ellipses. If they were circular around the local optimum, the gradient would point towards the center, which is the local optimum; however since they are elliptical, the gradient points towards the steepest direction which might be very off if you consider points around the corner of a very long ellipse. For seeing the steepest directions, just draw an ellipse, pick some points on the boundary draw lines perpendicular to the boundary. You'll see that these directions can be irrelevant of the vector pointing towards the center.