Research map / Bandits and online learning / Online convex optimization and games
Online Min-Max Optimization: From Individual Regrets to Cumulative Saddle Points
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes online min-max optimization measured against cumulative saddle points, introducing static duality gap (SDual-Gap_T) and dynamic saddle point regret (DSP-Reg_T), with OGDA/OMMNS and sleeping-experts reductions plus two-sided PL analysis.
Problem
Online min-max (zero-sum) optimization where standard individual regrets and static Nash equilibrium regret are incompatible, so no algorithm can jointly get sublinear individual regret and SNE-Reg; the cumulative saddle point is poorly approximated by existing notions.
Approach
Measure performance via a static gap function g'_t(x,y)=f_t(x,y')-f_t(x',y) relative to the cumulative saddle point (x',y'), turning the problem into OCO static/dynamic regret on g'_t; use OGDA (strongly convex-strongly concave) and a min-max Newton step OMMNS (min-max exponential concavity) as base learners, with a min-max FLH meta-algorithm for dynamic regret.
Key results
- OGDA achieves SDual-Gap_T <= (L_0^2/lambda) log T for lambda strongly convex-strongly concave functions.
- OMMNS achieves SDual-Gap_T <= 2d(1/alpha + L_0 D) log T under min-max EC, with DSP-Reg_T of O(d max{log T, sqrt(T V_T log T)}).
- Online AGDA under two-sided PL achieves Dual-Gap_T <= U_T + 2(g*_1 - g*_T), i.e. O(U_T) bounds on the cumulative duality gap.
Surprising findings
- Constant DNE-Reg_T can coexist with average actions staying Theta(1) away from the cumulative saddle point.
- SNE-Reg_T is incompatible with individual regrets even for strongly convex-strongly concave and min-max EC functions.
Limitations
- Dynamic regret bounds require knowledge of the cumulative saddle point (z') for the base learners' reduction.
- Results are theoretical only; no experiments are reported in the provided text.
Experimental setup
Metrics: SDual-Gap_T DSP-Reg_T DNE-Reg_T SNE-Reg_T Dual-Gap_T
Baselines: OGDA online proximal point method AGDA
Builds on: online convex optimization improved FLH (sleeping experts) alternating gradient descent ascent exponential concavity online newton step
Closest papers by meaning
- Small-loss Adaptive Regret for Online Convex Optimization (ICML 2024 · similarity 0.90)
- An Equivalence Between Static and Dynamic Regret Minimization (NeurIPS 2024 · similarity 0.90)
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · similarity 0.90)
- Improved Differentially Private and Lazy Online Convex Optimization: Lower Regret without Smoothness Requirements (ICML 2024 · similarity 0.89)
- Cumulative Regret Analysis of the Piyavskii–Shubert Algorithm and Its Variants for Global Optimization (AAAI 2024 · similarity 0.89)
- Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets (NeurIPS 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.