Generalized Implicit Follow-The-Regularized-Leader
Keyi Chen Francesco Orabona
We propose a new class of online learning algorithms, generalized implicit
Follow-The-Regularized-Leader (FTRL), that expands the scope of FTRL framework.
Generalized implicit FTRL can recover known algorithms, as FTRL with linearized
losses and implicit FTRL, and it allows the design of new update rules, as
extensions of aProx and Mirror-Prox to FTRL. Our theory is constructive in the
sense that it provides a simple unifying framework to design updates that
directly improve the worst-case upper bound on the regret. The key idea is
substituting the linearization of the losses with a Fenchel-Young inequality.
We show the flexibility of the framework by proving that some known algorithms,
like the Mirror-Prox updates, are instantiations of the generalized implicit
FTRL. Finally, the new framework allows us to recover the temporal variation
bound of implicit OMD, with the same computational complexity.