Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion
Preprint
Abstract
We study constrained comonotone min-max optimization, a structured class of nonconvex-nonconcave min-max optimization problems, and their generalization to comonotone inclusion. In our first contribution, we extend the Extra Anchored Gradient (EAG) algorithm, originally proposed by Yoon and Ryu (2021) for unconstrained min-max optimization, to constrained comonotone min-max optimization and comonotone inclusion, achieving an optimal convergence rate of $O\left(\frac{1}{T}\right)$ among all first-order methods. Additionally, we prove that the algorithm's iterations converge to a point in the solution set. In our second contribution, we extend the Fast Extra Gradient (FEG) algorithm, as developed by Lee and Kim (2021), to constrained comonotone min-max optimization and comonotone inclusion, achieving the same $O\left(\frac{1}{T}\right)$ convergence rate. This rate is applicable to the broadest set of comonotone inclusion problems yet studied in the literature. Our analyses are based on simple potential function arguments, which might be useful for analyzing other accelerated algorithms.
Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Accelerated Minimax Algorithms Flock TogetherSIAM Journal on Optimization, 2025
- On the proximal point algorithm and its Halpern-type variant for generalized monotone operators in Hilbert spaceOptimization Letters, 2021
- Accelerated proximal point method for maximally monotone operatorsMathematical Programming, 2021
- Generalized monotone operators and their averaged resolventsMathematical Programming, 2020
- Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemsMathematical Programming, 2019
- Golden ratio algorithms for variational inequalitiesMathematical Programming, 2019
- On the convergence properties of non-Euclidean extragradient methods for variational inequalities with generalized monotone operatorsComputational Optimization and Applications, 2014
- Convex Analysis and Monotone Operator Theory in Hilbert Spaces2011
- Dual extrapolation and its applications to solving variational inequalities and related problemsMathematical Programming, 2006
- Finite-Dimensional Variational Inequalities and Complementarity Problems2004