Universal Tensor Methods for Monotone Variational Inequalities

Abstract

We study monotone variational inequalities whose operators have Hölder continuous higher-order derivatives. For a fixed order $p\ge 2$, we assume that the $(p-1)$-th derivative of the monotone operator is Hölder continuous with parameter $\hat{I}½\in [0,1]$ on a bounded closed convex set. We develop regularized tensor extragradient methods that combine a high-order Taylor approximation of the operator with an extragradient correction step. When the Hölder parameter $\hat{I}½$ is known, our regularized tensor extragradient method finds an $\hat{I}\mu$-weak solution using $\mathcal{O}(\hat{I}{\mu }^{-2/(p+\hat{I}½)})$ tensor-oracle calls. When $\hat{I}½$ is unknown, we propose a universal tensor extragradient method whose tensor-oracle complexity is $\mathcal{O}(\hat{I}{\mu }^{-2p/((p+1)(p-1+\hat{I}½))})$.