Oracle complexity of higher-order smooth monotone variational inequalities

What residual rate and oracle complexity are possible for smooth monotone variational inequalities with pth-order information? Under the stated smoothness and oracle assumptions, the target is Õ(T^−p) residual or Õ(ε^−1/p) oracle complexity.

Why it matters and what counts as progress

Why it matters: It tests whether higher-order information can improve convergence for the general monotone class beyond results confined to convex-concave minimax problems.

What counts as progress: Improve the residual exponent or oracle bound for the full smooth monotone class, with matching lower bounds under the same oracle assumptions.

How the problem developed

2012 · Rate [1]
Renato D. C. Monteiro and Benar F. Svaiter Established an O(T^(−3/2)) convergence rate for the second-order NPE method for monotone variational inequalities.
2025 · Partial result [2]
Lesi Chen, Chengchang Liu, Tengyu Luo and Jingzhao Zhang Improved the rate to Õ(T^(−7/4)) for the convex-concave minimax subclass.
9 Aug 2026 · Upper bound [3]
Lesi Chen, Xinliang Zhang, Hengyu Wang, Chengchang Liu, Yongchao Chen and Jingzhao Zhang Reported a Halpern-NPE rate Õ(T^(−2)) and a pth-order generalization Õ(T^(−p)) for smooth monotone VIs. The authors attribute proof discoveries to Claude Opus 4.6 and GPT-5.6 Sol, then report manual verification.

AI contribution

Halpern Iteration Achieves Õ(ε⁻¹ᐟᵖ) pth-Order Oracle Complexity for Monotone Variational Inequalities

Lesi Chen, Xinliang Zhang, Hengyu Wang, Chengchang Liu, Yongchao Chen, Jingzhao Zhang

Under the paper’s pth-order smoothness and oracle assumptions, the final Halpern-based method for smooth monotone variational inequalities attains residual rate Õ(T^(−p)), or Õ(ε^(−1/p)) oracle complexity.

AI involvementAI-centered

ImportanceNotable

Technical verificationFormal (human)

Human understandingFull