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

By H. Brendan McMahan. 2011

267 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Wide & Deep Learning for Recommender Systems (2016, methodology): “In the experiments, we used Follow-the-regularized-leader (FTRL) algorithm [3] with L 1 regularization as the optimizer for the wide part of the model, and AdaGrad [1] for the deep part.”
Practical and Private (Deep) Learning without Sampling or Shuffling (2021, methodology): “Extension to composite losses: Composite losses (Duchi et al., 2010; McMahan, 2011; 2017) refer to the setting where in each round, the algorithm is provided with a function ft(θ) = `(θ; dt) + rt(θ) with rt : C → R being a convex regularizer that does not depend on the data sample dt.”
Evolutionary-Neural Hybrid Agents for Architecture Search (2018, methodology): “The optimizer used for the wide column is FTRL [29].”
Ad click prediction: a view from the trenches (2013, methodology): “In earlier experiments on smaller prototyping versions of our data, McMahan [24] showed that FTRL-Proximal with L 1 regularization signiﬁcantly outper-formed both RDA and FOBOS in terms of the size-versus-accuracy tradeoﬀs produced; these previous results are summarized in Table 1, rows 2 and 3.”
The Interplay Between Stability and Regret in Online Learning (2012, background): “While mirror descent and FTRL look fundamentally different algorithms and were considered to be two different ends of the spectrum for online learning algorithms [21], a recent paper [14] shows equivalence between different mirror descent algorithms and corresponding FTRL counterparts.”
Learning in high-dimensional multimedia data: the state of the art (2015, background): “Online gradient descent [1] generalizes this FTRL by deriving a simple reduction from convex functions to linear functions.”
Large-Scale Learning with Less RAM via Randomization (2013, methodology): “The extension to algorithms that eﬃciently handle L 1 regularization, like RDA (Xiao, 2009) and FTRL-Proximal (McMahan, 2011), is rela-Large-Scale tively straightforward.”
Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent (2014, methodology): “se two steps are totally equivalent (see Appendix A.3). In many other cases, although the steps look dierently, the algorithm using one step can be transformed into that using another, 2 and McMahan [McM11] has studied this equivalence in a broader way. We choose therefore to focus only on the mirro”
A Game Theoretic Framework for Model Based Reinforcement Learning (2020, methodology): “This has an effect similar to conservative model improvement in a follow the regularized leader interpretation (Shalev-Shwartz, 2012; Ross & Bagnell, 2012; McMahan, 2011).”
DiFacto: Distributed Factorization Machines (2016, methodology): “We adopted FTRL [11], which solves a “smoothed” proximal operator based on AdaGrad.”
Field-aware Factorization Machines for CTR Prediction (2016, background): “Recently, some adaptive learning-rate schedules such as [10, 11] have been proposed to boost the training process of SG.”
Proposal Scaling Distributed Machine Learning with System and Algorithm Co-design (2016, unknown): “We adopted FTRL [97], which solves a “smoothed” proximal operator based on AdaGrad.”
Distributed Coordinate Descent for L1-regularized Logistic Regression (2014, unknown): “Completely different approach is online learning [2, 8, 10, 11].”
A Modern Introduction to Online Learning (2019, unknown): “There is an interesting bit about FTRL-Proximal [McMahan, 2011]: FTRL-Proximal is an instantiation of FTRL that uses a particular proximal regularizer.”
Proximal Reinforcement Learning: A New Theory of Sequential Decision Making in Primal-Dual Spaces (2014, background): “RDA with local stabilizer can be seen in [41].”
Neural Replicator Dynamics (2019, methodology): “The family of no-regret algorithms known as Follow the Regularized Leader (FoReL) [39, 40, 52, 53] generalizes well-known decision making algorithms and population dynamics.”
A survey of Algorithms and Analysis for Adaptive Online Learning (2014, methodology): “Empirical evidence also suggests FTRL-Proximal can work better in practice (McMahan, 2011).”