Follow The Regularized Leader

It is an algorithm for on-line linear optimization. It is similar to Follow the leader, but instead of giving prediction $x_{T+1} = \arg\min_{x \in \mathcal{K}} \sum_{t=1}^T f'_t x$, it gives $x_{T+1} = \arg\min_{x \in \mathcal{K}} \sum_{t=1}^T f'_t x + cR(x)$, where $R(x)$ is some convex differentiable regularizing term. In the context of classification, see Svalev-Shwartz et al. (2007).


  • Shai Shalev-Shwartz and Yoram Singer. A primal-dual perspective of online learning algorithms. Mach. Learn., 69(2-3):115142, 2007.