Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion
Authors: Yang Cai, Argyris Oikonomou, Weiqiang Zheng
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study constrained comonotone min-max optimization, a structured class of nonconvexnonconcave 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 & Ryu (2021) for unconstrained min-max optimization, to constrained comonotone min-max optimization and comonotone inclusion, achieving an optimal convergence rate of O 1 T 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 & Kim (2021), to constrained comonotone min-max optimization and comonotone inclusion, achieving the same O 1 T 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. |
| Researcher Affiliation | Academia | 1Department of Computer Science, Yale University, New Haven, USA. Correspondence to: Yang Cai <yang,cai@yale.edu>, Argyris Oikonomou <argyris.oikonomou@yale.edu>, Weiqiang Zheng <weiqiang.zheng@yale.edu>. |
| Pseudocode | Yes | Algorithm 1 composite-EAG for CMI with ρ > 1 2L |
| Open Source Code | No | The paper does not provide an explicit statement or a link to open-source code for the described methodology. |
| Open Datasets | No | This is a theoretical paper and does not involve the use of datasets for training or evaluation. |
| Dataset Splits | No | This is a theoretical paper and does not involve dataset splits for validation. |
| Hardware Specification | No | This is a theoretical paper and does not describe the hardware used for experiments. |
| Software Dependencies | No | This is a theoretical paper and does not specify software dependencies with version numbers for reproducibility of experiments. |
| Experiment Setup | No | This is a theoretical paper and does not describe an experimental setup with specific hyperparameters or system-level settings. |