Research map / Optimization / Nonconvex and smooth optimization
Two-timescale Extragradient for Finding Local Minimax Points
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that two-timescale extragradient converges to second-order necessary local minimax points without assuming the Hessian in the maximization variable is nondegenerate, via a restricted Schur complement and hemicurvature analysis.
Problem
Finding local minimax points of nonconvex-nonconcave minimax problems with first-order methods, where prior two-timescale GDA results require the Hessian w.r.t. the maximization variable to be nondegenerate.
Approach
Introduces a restricted Schur complement giving a refined second-order necessary condition for local minimax points without nondegeneracy, and analyzes the spectrum of the timescaled Jacobian (with hemicurvature) to show two-timescale EG is locally stable at such points and almost surely avoids strict non-minimax points, while two-timescale GDA can avoid some degenerate local minimax points.
Key results
- Two-timescale EG almost surely avoids strict non-minimax points for step size 0 < eta < (sqrt5-1)/(2L) and sufficiently large tau.
- Two-timescale GDA almost surely avoids some non-strict local minimax points (with hemicurvature below eta/2) regardless of timescale separation.
- A bilinear example f(x,y)=xy: its unique local minimax point 0 is strict linearly stable for both continuous- and discrete-time two-timescale EG.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use two-timescale EG instead of two-timescale GDA | Minimax optimization with a degenerate maximization Hessian · Bilinear function f_b(x,y)=xy | convergence to local minimax point | Helped |
| Use two-timescale EG instead of two-timescale GDA | Minimax optimization with a degenerate maximization Hessian · Quadratic function f_q | finding local minimax points | Helped |
| Apply timescale separation to GDA | Two-timescale GDA · Non-strict local minimax points with degenerate maximization Hessian | convergence to local minimax point | Hurt |
| Remove the nondegeneracy assumption on the maximization-variable Hessian | Two-timescale EG convergence analysis · Local minimax points | applicability of convergence guarantee | Helped |
Surprising findings
- Two-timescale GDA can almost surely avoid certain degenerate local minimax points, even with large timescale separation.
- Two-timescale EG can find non-isolated local minimax points with singular Jacobian, though they are not strictly linearly stable.
Limitations
- Stability conditions depend on hemicurvature/s_0 that are hard to check in general.
- Gap between second-order necessary and sufficient conditions due to an extra condition on h.
- No explicit bound on how large the timescale parameter tau must be.
Experimental setup
Baselines: two-timescale GDA GDA extragradient
Builds on: two-timescale gradient descent ascent extragradient stable manifold theorem local minimax points (Jin et al.)
Closest papers by meaning
- Double-Step Alternating Extragradient with Increasing Timescale Separation for Finding Local Minimax Points: Provable Improvements (ICML 2024 · similarity 0.93)
- Accelerated last-iterate convergence of Extragradient via power-law stepsizes (NeurIPS 2026 · similarity 0.87)
- Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems (ICLR 2022 · similarity 0.87)
- Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization (NeurIPS 2024 · similarity 0.87)
- Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems (NeurIPS 2026 · similarity 0.86)
- Second-Order Min-Max Optimization with Lazy Hessians (ICLR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.