mlsanityData to 7 Oct 2026

Online Min-Max Optimization: From Individual Regrets to Cumulative Saddle Points

arXiv 2602.10565 ↗First posted 11 Feb 2026cs.LG math.OCcited by 0

Not on the map. Why?

Abstract (arXiv)

We propose and study an online version of min-max optimization based on cumulative saddle points under a variety of performance measures beyond convex-concave settings. After first observing the incompatibility of (static) Nash equilibrium (SNE-RegT) with individual regrets even for strongly convex-strongly concave functions, we propose an alternate static duality gap (SDual-GapT) inspired by the online convex optimization (OCO) framework. We provide algorithms that, using a reduction to classic OCO problems, achieve bounds for SDual-GapT~and a novel dynamic saddle point regret (DSP-RegT), which we suggest naturally represents a min-max version of the dynamic regret in OCO. We derive our bounds for SDual-GapT~and DSP-RegT~under strong convexity-strong concavity and a min-max notion of exponential concavity (min-max EC), and in addition we establish a class of functions satisfying min-max EC~that captures a two-player variant of the classic portfolio selection problem. Finally, for a dynamic notion of regret compatible with individual regrets, we derive bounds under a two-sided Polyak-Lojasiewicz (PL) condition.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 17 of its 30 references that are in the map. First posted on arXiv 11 Feb 2026.

Builds on

17 of 30 references.

References · 17

  1. 2019Introduction to Online Convex Optimizationcited by 793
  2. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  3. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 211
  4. 2013Non-stationary Stochastic Optimizationcited by 173
  5. 2018Adaptive Online Learning in Dynamic Environmentscited by 130
  6. 2015Strongly Adaptive Online Learningcited by 102
  7. 2021Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibriumcited by 51
  8. 2016Improved Strongly Adaptive Online Learning using Coin Bettingcited by 48
  9. 2019Policy Optimization Provably Converges to Nash Equilibria in Zero-Sum Linear Quadratic Gamescited by 38
  10. 2022No-Regret Learning in Time-Varying Zero-Sum Gamescited by 36
  11. 2020Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functionscited by 33
  12. 2019On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulatorcited by 20
5 more
  1. 2023On the Convergence of No-Regret Learning Dynamics in Time-Varying Gamescited by 14
  2. 2023Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedbackcited by 6
  3. 2019Competing Against Equilibria in Zero-Sum Games with Evolving Payoffscited by 4
  4. 2024Proximal Point Method for Online Saddle Point Problemcited by 3
  5. 2017Dynamic Regret of Strongly Adaptive Methodscited by 2

Built on by

Not cited yet.