Beyond first-order methods for non-convex non-concave min-max optimization
This addresses optimization challenges in machine learning for researchers, but it is incremental as it builds on recent theoretical works.
The paper tackles non-convex non-concave min-max optimization by developing higher-order methods, achieving an O(1/ε^(2/p)) rate for ε-approximate stationarity under a weakened Minty condition and showing practical benefits over first-order methods.
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/ε^\frac{2}{p})$ rate to achieve $ε$-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.