论文标题
加速算法，用于受约束的非Convex-Nonconcave Min-Max优化和共酮包含
Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion
论文作者
论文摘要
我们研究了约束的共酮Min-Max优化，这是一类结构化的非Convex-Nonconcave-Nonconcave Min-Max优化问题，及其对共酮包容性的概括。 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.此外，我们证明该算法的迭代会收敛到解决方案集中的一个点。在我们的第二个贡献中，我们扩展了由Lee和Kim（2021）开发的快速额外梯度（FEG）算法，以限制Comonotone Min-Max优化和共酮包容性，以实现相同的$ O \ left（\ frac {1} {1} {t} {t} {t} {t} \ right）$转化利率。该速率适用于文献中尚未研究的最广泛的共酮包容性问题。我们的分析基于简单的潜在函数参数，这对于分析其他加速算法可能很有用。
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.
