In AdaGrad, how does the running sum of squared gradients set each parameter's step size?

## What the rule is AdaGrad keeps one extra number per parameter: an accumulator that sums that parameter's squared gradients over the entire run. Writing `g` for the current gradient of a single parameter `w`, `lr` for the global learning rate, and `acc` for that parameter's accumulator (initialised to zero): ``` acc <- acc + g * g w <- w - lr * g / (sqrt(acc) + tiny) ``` Every operation is elementwise, so `acc` has exactly the same shape as the parameter tensor and no parameter's history mixes with any other's. `tiny` is a small positive constant that only exists so the first division is safe. The quantity `lr / (sqrt(acc) + tiny)` is what people mean by the *effective learning rate* of that parameter: the global `lr` is a ceiling, and each parameter's own gradient history divides it down. ## Why it is called a per-parameter learning rate The problem AdaGrad attacks is that a single global step size has to be chosen for the worst case. In a real network, parameters differ enormously in the scale of the gradients they see: an input feature measured in millions versus one in fractions, a weight in an early layer versus a late one, a row of an embedding matrix touched by every example versus one touched rarely. With one `lr`, the value has to be small enough not to blow up the largest-gradient parameter, which leaves every small-gradient parameter crawling. Dividing by `sqrt(acc)` fixes this in a strong sense. Suppose a parameter's gradient is roughly a constant `c` on every step. After `t` steps `acc = t * c^2`, so `sqrt(acc) = |c| * sqrt(t)`, and the update becomes ``` lr * c / (|c| * sqrt(t)) = sign(c) * lr / sqrt(t) ``` The gradient's magnitude has cancelled. A parameter with a gradient of 1.0 and one with a gradient of 0.001 move the *same distance* on step `t`. Only the sign survives from the gradient itself. That is the property being bought: AdaGrad equalises the distance travelled per step, not the gradient. The global `lr` is therefore closer to "how far should a parameter move per step" than to "how much should I trust this gradient". ## Why the step only ever shrinks `acc` is a sum of squares, so it is non-decreasing by construction — no gradient value can ever reduce it. That makes the effective learning rate of every parameter non-increasing for the entire run. This is deliberate, not an accident: it is a self-tuning anneal driven by observed gradients rather than by wall-clock progress, and in convex online learning it is exactly what gives AdaGrad its regret guarantee. In a deep, non-convex run it is also the method's main weakness. The `lr / sqrt(t)` decay derived above applies to any parameter whose gradient does not die down, which is most of them on a hard problem. Around a few tens of thousands of steps, the step size has been divided by a couple of hundred, and the loss curve goes flat. Note what is *not* true: the total distance is `sum over t of 1/sqrt(t)`, which grows like `2 * sqrt(T)` and diverges, so the parameters are not frozen — training has become asymptotically slow, not stopped. That distinction gives the diagnostic. Genuine convergence means small gradients: the loss is flat because there is nothing left to descend. A stalled AdaGrad run has a flat loss and gradient norms that are still substantial — the slope is there and the optimizer can no longer walk down it. If you suspect the second, look at gradient magnitudes before you conclude the model has finished. ## Which parameters keep their step size Because `acc` sums only that parameter's own gradients, a parameter that receives a gradient of zero contributes nothing on that step and its effective learning rate is unchanged. Parameters that are active on every batch with large gradients are damped hardest and fastest; quiet or rarely active parameters keep a small denominator and therefore a large step for far longer. This is the frequency-equalising behaviour that made AdaGrad the natural choice for models with many rarely seen parameters. ## What to remember Three claims cover almost every interview answer on AdaGrad. First, the denominator is that parameter's own accumulated squared gradients, which makes the step size scale-free. Second, because the accumulator is a sum, the effective learning rate is monotonically non-increasing for the whole run. Third, that monotonicity is a feature in a convex online setting and a liability in a long deep-learning run, where it produces a flat loss curve with a live gradient. Replacing the sum with a forgetful average is the standard fix, and it is what RMSProp does.