AdaGrad: Adaptive Coordinate Scaling & The Cumulative Gradient Trap
How does AdaGrad dynamically scale learning rates coordinate-by-coordinate, and why does monotonic sum-of-squares accumulation kill learning prematurely?
How this lesson unfolds.
Traditional SGD applies a uniform global learning rate across all parameters regardless of whether a feature occurs once per million samples or on every single step. AdaGrad adapts the step size independently for each individual parameter based on historical gradient frequency.
How does AdaGrad dynamically scale learning rates coordinate-by-coordinate, and why does monotonic sum-of-squares accumulation kill learning prematurely?
Imagine allocating study time for an exam. For subjects you practice every single day (frequent gradients), you reduce your study pace to fine-tune details. For a rare topic you haven't seen in weeks (sparse gradients), you give it a large, intensive study session. That is AdaGrad. However, AdaGrad never forgets: after 100 days of studying, your study pace drops to absolute zero, and you can never learn anything new!
- $$\mathbf{s}_{t+1} = \mathbf{s}_t + \mathbf{g}_t^2, \quad \mathbf{w}_{t+1} = \mathbf{w}_t - \frac{\alpha}{\sqrt{\mathbf{s}_{t+1}} + \epsilon} \mathbf{g}_t$$
- Learning goalDerive AdaGrad's coordinate scaling and prove why monotonic squared gradient accumulation causes premature training stagnation.
- Helpful foundationsVanilla SGD coordinate updates · Sparse word embeddings and one-hot inputs · Adaptive Subgradient Methods for Online Learning (Duchi et al., 2011)
- Common trapBelieving AdaGrad's learning rate decay can be reversed; because sum-of-squares is monotonic, AdaGrad can only ever decrease effective learning rate.
- Next connectionSee how RMSProp cures this fatal accumulation trap in Chapter 26 using an Exponential Moving Average.
More context & mechanics
AdaGrad maintains an accumulator s_t of historical squared gradients:
s_(t+1) = s_t + g_t \odot g_t = ∑_(τ=1)^(t+1) g_τ²
w_(t+1) = w_t - (α) / (√(s_(t+1)) + ε) \odot g_t
- Sparse / Infrequent Features: Historical sum sᵢ remains small ⟹ effective learning rate (α) / (√(sᵢ)) remains large.
- Dense / Frequent Features: Historical sum sⱼ accumulates rapidly ⟹ effective learning rate shrinks to prevent overshooting.
- The Fatal Flaw: Because g² ≥ 0, s_t is monotonically non-decreasing: s_(t+1) ≥ s_t. In deep architectures, lim_(t → ∞) (α) / (√(s_t)) = 0, freezing the network before reaching the minimum.
Let initial learning rate α = 1.0 and ε = 10^(-8). Consider a parameter with constant gradient g = 0.5:
- Step 1: s₁ = 0 + 0.25 = 0.25 ⟹ α_(eff) = (1.0) / (√(0.25)) = 2.0 ⟹ Δ w = 1.0.
- Step 10: s_(10) = 10 × 0.25 = 2.50 ⟹ α_(eff) = (1.0) / (√(2.50)) = 0.632.
- Step 1,000: s_(1000) = 250 ⟹ α_(eff) = (1.0) / (√(250)) = 0.063.
- Step 100,000: s_(100000) = 25000 ⟹ α_(eff) = (1.0) / (158.1) = 0.0063 (Learning rate collapsed by 99.7%!).
Ideal for sparse textual embeddings (Word2Vec, GloVe), but abandoned for deep neural networks.
Proposed by John Duchi, Elad Hazan, and Yoram Singer (2011) in 'Adaptive Subgradient Methods for Online Learning and Stochastic Optimization'.
Reward the rare, restrain the frequent; but infinite memory means early death.
How does accumulating past squared gradients adaptively scale learning rates individually for frequent versus rare features?
Imagine you are coaching a soccer team where one star striker gets the ball 50 times per game, while the backup goalkeeper touches the ball only once every three games. If you give both players the exact same 30-minute intense lecture after every ball touch, the striker is completely exhausted from over-coaching, while the goalkeeper barely learns anything. AdaGrad keeps a personal logbook for each player: frequent players get tiny, refined micro-adjustments; rare players get big, decisive learning boosts whenever they finally touch the ball.
- $$Divide parameter updates coordinate-wise by the square root of the accumulated sum of historical squared gradients G_t = G_{t-1} + g_t^2.$$
- Learning goalImplement the AdaGrad update rule and demonstrate how coordinate learning rates dynamically adapt to gradient frequency.
- Helpful foundationsElement-wise vector operations · Adaptive Subgradient Methods (Duchi, Hazan, Singer, 2011)
- Common trapBelieving AdaGrad's learning rate can recover after decaying; because G_t strictly sums positive numbers, G_t is monotonically non-decreasing, meaning effective learning rates can ONLY decrease.
- Next connectionWhat happens when G_t keeps growing forever? We discover AdaGrad's fatal flaw.
More context & mechanics
AdaGrad maintains an accumulated sum-of-squares vector G_t ∈ R^d, initialized to 0:
G_t = G_(t-1) + g_t²
Where g_t² = g_t \odot g_t is the element-wise square of the gradient.
The parameter update is:
w_(t+1) = w_t - (η) / (√(G_t) + ε) \odot g_t
Where ε ≈ 10^(-8) prevents division by zero.
Behavior across coordinate regimes:
- Frequent, Large Gradients (gᵢ² ≫ 0): G_(t, i) accumulates rapidly, shrinking (η) / (√(G_(t, i))). This prevents instability along steep, over-represented features.
- Sparse, Rare Gradients (gᵢ ≈ 0 most steps): G_(t, i) remains tiny. When a rare gradient occurs, its effective learning rate (η) / (√(G_(t, i))) remains large, ensuring decisive parameter updates.
AdaGrad was instrumental in training early NLP models with sparse one-hot vocabulary features (e.g. GloVe word embeddings by Pennington et al., 2014) and recommendation system embedding tables (DLRM).
John Duchi, Elad Hazan, and Yoram Singer published AdaGrad in 2011 in JMLR ('Adaptive Subgradient Methods for Online Learning and Stochastic Optimization').
- Sum of squared gradients in the denominator.
- Frequent features get dialed down; rare features get boosted.
Why does AdaGrad's monotonically growing gradient accumulator inevitably freeze learning in deep neural networks?
Imagine writing notes with a pencil whose lead wears down by 1% on every single letter you write, but which can never be sharpened. During chapter 1, the pencil writes bold, beautiful sentences. But by chapter 5, the lead has worn down to a flat wooden stump: you can push as hard as you want, but no graphite marks appear on the page. AdaGrad is that unsharpened pencil: its historical memory has no erase button. After 50,000 steps, its denominator is so enormous that learning completely freezes, even if you are miles away from the solution.
- $$Prove that because G_t = sum_{k=1}^t g_k^2 is monotonically non-decreasing, effective learning rate eta / sqrt(G_t) asymptotically decays to zero.$$
- Learning goalProve that AdaGrad's effective step size asymptotically converges to zero and explain why it causes training stagnation.
- Helpful foundationsInfinite series convergence · Monotone sequences · Adaptive Subgradient Methods for Online Learning (Duchi et al., 2011)
- Common trapAssuming restarting AdaGrad with fresh buffers solves the problem cleanly; manual resets discard useful local variance information, which is why an automatic exponential moving average is needed.
- Next connectionHow do we give the accumulator an automatic 'erase button' so it remembers recent history while forgetting ancient steps? We examine RMSProp.
More context & mechanics
In AdaGrad, the accumulator is a cumulative sum:
G_(t, i) = ∑_(k=1)^t g_(k, i)²
Since g_(k, i)² ≥ 0:
G_(t, i) ≥ G_(t-1, i) ⟹ lim_(t → ∞) G_(t, i) = ∞
The effective step size for coordinate i is:
η_(t, i)^(effective) = (η) / (√(G_(t, i)) + ε)
As training progresses:
lim_(t → ∞) η_(t, i)^(effective) = 0
Consequences in deep learning:
- Premature Freezing: Early training steps (which are noisy and far from optimal) contribute massive squared gradients, permanently depressing the learning rate before the optimizer ever reaches the true valley.
- Inability to Adapt to Changing Curvature: If the model transitions into a new optimization regime, it cannot accelerate because historical memory cannot be discarded.
Because of this fatal freezing, AdaGrad is completely unsuitable for training modern deep neural networks (Transformers, CNNs) over hundreds of thousands of iterations.
This limitation was recognized almost immediately after AdaGrad's release, prompting Matthew Zeiler to invent ADADELTA (2012) and Geoffrey Hinton to propose RMSProp (2012).
- Accumulator strictly grows; learning rate strictly dies.
- A pencil that never sharpens cannot write deep learning history.