Research map / Optimization / Nonconvex and smooth optimization
Double-Step Alternating Extragradient with Increasing Timescale Separation for Finding Local Minimax Points: Provable Improvements
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.
Proposes double-step alternating extragradient (Alt2-EG) with fixed or increasing timescale separation to find non-strict local minimax points in nonconvex-nonconcave minimax problems, with local stability and global convergence analyses.
Problem
Two-timescale gradient methods (GDA and EG) for nonconvex-nonconcave minimax optimization may be unstable at some non-strict local minimax points even with large timescale separation, and the required timescale separation is infeasible to compute in practice.
Approach
Replace the simultaneous update in two-timescale EG with a double-step alternating update (x-step uses a separate timescale gamma = sqrt(tau)), which implicitly regularizes the type (i) eigenvalues toward stability, and increase the timescale separation tau_k over iterations so no fixed large tau must be tuned.
Key results
- On the toy function f(x,y)=-x^2+2xy, Alt2-EG-FTS with tau=20 and Alt2-EG-ITS converge to the non-strict local minimax point, while GDA-FTS, EG-FTS and Alt1-EG-FTS do not.
- Theorem 5.4: for sufficiently large tau, Alt2-EG-FTS with (tau, sqrt(tau)) is exponentially stable at stationary points satisfying the second-order necessary condition, including non-strict ones.
- Theorem 6.1: Alt2-EG-ITS with tau_k = k^(1/(2+2c)) is asymptotically stable at such points with rate O(1/sqrt(k) e^{-2 sqrt(k)}).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use double-step alternating updates instead of simultaneous updates | Two-timescale extragradient · f(x,y) = -x² + 2xy | convergence to the local minimax point | Helped |
| increase timescale separation from τ = 2 to τ = 20 (ablation) | Alt2-EG-FTS · f(x,y) = -x² + 2xy | convergence to the local minimax point | Helped |
| use the standard alternating scheme (τ, γ) = (τ, τ) instead of the double-step scheme (τ, √τ) (ablation) | Alt2-EG-FTS · f(x,y) = -x² + 2xy | convergence to the local minimax point | Hurt |
| increase timescale separation over iterations using (k^(1/(2+2c)), k^(1/(4+4c))) | Alt2-EG-ITS · non-strict local minimax points satisfying the theorem assumptions | local asymptotic stability | Helped |
| use double-step alternating updates with γ = √τ rather than simultaneous updates | Two-timescale extragradient · non-strict local minimax points satisfying the theorem assumptions | stability at points satisfying the second-order necessary condition | Helped |
Surprising findings
- Standard alternating update with equal timescales (Alt1-EG) also fails on the toy example, so the gamma = sqrt(tau) choice in the double-step scheme is what matters.
Limitations
- Escaping behavior of Alt2-EG-ITS around strict non-minimax points is not established (non-autonomous system).
- Global convergence requires star-convex-star-concave assumption and assumes Assumption 3 at stationary points.
- Experiments are limited to a single toy two-dimensional example.
Experimental setup
Benchmarks: f(x,y) = -x^2 + 2xy toy example
Metrics: convergence to local minimax point (numerical trajectories) spectral radius / exponential stability
Baselines: GDA-FTS EG-FTS Alt1-EG-FTS two-timescale EG (Chae et al., 2024b)
Builds on: two-timescale extragradient (Chae et al., 2024b) two-timescale GDA (Jin et al., 2020) alternating GDA (Lee et al., 2024) local minimax points (Jin et al., 2020)
Closest papers by meaning
- Two-timescale Extragradient for Finding Local Minimax Points (ICLR 2024 · similarity 0.93)
- Local Convergence Analysis of Gradient Descent Ascent with Finite Timescale Separation (ICLR 2021 · similarity 0.89)
- Fundamental Benefit of Alternating Updates in Minimax Optimization (ICML 2024 · similarity 0.87)
- Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems (NeurIPS 2026 · similarity 0.87)
- Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization (NeurIPS 2024 · similarity 0.86)
- Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion (ICML 2024 · 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.