Matching Higher-Order Oracle Complexity for Smooth Monotone Variational Inequalities

We establish near-optimal higher-order oracle bounds for smooth monotone variational inequalities. For fixed p≥2, let F be monotone on a known compact convex set X of diameter at most D, with operatornameLip(Dp-1F)≤ Lp. Each feasible query returns the complete jet (F,DF,ldots,Dp-1F), and the goal is to find x with tangent residual operatornamedist(0,F(x)+NX(x))≤varepsilon. Writing Q=LpDp/varepsilon, we improve the widetilde Op(Q1/p) upper bound of Chen et al. to widetilde Op(Q2/(3p-1)) via a dimension-independent deterministic algorithm that returns an explicit tangent-residual certificate. We prove a matching Omegap(Q2/(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 widetildeThetap((LpDp/varepsilon)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.