Generalized Implicit Follow-The-Regularized-Leader
This work provides a unifying framework for online learning algorithms, which is incremental but offers flexibility for designing updates in optimization problems.
The authors introduced generalized implicit Follow-The-Regularized-Leader (FTRL) to expand the FTRL framework, enabling new update rules and unifying existing algorithms like Mirror-Prox, with results showing recovery of temporal variation bounds at the same computational complexity.
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.