Adaptive Subgradient Methods for Online Learning and Stochastic Optimization

In standard SGD, every parameter gets the same learning rate $\eta$. The update rule is simple:

$\theta_{t+1} = \theta_t - \eta \, g_t$

where $g_t$ is the gradient at step $t$. This works well when all parameters receive gradients of similar magnitude at similar frequencies. But in the real world, parameters live very different lives.

Consider a language model learning word embeddings. The word "the" appears in almost every sentence — its embedding gets updated thousands of times. The word "serendipity" might appear once in the entire corpus. With a shared learning rate, you face a dilemma: set $\eta$ high enough for "serendipity" to learn, and "the" oscillates wildly. Set it low enough for stability, and "serendipity" barely moves.

This is the sparse feature problem: in NLP, recommender systems, and click-through prediction, most of the predictive power lives in rare features — but a uniform learning rate starves them of the updates they need.

AdaGrad's core idea is deceptively simple: keep a running sum of squared gradients for each parameter, then divide the learning rate by the square root of that sum.

Think of the squared gradient sum as a "mileage counter" for each parameter. A parameter that has been updated many times with large gradients has high mileage — it's already close to where it needs to be, so take smaller steps. A parameter with low mileage has barely been explored — give it a bigger step to compensate.

This is the essence of per-parameter adaptive learning rates: instead of one global $\eta$, each parameter effectively has its own $\eta_i$ that shrinks in proportion to how much gradient signal it has accumulated.

Before we see symbols, let's trace the logic step by step. At each training step, AdaGrad does three things:

Step 1 — Compute the gradient for each parameter, exactly as in standard SGD.

Step 2 — Accumulate: add the square of each gradient component to a running sum. This sum grows monotonically — it never forgets.

Step 3 — Scale the update: divide the gradient by the square root of the accumulated sum, then multiply by the global learning rate. Parameters with large accumulated gradients get smaller effective learning rates; parameters with small accumulated gradients get larger ones.

Notice what happened: we started with a single global learning rate $\eta$ and ended with a different effective learning rate $\eta / \sqrt{G_{t,i}}$ for every parameter $i$. The adaptation is fully automatic — no manual schedule, no per-feature tuning. The only hyperparameter that matters is the initial $\eta$, and AdaGrad is far more robust to its choice than SGD.

There's a deeper way to understand AdaGrad. Standard SGD takes the gradient and steps in that direction with a fixed stride. Geometrically, it treats the loss surface as if it curves equally in all directions — using the identity matrix as a preconditioner.

But real loss surfaces are anisotropic: they curve steeply in some directions and gently in others. Think of a long, narrow valley — SGD bounces off the steep walls while crawling along the valley floor.

AdaGrad implicitly builds a diagonal approximation to the curvature from gradient history. The accumulated $G_t$ acts like the diagonal of the Hessian: large values mean the surface curves sharply there (take shorter steps), small values mean it's flat (take longer steps). The effect is to stretch the narrow valley into a rounder bowl where gradient descent converges naturally.

The full-matrix version of AdaGrad uses the outer product $\sum g_t g_t^T$ as a preconditioner — a complete second-order approximation. The diagonal version approximates this with just the diagonal, trading some accuracy for $O(d)$ memory instead of $O(d^2)$.

The magic of AdaGrad becomes clearest with sparse data. Consider a feature that appears in only 0.1% of training examples. In standard SGD, its gradient is zero 99.9% of the time, so its accumulated $G_{t,i}$ stays small. When the feature finally does appear and produces a nonzero gradient, AdaGrad divides by a small number — giving it a large effective learning rate. The rare feature gets a proportionally larger update, compensating for its infrequent appearances.

Conversely, a feature present in every example accumulates a large $G_{t,i}$ quickly. Its effective learning rate drops, preventing the oscillation that would occur with a fixed high learning rate.

This is why AdaGrad was transformative for NLP and recommender systems: these domains are dominated by sparse, high-dimensional feature spaces where the frequency of features varies by orders of magnitude.

AdaGrad has a critical drawback: the accumulated sum $G_t$ only grows. Every step adds a non-negative value to it, so the effective learning rate $\eta / \sqrt{G_t}$ can only decrease — it never recovers. In convex optimization this is fine: as you approach the minimum, you want to take smaller and smaller steps. In non-convex deep learning, however, the loss landscape has many regions, and a learning rate that decayed in a plateau region can't speed back up when it enters a steep descent.

After many iterations, the effective learning rate can become so small that the model essentially stops learning — the updates become negligible. This is why AdaGrad on its own struggles with deep neural networks that require thousands of epochs.

The paper actually proposes a more general form: instead of tracking only the diagonal, accumulate the full outer product of gradients:

$H_t = \sum_{\tau=1}^{t} g_\tau g_\tau^T$

The update then uses $H_t^{1/2}$ (the matrix square root) as the preconditioner:

$\theta_{t+1} = \theta_t - \eta \, H_t^{-1/2} \, g_t$

This is the optimal preconditioning — it captures correlations between parameters, not just individual magnitudes. But computing and inverting a $d \times d$ matrix every step is infeasible for millions of parameters. The diagonal version $G_t = \text{diag}(H_t)$ is the practical compromise that became "AdaGrad" in common usage.

The full-matrix idea didn't die, though — it re-emerged years later in Shampoo, which finds efficient ways to approximate the full preconditioner for large-scale training.

AdaGrad comes with a formal guarantee from online learning theory. The regret measures how much worse the algorithm performs compared to the single best fixed decision in hindsight. For standard SGD with a fixed learning rate, the regret bound depends on knowing the scale of the gradients in advance. Pick a rate too high and regret explodes; too low and convergence is slow.

AdaGrad's regret bound is:

$R(T) \leq 2 \sum_{i=1}^{d} \|g_{1:T,i}\|_2$

where $\|g_{1:T,i}\|_2 = \sqrt{\sum_{t=1}^{T} g_{t,i}^2}$ is the cumulative gradient norm for parameter $i$. This bound is dimension-dependent but data-adaptive: if most parameters have small gradients (sparse data), the bound is small even in very high dimensions. For sparse problems, this can be dramatically better than SGD's $O(\sqrt{T})$ bound.

In plain language: AdaGrad is provably as good as the best learning rate schedule you could have chosen if you could see the future.

AdaGrad planted the seed, but its descendants grew taller:

RMSProp (Hinton, 2012) — Replaced the ever-growing sum with an exponential moving average of squared gradients: $v_t = \beta v_{t-1} + (1-\beta) g_t^2$. This "forgets" old gradients, so the learning rate stabilizes instead of decaying to zero. Think of it as AdaGrad with a leaky memory.

AdaDelta (Zeiler, 2012) — Similar to RMSProp but also adapts the numerator using an exponential average of squared parameter updates, eliminating the global learning rate entirely.

Adam (Kingma & Ba, 2014) — Combined RMSProp's adaptive second moment with momentum's first-moment moving average, plus bias correction for the initial steps. Became the default optimizer for deep learning.

Shampoo (Gupta et al., 2018) — Resurrected AdaGrad's full-matrix preconditioner, making it practical for large-scale training through Kronecker-product approximations.

Every one of these is a direct answer to AdaGrad's question: how should gradient history shape the update step? They differ only in how much history to remember and how to structure the preconditioner.

Despite its age, AdaGrad remains the right choice in specific settings:

Use AdaGrad when your features are sparse and high-dimensional — click-through rate prediction, large-vocabulary NLP, recommender systems with millions of items. The automatic per-feature adaptation handles the frequency imbalance perfectly, and the monotonic decay is actually a feature: in convex problems, it guarantees convergence.

Use Adam or RMSProp instead when training deep neural networks on dense data (images, audio, continuous signals). The non-convex landscape benefits from a learning rate that can recover after flat regions.

The key intuition: if your problem has features that vary wildly in frequency and your loss is (approximately) convex, AdaGrad is still hard to beat. If you're in deep learning territory with dense gradients and non-convex loss, reach for Adam.