AdaGrad

⚡ Key Takeaways

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(\sqrt{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.

💡 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.

DefinitionAdaGrad Update Rule

Let $f_t : \mathbb{R}^d \to \mathbb{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:

1

\quad G_t = \sum_{\tau=1}^{t} g_\tau g_\tau^{\top}, \qquad (G_t)_{jj} = \sum_{\tau=1}^{t} g_{\tau,j}^2

Derivation hint: 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):

2

\quad x_{t+1,j} = x_{t,j} - \frac{\eta}{\sqrt{\textstyle\sum_{\tau=1}^{t} g_{\tau,j}^2} + \epsilon}\; g_{t,j}

Derivation hint: divide the global step $\eta$ by the square root of the accumulated squared gradient for coordinate $j$ ; $\epsilon>0$ prevents division by zero. In compact vector notation, with $s_t = s_{t-1} + g_t \odot g_t$ (elementwise):

3

\quad x_{t+1} = x_t - \eta\, \frac{g_t}{\sqrt{s_t} + \epsilon}

Derivation hint: $\odot$ is the Hadamard product and $\sqrt{\cdot}$ is elementwise; this is exactly [2] stacked across coordinates. Symbols: $x_t \in \mathbb{R}^d$ parameters, $\eta>0$ master learning rate, $g_t$ (sub)gradient, $s_t$ accumulator (= $\mathrm{diag}(G_t)$ ), $\epsilon \approx 10^{-8}$ numerical stabilizer, $\odot$ elementwise product.

DefinitionFull-Matrix (Mahalanobis) AdaGrad

The original general form preconditions by the full matrix:

4

\quad x_{t+1} = x_t - \eta\, G_t^{-1/2} g_t, \qquad G_t = \sum_{\tau=1}^t g_\tau g_\tau^\top

Derivation hint: 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$ .

TheoremRegret Bound for Diagonal AdaGrad

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

5

\quad R_T = \sum_{t=1}^{T} \big(f_t(x_t) - f_t(x^\star)\big) \;\le\; 2 D_\infty \sum_{j=1}^{d} \sqrt{\sum_{t=1}^{T} g_{t,j}^2}

Derivation hint: substitute the AdaGrad proximal metric into the standard online-mirror-descent regret inequality, then use the telescoping bound $\sum_t g_{t,j}^2 / \sqrt{s_{t,j}} \le 2\sqrt{s_{T,j}}$ . In the worst case $\sum_t g_{t,j}^2 \le G_\infty^2 T$ , giving $R_T = O(D_\infty G_\infty \sqrt{dT})$ , but when gradients are sparse the data-dependent right side of [5] is dramatically smaller.

ProofRegret Bound via Adaptive Mirror Descent — Sketch

Step 1 (Proximal step in a time-varying norm). Define the Mahalanobis norm $\|u\|_{H_t} = \sqrt{u^\top H_t u}$ with $H_t = \mathrm{diag}(\sqrt{s_t})$ . The AdaGrad update [3] is the proximal step

x_{t+1} = \arg\min_{x\in\mathcal{X}} \;\eta\, \langle g_t, x\rangle + \tfrac{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^\star) \le \langle g_t, x_t - x^\star\rangle.

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

\langle g_t, x_t - x^\star\rangle \le \frac{1}{2\eta}\Big(\|x_t - x^\star\|_{H_t}^2 - \|x_{t+1}-x^\star\|_{H_t}^2\Big) + \frac{\eta}{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 $\tfrac{1}{2\eta} D_\infty^2 \sum_j \sqrt{s_{T,j}}$ .

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

\sum_{t=1}^{T} \frac{g_{t,j}^2}{\sqrt{\sum_{\tau\le t} g_{\tau,j}^2}} \le 2\sqrt{\sum_{t=1}^{T} g_{t,j}^2}.

Thus $\sum_t \|g_t\|_{H_t^{-1}}^2 \le 2\sum_j \sqrt{s_{T,j}}$ .

Step 6 (Combine and optimize $\eta$ ). Adding the two pieces and choosing $\eta \propto D_\infty$ balances them, producing the bound [5]. $\qquad\blacksquare$

∎

JD

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.

🧠 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/\sqrt{t}$ for a coordinate that fires every step — the canonical optimal SGD schedule — but stay near $\eta$ 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.

Figure

Per-coordinate effective learning rate

\eta/\sqrt{s_{t}}

vs. step

t

for a frequent (dense) vs. rare (sparse) coordinate

ExampleSingle coordinate, repeated gradient

Given: One parameter, $\eta = 0.5$ , $\epsilon = 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/\sqrt{4} = 0.5$ . $x_2 = 10 - 0.5 = 9.5$ .
$t=2$ : $s_2 = 4+4 = 8$ , step $= 0.5 \cdot 2/\sqrt{8} = 1.0/2.828 = 0.3536$ . $x_3 = 9.5 - 0.3536 = 9.1464$ .
$t=3$ : $s_3 = 12$ , step $= 1.0/\sqrt{12} = 0.2887$ . $x_4 = 9.1464 - 0.2887 = 8.8577$ .

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

\boxed{x_2=9.5,\; x_3=9.146,\; x_4=8.858 \ \text{(dimensionless parameter units)}}

ExampleTwo coordinates: dense vs. sparse

Given: $\eta = 1$ , $\epsilon = 0$ , two coordinates. Coordinate 1 (dense) gets gradient $1$ at every step. Coordinate 2 (sparse) gets gradient $0$ at $t=1,2$ and gradient $3$ at $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/\sqrt{3} = 0.5774$ .
Coord 2 at $t=3$ : $s_{3,2} = 0+0+9 = 9$ , update $= 1\cdot 3/\sqrt{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$ .

\boxed{\Delta x_1 = 0.577,\quad \Delta x_2 = 1.000 \ \text{(parameter units)}}

⚠️ Common mistake

AdaGrad does not have a single learning rate that you tune to convergence speed alone. The master rate $\eta$ sets the scale, but the effective per-coordinate rate is $\eta/(\sqrt{s_{t,j}}+\epsilon)$ , 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.

⚠️ Common mistake

$\epsilon$ is not just a numerical guard — it caps the maximum effective learning rate. Early on, when $s_{t,j}$ is tiny, the term $\eta/(\sqrt{s_{t,j}}+\epsilon)$ would explode without $\epsilon$ . Setting $\epsilon$ too small can cause enormous first steps; too large effectively reduces AdaGrad to vanilla SGD with rate $\eta/\epsilon$ .

Counterexample

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.

connection

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).

🔬 Where this appears

⏳ History

- 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.

open-problem

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/\sqrt{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 $\eta$ and $\epsilon$ 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.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also