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).

Bibliography

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