2
$\begingroup$

For adaptive learning optimizers such as Adam and RMSProb, the effective learning rate is not the same for all weight parameters. This means that we are not really following the direction of the steepest decent vector in the weights space, correct? If so, why then should we bother with computing the gradient (via backprop) in the first place?

$\endgroup$
4
  • $\begingroup$ The learning rate only indicates how far you move in the opposite direction of the gradient,. If there are different learning rates for the weights, it means that the is net going further in the opposite direction of the gradient for some weights... Adam and RMSProb are variants of the Gradient Descent Algorithm... Take a look at this post: ruder.io/optimizing-gradient-descent/index.html#adam $\endgroup$
    – ignatius
    May 15, 2018 at 6:53
  • $\begingroup$ Yes, but when we are multiplying the negative gradient vector by different learning rates, we are effectively changing the direction of the vector we are following and thus not following the steepest decent. $\endgroup$
    – mhmhsh
    May 15, 2018 at 19:50
  • $\begingroup$ So, does the magnitude of a vector change its direction? $\endgroup$
    – ignatius
    May 16, 2018 at 7:38
  • $\begingroup$ If you have a vector v=[1, 2, 3] and multiply it with one number, that doesn't change its direction, only its magnitude. However, if you multiply each element of the vector with a different number, say [4, 5, 6], then yes, v .* [4, 5, 6] is a different vector. Adam and RMSProb multiply each element of the gradient with different learning rate. $\endgroup$
    – mhmhsh
    Nov 8, 2019 at 21:05

1 Answer 1

4
$\begingroup$

Adam and RMSprop are both optimization algorithms which make the vanilla gradient descent more robust. You still need to calculate the gradient however, these algorithms will facilitate the descent in certain directions and punish the descent in others based on some criteria.

Before delving into the details consider this analogy; imagine you are on a mountain and you want to get back to the village. To do this you will follow the downhill slope until you get to the bottom of the mountain. However imagine a mountain that looks like the following

enter image description here

Evidently the best path down the mountain should just be straight down the snowy path. However, if we carefully calculate the gradient we will notice that it will always have a slight left and right component. This will cause us to oscilate from left to right while going down the mountain. This is a huge waste of energy, but it's not catastrophic. However, when we start reaching the base of the mountain the downward slope will start to subside and the oscillations will become more prominent. This may cause us to never truly reach the minimum due to the oscillations becoming dominant, or cause the learning process to be dragged on excessively thus wasting resources.

The optimization techniques such as Adam and RMSprop simply make adjustments to the gradient descent step such that we can more directly find the minimum of the objective function without distraction from oscillating gradients. This is achieved in RMSprop and Adam by maintaining statistics relevant to the past computed gradients. RMSprop keeps track of the mean and Adam keeps track of both the mean and the moment of the past gradients.


An amazing reference for the inner-workings of the gradient descent variants can be found here.

Gradient descent

Vanilla gradient descent is defined as

$\theta_{t+1} = \theta_t - \eta \nabla_\theta J(\theta)$

where $\theta$ is the set of parameters which define our objective function $J(\theta)$. The learning rate is $\eta$ and $\nabla$ defines the gradient operator. We will extend this function.

Adding Momentum

Firstly, if we throw a ball down our cliff it will get some momentum as it falls. This will cause it to tend towards the steepest part of the gradient and left to right oscillations would be minimized. We can do the same to the gradient descent algorithm by introducing momentum $\gamma$ as

$\nu_{t} = \gamma \nu_{t-1} + \eta \nabla_\theta J(\theta)$

$\theta_{t+1} = \theta_{t} - \nu_t$

This is a good result but we can still do better.

Adagrad

It is preferable to have a distinct learning rate for each parameter such that we can adjust their impact on the gradient based on their past values. This is achieved by weighing the gradients by a sum of squares term of their past gradients up until the current time $t$. The matrix $G_t$ is a diagonal matrix where its entries are precisely this sum of squares of past gradients for each parameter. The Adagrad update is thus,

$\theta_{t+1,i} = \theta_{t,i} - \frac{\eta}{\sqrt{G_{t,ii} + \epsilon}}\nabla_{\theta_t}J(\theta_{t,i})$.

However, this method suffers from diminishing gradients when the sum of squares matrix makes it such that the past values are all too small and cause no more updates to be possible. Or for parameters which may be impactfull in the future to lose all relevance due to their low gradients at the start.

RMSprop

This is a solution to the diminishing gradients problem. We will use a running average of the past gradients until a time $t$ as defined by $E[g^2]_t$. The update rule is thus

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

$\theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{E[g^2]_t + \epsilon}}g_t$

where $g$ is the gradient for a single parameter.

Adam

In addition to keeping track of the running average of the past gradients we will also keep track of their second order moment. $m$ is the mean and $\nu$ is the moment. Thus we keep track of them as follows

$m_t = \beta_1 m_{t-1} + (1-\beta_1)g_t$

$\nu_t = \beta_2 \nu_{t-1} + (1-\beta_2)g^2_t$

We will correct these terms to remove their bias that tends towards a zero vector as

$\hat{m}_t = \frac{m_t}{1-\beta^t_1}$

$\hat{\nu}_t = \frac{\nu_t}{1-\beta^t_2}$

Finally, the update rule is

$\theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{\hat{\nu}} + \epsilon}\hat{m}_t$

$\endgroup$
2
  • $\begingroup$ Are oscillations always the case with vanilla batch gradient decent? Are there cases where it's better to follow the true gradient (steepest decent) even with oscillations? $\endgroup$
    – mhmhsh
    May 15, 2018 at 20:04
  • $\begingroup$ @mhmhsh From what I have read these oscillations are most common when optimizing over parameters trained over a sparse dataset like NLP or images. In this case these optimized models are far better, I usually use Adadelta. I cannot really think of a situation where vanilla gradient descent would be preferable. Because the optimized techniques simply try to correct for unnecessary gradient directions. Not sure though. $\endgroup$
    – JahKnows
    May 16, 2018 at 3:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.