# Proximal Point Method for Online Saddle Point Problem

arXiv: https://arxiv.org/abs/2407.04591 · HTML: https://mlsanity.com/paper/2407.04591/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 35 references that are in the map.
- First posted on arXiv 5 Jul 2024.

## Builds on (most cited first, 20 of 20)

- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Learning in games with continuous action sets and unknown payoff functions](https://mlsanity.com/paper/1608.07310/) (2016)
- [Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium](https://mlsanity.com/paper/2104.12761/) (2021)
- [Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games](https://mlsanity.com/paper/2111.06008/) (2021)
- [No-Regret Learning in Time-Varying Zero-Sum Games](https://mlsanity.com/paper/2201.12736/) (2022)
- [Faster Rates for Convex-Concave Games](https://mlsanity.com/paper/1805.06792/) (2018)
- [Temporal Variability in Implicit Online Learning](https://mlsanity.com/paper/2006.07503/) (2020)
- [Coordinate Methods for Matrix Games](https://mlsanity.com/paper/2009.08447/) (2020)
- [Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods](https://mlsanity.com/paper/2202.04640/) (2022)
- [On the Convergence of No-Regret Learning Dynamics in Time-Varying Games](https://mlsanity.com/paper/2301.11241/) (2023)
- [A closer look at temporal variability in dynamic online learning](https://mlsanity.com/paper/2102.07666/) (2021)
- [Exploiting Problem Structure in Optimization under Uncertainty via Online Convex Optimization](https://mlsanity.com/paper/1709.02490/) (2017)
- [Online Learning in Periodic Zero-Sum Games](https://mlsanity.com/paper/2111.03377/) (2021)
- [Learning and Efficiency in Games with Dynamic Population](https://mlsanity.com/paper/1505.00391/) (2015)
- [The Online Saddle Point Problem and Online Convex Optimization with Knapsacks](https://mlsanity.com/paper/1806.08301/) (2018)
- [Online and Bandit Algorithms for Nonstationary Stochastic Saddle-Point Optimization](https://mlsanity.com/paper/1912.01698/) (2019)
- [Fully Implicit Online Learning](https://mlsanity.com/paper/1809.09350/) (2018)

## Built on by (most cited first, 3 of 3)

- [A Modular Algorithm for Non-Stationary Online Convex-Concave Optimization](https://mlsanity.com/paper/2509.07901/) (2025)
- [Online Multi-Agent Control with Adversarial Disturbances](https://mlsanity.com/paper/2506.18814/) (2025)
- [Online Min-Max Optimization: From Individual Regrets to Cumulative Saddle Points](https://mlsanity.com/paper/2602.10565/) (2026)

## Abstract (arXiv)

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.