Beyond First-Order Methods for ${\ell }_p$-Structured Non-Monotone Variational Inequalities

Abstract

We propose novel high-order algorithms for a class of ${\ell }_p$-structured non-monotone variational inequalities. In particular, work by Diakonikolas et al. (2021), which introduced the weak Minty variational inequality (weak-MVI) setting, showed how to find an approximate first-order Euclidean stationary point for a strictly positive range of the weak-MVI parameter $\ddot{I}$. However, for the ${\ell }_p$-norm stationary point setting ($p\ne 2$), their guarantees are limited to $\ddot{I}=0$, which recovers the standard MVI setting. In this work, we address this gap by presenting a suite of high-order methods that converge to ${\ell }_p$-norm stationary points for a suitable range of $\ddot{I}>0$, thereby circumventing previous fundamental challenges in ${\ell }_p$ settings. We further show convergence for high-order smooth \textit{monotone} operators, generalizing Adil et al. (2022) to the case where $p\ge 2$, and we extend our Euclidean techniques to continuous-time settings.