Smooth Convex–Concave Saddle Problems
Descriptions may be stale. Consult the linked Lean sources.
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
Results
Nonempty compact convex sets
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) SmoothConvexConcave (Ours) (review) | |||
| (2) Mirror-Prox (Nemirovski 2004, Thm. 3.2, (3.10)). Euclidean specialization; finite dimensions. | (1): Matches known rate on finite-dimensional overlap; Lean formalization. Scope: compact subsets of Hilbert spaces instead of finite-dimensional spaces. | (1) needs ambient
differentiability and Lipschitz continuity; (2) needs
them only on |
|
| (3) Lower bound (Ouyang and Xu 2018, Thm. 9). Bilinearly coupled problems on Euclidean balls. | (1) matches the
worst-case order for deterministic first-order methods when |
Abbr: