Universal Tensor Methods for Monotone Variational Inequalities

We study monotone variational inequalities whose operators have H"older continuous higher-order derivatives. For a fixed order p≥ 2, we assume that the (p-1)-th derivative of the monotone operator is H"older continuous with parameter nu∈[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"older parameter nu is known, our regularized tensor extragradient method finds an ε-weak solution using O(ε-2/(p+nu)) tensor-oracle calls. When nu is unknown, we propose a universal tensor extragradient method whose tensor-oracle complexity is O(ε-2p/((p+1)(p-1+nu))).