Alex Gda Convex Concave — Alex-GDA for Block-Smooth Saddle Problems
Descriptions may be stale. Consult the linked Lean sources.
Alex-GDA for Block-Smooth Saddle Problems · Lean proof
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
Proved result
OracleTemplate.Convergence LongTails.Setups.BlockSmoothConvexConcave.spec OracleTemplate.BlockSaddle.budgetRelevant previous results
- G. M. Korpelevich. The
Extragradient Method for Finding Saddle Points and Other Problems.
1976; English translation 1977. Complexity:
fixed exact partial-gradient calls for joint gradient norm at most , using extragradient with best-iterate selection; four partial-gradient calls per iteration, no additional initialization calls, and zero calls when . - Taeho Yoon and Ernest K. Ryu. Accelerated
Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k²) Rate
on Squared Gradient Norm. 2021. Complexity:
fixed exact partial-gradient calls for last-iterate joint gradient norm at most , using extra anchored gradient; four partial-gradient calls per iteration and no additional initialization calls.