In a recent series of papers it has been established that variants of
Gradient Descent/Ascent and Mirror Descent exhibit last iterate convergence in
convex-concave zero-sum games. Specifically, \cite{DISZ17, LiangS18} show last
iterate convergence of the so called "Optimistic Gradient Descent/Ascent" for
the case of \textit{unconstrained} min-max optimization. Moreover, in
\cite{Metal} the authors show that Mirror Descent with an extra gradient step
displays last iterate convergence for convex-concave problems (both constrained
and unconstrained), though their algorithm does not follow the online learning
framework; it uses extra information rather than \textit{only} the history to
compute the next iteration. In this work, we show that "Optimistic
Multiplicative-Weights Update (OMWU)" which follows the no-regret online
learning framework, exhibits last iterate convergence locally for
convex-concave games, generalizing the results of \cite{DP19} where last
iterate convergence of OMWU was shown only for the \textit{bilinear case}. We
complement our results with experiments that indicate fast convergence of the
method.

本文研究了凸凹零和博弈问题，并提出了一种遵循在线学习框架的近似算法 Optimistic Multiplicative-Weights Update，在本地范围内表现出最后收敛性。

无悔学习中的最后迭代收敛：凸凹景观的约束极小极大优化

Last iterate convergence in no-regret learning: constrained min-max  optimization for convex-concave landscapes

Motivated by applications in Game Theory, Optimization, and Generative
Adversarial Networks, recent work of Daskalakis et al \cite{DISZ17} and
follow-up work of Liang and Stokes \cite{LiangS18} have established that a
variant of the widely used Gradient Descent/Ascent procedure, called
"Optimistic Gradient Descent/Ascent (OGDA)", exhibits last-iterate convergence
to saddle points in {\em unconstrained} convex-concave min-max optimization
problems. We show that the same holds true in the more general problem of {\em
constrained} min-max optimization under a variant of the no-regret
Multiplicative-Weights-Update method called "Optimistic Multiplicative-Weights
Update (OMWU)". This answers an open question of Syrgkanis et al \cite{SALS15}.
The proof of our result requires fundamentally different techniques from
those that exist in no-regret learning literature and the aforementioned
papers. We show that OMWU monotonically improves the Kullback-Leibler
divergence of the current iterate to the (appropriately normalized) min-max
solution until it enters a neighborhood of the solution. Inside that
neighborhood we show that OMWU is locally (asymptotically) stable converging to
the exact solution. We believe that our techniques will be useful in the
analysis of the last iterate of other learning algorithms.

本文研究了一种叫做 OMWU 的算法，该算法在约束的 min-max 最优化问题中表现出优秀的收敛性以及稳定性。该算法与先前的梯度下降法及其他学习算法不同，且需要使用新的技术和思路。