Online Gradient Descent and FTRL-Proximal

A click-through model at advertising scale sees billions of examples a day, each touching a few hundred out of billions of possible features. Two constraints follow. Each example can be looked at once, and the model served at the end has to be sparse, because every non-zero coefficient costs RAM on every serving machine. Plain SGD handles the first and fails the second: add an L1 subgradient to the gradient and coefficients hover near zero without ever landing on it. The fix that shipped was a rewrite of the same update, not a new learning rule.

The neighbouring concept, Online Learning and Regret Bounds, sets out the protocol and the guarantee. This one covers the two algorithms that achieve it and why a difference between them, invisible without regularisation, decides whether a model fits in memory.

Greedy projection and where the square root comes from

The algorithm fits in one line (Zinkevich, 2003, Online Convex Programming and Generalized Infinitesimal Gradient Ascent, ICML). On round \(t\) play \(x_t\) from a convex feasible set \(F\), observe a convex cost \(c_t\), take its gradient \(g_t\), and set

where \(P_F\) is Euclidean projection back onto \(F\). With \(\eta_t = t^{-1/2}\), diameter \(\lVert F \rVert\) and gradient norms bounded by \(\lVert \nabla c \rVert\), Theorem 1 of the paper gives

The two terms have separate origins. The first is the price of starting on the wrong side of \(F\); a larger step size shrinks it. The second is the price of always reacting one round late; a smaller step size shrinks it. A \(1/\sqrt{t}\) schedule balances them. With diameter 1, gradients bounded by 1 and a million rounds, the bound is about \(500 + 1000 = 1500\), an average regret of 0.0015 per round.

FTRL: the same point, computed from a different state

Follow the regularised leader plays the minimiser of all linearised losses so far plus a strong convex regulariser:

With \(R(w) = \lVert w\rVert^2 / 2\eta\) and no constraint, the minimiser is \(w_{t+1} = -\eta\, g_{1:t}\), exactly the point constant-step gradient descent reaches. What differs is the stored state: gradient descent keeps \(w\), FTRL keeps the running gradient sum and recomputes \(w\) from it. McMahan showed that mirror descent and FTRL are equivalent up to where the regulariser is centred, and that the choice matters once a non-smooth term like \(\lambda_1\lVert w\rVert_1\) enters (McMahan, 2011, Follow-the-Regularized-Leader and Mirror Descent: Equivalence Theorems and L1 Regularization, AISTATS). Because FTRL applies the L1 term to the whole accumulated sum rather than to one noisy step, a coordinate is set exactly to zero whenever its accumulated evidence is weaker than \(\lambda_1\).

FTRL-Proximal, as deployed for ad click prediction, centres the quadratic regulariser at past iterates and solves per coordinate in closed form (McMahan et al., 2013, Ad Click Prediction: a View from the Trenches, KDD). Each coordinate stores \(z_i\) (an adjusted gradient sum) and \(n_i\) (a sum of squared gradients), and

The factor \(\alpha / (\beta + \sqrt{n_i})\) is a per-coordinate learning rate: rare features keep large steps, common ones anneal fast.

A worked coordinate

Take \(\alpha = 0.1\), \(\beta = 1\), \(\lambda_1 = 1\), \(\lambda_2 = 0\). A feature with \(n_i = 4\) and \(z_i = -1.5\) has \(|z_i| > \lambda_1\), so \(w_i = -(3/0.1)^{-1}(-1.5 + 1) = 0.5/30 \approx 0.0167\). A feature with \(z_i = 0.8\) gets \(w_i = 0\) exactly and never needs to be shipped to a server, even though it is still tracked during training and can come back if later gradients push \(|z_i|\) past 1.

Measured against FTRL-Proximal at equal accuracy, RDA needed 38% more non-zero coefficients and FOBOS 216% more; a straw-man that simply zeroed features until they had been seen \(k\) times, tuned to match, kept 3% more coefficients and still lost 0.6% AucLoss. Per-coordinate rates alone cut AucLoss by 11.2% against a single global rate, in a setting where 1% counts as large. The approach outlived pure linear models: Wide & Deep trained its wide component with FTRL and L1 while the deep tower used AdaGrad (Cheng et al., 2016, Wide & Deep Learning for Recommender Systems, arXiv:1606.07792).

When it breaks

The guarantee is for convex losses and a fixed comparator. FTRL on a linear model inherits the bound; FTRL on embeddings feeding a network does not, and the per-coordinate rate becomes a useful heuristic rather than a regret-optimal schedule.

Two numbers per coordinate is still a lot. Storing \(z_i\) and \(n_i\) doubles the per-coordinate state of plain SGD. The KDD paper recovered some of it with 16-bit q2.13 fixed-point coefficients using randomised rounding, which saved 75% of coefficient RAM with no measurable loss, and with Bloom-filter feature admission that saved 55 to 66% of RAM at an AucLoss cost below 0.01%.

Annealed rates stop adapting. Because \(\sqrt{n_i}\) only grows, a common feature's step size keeps shrinking, so a shift in its true effect is absorbed slowly. That is the fixed-comparator assumption failing under drift, and a reason to reset or decay accumulators rather than trust one stream forever.

Memory tricks that work elsewhere did not work here. Feature hashing is a standard way to bound RAM, and other groups reported good results hashing into \(2^{24}\) buckets. The Google team could not hash below several billion features without observable loss and kept unhashed, interpretable features instead. Whether hashing is free depends on how much signal lives in rare features, a property of the data, not the optimiser.