AdaGrad: A Learning Rate for Every Parameter

Everything so far used one learning rate for all parameters. Often that is a poor fit, because different parameters see very different gradients.

The problem: sparse features

Think of a model over text with one weight per word. Common words like "the" appear in almost every example, so their weights get a gradient at almost every step. A rare word appears in a handful of examples, so its weight gets a gradient only occasionally, but when it does, that gradient is informative.

With one global $\eta$, the frequent weights would be updated constantly and might need a small rate to stay stable, while the rare weights barely move and would like a large rate to learn anything from their few chances. One rate cannot suit both.

The idea

AdaGrad keeps, for every parameter, the running sum of its squared gradients, and divides the step by the square root of it. Writing $g_t$ for the gradient (all operations element by element):

The tiny constant $\epsilon$, such as $10^{-8}$, only prevents division by zero. Each parameter therefore has its own effective learning rate $\eta/\sqrt{G_t}$:

• a parameter with large or frequent gradients builds up a large $G$ and takes small steps,
• a parameter with small or rare gradients keeps a small $G$ and takes large steps.

A quick check with numbers. Parameter 1 gets a gradient of size 1 at every one of 100 steps, so $G_1 = 100$. Parameter 2 gets a gradient of size 1 only every tenth step, so $G_2 = 10$. The effective rates are $\eta/10$ and $\eta/\sqrt{10} \approx \eta/3.2$. The rare parameter gets a rate 3.2 times larger, as we wanted.

What the first steps look like

On the sigmoid toy problem from $(-2, -2)$ the gradient is tiny, about $(-0.0055, -0.0077)$. Plain gradient descent moves by about $0.005$ per step. AdaGrad divides by $\sqrt{G}$, which at the first step is just the gradient's own size, so the first step moves each parameter by almost exactly $\eta$, whatever the gradient's scale.

At first the effective rate is enormous, because the gradient was so small. That escapes the flat start at once. The rate then falls quickly as the squared gradients accumulate.

Results with $\eta = 1$ on the sigmoid toy problem: the loss stays below $10^{-3}$ after 21 steps, against 183 for plain gradient descent at the same rate. On the narrow valley with $\eta = 0.5$ it takes 10 steps against 25 for the best plain rate. The valley is a flattering case: its steep and gentle directions line up exactly with the two parameters, so per-parameter scaling fixes the imbalance perfectly. Do not expect such gains on every problem.

The weakness

$G_t$ only ever grows. So every effective rate only ever shrinks, and eventually the steps become tiny whether or not training has finished. In a long training run AdaGrad can stall long before reaching a good solution. The next lessons fix exactly this.

In code

def adagrad_step(theta, G, grad, eta=0.5, eps=1e-8):
    g = grad(theta)
    G = G + g ** 2                      # running sum of squared gradients
    return theta - eta * g / (np.sqrt(G) + eps), G