Universal Tensor Methods for Monotone Variational Inequalities

We study monotone variational inequalities whose operators have Hölder continuous higher-order derivatives.

For a fixed order $p\geq 2$, we assume that the $(p-1)$-th derivative of the monotone operator is Hölder continuous with parameter $\nu\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 $\nu$ is known, our regularized tensor extragradient method finds an $\epsilon$-weak solution using $\mathcal{O}(\epsilon^{-2/(p+\nu)})$ tensor-oracle calls.

When $\nu$ is unknown, we propose a universal tensor extragradient method whose tensor-oracle complexity is $\mathcal{O}(\epsilon^{-2p/((p+1)(p-1+\nu))})$.