1
$\begingroup$

The update formula for Adagrad is:

\begin{equation} w^i(t)=w^i(t-1) -\frac{\eta}{\sqrt{\epsilon +\sum_{1}^t |\nabla_i\mathcal{L}}|^2} \nabla_i\mathcal{L} \end{equation}

It indicates that if the accumulated gradient is large learning rate will become slow. I find it counter-intuitive. If I observe that gradient in a particular direction is large I would like to update my weights by a higher amount. Similarly, if gradient in a direction is small, that indicates I am near minima or a plateau and I would like small steps.

But the formula indicates opposite. Please explain the correct logic behind AdaGrad.

$\endgroup$

1 Answer 1

0
$\begingroup$

The update formula for Adagrad is: $$w^i(t+1)=w^i(t)-\frac{\eta}{\sqrt{\epsilon+\sum\limits_{k=1}^t|\nabla_i\mathcal{L(k)}|^2}}\nabla_i\mathcal{L(t)}$$ First of all, the iteration on the left-hand side is $t+1$, and all iterations on the right-hand side are up to $t$ (you could put $t$ to the LHS but then it should be $t-1$ in all places on the RHS, including the sum).

More importantly, there are different $\nabla_i\mathcal{L}$ in the numerator and the denominator.

In the numerator, there is the gradient at the current iteration step $t$: $\nabla_i\mathcal{L}(t)$. This agrees with your intuition: the larger the slope, the larger the update.

In the denominator, there is the sum of gradients at the previous iteration steps. If previously we went along the valley, and suddenly came to a steep slope, then the current gradient will be large but the denominator will be small (previous gradients were small), and the parameter update will be large.

The main reason for Adagrad is to adjust the learning rate separately for each parameter, thus the index $i$, and $\nabla_i\mathcal{L}$ is actually not a gradient but a partial derivative along the direction of the $i$-th parameter. If you use stochastic gradient descent or mini-batch learning, and your dataset is such that there are certain features that give infrequent contributions to the gradient, then you might not move fast enough into that direction. Adagrad makes larger jumps every time when such a feature contributes to the gradient, and smaller jumps for features that make frequent contributions to the gradient.

It's OK to have smaller jumps for frequently contributing features because in stochastic gradient descent you update your weights after each step, and the total update will be large after you go through the whole dataset. For a certain feature that pushes the learning infrequently (rarely occurs in your dataset), you need a larger jump.

The drawback is that the denominator is always positive, so the learning rate only decreases, and may become too small at some point. To mitigate it, you consider not the whole history of previous gradients but restrict them to a certain window. Such an algorithm is called Adadelta.

$\endgroup$

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.