Smooth Convex Concave — Smooth Convex–Concave Saddle Problems
Descriptions may be stale. Consult the linked Lean sources.
Smooth Convex–Concave Saddle Problems · Lean proof
Smooth Convex–Concave Saddle Problems
We consider a convex–concave function
The saddle-point problem is
Our assumptions:
Assumption 1 (Feasible geometry). The sets
Assumption 2 (Convexity and concavity). For every
Assumption 3 (Global smoothness). For every
Queries may be made at any point of
Proved result
OracleTemplate.Convergence LongTails.Setups.SmoothConvexConcave.spec OracleTemplate.SaddlePoint.budgetRelevant previous results
- Arkadi Nemirovski. Prox-Method
with Rate of Convergence O(1/t) for Variational Inequalities with
Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle
Point Problems. 2004. Complexity:
exact saddle-gradient oracle calls; Mirror-Prox, two calls per iteration, deterministic saddle gap at most . - Axel Böhm, Michael Sedlmayer, Ernö Robert Csetnek, Radu Ioan Boţ. Two Steps at a Time—Taking GAN
Training in Stride with Tseng’s Method. 2020 preprint, version 1;
published 2022. Complexity:
exact saddle-gradient oracle calls for deterministic saddle gap at most ; forward-backward-forward uses two calls per iteration, and its past-gradient variant uses one per iteration plus one initialization call.