Research map / Optimization / Nonconvex and smooth optimization
Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion
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.
Extends the Extra Anchored Gradient (EAG) and Fast Extra Gradient (FEG) algorithms to constrained comonotone min-max optimization and comonotone inclusion, proving O(1/T) last-iterate tangent-residual rates and point convergence in several regimes.
Problem
Comonotone (nonconvex-nonconcave, structured) min-max optimization and composite comonotone inclusion with constraints: existing methods were sub-optimal, unconstrained-only, or lacked point convergence.
Approach
Introduce an auxiliary variable c_k in A(z_k) so that F(z_k)+c_k is an element of (F+A)(z_k), letting the EAG/FEG update be analyzed as if it were unconstrained using a potential function; proves O(1/T) tangent residual rate for rho >= -1/(20L) (composite-EAG) and rho > -1/(2L) (composite-FEG), with point convergence via a merging path to optimized Halpern iteration.
Key results
- composite-EAG achieves tangent residual bound r^tan(z_T)^2 <= 20H^2/(eta^2 T^2) with eta=0.31/L for rho >= -1/(20L), with point convergence.
- composite-FEG achieves r^tan(z_T)^2 <= 4 H_0^2 L^2/((eta+2rho)^2 L^2 T^2) for rho in (-1/(2L), 0], matching the Omega(1/T) lower bound for first-order methods.
- Merging path result gives ||z_{k+1}-w_{k+1}||^2 = O(1/sqrt(k)) between composite-EAG and optimized Halpern, implying point convergence.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Extend EAG to constrained comonotone inclusion with ρ ≥ -1/(20L) | EAG · Comonotone inclusion | tangent residual convergence rate: O(1/T) | Helped |
| Extend FEG to constrained comonotone inclusion with ρ > -1/(2L) | FEG · Comonotone inclusion | tangent residual convergence rate: O(1/T) | Helped |
| Extend EAG to the constrained, negatively comonotone setting | EAG · Comonotone inclusion, ρ ≥ -1/(20L) | point convergence | Helped |
| Extend FEG to constrained comonotone inclusion | FEG · Comonotone inclusion, ρ = 0 | point convergence | Helped |
Limitations
- Point-convergence rate for composite-EAG is O(1/sqrt(k)) merging path, worse than O(1/k^2) in unconstrained monotone case.
- Composite-EAG range rho >= -1/(20L) is narrower than composite-FEG range rho > -1/(2L).
- Point convergence for composite-FEG only shown in monotone case (rho=0).
Experimental setup
Metrics: tangent residual natural residual
Baselines: EG+ CEG+ Double-loop Halpern APG ARG AOG fOGDA
Builds on: Extra Anchored Gradient (EAG) Fast Extragradient (FEG) Optimized Halpern iteration
Closest papers by meaning
- Optimal Acceleration for Minimax and Fixed-Point Problems is Not Unique (ICML 2024 · similarity 0.89)
- Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints (ICML 2025 · similarity 0.88)
- Semi-infinite Nonconvex Constrained Min-Max Optimization (NeurIPS 2025 · similarity 0.88)
- Faster Accelerated First-order Methods for Convex Optimization with Strongly Convex Function Constraints (NeurIPS 2024 · similarity 0.87)
- Stochastic Extragradient with Flip-Flop Shuffling & Anchoring: Provable Improvements (NeurIPS 2024 · similarity 0.87)
- Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems (NeurIPS 2026 · similarity 0.87)
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.