Last-Iterate Convergence in Constrained Min-Max Optimization: SOS to the Rescue
summary
Proves that the extra-gradient method with constant step η = C / L achieves last-iterate convergence for monotone variational inequalities over arbitrary convex constraints, giving a gap that scales like O(poly(dim) / √T) and matching known lower bounds. The proof builds a monotone projected Hamiltonian via a degree-6 SOS certificate after reducing any feasible set to the intersection of three supporting halfspaces, and the SOS-derived identity yields a simple, verifiable monotonicity that makes the algorithm converge.
AI-written summary · about
chapters (15)
- 0:00Start
- 0:57Logistics
- 4:46Convex Concave Case
- 13:17Results for Elasticity Convergence
- 19:34Extra Gradient Method
- 21:53Convergence Measure
- 22:37The Standard Convergence Measure
- 23:33Is Compactness Really Needed
- 30:16The Projected Hamiltonian
- 30:52Second Correction Term
- 34:11The Best Bitrate Guarantee for the Projected Hamiltonian
- 38:03Proof for the Monotonicity of the Projector Hamiltonian
- 39:25Gradient Method
- 55:29Constraint and Dimensional Reduction
- 56:33Constraint Reduction
related talks
27mTalk by Ali Kavis (UT Austin)
58mContinuous Methods 2
31mGradient Descent-Ascent Provably Converges to Strict Local Minmax Equilibria with a Finite Timescale
58mFirst-Order Stochastic Optimization
01h 11m(Hidden) Symmetries of Computational Problems (continued)
01h 18mOptimization I
53mAn Interior-Point Method for Convex Optimization over Non-symmetric Cones
27mNonnegative Polynomials, Nonconvex Polynomial Optimization, and Applications to Learning