We propose a study of structured non-convex non-concave min-max problems which goes beyond standard first-order approaches. Inspired by the tight understanding established in recent works [Adil et al., 2022, Lin and Jordan, 2022b], we develop a suite of higher-order methods which show the improvements attainable beyond the monotone and Minty condition settings. Specifically, we provide a new understanding of the use of discrete-time $p^{th}$-order methods for operator norm minimization in the min-max setting, establishing an $O(1/\epsilon^\frac{2}{p})$ rate to achieve $\epsilon$-approximate stationarity, under the weakened Minty variational inequality condition of Diakonikolas et al. [2021]. We further present a continuous-time analysis alongside rates which match those for the discrete-time setting, and our empirical results highlight the practical benefits of our approach over first-order methods.
翻译:我们提出了一种针对结构化非凸非凹极小极大问题的研究,超越了标准的一阶方法。受最近几篇论文的启发(Adil等人,2022年;Lin和Jordan,2022b年),我们开发了一套更高阶方法,展示了在单调和Minty条件以外取得的进展。具体来说,我们提出了一种新的理解,即在极小极大设置中,离散时间的$p$阶方法可用于运算符范数最小化,根据Diakonikolas等人[2021]所放宽的Minty变分不等式条件,我们建立了一个$O(1/\epsilon^\frac{2}{p})$的速率来实现$\epsilon$-近似的平稳性。此外,我们还提供了一个连续时间分析,其速率与离散时间设置相匹配,我们的实证结果突出了我们的方法在一阶方法上的实用优势。