AdaGrad and RMSProp

In plain Stochastic and Mini-Batch Gradient Descent, every parameter $\theta_i$ is updated by the same global learning rate $\eta$:

where $g_i = \partial L / \partial \theta_i$ is the gradient of the loss with respect to that parameter on the current mini-batch. This treats all coordinates identically, which is wasteful when the loss surface is curved very differently along different directions — a common situation in deep networks, where some weights sit in flat regions and others in steep, narrow ravines.

AdaGrad (Adaptive Gradient algorithm) fixes this by maintaining, for each parameter, a running sum of squared gradients seen so far:

Here $r_i$ accumulates over the entire history of training, and $\epsilon$ (typically $10^{-8}$ to $10^{-10}$) prevents division by zero. Because $r_i$ only grows, the effective learning rate $\eta / (\sqrt{r_i}+\epsilon)$ only shrinks — a feature that is provably optimal for the online convex setting AdaGrad was designed for, but becomes a liability in long-running deep network training.

RMSProp (Root Mean Square Propagation) keeps the same denominator idea but replaces the sum with an exponential moving average (EMA) of squared gradients, controlled by a decay rate $\rho$ (commonly $0.9$ or $0.99$):

Because old squared gradients are discounted geometrically, $r_i$ tracks the recent magnitude of gradients rather than their entire history. This lets the effective learning rate rise again if gradients shrink, and shrink again if gradients grow — exactly the adaptivity needed on the nonstationary, nonconvex loss surfaces of deep networks, where the local curvature along a given direction changes substantially as training progresses.

Both algorithms are drop-in replacements for the update rule inside a standard mini-batch training loop. The only state added is one accumulator vector $r$, the same shape as the parameter vector $\theta$. ```

# Shared setup Initialize parameters θ Initialize accumulator r ← 0 (same shape as θ) Choose global learning rate η (e.g., 0.01 for AdaGrad, 0.001 for RMSProp) Choose ε (e.g., 1e-8) Choose decay ρ (RMSProp only, e.g., 0.9) for t = 1, 2, 3, ... until convergence: Sample mini-batch B_t g ← ∇_θ L(θ; B_t) # gradient on this mini-batch, elementwise vector

# --- AdaGrad update --- r ← r + g ⊙ g # elementwise square, accumulate forever Δθ ← -(η / (sqrt(r) + ε)) ⊙ g # elementwise divide θ ← θ + Δθ

# --- RMSProp update (replaces the two lines above) --- r ← ρ · r + (1 - ρ) · (g ⊙ g) # exponential moving average of squared gradient Δθ ← -(η / (sqrt(r) + ε)) ⊙ g θ ← θ + Δθ ``` Every operation above (`⊙`, `sqrt`, `/`) is elementwise — each coordinate $i$ of $\theta$ gets its own scalar accumulator $r_i$ and its own effective step size. No cross-coordinate interaction occurs; this is what makes the method "per-parameter."

Why the square root? Squaring the gradient before accumulating makes $r_i$ track the magnitude of gradients regardless of sign (a large negative gradient should shrink the step just as much as a large positive one). Taking the square root before dividing restores the original units: $g_i / \sqrt{r_i}$ has the same units as $g_i / |g_i|$-scale, i.e., the division converts the raw gradient into something closer to a unit-scaled direction, similar in spirit to a per-coordinate Newton step using a diagonal curvature estimate.

Why $\epsilon$ matters in practice. At $t=1$ for AdaGrad, $r_i = g_i^2$, so the update is $-\eta \, g_i / (|g_i| + \epsilon) \approx -\eta \cdot \text{sign}(g_i)$ when $|g_i| \gg \epsilon$ — the very first step is already close to a fixed-magnitude step in the gradient's direction, not a large uncontrolled step. If $\epsilon$ is too large relative to typical gradient magnitudes, it dominates the denominator and adaptivity is suppressed; if too small, numerical division by a near-zero $r_i$ for a parameter that has genuinely never received a gradient (e.g., an unused embedding row) can produce instability.

Time complexity. Each step requires computing the gradient $g$ (cost dominated by the forward/backward pass of the network, $O(P)$ where $P$ is the number of parameters, same as plain SGD), then performing a constant number of elementwise operations on vectors of length $P$: squaring, one multiply-add for the accumulator update, one square root, one division, one scaled subtraction. All of these are $O(P)$ per step. So AdaGrad and RMSProp cost exactly the same asymptotic time per step as SGD, $O(P)$ beyond the gradient computation itself — the adaptive scaling adds only a small constant-factor overhead (a handful of elementwise vector operations), which is negligible compared to the cost of the forward/backward pass in any real network.

Space complexity. Both methods store one extra vector $r$ of size $P$, i.e., $O(P)$ additional memory — doubling the optimizer's state footprint relative to vanilla SGD (which needs none), but this is standard and modest compared to the memory needed for activations during backpropagation.

Correctness / why it works — AdaGrad. AdaGrad was originally derived and analyzed in the framework of online convex optimization. For a sequence of convex loss functions $f_t$ observed online, and true (not stochastic-noisy) subgradients $g_t = \nabla f_t(\theta_t)$, AdaGrad's diagonal preconditioning achieves a regret bound

which is never worse, and can be much better, than the $O(\sqrt{T})$ bound of plain online gradient descent, especially when gradients are sparse — i.e., when most $g_{t,i}$ are zero for most $t$, so the per-coordinate norm $\|g_{1:T,i}\|_2$ stays small for rarely-updated coordinates. Intuitively: the bound rewards AdaGrad for adapting to geometry — it behaves like an adaptively-chosen diagonal Mahalanobis norm rather than the fixed Euclidean norm implicit in plain gradient descent. The tradeoff is that this same monotonic accumulation, which is what makes the regret bound provable, is exactly what causes the effective learning rate to decay towards zero over a long non-convex training run: since $r_i$ never decreases, $\eta/(\sqrt{r_i}+\epsilon) \to 0$ as $t \to \infty$ whenever gradients keep arriving, and training can stall long before reaching a good minimum.

Correctness / why it works — RMSProp. RMSProp abandons the clean online-regret guarantee in exchange for tracking a nonstationary signal. Because $r_i$ is an exponential moving average with a fixed decay $\rho$, it has an effective "window" of roughly $1/(1-\rho)$ recent steps (e.g., $\rho = 0.9 \Rightarrow$ effective window $\approx 10$ steps): old gradient information is discounted geometrically and eventually forgotten. This means $r_i$ estimates $\mathbb{E}[g_i^2]$ over a sliding recent window rather than over all of history, so if the gradient scale for a coordinate shrinks later in training (e.g., because the network has entered a flatter region), $r_i$ shrinks too and the effective step size grows back — unlike AdaGrad, whose accumulator can never shrink. This adaptivity to a moving target is essential in deep learning, where the loss landscape's local curvature changes continually as other parameters move (the gradient distribution for any one weight is nonstationary due to the other weights changing under it). RMSProp has no known regret bound of the AdaGrad type — it was introduced as an unpublished but widely validated empirical fix, and its justification is primarily the extensive empirical record of successful deep network training, together with the informal argument above about tracking a moving second-moment estimate. This is the honest tradeoff: AdaGrad's guarantee is provable but eventually self-defeating in non-convex deep learning; RMSProp's guarantee is empirical but far more useful in practice.

A shared invariant worth checking. In both algorithms $r_i \ge 0$ always (sums and convex combinations of squares), so $\sqrt{r_i}$ is always well-defined and the denominator $\sqrt{r_i}+\epsilon$ is always strictly positive — the update is always well-defined, never a division by exactly zero, which is the basic well-posedness property any implementation must preserve.

Consider two parameters, $\theta_1$ (a "dense" feature weight receiving a moderate gradient every step) and $\theta_2$ (a "sparse" feature weight receiving a large gradient only occasionally, zero otherwise). Take $\eta = 1$, $\epsilon = 0$ for clarity, $\rho = 0.9$ for RMSProp. Suppose the gradient sequence over 4 steps is:

AdaGrad trace ($r_i \leftarrow r_i + g_i^2$, step $= g_i/\sqrt{r_i}$):

Note the effect: $\theta_1$'s step size shrinks monotonically ($1.00 \to 0.71 \to 0.58 \to 0.50$) purely because it keeps receiving gradients — even though every $g_1$ has the same magnitude, $1.0$, each step. Meanwhile $\theta_2$'s accumulator stays frozen at $r_2=25$ during the zero-gradient steps ($t=2,3$), so when a gradient finally reappears at $t=4$ its step ($0.71$) is comparable to the very first step ($1.00$) — AdaGrad preserved a usable step size for the rare feature.

RMSProp trace ($r_i \leftarrow 0.9\,r_i + 0.1\,g_i^2$, $r_0 = 0$):

RMSProp's step for $\theta_1$ also decreases across these 4 steps ($3.16 \to 2.29 \to 1.92 \to 1.71$) — but it is converging toward a steady state, not decaying to zero. If the gradient sequence for $\theta_1$ continued at $g_1 = 1.0$ forever, $r_1$ would converge to a fixed point $r^\star$ solving $r^\star = 0.9 r^\star + 0.1(1)^2 \Rightarrow r^\star = 1.0$, giving a constant long-run step size of $1/\sqrt{1.0} = 1.0$ — it never vanishes, unlike AdaGrad's ever-shrinking $1/\sqrt{t}$-type decay. This is the crux of the practical difference: run both optimizers for $10{,}000$ more steps with the same constant gradient, and AdaGrad's step for $\theta_1$ keeps shrinking toward zero while RMSProp's settles at a fixed, useful value.

AdaGrad emerged from the online convex optimization community, where the goal was not deep learning specifically but robust, theoretically-grounded online learning with per-coordinate adaptivity for sparse, high-dimensional data such as text and click-through logs. RMSProp, in contrast, was a pragmatic fix proposed within the neural network community once it became clear that AdaGrad's ever-shrinking learning rate was unsuitable for the long, nonconvex training runs required by deep networks.

Adaptive per-parameter learning rates are indispensable whenever a model has features or parameters with wildly different update frequencies or gradient scales. Natural language processing systems with huge, sparse word-embedding tables rely on exactly this property: common words get frequent, well-damped updates while rare words retain large enough steps to actually learn something from their few appearances — a scenario close to the sparse-gradient setting AdaGrad was designed for. RMSProp and its descendants are used extensively in recurrent network training, where gradient magnitudes can vary enormously across time steps and layers, and where the loss surface changes character continuously as training proceeds — exactly the nonstationary regime RMSProp targets. In production deep learning frameworks, both algorithms are available as standard optimizer classes, but RMSProp is more often chosen for practical training given its resistance to premature learning-rate collapse, while AdaGrad persists in linear/convex online-learning systems such as click-through-rate prediction, contextual bandits, and other settings closer to its original theoretical home. Both are also the direct conceptual ancestors of Adam, which layers first-moment (momentum) estimation on top of RMSProp's second-moment adaptive scaling, becoming the default optimizer choice across most of modern deep learning — a connection the study of Adam and Its Variants develops fully.

Ask the tutor: How does adding momentum to RMSProp's adaptive scaling produce the Adam optimizer's update rule?