# Online and Bandit Algorithms for Nonstationary Stochastic Saddle-Point Optimization

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Dec 2019.

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

- [No-Regret Learning in Time-Varying Zero-Sum Games](https://mlsanity.com/paper/2201.12736/) (2022)
- [Improving LLM General Preference Alignment via Optimistic Online Mirror Descent](https://mlsanity.com/paper/2502.16852/) (2025)
- [Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/2108.00473/) (2021)
- [Stochastic Saddle Point Problems with Decision-Dependent Distributions](https://mlsanity.com/paper/2201.02313/) (2022)
- [Proximal Point Method for Online Saddle Point Problem](https://mlsanity.com/paper/2407.04591/) (2024)
- [A Modular Algorithm for Non-Stationary Online Convex-Concave Optimization](https://mlsanity.com/paper/2509.07901/) (2025)

## Abstract (arXiv)

Saddle-point optimization problems are an important class of optimization problems with applications to game theory, multi-agent reinforcement learning and machine learning. A majority of the rich literature available for saddle-point optimization has focused on the offline setting. In this paper, we study nonstationary versions of stochastic, smooth, strongly-convex and strongly-concave saddle-point optimization problem, in both online (or first-order) and multi-point bandit (or zeroth-order) settings. We first propose natural notions of regret for such nonstationary saddle-point optimization problems. We then analyze extragradient and Frank-Wolfe algorithms, for the unconstrained and constrained settings respectively, for the above class of nonstationary saddle-point optimization problems. We establish sub-linear regret bounds on the proposed notions of regret in both the online and bandit setting.