Beyond first-order methods for non-convex non-concave min-max optimization

arXiv2304.08389MaRDI QIDQ6433386

Author name not available (Why is that?)

Publication date: 17 April 2023

Abstract: 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/epsilo{n}^{f}rac2p)$ 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.

Has companion code repository: https://github.com/abhijeetiitmvyas/higher-order-methods-for-weak-mvis

This page was built for publication: Beyond first-order methods for non-convex non-concave min-max optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6433386)