# 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.

Source: https://www.mlfoundry.in/learn/adagrad  
Section: Deep Learning › Optimization Algorithms  
Level: core · 10 min read · updated 2026-10-11

**AdaGrad:** (adaptive gradient) keeps, for every parameter $i$, the running sum of its squared gradients $G_{t,i}=\sum_{s\le t}g_{s,i}^2$ and updates $\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 $\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

$$
G_{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}
$$

- $g_{t,i}$: gradient of the loss with respect to parameter $i$ at step $t$
- $G_{t,i}$: accumulator: the **sum** (not the average) of all squared gradients so far; $G_{0,i}$ is `initial_accumulator_value`, default 0
- $\eta$: global learning rate; PyTorch's default is $0.01$
- $\epsilon$: small constant added **after** the square root; PyTorch's default is $10^{-10}$
- $\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 $\big(\sum_s g_sg_s^\top\big)^{-1/2}$, which can adapt to correlated directions, but it needs a $d\times d$ matrix and its inverse square root for $d$ 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 $|g_{t,i}|\le\sqrt{G_{t,i}}$ when $G_{0,i}\ge0$; with $G_0=0$ the very first step is exactly $\eta\operatorname{sign}(g)$. Second, the update is invariant to rescaling one coordinate's gradient: multiply $g_i$ by 100 and $\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), $\epsilon=10^{-10}$, `initial_accumulator_value=0`, `lr_decay=0`
- **Largest step:** $|\Delta\theta_i|\le\eta$ in every coordinate, at every step
- **Scale invariance:** per coordinate: gradients of any size give steps of size about $\eta/\sqrt n$ on the $n$-th update
- **Best for:** sparse features, convex and online problems, embeddings with sparse updates
- **Main weakness:** $G$ never shrinks, so the effective learning rate decays like $1/\sqrt t$ even when that is too fast

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

## The ever-shrinking step

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

$$
\sum_{k=1}^{n}\frac{\eta}{\sqrt k}\;<\;2\eta\sqrt n\qquad\text{(e.g. } \eta=0.1,\ n=200:\ 2.69\text{)}
$$

- $\eta/\sqrt k$: step $k$ when the gradient size stays constant; with shrinking gradients each step is even smaller
- $2\eta\sqrt n$: travel budget; to move a parameter a distance $D$ needs about $(D/2\eta)^2$ updates, quadratic in $D$

For convex problems with noisy gradients this decay is a feature: a $1/\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 $\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 $x$ 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=\tfrac12(x^2+25y^2)$, start $(-4,\,1.6)$, gradient $(x,\,25y)$, $\eta=0.5$, $G_0=0$. Values computed by the figure's code.

AdaGrad on the valley, η = 0.5

| 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 |

1. Step 1: $G=g^2$, so the update is $\eta\,g/|g|=0.5\,\operatorname{sign}(g)$: $(-4,1.6)\to(-3.5,\,1.1)$. The 10× larger $y$-gradient gives no larger step.
2. Step 2: $G_y=1600+27.5^2=2356$, $\sqrt{G_y}=48.5$, so $\Delta y=-0.5\cdot27.5/48.5=-0.283$. $G_x=16+3.5^2=28.25$, $\Delta x=0.5\cdot3.5/5.32=0.329$.
3. The effective rates shrink every step and by about 10× more in $y$ than in $x$, because $y$'s gradients were 10× larger. By step 50 they have settled at $(0.047,\,0.0086)$: the gradients have become tiny, so the sum stops growing.
4. After 200 steps AdaGrad is at loss $1.7\times10^{-8}$. SGD at $0.075$ reaches $2.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
import torch, torch.nn as nn

theta = torch.tensor([-4.0, 1.6], requires_grad=True)
opt = torch.optim.Adagrad([theta], lr=0.5)   # lr_decay=0, initial_accumulator_value=0, eps=1e-10

def f(t):
    return 0.5 * (t[0] ** 2 + 25 * t[1] ** 2)

for step in range(2):
    opt.zero_grad()
    f(theta).backward()
    opt.step()       # sum += g*g ;  theta -= lr * g / (sqrt(sum) + eps)

print(theta.detach())            # ≈ (-3.171, 0.817)
print(opt.state[theta]["sum"])   # ≈ (28.25, 2356.25)

# Sparse features: only the rows looked up in a batch get gradients (and accumulator updates)
emb = nn.Embedding(1_000_000, 64, sparse=True)
opt = torch.optim.Adagrad(emb.parameters(), lr=0.05, initial_accumulator_value=0.1)

# From scratch, per parameter p with gradient g and state s (initialised to initial_accumulator_value):
#   s += g * g
#   p -= lr * g / (s.sqrt() + eps)
```

torch.optim.Adagrad on the figure's valley, and the typical sparse-embedding use

> **The learning rate dies:** On long non-convex training runs AdaGrad's effective learning rate keeps decaying and training stalls, even though the loss is far from a minimum. Starting with a larger $\eta$ only delays it; the cure is a decaying average of squared gradients (RMSProp, AdaDelta, Adam). In the figure at $\eta=0.1$, the $x$-coordinate has moved 2.29 of the 4 units it needs after 200 steps and its effective rate is down to 0.0028.

> **eps and initial_accumulator_value:** $\epsilon$ only matters while $G$ is near 0: a parameter that has never received a gradient has effective rate $\eta/\epsilon$, but its step is $0\cdot\eta/\epsilon=0$. `initial_accumulator_value` $G_0>0$ makes the first steps smaller and smoother: with $G_0=10$ the first $x$-step in the figure is $0.5\cdot4/\sqrt{26}=0.39$ instead of 0.5. Values around 0.1 are common in large sparse models (TensorFlow's default for Adagrad is 0.1; PyTorch's is 0).

> **Adaptive methods normalize scale, not curvature:** AdaGrad divides by gradient size, which on an axis-aligned quadratic is related to curvature, so it helps there. If the steep direction is diagonal to the axes, both coordinates see large gradients and the per-coordinate scaling cannot single out the bad direction. That is the rotated-valley lesson of the overview figure, and why the diagonal methods are not a substitute for true second-order information.

**Strengths**

- Rare features get larger effective learning rates automatically
- Insensitive to gradient scale per coordinate; no step exceeds $\eta$
- A $1/\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))

**Limitations**

- 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

**Question:** 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?

- A. A's step is 10,000× smaller
- B. They are the same, η/5
- C. B's step is 10,000× smaller
- D. A's step is 100× larger

**Answer:** B. They are the same, η/5 — With a constant gradient size $c$, the $n$-th update is $\eta c/\sqrt{nc^2}=\eta/\sqrt n$, independent of $c$. For $n=25$ both move by $\eta/5$. This per-coordinate scale invariance is what makes AdaGrad's step independent of the gradient's units.

**Question:** Why does AdaGrad tend to stall in long deep-network training runs?

- A. Its first step is too large
- B. The accumulator is a sum of squared gradients, so the effective learning rate only decreases
- C. It forgets old gradients too quickly
- D. It needs second derivatives

**Answer:** B. The accumulator is a sum of squared gradients, so the effective learning rate only decreases — $G_t=\sum_s g_s^2$ never shrinks, so $\eta/\sqrt{G_t}$ falls roughly like $1/\sqrt t$ whenever gradients stay non-negligible. RMSProp replaces the sum with an exponential moving average so the step size can recover.

**Key points**

- AdaGrad: $G\leftarrow G+g^2$, $\theta\leftarrow\theta-\eta\,g/(\sqrt G+\epsilon)$, element-wise (Duchi, Hazan and Singer, 2011).
- Each coordinate's effective rate $\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/\sqrt p$ times larger for a feature seen in a fraction $p$ of examples.
- $G$ only grows, so the step size only shrinks; with steady gradients the $n$-th step is $\eta/\sqrt n$ and the total travel is below $2\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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
