Online Saddle Point Problem and Online Convex-Concave Optimization
This work addresses online optimization for two-player games, extending Online Convex Optimization, but is incremental as it builds on existing methods.
The paper tackles the Online Saddle Point problem by introducing the Online Convex-Concave Optimization (OCCO) framework and proposes the generalized duality gap as a performance metric, with empirical results showing algorithm effectiveness.
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.