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.

该研究提出了一种新的在线学习算法，即广义隐式 FTRL，该算法扩展了 FTRL 框架的范围，可恢复已知算法，设计新的更新规则，直接改善遗憾的最坏情况的上界。

广义隐式 Follow-The-Regularized-Leader

Generalized Implicit Follow-The-Regularized-Leader

This paper studies first order methods for solving smooth minimax
optimization problems $\min_x \max_y g(x,y)$ where $g(\cdot,\cdot)$ is smooth
and $g(x,\cdot)$ is concave for each $x$. In terms of $g(\cdot,y)$, we consider
two settings -- strongly convex and nonconvex -- and improve upon the best
known rates in both. For strongly-convex $g(\cdot, y),\ \forall y$, we propose
a new algorithm combining Mirror-Prox and Nesterov's AGD, and show that it can
find global optimum in $\tilde{O}(1/k^2)$ iterations, improving over current
state-of-the-art rate of $O(1/k)$. We use this result along with an inexact
proximal point method to provide $\tilde{O}(1/k^{1/3})$ rate for finding
stationary points in the nonconvex setting where $g(\cdot, y)$ can be
nonconvex. This improves over current best-known rate of $O(1/k^{1/5})$.
Finally, we instantiate our result for finite nonconvex minimax problems, i.e.,
$\min_x \max_{1\leq i\leq m} f_i(x)$, with nonconvex $f_i(\cdot)$, to obtain
convergence rate of $O(m(\log m)^{3/2}/k^{1/3})$ total gradient evaluations for
finding a stationary point.

本文研究解决平滑最小最大优化问题的一阶方法，其中 g (x,y) 是平滑的且 g (x,・) 对于每个 x 均为凹性。对于 g (・，y)，我们考虑两种情况 —— 强凸性和非凸性 —— 并在两种情况下改进了已知最佳速率。