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

We propose novel high-order algorithms for a class of ${\mathrm{\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 $\rho$. However, for the ${\mathrm{\ell }}_p$-norm stationary point setting ($p\mathrm{\ne }2$), their guarantees are limited to $\rho =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 ${\mathrm{\ell }}_p$-norm stationary points for a suitable range of $\rho >0$, thereby circumventing previous fundamental challenges in ${\mathrm{\ell }}_p$ settings. We further show convergence for high-order smooth $\mathit{\text{monotone}}$ operators, generalizing Adil et al. (2022) to the case where $p\ge 2$, and we extend our Euclidean techniques to continuous-time settings.