Centered around solving the Online Saddle Point problem, this paper
introduces the Online Convex-Concave Optimization (OCCO) framework, which
involves a sequence of two-player time-varying convex-concave games. We propose
the generalized duality gap (Dual-Gap) as the performance metric and establish
the parallel relationship between OCCO with Dual-Gap and Online Convex
Optimization (OCO) with regret. To demonstrate the natural extension of OCCO
from OCO, we develop two algorithms, the implicit online mirror descent-ascent
and its optimistic variant. Analysis reveals that their duality gaps share
similar expression forms with the corresponding dynamic regrets arising from
implicit updates in OCO. Empirical results further substantiate the
effectiveness of our algorithms. Simultaneously, we unveil that the dynamic
Nash equilibrium regret, which was initially introduced in a recent paper, has
inherent defects.

该研究论文围绕解决在线鞍点问题，引入了在线凸凹优化（OCCO）框架，该框架涉及一系列二人时变凸凹博弈。我们提出了广义对偶间隙（Dual-Gap）作为性能度量，并建立了 OCCO 与 Dual-Gap 之间与在线凸优化（OCO）与后悔之间的并行关系。为了展示 OCCO 从 OCO 的自然扩展，我们开发了两种算法：隐式在线镜象下降 - 上升和其乐观变体。分析表明，它们的对偶间隙与 OCO 中隐式更新导致的相应动态后悔具有类似的表达形式。实证结果进一步证明了我们算法的有效性。同时，我们揭示了最近一篇论文中最初引入的动态 Nash 均衡后悔具有固有的缺陷。