Proximal Point Method for Online Saddle Point Problem
arXiv:2407.04591 · doi:10.1007/978-981-96-6579-2_27
Abstract
This paper focuses on the online saddle point problem, which involves a sequence of two-player time-varying convex-concave games. Considering the nonstationarity of the environment, we adopt the duality gap and the dynamic Nash equilibrium regret as performance metrics for algorithm design. We present three variants of the proximal point method: the Online Proximal Point Method (OPPM), the Optimistic OPPM (OptOPPM), and the OptOPPM with multiple predictors. Each algorithm guarantees upper bounds for both the duality gap and dynamic Nash equilibrium regret, achieving near-optimality when measured against the duality gap. Specifically, in certain benign environments, such as sequences of stationary payoff functions, these algorithms maintain a nearly constant metric bound. Experimental results further validate the effectiveness of these algorithms. Lastly, this paper discusses potential reliability concerns associated with using dynamic Nash equilibrium regret as a performance metric. The technical appendix and code can be found at https://github.com/qingxin6174/PPM-for-OSP.
References in corpus (6)
- Exploiting Problem Structure in Optimization under Uncertainty via Online Convex Optimization
- Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games
- Online and Bandit Algorithms for Nonstationary Stochastic Saddle-Point Optimization
- The Online Saddle Point Problem and Online Convex Optimization with Knapsacks
- Fully Implicit Online Learning
- A closer look at temporal variability in dynamic online learning