AdaGrad and RMSProp

Per-parameter learning rates, why AdaGrad dies on dense problems, and RMSProp's fix.

SGD and momentum apply the same learning rate α to every parameter. This breaks as soon as parameters operate at different scales — which they always do in real networks. Word embeddings exposed the problem most clearly. The embedding for "the" appears in nearly every training sentence and accumulates gradients continuously. The embedding for "quasar" appears rarely and receives gradients in sparse bursts. A fixed α that is large enough to meaningfully update "quasar" when it finally appears is too large for "the," which has already converged. You need different effective learning rates for different parameters based on how often and how strongly they are updated. AdaGrad (Duchi et al., 2011) invented this: maintain a running sum of squared gradients per parameter, G_i = Σ g_{i,t}², then scale each step by α/√G_i. Parameters with large historical gradients get smaller steps; parameters with sparse or small gradients get larger steps. For sparse NLP embeddings, this is exactly right — rare words finally get appropriately large updates when they appear. The fatal flaw: G_i only ever grows. For a dense convolutional layer that receives a gradient on every example, G_i grows without bound, and the effective learning rate collapses toward zero.

Training stalls long before convergence. RMSProp fixes this with one change: replace the cumulative sum with an exponential moving average. G_i now reflects recent gradient magnitude rather than all-time total, so it can stabilize or decrease. Dense parameters stop dying.

Key points

• The problem AdaGrad solved was sparse gradients at wildly different scales. SGD with a fixed learning rate was applying the same update size to frequently-updated parameters (which had already converged) and rarely-updated parameters (which needed large updates when they finally appeared). Per-parameter learning rates proportional to gradient history were the solution.
• AdaGrad update: G_i ← G_i + g_i²; θ_i ← θ_i − (α/√(G_i + ε))·g_i. The running sum G_i records how much gradient has flowed through parameter i in total. Parameters with large cumulative gradient history get smaller steps; parameters with small history get larger ones. For word embeddings, this automatically assigns large effective learning rates to rare words and small ones to common words — exactly what manual tuning would have done.
• AdaGrad's fatal failure for dense networks: in a convolutional layer, every filter parameter receives a nonzero gradient on every training example. G_i grows linearly with the number of training steps T. The effective learning rate α/√G_i ≈ α/√T → 0. Assuming average squared-gradient magnitude ≈1 per step (so G_i≈T), the effective rate at T=100,000 versus T=1 has shrunk by √100,000/√1 ≈ 316×. The network stops learning long before it converges. This is not a tuning failure — it is a structural flaw in the algorithm.
• RMSProp patches the flaw with one change: replace the cumulative sum with an exponential moving average. G_i ← ρG_i + (1−ρ)g_i². With ρ=0.9, G_i tracks the recent (≈10-step window) mean squared gradient rather than the all-time total. If gradients stabilize, G_i stabilizes, and the effective learning rate stabilizes instead of decaying to zero. Dense-gradient parameters stay trainable throughout training.
• The connection to curvature: squared gradient magnitude g_i² approximates the diagonal of the Fisher information matrix — a proxy for how steeply the loss curves in the direction of parameter i. Dividing by √G_i approximates a diagonal Newton step, adapting the update to local curvature without the O(n²) cost of computing the full Hessian. AdaGrad and RMSProp are cheap approximate second-order methods.
• RMSProp was invented to train RNNs (proposed by Hinton in an unpublished lecture, 2012). RNNs have wildly variable gradient magnitudes across timesteps — gradients explode on some timesteps and vanish on others. The exponential moving average smooths out spikes while adapting to the typical gradient scale at each point in training, which made RNNs significantly more trainable than with fixed-rate SGD.
• The ρ hyperparameter sets the memory window. ρ=0.9 gives a 10-step window — responds quickly to changes in gradient scale. ρ=0.99 gives 100 steps — more stable but slow to adapt. For highly non-stationary gradient environments (reinforcement learning, tasks with phase transitions), lower ρ is better. For stable supervised learning, ρ=0.9–0.99 both work and the choice matters little.

Recap

• One global LR fails when parameters update at different scales: the embedding for "the" gets a gradient every step, "quasar" once in thousands — a single rate is too big for one and too small for the other.
• AdaGrad gives each parameter its own learning rate: accumulate G_i ← G_i + g_i² and scale the step by α/√(G_i+ε) — parameters with small/rare gradients get big steps, those with large frequent ones get small steps.
• It shines on sparse NLP embeddings: rare words finally receive appropriately large updates instead of being starved by a shared rate tuned for common words.
• AdaGrad's fatal flaw is a monotone accumulator: G_i only ever grows, so on dense layers the effective rate decays like α/√T → 0 and training grinds to a halt long before convergence.
• RMSProp fixes it with one structural change: swap the cumulative *sum* for an exponential moving average, G_i ← ρG_i + (1−ρ)g_i², so the denominator stabilizes at the recent gradient scale instead of decaying to zero — keeping the per-parameter adaptation viable for dense networks.
• The curvature link: g_i² approximates the diagonal of the Fisher information, so dividing the step by √G_i is a cheap stand-in for a diagonal Newton step — borrowing a little of Newton's curvature wisdom without the Hessian's cost.
• RMSProp was built for RNNs (Hinton's 2012 course); ρ=0.9 gives a ~10-step window, ρ=0.99 a ~100-step one — lower ρ for non-stationary settings (RL, phase transitions), either is fine for stable supervised learning.

Check your understanding