AdaGrad

Divide each parameter's step by the root of the sum of all its past squared gradients. Rarely updated (sparse) features keep large steps and frequent ones get small steps, but the sum only grows, so every step size shrinks for ever.

10 min read1134 wordscore0 viewsupdated 2026-10-11

Definition

AdaGrad (adaptive gradient) keeps, for every parameter ii, the running sum of its squared gradients Gt,i=∑s≤tgs,i2G_{t,i}=\sum_{s\le t}g_{s,i}^2 and updates θi←θi−ηGt,i+ϵ gt,i\theta_i\leftarrow\theta_i-\dfrac{\eta}{\sqrt{G_{t,i}}+\epsilon}\,g_{t,i}. 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 T\sqrt T 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

Gt,i=Gt−1,i+gt,i2,θt+1,i=θt,i−ηGt,i+ϵ gt,iG_{t,i}=G_{t-1,i}+g_{t,i}^2,\qquad \theta_{t+1,i}=\theta_{t,i}-\frac{\eta}{\sqrt{G_{t,i}}+\epsilon}\,g_{t,i}
gt,ig_{t,i}
gradient of the loss with respect to parameter ii at step tt
Gt,iG_{t,i}
accumulator: the sum (not the average) of all squared gradients so far; G0,iG_{0,i} is initial_accumulator_value, default 0
η\eta
global learning rate; PyTorch's default is 0.010.01
ϵ\epsilon
small constant added after the square root; PyTorch's default is 10−1010^{-10}
η/(Gt,i+ϵ)\eta/(\sqrt{G_{t,i}}+\epsilon)
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 (∑sgsgs⊤)−1/2\big(\sum_s g_sg_s^\top\big)^{-1/2}, which can adapt to correlated directions, but it needs a d×dd\times d matrix and its inverse square root for dd 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 η\eta, because ∣gt,i∣≤Gt,i|g_{t,i}|\le\sqrt{G_{t,i}} when G0,i≥0G_{0,i}\ge0; with G0=0G_0=0 the very first step is exactly ηsign⁡(g)\eta\operatorname{sign}(g). Second, the update is invariant to rescaling one coordinate's gradient: multiply gig_i by 100 and Gi\sqrt{G_i} grows by 100 too, so the step is unchanged.

At a glance

State
one accumulator per parameter (PyTorch's state["sum"])
Hyperparameters
η\eta (default 0.01), ϵ=10−10\epsilon=10^{-10}, initial_accumulator_value=0, lr_decay=0
Largest step
∣Δθi∣≤η|\Delta\theta_i|\le\eta in every coordinate, at every step
Scale invariance
per coordinate: gradients of any size give steps of size about η/n\eta/\sqrt n on the nn-th update
Best for
sparse features, convex and online problems, embeddings with sparse updates
Main weakness
GG never shrinks, so the effective learning rate decays like 1/t1/\sqrt t even when that is too fast
f = ½(x² + 25y²)startminloss (log) vs step1e-81e-41AdaGrad η/(√G+ε) per coordinate1e-41e-21x (flat)y (steep)0100200
t = 200|x seen every
noise|initial_accumulator_value
● AdaGrad loss 1.7e-8 at (−0.00, 0.00)● SGD, η = 0.075 loss 2.3e-13 at (−0.00, 0.00)G = (113.5, 3385.8)η/(√G+ε) = (0.047, 8.6e-3)x has moved 4.00 of 4 in 200 updatesbound η·Σ1/√n (if |g| never grows) 13.43
G only grows, so each coordinate's step size only shrinks. Dashed line: SGD's fixed η = 0.075, close to the largest stable value 2/25 = 0.08. No AdaGrad step moves a coordinate by more than η.
fig.AdaGrad (green) and plain SGD at its near-best fixed rate 0.075 (grey) on f = ½(x² + 25y²), with AdaGrad's effective learning rate η/(√G+ε) per coordinate below. At the default η = 0.5 the first step is exactly 0.5 in both coordinates despite the 10× gradient ratio, and after 200 steps the steep y-coordinate has effective rate 0.0086 while the flat x-coordinate has 0.047. Drop η to 0.1: x stops at −1.71 because the steps η/√n can add up to at most 2.69 in 200 updates. Make x a rare feature seen every 16th step and set η = 1: AdaGrad reaches x = −0.42 while SGD is at −1.57. Turn on noise σ = 2 to see the effective rates keep falling.

Why it helps sparse features

Suppose feature ii is nonzero in a fraction pp of the examples. With SGD it gets pTpT updates in TT steps, all at the same learning rate as the common features, so it learns 1/p1/p times more slowly. With AdaGrad its accumulator counts only the steps on which it actually received a gradient. After TT steps a common feature with gradients of size cc has G≈Tc2G\approx Tc^2, the rare one only G≈pTc2G\approx pTc^2, so the rare feature's effective learning rate is 1/p1/\sqrt p 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 xx observed only on every 16th step and η=1\eta=1, the accumulators after 200 steps are G=(43.1, 1872)G=(43.1,\,1872), giving effective rates (0.152, 0.023)(0.152,\,0.023). The rare coordinate has had 12 updates and is at x=−0.42x=-0.42; SGD's has had the same 12 updates at rate 0.075 and is still at x=−1.57x=-1.57. SGD's rate cannot be raised to help, because the frequently updated, steep yy-coordinate makes anything above 2/25=0.082/25=0.08 diverge.

The ever-shrinking step

GG is a sum of non-negative terms, so it never decreases, and the effective learning rate η/G\eta/\sqrt{G} never increases. In a coordinate whose gradient keeps roughly the same size cc, the nn-th update has G=nc2G=nc^2 and moves the parameter by ηc/nc2=η/n\eta c/\sqrt{nc^2}=\eta/\sqrt n, regardless of cc. The total distance it can travel in nn updates is then bounded:

∑k=1nηk  <  2ηn(e.g. η=0.1, n=200: 2.69)\sum_{k=1}^{n}\frac{\eta}{\sqrt k}\;<\;2\eta\sqrt n\qquad\text{(e.g. } \eta=0.1,\ n=200:\ 2.69\text{)}
η/k\eta/\sqrt k
step kk when the gradient size stays constant; with shrinking gradients each step is even smaller
2ηn2\eta\sqrt n
travel budget; to move a parameter a distance DD needs about (D/2η)2(D/2\eta)^2 updates, quadratic in DD

For convex problems with noisy gradients this decay is a feature: a 1/t1/\sqrt t step size is exactly what the regret analysis needs, and AdaGrad gets it without a hand-tuned schedule. In the figure with noise σ=2\sigma=2, 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 xx 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 f=12(x2+25y2)f=\tfrac12(x^2+25y^2), start (−4, 1.6)(-4,\,1.6), gradient (x, 25y)(x,\,25y), η=0.5\eta=0.5, G0=0G_0=0. Values computed by the figure's code.

tgradient gaccumulator Geffective rate η/√Gθ after steploss
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
AdaGrad on the valley, η = 0.5
  1. 1Step 1: G=g2G=g^2, so the update is η g/∣g∣=0.5 sign⁡(g)\eta\,g/|g|=0.5\,\operatorname{sign}(g): (−4,1.6)→(−3.5, 1.1)(-4,1.6)\to(-3.5,\,1.1). The 10× larger yy-gradient gives no larger step.
  2. 2Step 2: Gy=1600+27.52=2356G_y=1600+27.5^2=2356, Gy=48.5\sqrt{G_y}=48.5, so Δy=−0.5⋅27.5/48.5=−0.283\Delta y=-0.5\cdot27.5/48.5=-0.283. Gx=16+3.52=28.25G_x=16+3.5^2=28.25, Δx=0.5⋅3.5/5.32=0.329\Delta x=0.5\cdot3.5/5.32=0.329.
  3. 3The effective rates shrink every step and by about 10× more in yy than in xx, because yy's gradients were 10× larger. By step 50 they have settled at (0.047, 0.0086)(0.047,\,0.0086): the gradients have become tiny, so the sum stops growing.
  4. 4After 200 steps AdaGrad is at loss 1.7×10−81.7\times10^{-8}. SGD at 0.0750.075 reaches 2.3×10−132.3\times10^{-13}: on a noiseless quadratic a well-tuned fixed rate is better. AdaGrad's advantage is that η\eta anywhere from about 0.3 to 3 works, and no step can exceed η\eta.
python
1import torch, torch.nn as nn
2
3theta = 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-10
5
6def f(t):
7 return 0.5 * (t[0] ** 2 + 25 * t[1] ** 2)
8
9for step in range(2):
10 opt.zero_grad()
11 f(theta).backward()
12 opt.step() # sum += g*g ; theta -= lr * g / (sqrt(sum) + eps)
13
14print(theta.detach()) # ≈ (-3.171, 0.817)
15print(opt.state[theta]["sum"]) # ≈ (28.25, 2356.25)
16
17# 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)
20
21# From scratch, per parameter p with gradient g and state s (initialised to initial_accumulator_value):
22# s += g * g
23# p -= lr * g / (s.sqrt() + eps)
torch.optim.Adagrad on the figure's valley, and the typical sparse-embedding use

Use when

  • +Rare features get larger effective learning rates automatically
  • +Insensitive to gradient scale per coordinate; no step exceeds η\eta
  • +A 1/t1/\sqrt t 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: G←G+g2G\leftarrow G+g^2, θ←θ−η g/(G+ϵ)\theta\leftarrow\theta-\eta\,g/(\sqrt G+\epsilon), element-wise (Duchi, Hazan and Singer, 2011).
  • ✓Each coordinate's effective rate η/Gi\eta/\sqrt{G_i} depends on its own gradient history; no step exceeds η\eta.
  • ✓Rare features accumulate less, so their steps stay large: about 1/p1/\sqrt p times larger for a feature seen in a fraction pp of examples.
  • ✓GG only grows, so the step size only shrinks; with steady gradients the nn-th step is η/n\eta/\sqrt n and the total travel is below 2ηn2\eta\sqrt n.
  • ✓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.
← back to Deep Learning roadmap