Gradient Descent

Note

  • Taylor’s series

  • Local linear approximation information captured by gradient.

  • Local quadratic approximation information captured by Hessian.

  • First order approximation of the gradient near a point

Nature of the Error Surface near Stationary Point

Note

  • Understanding the nature of local stationary point (maxima/minima/saddle point) with the help of Hessian.

Warning

Largest eigenvalue = direction of slowest descent

Gradient Descent

Batch Gradient Descent

Stochastic Gradient Descent

Mini-batch Gradient Descent

Convergence

Warning

  • With fixed learning rate, convergence is not guaranteed.

    • (TODO: derive) In the near proximity of a stationary point where quadratic approximation is reasonable

      • the Learning-rate should be \(\eta\le 2/\lambda_\mathrm{max}\)

      • With this learning-rate, the optimization improves on the error by a factor of \((1+1/\kappa)\) where \(\kappa=\lambda_\mathrm{max}/\lambda_\mathrm{min}\) is the condition number of the Hessian.

    • Assuming that the LR is set accordingly, it takes infinitely many steps to reach the minimum.

    • Need to set the threshold somewhere.

  • TODO: proof

Learning-Rate Schedule

Warning

Key idea: Larger LR at the beginning, smaller towards the end.

Note

  • Linear decay

  • Exponential decay

  • Power-law decay

Faster Covergence with Momentum

Warning

  • Carry on a little bit extra along the previous direction before stopping and changing direction again.

  • Moves fast near optima as opposed to a fixed variant.

Heavy-Ball Momentum

Nesterov Accelerated Momentum

Adaptive Learning Rates

Warning

  • Allow different LR along different Eigen-direction (making up for Newton’s Method without having to compute Hessian)

  • Sensible to infrequent updates to certain weights.

  • Moves fast in the beginning, slows down later.

Generic Equation

\[w_{t+1}=w_t-\underbrace{\alpha_tH_t^{-1}\widehat{\nabla E_t}(w_t+\gamma_t(w_t-w_{t-1}))}_\text{adaptive gradient component}+\underbrace{\beta_tH_t^{-1}H_{t-1}(w_t-w_{t-1})}_\text{adaptive momemtum component}\]

Note

  • \(\widehat{\nabla E_t}\) is an estimate of the gradient (stochastic/mini-batch estimate)

  • \(H_t=\sqrt{G_t}\) is a diagonal matrix where \(G_t\) is an approximation of the Hessian (only along major axes)

  • With \(H_t=I\) we recover NAG.

AdaGrad

Note

  • Keep a running weighted average of the gradient magnitudes to set up the LR

  • \(G_t=G_{t-1}+D_t\) where \(D_t\) is a diagonal matrix with squared gradient component.

  • \(\gamma_t=0\) and \(\beta_t=0\)

Warning

  • Issues: accumulating gradients cause diminishing LR.

RMSProp

Note

  • Keep more importance to recently computed gradients.

  • \(G_t=(1-\beta)G_{t-1}+\beta D_t\).

  • \(\gamma_t=0\) and \(\beta_t=0\)

Warning

  • Issues: LR can get real close to 0.

Adam

Note

RMSProp with momentum

Tip

  • Renormalizes the momentum and LR to keep things numerically stable.

Managing Numerical Issues with Gradients

Weight & Bias Initialisation

Input normalisation

Weight normalisation

Batch Normalisation

Layer Normalisation