Abstract
Centered around solving the Online Saddle Point problem, this paperintroduces the Online Convex-Concave Optimization (OCCO) framework, whichinvolves a sequence of two-player time-varying convex-concave games. We proposethe generalized duality gap (Dual-Gap) as the performance metric and establishthe parallel relationship between OCCO with Dual-Gap and Online ConvexOptimization (OCO) with regret. To demonstrate the natural extension of OCCOfrom OCO, we develop two algorithms, the implicit online mirror descent-ascentand its optimistic variant. Analysis reveals that their duality gaps sharesimilar expression forms with the corresponding dynamic regrets arising fromimplicit updates in OCO. Empirical results further substantiate theeffectiveness of our algorithms. Simultaneously, we unveil that the dynamicNash equilibrium regret, which was initially introduced in a recent paper, hasinherent defects.