How do AdaGrad and RMSProp differ on rare parameters in a mostly-sparse embedding table?

## The setting Consider a model whose largest parameter block is an embedding table with a couple of million ids — products, advertisers, items — where usage is long-tailed: a few thousand ids appear in nearly every batch, and the great majority appear a handful of times in an entire epoch. The gradient for such a table is *sparse*: on any given step, only the rows corresponding to ids present in that minibatch receive a non-zero gradient, and every other row's gradient is exactly zero. The interesting question is what each optimizer's per-parameter state does on the steps where a parameter's gradient is zero, because that is the overwhelming majority of steps for a tail row. ## AdaGrad: the accumulator is a per-parameter clock AdaGrad maintains `acc <- acc + g * g` and steps by `lr * g / (sqrt(acc) + tiny)`. A zero gradient adds zero, so `acc` is unchanged: a row that is not touched neither advances nor decays. That means `acc` for row `i` after the whole run reflects only the `k_i` occasions on which that row actually received a gradient — it is a counter of that row's own experience, not of global training steps. If the non-zero gradients for a row are of typical magnitude `c`, then `acc` is about `k_i * c^2` and the step is about `lr / sqrt(k_i)`. A head id seen a million times steps at roughly `lr / 1000`; a tail id seen four times steps at roughly `lr / 2`. Both have made comparable *total* progress for the evidence they have each seen, which is precisely the frequency-equalising behaviour AdaGrad is famous for on sparse problems. Nobody has to hand-tune a separate learning rate for rare features; the accumulator does it from the data. The failure mode of this on a long run is the mirror image. Head rows are the ones whose accumulators grow fastest, so they are the first to effectively stop moving. If the behaviour of your most popular items shifts — a seasonal change, a repricing, a new placement — AdaGrad has no mechanism to give those rows their step size back, because a sum of squares cannot forget. Late in a long-lived run you can end up with a model that is still learning the tail and has quietly frozen the head. ## RMSProp: the average decays whether or not there is a signal RMSProp maintains `v <- rho * v + (1 - rho) * g * g`. Feed it a zero gradient and it does *not* stay put: `v` shrinks by a factor `rho`. After `k` idle steps, `v` has fallen to `rho^k` of its previous value — at `rho = 0.9`, a hundred idle steps leaves about `0.9^100`, which is roughly three thousandths of what it was. The next time the row appears in a batch, its step is `lr * g / sqrt(v)`, and with `v` collapsed that step can be one or two orders of magnitude larger than intended. In practice this shows up as tail embeddings taking wild jumps after long gaps, loss spikes when a batch happens to contain several long-idle ids, and a model whose rare-id representations never settle. There is a second framing worth knowing, because it changes the answer. If the squared-gradient statistics are only advanced on the steps where a row actually receives a gradient, then RMSProp's window is measured in *that row's occurrences* rather than in global steps, and the collapse disappears. That is a reasonable design — but note the window is then extremely short in wall-clock terms: at `rho = 0.9`, a tail row's denominator remembers only its last ten appearances, which may span months of traffic. ## How to decide The choice is between two different things you might want. AdaGrad gives you frequency-equalised step sizes and a denominator that cannot decay in the absence of signal, at the cost of never recovering step size for the head. RMSProp gives you statistics that track the current gradient scale, which matters when the catalogue itself turns over and old squared-gradient statistics are genuinely stale, at the cost of instability on rows that go quiet — mitigated by a decay rate much closer to one, or by advancing the statistics per occurrence rather than per step. Two diagnostics separate the failures in practice. Oversized parameter jumps concentrated on rarely-seen rows, especially right after a gap, point at a denominator that decayed while the row sat idle. Popular items whose predictions stop responding to changed behaviour, while tail items keep improving, point at accumulators that have grown too large to forget. ## The caveat that ends the argument All of this rests on sparsity. If gradients for the table were dense — every row touched on every step — then every accumulator advances on every step, the `k_i` in AdaGrad's `lr / sqrt(k_i)` is the same for all rows, and the whole frequency argument evaporates. The choice would then rest on stationarity alone: whether you want a step size that anneals from total history or one that tracks recent gradient scale. Check which regime you are in before reasoning about rare-parameter behaviour.