FTRL-Proximal Sparse Logistic Updates

Follow adaptive accumulators to see when an online logistic weight becomes exactly sparse.

FTRL-Proximal Sparse Logistic Updates

Concept Overview

Follow adaptive accumulators to see when an online logistic weight becomes exactly sparse. FTRL-Proximal maintains a lazy dual accumulator for gradients (z) and squared gradients (n), applying L1 regularization analytically at each step. This yields exact zero weights for features that are not sufficiently predictive, making it highly effective for massive, sparse datasets like ad click prediction.

Worked Example

Consider a step with an initial accumulator state z₀ = -0.5, n₀ = 0.25, and current weight w₀ = 0. Let alpha = 1, lambda1 = 0.5, and lambda2 = 0. We receive an example with target y = 1, and feature x₀ = 1. We use a no-intercept logistic model.

We first calculate the prediction: sigmoid(0 * 1) = 0.5.
The gradient for this coordinate is g₀ = (prediction - y) * x₀ = (0.5 - 1) * 1 = -0.5.
Next, we compute the adaptive learning rate term: σ₀ = (sqrt(n₀ + g₀²) - sqrt(n₀)) / alpha = (sqrt(0.25 + 0.25) - 0.5) / 1 = 0.707106 - 0.5 = 0.207106.
We update the dual accumulators simultaneously using the OLD weights and n:
z₀ += g₀ - σ₀ * w₀ = -0.5 - 0.5 - 0.207106 * 0 = -1.0
n₀ += g₀² = 0.25 + 0.25 = 0.5.
Finally, we recompute the weight for the next round. Since |z₀| (1.0) > lambda1 (0.5), the new weight is:
w₀ = -(z₀ - sign(z₀) * lambda1) / ((1 + sqrt(n₀)) / alpha + lambda2) = -(-1.0 - (-1) * 0.5) / (1 + 0.707106) = 0.5 / 1.707106 = 0.292893.

Experiment

Use the FTRL-Proximal Sparse Logistic Updates module to see how dual accumulators create exact sparsity.

Set Examples to Separable, Alpha to 1, and L1 to 0.5. At 4 steps, observe that Weight one is exactly 0.0 while Weight zero is positive.
Change L1 to 0. Notice how Weight one is no longer zero; the sparsity is lost without L1 regularization.
Switch to the Sparse examples dataset. After 4 steps with L1=0, Weight zero climbs to ~0.96. The L1 penalty would have otherwise forced less predictive features to exactly zero early in training.

Limitations

This module implements a two-coordinate, no-intercept logistic regression model to clearly visualize the trajectory of the weights and accumulators. Real-world implementations handle millions of sparse features. Furthermore, this visualization plots the primal weights instead of the dual space where the exact thresholding geometrically occurs. Exact integers and decisions are precise, but algebraically zero floating residuals are subject to floating-point precision limits.

References

The mathematical derivation of this algorithm is well documented in optimization literature:

Ad Click Prediction: a View from the Trenches (McMahan et al., 2013) - Introduces the FTRL-Proximal algorithm, showing how it achieves excellent predictive accuracy while maintaining strict sparsity.

FTRL-Proximal Sparse Logistic Updates