Definition
AdaGrad (adaptive gradient) keeps, for every parameter , the running sum of its squared gradients and updates . Each coordinate gets its own learning rate, set by how much gradient it has seen so far.
SGD uses one learning rate for every parameter. That is a poor fit when parameters see very different gradients: a word embedding for "the" is updated on almost every batch, one for a rare word only now and then, and the weights of a rare but informative feature in a linear model get a gradient only on the few examples where the feature is nonzero. A step size small enough for the busy parameters starves the rare ones. AdaGrad lets the gradient history choose: a parameter that has accumulated a lot of gradient takes small steps, one that has accumulated little takes large ones.
John Duchi, Elad Hazan and Yoram Singer introduced it in "Adaptive Subgradient Methods for Online Learning and Stochastic Optimization" (JMLR, 2011); McMahan and Streeter proposed closely related adaptive bounds at COLT 2010. Their analysis is online convex optimization: AdaGrad's regret grows like with a constant that adapts to the geometry of the data, and on sparse data it can be far smaller than the bound for any single fixed learning rate. It was then used at scale: Dean et al.'s DistBelief (2012) trained large networks with asynchronous AdaGrad, and Pennington, Socher and Manning trained GloVe word vectors (2014) with it.
The update rule
- gradient of the loss with respect to parameter at step
- accumulator: the sum (not the average) of all squared gradients so far; is
initial_accumulator_value, default 0 - global learning rate; PyTorch's default is
- small constant added after the square root; PyTorch's default is
- the effective per-coordinate learning rate. It can only decrease
All operations are element-wise: the method is diagonal. Duchi et al. also analyse a full-matrix version that preconditions by , which can adapt to correlated directions, but it needs a matrix and its inverse square root for parameters, so only the diagonal version is used for neural networks.
Two properties follow straight from the formula. First, the step in any coordinate is at most , because when ; with the very first step is exactly . Second, the update is invariant to rescaling one coordinate's gradient: multiply by 100 and grows by 100 too, so the step is unchanged.
At a glance
- State
- one accumulator per parameter (PyTorch's
state["sum"]) - Hyperparameters
- (default 0.01), ,
initial_accumulator_value=0,lr_decay=0 - Largest step
- in every coordinate, at every step
- Scale invariance
- per coordinate: gradients of any size give steps of size about on the -th update
- Best for
- sparse features, convex and online problems, embeddings with sparse updates
- Main weakness
- never shrinks, so the effective learning rate decays like even when that is too fast
Why it helps sparse features
Suppose feature is nonzero in a fraction of the examples. With SGD it gets updates in steps, all at the same learning rate as the common features, so it learns times more slowly. With AdaGrad its accumulator counts only the steps on which it actually received a gradient. After steps a common feature with gradients of size has , the rare one only , so the rare feature's effective learning rate is times larger: 4× for a feature present in 1 example in 16. Each rare update is larger, which partly compensates for there being fewer of them.
In the figure, with observed only on every 16th step and , the accumulators after 200 steps are , giving effective rates . The rare coordinate has had 12 updates and is at ; SGD's has had the same 12 updates at rate 0.075 and is still at . SGD's rate cannot be raised to help, because the frequently updated, steep -coordinate makes anything above diverge.
The ever-shrinking step
is a sum of non-negative terms, so it never decreases, and the effective learning rate never increases. In a coordinate whose gradient keeps roughly the same size , the -th update has and moves the parameter by , regardless of . The total distance it can travel in updates is then bounded:
- step when the gradient size stays constant; with shrinking gradients each step is even smaller
- travel budget; to move a parameter a distance needs about updates, quadratic in
For convex problems with noisy gradients this decay is a feature: a step size is exactly what the regret analysis needs, and AdaGrad gets it without a hand-tuned schedule. In the figure with noise , the average loss over steps 101 to 200 is 0.056 for AdaGrad against 1.19 for SGD at a fixed 0.075, and AdaGrad's effective rate on keeps falling, from 0.045 at step 10 to 0.016 at step 200. For deep networks it is a problem. The first, large gradients of training fill the accumulator, and the learning rate then decays toward zero long before the network has converged. This is what RMSProp and AdaDelta fix by replacing the sum with an exponential moving average, and Adam inherits that fix.
Worked example: the first steps
The figure's valley , start , gradient , , . Values computed by the figure's code.
| t | gradient g | accumulator G | effective rate η/√G | θ after step | loss |
|---|---|---|---|---|---|
| 1 | (−4.00, 40.0) | (16.0, 1600) | (0.125, 0.0125) | (−3.500, 1.100) | 21.25 |
| 2 | (−3.50, 27.5) | (28.3, 2356) | (0.094, 0.0103) | (−3.171, 0.817) | 13.37 |
| 3 | (−3.17, 20.4) | (38.3, 2773) | (0.081, 0.0095) | (−2.915, 0.623) | 9.10 |
| 4 | (−2.91, 15.6) | (46.8, 3016) | (0.073, 0.0091) | (−2.702, 0.481) | 6.54 |
- 1Step 1: , so the update is : . The 10× larger -gradient gives no larger step.
- 2Step 2: , , so . , .
- 3The effective rates shrink every step and by about 10× more in than in , because 's gradients were 10× larger. By step 50 they have settled at : the gradients have become tiny, so the sum stops growing.
- 4After 200 steps AdaGrad is at loss . SGD at reaches : on a noiseless quadratic a well-tuned fixed rate is better. AdaGrad's advantage is that anywhere from about 0.3 to 3 works, and no step can exceed .
1import torch, torch.nn as nn23theta = torch.tensor([-4.0, 1.6], requires_grad=True)4opt = torch.optim.Adagrad([theta], lr=0.5) # lr_decay=0, initial_accumulator_value=0, eps=1e-1056def f(t):7 return 0.5 * (t[0] ** 2 + 25 * t[1] ** 2)89for step in range(2):10 opt.zero_grad()11 f(theta).backward()12 opt.step() # sum += g*g ; theta -= lr * g / (sqrt(sum) + eps)1314print(theta.detach()) # ≈ (-3.171, 0.817)15print(opt.state[theta]["sum"]) # ≈ (28.25, 2356.25)1617# Sparse features: only the rows looked up in a batch get gradients (and accumulator updates)18emb = nn.Embedding(1_000_000, 64, sparse=True)19opt = torch.optim.Adagrad(emb.parameters(), lr=0.05, initial_accumulator_value=0.1)2021# From scratch, per parameter p with gradient g and state s (initialised to initial_accumulator_value):22# s += g * g23# p -= lr * g / (s.sqrt() + eps)Use when
- +Rare features get larger effective learning rates automatically
- +Insensitive to gradient scale per coordinate; no step exceeds
- +A decay for free: strong guarantees for convex and online learning
- +Few hyperparameters, and a wide range of working η
- +Supports sparse gradients (e.g. nn.Embedding(sparse=True))
Avoid when
- −The accumulator only grows: the learning rate decays to near zero on long runs
- −Early large gradients permanently shrink a coordinate's step
- −One extra state tensor per parameter
- −Diagonal only: no help when the ill-conditioning is not aligned with the axes
- −Rarely the best choice for deep networks today; RMSProp and Adam replaced it there
Check yourself
Coordinate A has received gradient 0.01 on every step; coordinate B gradient 100 on every step. With AdaGrad (ε negligible, G₀ = 0), how do their steps on the 25th update compare?
Check yourself
Why does AdaGrad tend to stall in long deep-network training runs?
Remember
- ✓AdaGrad: , , element-wise (Duchi, Hazan and Singer, 2011).
- ✓Each coordinate's effective rate depends on its own gradient history; no step exceeds .
- ✓Rare features accumulate less, so their steps stay large: about times larger for a feature seen in a fraction of examples.
- ✓ only grows, so the step size only shrinks; with steady gradients the -th step is and the total travel is below .
- ✓PyTorch:
torch.optim.Adagrad(params, lr=0.01, lr_decay=0, initial_accumulator_value=0, eps=1e-10). - ✓Good for convex, online and sparse problems; for deep networks its decaying-to-zero step led to RMSProp, AdaDelta and Adam.