OptimizersPermalink

https://youtu.be/mdKjMPmcWjY

Gradient DescentPermalink

• Update once every epoch
• $\begin{array}{r}\theta =\theta -\alpha {\mathrm{\nabla }}_{\theta }J(\theta )\end{array}$.

Stochastic Gradient DescentPermalink

• update every sample
  • Takes long
  • sensitive to each sample
• $\begin{array}{r}\theta =\theta -\alpha {\mathrm{\nabla }}_{\theta }J(\theta )\end{array}$.

Mini-batch Gradient DescentPermalink

• Decrease noise of SGD
• update every N-sample
• $\begin{array}{r}\theta =\theta -\alpha {\mathrm{\nabla }}_{\theta }J(\theta )\end{array}$.

SGD + MomentumPermalink

• Decrease noise of SGD
• $\begin{array}{r}v=\gamma v+\eta {\mathrm{\nabla }}_{\theta }J(\theta )\end{array}$.
• $\begin{array}{r}\theta =\theta -\alpha v\end{array}$.
• parameters of a model tend to change in single direction as examples are similar.
  • pros
    • With this property, using momentum, a model learns faster by paying little attention to some samples.
  • Cons
    • Choosing samples blindly not guarantee the right direction.

SGD + Momentum + AccelerationPermalink

• $\begin{array}{r}v=\gamma v+\eta {\mathrm{\nabla }}_{\theta }J(\theta -\gamma v)\end{array}$.
• $\begin{array}{r}\theta =\theta -\alpha v\end{array}$.

Adaptive Learning Rate OptimizersPermalink

• learn more along one direction than another

AdagradPermalink

• for every epoch $t$
  • for every parameter ${\theta }_i$
• $\begin{array}{r}{\theta }_{t+1,i}={\theta }_{t,i}-\frac{\eta }{\sqrt{G_{t,ii}}+ϵ}{\mathrm{\nabla }}_{{\theta }_{t,i}}J({\theta }_{t,i})\end{array}$.
• $\begin{array}{r}{G}_{t,ii}=G_{t-1,ii}+{\mathrm{\nabla }}_{{\theta }_{t,i}}^{2}J({\theta }_{t,i})\end{array}$.
• or $\begin{array}{r}{G}_{t,ii}={\mathrm{\nabla }}_{{\theta }_{1,i}}^{2}J({\theta }_{1,i})+{\mathrm{\nabla }}_{{\theta }_{2,i}}^{2}J({\theta }_{2,i})+{\mathrm{\nabla }}_{{\theta }_{3,i}}^{2}J({\theta }_{3,i})+\cdots +{\mathrm{\nabla }}_{{\theta }_{t,i}}^{2}J({\theta }_{t,i})\end{array}$
  • $\begin{array}{r}{G}_{t,ii}\end{array}$ : Sum of squares of the gradients w.r.t ${\theta }_i$ until that point
• Problem:
  • G is monotonically increasing over iterations
    • LR will decay to a point where the parameter will no longer update (no learning)
    • $\begin{array}{r}\frac{\eta }{\sqrt{G_{t,ii}}+ϵ}\end{array}$ tends to 0
    • learns slower

AdadeltaPermalink

• for every epoch $t$
  • for every parameter ${\theta }_i$
• reduce the influence of the past squared gradients by introducing gamma weight to all of those gradients
  • reduces the effect exponentially
  • $\begin{array}{r}{\theta }_{t+1,i}={\theta }_{t,i}-\frac{\eta }{\sqrt{E[G_{t,ii}]}+ϵ}{\mathrm{\nabla }}_{{\theta }_{t,i}}J({\theta }_{t,i})\end{array}$.
  • $\begin{array}{r}{G}_{t,ii}=\gamma G_{t-1,ii}+(1-\gamma ){\mathrm{\nabla }}_{{\theta }_{t,i}}^{2}J({\theta }_{t,i})\end{array}$.
  • $\begin{array}{r}\frac{\eta }{\sqrt{E[G_{t,ii}]}+ϵ}\end{array}$ not tend to 0

Adam (Adadelta + momentum)Permalink

• for every epoch $t$
  • for every parameter ${\theta }_i$
• Adadelta + expected value of past gradients
  • $\begin{array}{r}{\theta }_{t+1,i}={\theta }_{t,i}-\frac{\eta }{\sqrt{E[G_{t,ii}]}+ϵ}E[g_{t,i}]\end{array}$.
  • $\begin{array}{r}{G}_{t,ii}=\gamma G_{t-1,ii}+(1-\gamma ){\mathrm{\nabla }}_{{\theta }_{t,i}}^{2}J({\theta }_{t,i})\end{array}$.
  • $\begin{array}{r}E[g_{t,i}]=\beta E[g_{t-1,i}]+(1-\beta ){\mathrm{\nabla }}_{{\theta }_{t,i}}^{2}J({\theta }_{t,i})\end{array}$.
    • slow initially, pick up speed over time.
    • similar to momentum
  • different step size for different parameters
  • With momentum for every parameter, Adam leads to faster convergence
  • This is why Adam is de facto of optimizer of many projects.

ref: https://youtu.be/mdKjMPmcWjY