Alex-GDA for Block-Smooth Saddle Problems
Descriptions may be stale. Consult the linked Lean sources.
Alex-GDA for Block-Smooth Saddle Problems
We consider
The saddle-point problem is
Our assumptions:
Assumption 1 (Convexity and concavity). For every
Assumption 2 (Block smoothness). Both partial
functions are Fréchet differentiable everywhere. For all
Assumption 3 (Saddle point and initial distance).
There exists
Queries may be made at any pair in
Our result is algorithm-specific: we analyze Alex-GDA. The method
chooses fixed step sizes
The required accuracy is the squared gradient-residual bound
Results
On real Hilbert spaces
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) AlexGdaConvexConcave (Ours) (review) | |||
| (2) EAG-V (Yoon and Ryu 2021, Cor. 2) | (1): No established improvement on the finite-dimensional overlap. | (1): For fixed |
|
| (3) Optimistic gradient / PEG (Gorbunov et al. 2022, Thm. 1) | (1): Matches known rate
for fixed |
(1): Selected rather than
last iterate; at least tenfold larger leading constant; deteriorates as
|
|
| (4) Alternating GDA,
momentum |
(1): Deterministic
selected output instead of expected random-iterate accuracy; matches the
rate for fixed |
||
| (5) Derived bound (Shugart et al. 2026, Thm. 3.1) | (1): No extra selection
queries; two rather than three calls per iteration. Matched total-cost
order for fixed |
||
| (6) Alex-GDA (Lee et al. 2024, Thm. 5.1; Conj. 8.2) | No general convex–concave bound in
Thm. 5.1: requires twice-differentiable, finite-dimensional, strongly
convex–strongly concave objectives and |
(1): Method-specific
scope extension to mere convexity–concavity, including |
Abbr: