Follow-the-Regularized-Leader and Mirror Descent: Equivalence Theorems and L1 Regularization

H. Brendan McMahanAISTATS 2011

Introduction

In the field of online convex optimization, two primary algorithmic families have dominated the landscape: Mirror Descent (MD), exemplified by algorithms like FOBOS, and Follow-the-Regularized-Leader (FTRL), exemplified by Regularized Dual Averaging (RDA). While both frameworks achieve optimal regret bounds, they exhibit significantly different empirical behaviors, particularly regarding model sparsity when using $L_1$ regularization. This paper establishes a formal mathematical bridge between these two families, proving their equivalence under specific conditions and introducing a hybrid algorithm, FTRL-Proximal, which leverages the strengths of both.

Theoretical Framework and Equivalence

The core contribution of this work is the unification of MD and FTRL. Traditionally, MD updates are performed relative to the current weight vector (proximal centering), while FTRL optimizes over the entire history of gradients. The author presents two primary equivalence theorems:

  1. Theorem 2: Establishes that composite-objective mirror descent is equivalent to a "proximal" version of FTRL.
  2. Theorem 4: Demonstrates that mirror descent on a regularized function is equivalent to standard FTRL with origin-centered regularization.

The fundamental difference between existing algorithms lies in two design choices: the centering of the "strong convexity" term (proximal vs. origin-centered) and the handling of the $L_1$ penalty. FOBOS effectively uses "stale" subgradient approximations for previous $L_1$ steps, which "blurs" the sparsity signal. In contrast, RDA and the proposed FTRL-Proximal handle the cumulative $L_1$ penalty exactly at each step, maintaining a "sharp" signal that induces greater sparsity.

The FTRL-Proximal Algorithm

Building on these theoretical insights, the author proposes FTRL-Proximal. This algorithm combines the proximal centering of FOBOS—which provides better stability in the face of changing data distributions—with the cumulative $L_1$ handling of RDA for superior sparsity. By considering the sum of all penalties exactly in a closed-form optimization at each step, FTRL-Proximal achieves a better trade-off between predictive accuracy and model size.

Experimental Evaluation

The algorithms were evaluated across a diverse set of tasks, including sentiment analysis (Books, DVD, Electronics, Kitchen), standard benchmarks (RCV1, News20), and a large-scale industrial Web Search Ads dataset (~1 million impressions) for Click-Through-Rate (CTR) prediction.

Table 1: AUC and model density (in parentheses) across various datasets. Lower density indicates higher sparsity.

Key Results

The experimental results highlight several critical findings:

  • Superior Sparsity: On the news20 dataset, FTRL-Proximal and RDA achieved significantly higher sparsity (densities of 0.052 and 0.054) compared to FOBOS (0.194) for the same level of accuracy (AUC ~0.99).
  • Pareto Dominance: Across most tasks, FOBOS was "Pareto-dominated" by FTRL-Proximal and RDA, meaning the latter algorithms could provide models that were simultaneously more accurate and sparser.
  • Industrial Scale Performance: On the Web Search Ads dataset, FTRL-Proximal demonstrated a clear performance advantage, outperforming both RDA and FOBOS when considering the trade-off between accuracy and sparsity.
Figure 1: Accuracy (AUC) vs. Sparsity (Nonzero Fraction) on the Web Search Ads dataset. FTRL-Proximal shows superior performance across the sparsity spectrum.

Conclusion

This work clarifies the relationship between Mirror Descent and FTRL, showing they are essentially "two sides of the same coin." By identifying that the handling of cumulative non-smooth terms is the key to sparsity, the author provides a principled way to design online learning algorithms. FTRL-Proximal emerges as a robust choice for large-scale applications where both high accuracy and model compactness are required.

Summary updated

BibTeX
@article{mcmahan2011follow,
  author = {H. Brendan McMahan},
  title = {{Follow-the-Regularized-Leader and Mirror Descent: Equivalence Theorems and L1 Regularization}},
  journal = {AISTATS},
  year = {2011},
}
Figure