# Matching Higher-Order Oracle Complexity for Smooth Monotone Variational Inequalities

arXiv: https://arxiv.org/abs/2609.13462 · HTML: https://mlsanity.com/paper/2609.13462/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Sep 2026.

## Built on by (most cited first, 2 of 2)

- [Optimal High-Order Methods for Solving Monotone Variational Inequalities](https://mlsanity.com/paper/2609.23557/) (2026)
- [Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems](https://mlsanity.com/paper/2609.30212/) (2026)

## Abstract (arXiv)

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.