When we talked about Gradient Descent in part 3, we found it out to be an extremely meaningful optimization technique. Though gradient descent and its variations like mini batch and stochastic gradient descent act as dependable building blocks of AI optimization, they do have some limitations. One of the shortcomings is when the learning process gets stuck in some plateau region along the error surface which is not optimal. Another problem might arise with the speed of convergence; sometimes owing to the small gradient, the descent in each iteration can be very small leading to a large number of iterations. In this blog, we will discuss some of the techniques to address these challenges.
What is Momentum?
Momentum is an idea borrowed from Physics and is calculated as a product of mass and velocity. For a particle with unit mass, the velocity acts as the momentum. Assume a heavy ball is rolling down a curved path across a valley. In the vanilla gradient descent, it will stop once it reaches the bottom of the valley where the gradient diminishes. Momentum on the contrary helps the ball accumulate speed when it is rolling down and that generates the extra push to cross the uphill bumps ahead. With this technique the optimization process will not be stuck in the sub-optimal terrain and can navigate to the other areas across the loss landscape crossing flat saddle points.
Consider, \(\theta\) as parameter of the optimization problem, learning rate \(\alpha\), momentum factor \(\beta\), loss function \(L\), velocity \(v\) and \(t\) as the current timestep. Then:
Vanilla gradient descent update will be -
$$ \theta_{t+1} \leftarrow \theta_t - \alpha \cdot \nabla L(\theta_t) $$
Gradient descent with moment update will become -
$$ v_{t+1} \leftarrow \beta \cdot v_t - \alpha \cdot \nabla L(\theta_t) $$
$$ \theta_{t+1} \leftarrow \theta_t + v_{t+1} $$
The hyperparameter \(\beta\) controls how much weight is given to previous velocity and ranges between 0 and 1.
Nesterov Momentum
The Nesterov momentum method is actually a variation of the standard momentum method and the only difference lies where the gradient is evaluated. It does not calculate the gradient at the current step, rather uses a look-ahead step projecting where the parameter will be using the momentum and calculates the momentum there.
$$ \text{Look ahead value of } \theta_t: \quad \hat{\theta}_t \leftarrow \theta_t + \beta \cdot v_t $$
$$ v_{t+1} \leftarrow \beta \cdot v_t - \alpha \cdot \nabla L(\hat{\theta}_t) $$
$$ \theta_{t+1} \leftarrow \theta_t + v_{t+1} $$
Parameter Initialization Strategies
Sometimes initial values of the model parameters - weights and biases affect the convergence of the model - can trigger large iterations or no convergence at all. The optimization process wants the parameters to be large enough so that their gradient is large and information propagation happens through backpropagation whereas the regularization process wants them to be smaller. There are heuristics based methods to choose the initial values. One approach for a fully connected layer with \(m\) inputs and \(n\) outputs is to sample each parameter from a uniform distribution \(U\left(-\frac{1}{\sqrt{m}}, \frac{1}{\sqrt{m}}\right)\). Another approach on the same line was proposed by Glorot and Bengio and is called Normalized Initialization.
$$ \text{Normalized Initialization } w_{ij} \sim U\left(-\sqrt{\frac{6}{m+n}}, \sqrt{\frac{6}{m+n}}\right) $$
Adaptive Learning Rates
We have seen from the equation of gradient descent that the learning parameter nudges the value of the parameter in the direction where loss minimizes. Now a model with more than one parameter has a single global learning rate; so the nudging is equal for all of them. But it is not realistic; because for a parameter where the gradient is large, the learning rate may overshoot the desired change and that parameter can oscillate around its true value. On the other hand, where the gradient is small needs a larger learning rate to reach its optimal value quickly. The bottomline is instead of having a single learning rate across the parameters, we need a customized learning rate for each parameter. AdaGrad and RMSProp solve this problem by tracking historical gradients and adapt the learning rate according to the gradient of each parameter.
Adaptive Gradient (AdaGrad)
AdaGrad updates the learning rate of each parameter by scaling them inversely proportional to the sum of its historical squared gradients. If for a parameter, the gradient is high, its learning rate will have a sharp decrease controlling the step size and conversely, for a parameter with low gradient, its learning rate remains high. The outcome is the optimizer accelerates along the gentle slopes while braking on the steep cliffs. It balances out the movement across all directions.
Consider, \(\theta\) as parameter of the optimization problem, initial learning rate \(\alpha\), loss function \(L\), running accumulator variable \(G\), \(\epsilon\) as a smoothing term and \(t\) as the current timestep. Then:
$$ G_{t+1} \leftarrow G_t + \nabla L(\theta_t) \odot \nabla L(\theta_t) $$
$$ \theta_{t+1} \leftarrow \theta_t - \frac{\alpha}{\sqrt{G_{t+1} + \epsilon}} \odot \nabla L(\theta_t) $$
\(\odot\) signifies element wise operation.
Root Mean Square Propagation (RMSProp)
The problem of AdaGrad is accumulation of gradients across all steps in history. The sum can only grow larger and eventually the denominator becomes so large that the learning rate shrinks to zero and the algorithm stops learning. RMSProp addresses this challenge by considering an exponentially decaying moving average EMA that provides a short-term memory to the algorithm. When recent history has small gradients, it amplifies the learning rate to slide out of the saddle point and when the recent gradients are large, RMSProp scales down learning rate for those parameters.
Consider, \(\theta\) as parameter of the optimization problem, initial learning rate \(\alpha\), loss function \(L\), running accumulator variable \(G\), \(\epsilon\) as a smoothing term, \(\rho\) as decay factor and \(t\) as the current timestep. Then:
$$ G_{t+1} \leftarrow \rho \cdot G_t + (1 - \rho) \cdot \nabla L(\theta_t) \odot \nabla L(\theta_t) $$
$$ \theta_{t+1} \leftarrow \theta_t - \frac{\alpha}{\sqrt{G_{t+1} + \epsilon}} \odot \nabla L(\theta_t) $$
\(\odot\) signifies element wise operation.