Update Rules
- SGD
- Momentum
- NAG
- Adagrad
- Adadelta
- Rmsprop
SGD
If you have a pretty smooth error surface with a clear global minimum, like a bowl, but you have a strong gradient in one axis and a weak one in the other, then it's quite hard to get the learning rate down with SGD. You'll see very slow but steady movement in the direction of the weak gradient, but overshooting in the direction of the strong gradient. E.g. horizontal movement with vertical zigzagging.
Momentum
The momentum rule can help remedy this behavior. The analogy is that the gradient is just one of the forces applied to the current velocity of a "ball" rolling down the surface of the loss function. In the aforementioned example, the gradient step may be on the x-axis and steady, but from the step before there's still the oscillating movement on the y-axis.
Combining these forces smooths out the oscillating effect on the y-axis while speeding up the movement on the x-axis.
Nesterov Momentum
Nesterov momentum does a "lookahead".
At the update step, first "follow" the momentum step to see where the momentum would bring you after one step. Then compute the gradient from that position instead of the current one.
RMSProp
One of the problems of the SGD example above is that the same learning rate is applied in all dimensions (i.e. for all parameters to be updated), which caused undesirable behavior.
So why don't we instead have a separate learning rate for each parameter?
RMSProp does this. We start with a global learning rate. At each update, we compute a cache for each parameter that adjust the global learning rate .
Rationale: do small updates for large gradients, and big updates for small gradients. This is achieved by dividing by the cache of the parameter, which is bigger for larger gradients.
$$cache = decayrate * cache + (1 - decayrate) * dx^2$$
Then
$$x += - \lambda * dx / \sqrt(cache) + \epsilon$$
Adam
ADAM combine the ideas of momentum and RMSProp.
$$momentum = \beta_1 * m + (1 - \beta_1) * dx$$
$$velocity = \beta_2 * v + (1 - \beta_2) * dx^2$$
$$x += -\lambda * m / \sqrt{v} + \epsilon$$