AdaGrad

AdaGrad (Adaptive Gradient algorithm) is a first-order stochastic optimization method that scales each coordinate's learning rate inversely by the square root of the accumulated sum of squared past gradients. Key result: it achieves regret

O (T)

for convex problems while automatically adapting per-feature step sizes, excelling on sparse data. Applies to convex and non-convex stochastic optimization, prominently in machine learning. Introduced by John Duchi, Elad Hazan, and Yoram Singer in 2011.

AdaGrad modifies plain stochastic gradient descent by maintaining a running sum of the squares of all previously observed gradients on a per-coordinate basis, then dividing the global learning rate by the square root of this accumulator. This yields effective learning rates that shrink quickly for frequently-updated (dense) coordinates and stay large for rarely-updated (sparse) coordinates, making it ideal for problems with heavy-tailed feature frequencies such as text and recommendation systems. It matters because it was among the first principled, theoretically grounded adaptive learning-rate methods, with a tight regret bound derived from online convex optimization. The surprising fact: even though AdaGrad uses only first-order information, its per-coordinate preconditioner approximates a diagonal of the Mahalanobis geometry induced by the data, giving it a quasi-second-order flavor at linear cost. Its chief weakness — monotonic decay of the learning rate to zero — directly motivated the successors RMSProp and Adam.

The Core Insight

Treat the cumulative magnitude of each coordinate's gradient history as a measure of how "well-explored" that coordinate is. Coordinates whose gradients have been large and frequent have been learned about a lot, so their step should be damped; coordinates seen rarely deserve aggressive updates. The mechanism is a diagonal preconditioner $G_{t}^{- 1/2}$ built purely from accumulated squared gradients — turning a single scalar learning rate into a data-driven, per-parameter, time-varying vector of learning rates.

Formal Statement

AdaGrad Update Rule

Let $f_{t} : R^{d} \to R$ be the (sub)differentiable loss at step $t$ , and $g_{t} \in \partial f_{t} (x_{t})$ a (sub)gradient. AdaGrad maintains an accumulator and updates parameters as follows.

The diagonal accumulator:

G_{t} = τ = 1 \sum t g_{τ} g_{τ}^{⊤}, (G_{t})_{j j} = τ = 1 \sum t g_{τ, j}^{2}

⟳full-matrix AdaGrad uses the outer-product sum; the practical diagonal version keeps only the diagonal entries, the per-coordinate sum of squared gradients.

The per-coordinate update (diagonal form):

x_{t + 1, j} = x_{t, j} - \frac{η}{\sum _{τ = 1}^{t} g _{τ, j}^{2} + ϵ} g_{t, j}

⟳divide the global step

η

by the square root of the accumulated squared gradient for coordinate

j

;

ϵ > 0

prevents division by zero.

In compact vector notation, with $s_{t} = s_{t - 1} + g_{t} ⊙ g_{t}$ (elementwise):

x_{t + 1} = x_{t} - η \frac{g _{t}}{s _{t} + ϵ}

⟳

⊙

is the Hadamard product and

\cdot

is elementwise; this is exactly [2] stacked across coordinates.

Symbols: $x_{t} \in R^{d}$ parameters, $η > 0$ master learning rate, $g_{t}$ (sub)gradient, $s_{t}$ accumulator (= $diag (G_{t})$ ), $ϵ \approx 1 0^{- 8}$ numerical stabilizer, $⊙$ elementwise product.

Full-Matrix (Mahalanobis) AdaGrad

The original general form preconditions by the full matrix:

x_{t + 1} = x_{t} - η G_{t}^{- 1/2} g_{t}, G_{t} = τ = 1 \sum t g_{τ} g_{τ}^{⊤}

⟳this arises from choosing the proximal/Mahalanobis norm

∥ \cdot ∥_{G_{t}}

that minimizes the regret bound; the diagonal version is its scalable approximation.

This costs $O (d^{2})$ storage and $O (d^{3})$ per step (matrix inverse-square-root), so it is rarely used directly for large $d$ .

Regret Bound for Diagonal AdaGrad

Let $X \subseteq R^{d}$ be a closed convex feasible set with diameter $D_{\infty} = sup_{x, y \in X} ∥ x - y ∥_{\infty}$ , and let each $f_{t}$ be convex with bounded subgradients. Diagonal AdaGrad (with projection onto $X$ ) satisfies, against any fixed $x^{⋆} \in X$ :

R_{T} = t = 1 \sum T (f_{t} (x_{t}) - f_{t} (x^{⋆})) \leq 2 D_{\infty} j = 1 \sum d t = 1 \sum T g_{t, j}^{2}

⟳substitute the AdaGrad proximal metric into the standard online-mirror-descent regret inequality, then use the telescoping bound

\sum_{t} g_{t, j}^{2} / s_{t, j} \leq 2 s_{T, j}

In the worst case $\sum_{t} g_{t, j}^{2} \leq G_{\infty}^{2} T$ , giving $R_{T} = O (D_{\infty} G_{\infty} d T)$ , but when gradients are sparse the data-dependent right side of [5] is dramatically smaller.

Why It Holds / Derivation

Regret Bound via Adaptive Mirror Descent — Sketch

Step 1 (Proximal step in a time-varying norm). Define the Mahalanobis norm

∥ u ∥_{H_{t}} = u^{⊤} H_{t} u

with

H_{t} = diag (s_{t})

. The AdaGrad update [3] is the proximal step

x_{t + 1} = ar g x \in X min η ⟨ g_{t}, x ⟩ + \frac{1}{2} ∥ x - x_{t} ∥_{H_{t}}^{2} .

Step 2 (Convexity gives a linear bound). By convexity of

f_{t}

f_{t} (x_{t}) - f_{t} (x^{⋆}) \leq ⟨ g_{t}, x_{t} - x^{⋆} ⟩ .

Step 3 (Per-step descent inequality). Standard analysis of the proximal step yields, for each

t

⟨ g_{t}, x_{t} - x^{⋆} ⟩ \leq \frac{1}{2 η} (∥ x_{t} - x^{⋆} ∥_{H_{t}}^{2} - ∥ x_{t + 1} - x^{⋆} ∥_{H_{t}}^{2}) + \frac{η}{2} ∥ g_{t} ∥_{H_{t}^{- 1}}^{2} .

Step 4 (Telescoping the metric-difference terms). Summing over

t

, the difference of distance terms telescopes; because

H_{t}

is increasing in

t

(entries grow), the residual is controlled by

\frac{1}{2 η} D_{\infty}^{2} \sum_{j} s_{T, j}

. Step 5 (Bounding the gradient terms). The key adaptive lemma states, for any nonnegative sequence,

t = 1 \sum T \frac{g _{t, j}^{2}}{\sum _{τ \leq t} g _{τ, j}^{2}} \leq 2 t = 1 \sum T g_{t, j}^{2} .

Thus

\sum_{t} ∥ g_{t} ∥_{H_{t}^{- 1}}^{2} \leq 2 \sum_{j} s_{T, j}

. Step 6 (Combine and optimize $η$ ). Adding the two pieces and choosing

η \propto D_{\infty}

balances them, producing the bound [5].

■

John Duchi, Elad Hazan, Yoram Singer | active 2010s–present

Though all three are computer scientists/applied mathematicians rather than physicists, they are the architects of AdaGrad. Duchi (Stanford) specializes in stochastic optimization and statistical learning; Hazan (Princeton) is a foundational figure in online convex optimization and regret minimization; Singer (then at Google) contributed expertise in large-scale machine learning. Their 2011 JMLR paper "Adaptive Subgradient Methods for Online Learning and Stochastic Optimization" unified online learning regret theory with practical deep-learning optimization, and the adaptive lemma (Step 5 above) is the technical heart of the entire adaptive-method family that includes RMSProp, AdaDelta, and Adam.

Building Intuition

Imagine descending a long, narrow valley whose floor is shaped differently along each axis: one direction is steep and bumpy, another is a shallow, gentle slope explored only rarely. Plain SGD uses the same step size in all directions, so it either overshoots the steep axis or crawls along the shallow one. AdaGrad keeps a "budget meter" per axis recording how much gradient signal has already arrived there. Axes that have received a lot of strong gradient feedback get their step size throttled (we already know a lot about them), while axes touched only occasionally retain large, aggressive steps. The square root is crucial: it makes the per-coordinate effective rate decay like $1/ t$ for a coordinate that fires every step — the canonical optimal SGD schedule — but stay near $η$ for a coordinate that fires rarely. Geometrically, $G_{t}^{- 1/2}$ rescales space so the loss looks locally isotropic, mimicking a Newton-style preconditioner using only first-order data.

Per-coordinate effective learning rate $\eta/\sqrt{s_{t}}$ vs. step $t$ for a frequent (dense) vs. rare (sparse) coordinate

Worked Examples

Single coordinate, repeated gradient

Given: One parameter,

η = 0.5

ϵ = 0

, and constant gradient

g_{t} = 2

at every step. Compute

x_{1} \to x_{4}

starting from

x_{1} = 10

. Steps:

$t = 1$ : $s_{1} = 2^{2} = 4$ , step $= 0.5 \cdot 2/ 4 = 0.5$ . $x_{2} = 10 - 0.5 = 9.5$ .
$t = 2$ : $s_{2} = 4 + 4 = 8$ , step $= 0.5 \cdot 2/ 8 = 1.0/2.828 = 0.3536$ . $x_{3} = 9.5 - 0.3536 = 9.1464$ .
$t = 3$ : $s_{3} = 12$ , step $= 1.0/ 12 = 0.2887$ . $x_{4} = 9.1464 - 0.2887 = 8.8577$ .

Notice the step shrinks even though the gradient is constant — the hallmark $1/ t$ decay.

x_{2} = 9.5, x_{3} = 9.146, x_{4} = 8.858 (dimensionless parameter units)

Two coordinates: dense vs. sparse

Given:

η = 1

ϵ = 0

, two coordinates. Coordinate 1 (dense) gets gradient

1

at every step. Coordinate 2 (sparse) gets gradient

0

t = 1, 2

and gradient

3

t = 3

. Compute the magnitude of each coordinate's update at

t = 3

. Steps:

Coord 1 at $t = 3$ : $s_{3, 1} = 1 + 1 + 1 = 3$ , update $= 1 \cdot 1/ 3 = 0.5774$ .
Coord 2 at $t = 3$ : $s_{3, 2} = 0 + 0 + 9 = 9$ , update $= 1 \cdot 3/ 9 = 3/3 = 1.0$ .

Despite coordinate 2's gradient being three times larger, its first update is not over-damped because its accumulator only just turned on. The dense coordinate is already throttled to $0.577$ .

Δ x_{1} = 0.577, Δ x_{2} = 1.000 (parameter units)

Common Misconceptions

AdaGrad does not have a single learning rate that you tune to convergence speed alone. The master rate

η

sets the scale, but the effective per-coordinate rate is

η / (s_{t, j} + ϵ)

, which monotonically decreases. A frequent mistake is to expect AdaGrad to keep making progress late in training; because

s_{t, j}

never decreases, the effective rate eventually becomes negligibly small and learning stalls. This is the defining flaw that RMSProp fixes by using an exponential moving average instead of a cumulative sum. $ϵ$ is not just a numerical guard — it caps the maximum effective learning rate. Early on, when

s_{t, j}

is tiny, the term

η / (s_{t, j} + ϵ)

would explode without

ϵ

. Setting

ϵ

too small can cause enormous first steps; too large effectively reduces AdaGrad to vanilla SGD with rate

η / ϵ

. AdaGrad can fail to converge on simple non-stationary or non-convex problems specifically because of accumulator monotonicity. Consider an online problem where the optimal direction reverses after many steps (a shifting target). By the time the shift occurs,

s_{t, j}

has grown large, so the effective learning rate is far too small to track the new optimum — AdaGrad freezes near the stale solution. Plain SGD with a constant rate, by contrast, keeps adapting. This concrete failure motivated AdaDelta (2012) and RMSProp, which forget old gradient information geometrically.

Connections

AdaGrad sits at the intersection of Online Convex Optimization and Stochastic Gradient Descent. Its regret analysis is a specialization of Online Mirror Descent with a time-varying, data-adaptive Bregman divergence. The full-matrix form [4] is a first-order approximation to Newton's Method in Optimization, replacing the Hessian with the empirical Fisher-like matrix $G_{t}$ , linking it to Natural Gradient Descent and the Fisher Information Matrix. Its decay flaw is repaired by exponential averaging in RMSProp and AdaDelta, and combined with momentum it becomes Adam (optimizer). The per-coordinate preconditioner also relates to diagonal Preconditioning (numerical analysis).

Real-World Applications

Large-scale text classification / NLP — AdaGrad's sparsity advantage shines on bag-of-words and TF-IDF features where most coordinates are zero in any example; rare words get large updates. Used in early Google text systems.
Recommender systems — User/item embedding tables are extremely sparse per update; AdaGrad adapts per-embedding-coordinate rates, a pattern still seen in sparse embedding optimizers.
GloVe word embeddings — Pennington, Socher & Manning (2014) explicitly used AdaGrad to train the GloVe co-occurrence factorization, exploiting heavily skewed word-frequency statistics.
Click-through-rate (CTR) prediction in ad systems — High-dimensional sparse categorical features benefit from per-feature adaptive rates; AdaGrad and its sibling FTRL-Proximal became industry standards.
Early deep learning training — Before Adam, AdaGrad was a common default for training feedforward and convolutional nets in libraries such as Theano and early TensorFlow.
Online learning / streaming — Its regret guarantees make it appropriate for one-pass, adversarial-data streaming settings where no fixed schedule can be pre-tuned.
Structured prediction (CRFs, parsers) — Adaptive per-feature rates help when feature templates fire at wildly different frequencies.

Historical Development

2003–2007 — Foundations of online convex optimization and regret minimization laid by Zinkevich (online gradient descent, 2003) and Hazan and collaborators; mirror descent (Nemirovski–Yudin) provides the geometric backbone.
2010 (June) — Duchi, Hazan & Singer present the conference version "Adaptive Subgradient Methods for Online Learning and Stochastic Optimization" at COLT.
2011 (July) — The expanded journal version appears in the Journal of Machine Learning Research (JMLR), establishing both full-matrix and diagonal AdaGrad with rigorous regret bounds.
2011 — McMahan & Streeter independently derive closely related adaptive bounds; their work feeds into FTRL-Proximal.
2012 — Zeiler proposes AdaDelta, directly addressing AdaGrad's monotonic-decay flaw via a windowed/EMA accumulator and unit correction.
2012 — Tieleman & Hinton introduce RMSProp in a Coursera lecture, replacing the cumulative sum with an exponential moving average — the most enduring fix.
2013–2014 — AdaGrad adopted for GloVe embeddings (Pennington et al., 2014) and widely used in industrial sparse-learning pipelines.
2014 (December) — Kingma & Ba publish Adam, fusing RMSProp-style second-moment estimation with momentum and bias correction, becoming the dominant successor.
2018–2019 — Renewed theoretical scrutiny of adaptive methods (Reddi et al.'s "On the Convergence of Adam"; AMSGrad) re-examines AdaGrad's clean guarantees as a benchmark for non-convergence pathologies in EMA-based variants.

Subtleties & Limits

The cleanest theoretical guarantees for AdaGrad are in the convex regret setting; its behavior in modern non-convex deep learning is far less understood. Open and active questions include: (1) tight non-convex convergence rates for diagonal AdaGrad and whether they match SGD's $O (1/ T)$ stationarity bound without restrictive assumptions; (2) the generalization gap — adaptive methods like AdaGrad/Adam sometimes generalize worse than tuned SGD despite faster training (Wilson et al., 2017), and the precise mechanism remains debated; (3) when, theoretically, the full-matrix preconditioner [4] is worth its $O (d^{2})$ cost, and whether low-rank or Kronecker-factored approximations (Shampoo, K-FAC) recover most of its benefit; (4) principled, automatic schedules for $η$ and $ϵ$ that remove the remaining hyperparameters. The monotonic decay of $s_{t}$ is not merely an engineering nuisance but a fundamental tension between provable regret and adaptivity to non-stationary objectives.