Matching Higher-Order Oracle Complexity for Smooth Monotone Variational Inequalities

Abstract

We establish near-optimal higher-order oracle bounds for smooth monotone variational inequalities. For fixed $p\ge 2$, let $F$ be monotone on a known compact convex set $X$ of diameter at most $D$, with $\mathrm{Lip}(D^{p-1}F)\le L_p$. Each feasible query returns the complete jet $(F,DF,\dots ,D^{p-1}F)$, and the goal is to find $x$ with tangent residual $\mathrm{dist}(0,F(x)+N_X(x))\le \epsilon$. Writing $Q=L_p{D}^p/\epsilon$, we improve the ${\tilde{O}}_p(Q^{1/p})$ upper bound of Chen et al. to ${\tilde{O}}_p(Q^{2/(3p-1)})$ via a dimension-independent deterministic algorithm that returns an explicit tangent-residual certificate. We prove a matching ${\Omega }_p(Q^{2/(3p-1)})$ lower bound for arbitrary adaptive deterministic algorithms and randomized algorithms with per-instance success probability at least $2/3$, without span or tensor-update restrictions. Hence the high-dimensional worst-case oracle complexity is ${\tilde{\Theta }}_p((L_p{D}^p/\epsilon {)}^{2/(3p-1)})$. The same method applies to smooth convex--concave minimax problems, improving the fixed-geometry accuracy exponent from $4/(3p+1)$ to $2/(3p-1)$ and matching the known lower-bound exponent.