An Overview Of Gradient Descent Optimization Algorithms

Paper: An overview of gradient descent optimization algorithms

But I kinda prefer reading the Blog of the same :

• https://www.ruder.io/optimizing-gradient-descent/
• Another nice blog: https://johnchenresearch.github.io/demon

Another great ref material on the same from CS231n: here

This note is going be just for me to always have a quick refresher lookup for when things feel muddy, will keep adding and updating the optimizers and their understanding as needed.

Gradient Descent

Batch gradient descent

$$\theta =\theta -\eta \cdot {\nabla }_{\theta }J(\theta )$$

for i in range(nb_epochs):
  params_grad = evaluate_gradient(loss_function, data, params)
  params = params - learning_rate * params_grad

• Gradients are calculated once per epoch for the FULL dataset and one update is performed.

Batch gradient descent is guaranteed to converge to the global minimum for convex error surfaces and to a local minimum for non-convex surfaces.

Stochastic Gradient Descent

$$\theta =\theta -\eta \cdot {\nabla }_{\theta }J(\theta ;x(i);y(i)).$$

for i in range(nb_epochs):
  np.random.shuffle(data)
  for example in data:
    params_grad = evaluate_gradient(loss_function, example, params)
    params = params - learning_rate * params_grad

• grads are calculated after every sample seen and update is performed per sample.
• high variance updates, can eventually converge to global minima if lr decay is used.

Mini-batch gradient descent

$$\theta =\theta -\eta \cdot {\nabla }_{\theta }J(\theta ;x(i:i+n);y(i:i+n)).$$

for i in range(nb_epochs):
  np.random.shuffle(data)
  for batch in get_batches(data, batch_size=50):
    params_grad = evaluate_gradient(loss_function, batch, params)
    params = params - learning_rate * params_grad

• Lower variance compared to vanilla-SGD
• can make use of hardware optim for mat-muls with optimal mini-batch-sizes

---

Gradient Descent Optimisations

Momentum

• Amplifies relative direction of GD while also dampening oscillations
• Done by adding $\gamma$ to the previous step update vector $v_{t-1}$ in order to calculate current update vector $v_t$

$$v_t=\gamma .v_{t-1}+\eta .{\nabla }_{\theta }J(\theta )$$ $$\theta =\theta -v_t$$

Nesterov accelerated gradient

• This is using the idea of momentum and performing a look-ahead on the cost function giving an anticipatory adapting behaviour to updates.

$$v_t=\gamma .v_{t-1}+\eta .{\nabla }_{\theta }J(\theta -\gamma .v_{t-1})$$ $$\theta =\theta -v_t$$

Adagrad

• Provides adaptive learning rates per parameter
• Instead of all params getting same learning_rate for update, params associated with more frequent features get more frequent updates.

Let $g_{t,i}={\nabla }_{\theta }J({\theta }_{t,i})$ be the gradient at time step t for the i’th param. Then the update rule is:

$${\theta }_{t+1,i}={\theta }_{t,i}-\eta \cdot g_{t,i}.$$

Now Ada modifies the learning rate such that instead of a static $\eta$ it is based on param $i$ :

$${\theta }_{t+1,i}={\theta }_{t,i}-\frac{\eta }{\sqrt{G_{t,ii}+ϵ}}\cdot g_{t,i}$$

With just $G_t$ containing the sum of the squares of the past gradients w.r.t all params $\theta$ along its diagonal (hence t,ii in $G_{t,ii}$), the above can we vectorized as a matrix vector prod between $G_t$ and $g_t$ as:

$${\theta }_{t+1}={\theta }_t-\frac{\eta }{\sqrt{G_t+ϵ}}\odot g_t$$

• Main adv of adagrad being that we do not need to tune the learning_rate.
• Main drawback, the accumulation of sqr of grads in the denominator , since all sqr’s are positive the number keeps growing, which inturn causes the actual updates for the step $g_t$ to shrink and after a point becomes too small to cause meaningful updates to weights.

Adadelta

• This just fixes the Adagrad by having a window($w$) for calculating $G_t$ which reduces the effect of shrinking learning_rate.
• Instead of inefficiently storing all previous $w$ grads, they calculate a moving average at each time-step $t$ as $E[g^2{]}_t$ and then use that that calculate the next moving avg as :

$$E[g^2{]}_t=\gamma .E[g^2{]}_{t-1}+(1-\gamma )g_t^2$$

• Now the update term , we just replace the $G_t$ from the Adagrad with the above moving average:

$$\Delta {\theta }_t=\frac{-\eta }{\sqrt{E[g^2{]}_t+ϵ}}{g}_t$$

• Now we can see that the demonimator is just the root-mean-sqr of the gradients, hence rewritting it as:

$$\Delta {\theta }_t=\frac{-\eta }{RMS[g{]}_t}{g}_t$$

• Then the authors do something fun! Dimensional analysis on the update term ( where params, loss and grad, i.e: L/$\theta$ units, are treated as having their own units), they find the LHS != RHS units! hence, they balance it out by adding another RMS but this time for the param update itself, hence it becomes:

$$\Delta {\theta }_t=-\frac{RMS[{\Delta }_{\theta }{]}_{t-1}}{RMS[g{]}_t}{g}_t$$ $${\theta }_{t+1}={\theta }_t+\Delta {\theta }_t$$

Now this doesnt even require a default learning rate! Its auto-tuned by the rate of grad and param updates! Super cool!

RMSprop

• RMSProp is just the Adadelta without the units correction and a slight assumption of $\gamma =0.9$ in calculating the moving avg for gradients as below:

$$E[g^2{]}_t=0.9E[g^2{]}_{t-1}+0.1g_t^2$$ $${\theta }_{t+1}={\theta }_t-\frac{\eta }{\surd E[g^2{]}_t+ϵ}{g}_t$$

Adam

• Adaptive Moment Estimation (Adam)
• Like RMSprop and Adadelta Adam also tracks of decaying avg of past squared grads in $v_t$ as well as past grads* like momentum in $m_t$:
  • $m_t={\beta }_1{m}_{t-1}+(1-{\beta }_1)g_t$
  • $v_t={\beta }_2{v}_{t-1}+(1-{\beta }_2)g_t^2$
• $m_t$ and $v_t$ are estimates of the first moment(mean) and second moment (variance) respectively, hence the name.
• Since the above m and v are vectors and initialized to 0s, they are biased to the initial 0 value hence its de-biased by:

$${\hat{m}}_t=\frac{m_t}{1-{\beta }_1^t}$$ $${\hat{v}}_t=\frac{v_t}{1-{\beta }_2^t}$$

• And the update rule becomes:

$${\theta }_{t+1}={\theta }_t-\frac{\eta }{\sqrt{\widehat{v_t}+ϵ}}{\hat{m}}_t$$

AdamW

• Popular notion, larger magnitude of weights = overfitting, so controlling that is seemingly useful. To do that we have “weight decay”
• If we scale the gradient at timestep $t$

$$g_t=\nabla f({\theta }_t)+w_t{\theta }_t$$

• Then AdamW makes it implicitly a part of the gradient update as

$${\theta }_{t+1}={\theta }_t-\eta (\frac{1}{\sqrt{\widehat{v_t}+ϵ}}{\hat{m}}_t+w_t{\theta }_t)$$

• Turns out this makes a different in practice

---

Adam Vs AdamW Insight

Basically when Adam decays it decays the gradient term $g_t$ which effects both the momentum $m$ and variance estimate $v$.

$$g_t\leftarrow g_t+\lambda {\theta }_{t-1}$$

Because the gradient is decayed and the momentum & variance are calculated based on $g_t$ the optimizer remembers the decay. So the weight decay plays a partial role in the update along with other variables like ${\beta }_1$ , ${\beta }_2$ and the grad_history.

When AdamW decays, it directly effects the parameter $\theta$ and not the gradient term, hence causing a shrinkage irrespective of the gradients.

$${\theta }_t\leftarrow {\theta }_{t-1}-\gamma \lambda {\theta }_{t-1}$$

So AdamW is classically just doing what it says, decaying the params directly and doesnt affect momentum or variance.

PS: Split screen the docs pseudo code algo for Adam and AdamW to see it yourself.

---