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≥2, let F be monotone on a known compact convex set X of diameter at most D, with Lip(D^p−1F)≤ L_p. Each feasible query returns the complete jet (F,DF,…,D^p−1F), and the goal is to find x with tangent residual dist(0,F(x)+N_X(x))≤ε. Writing Q=L_pD^p/ε, we improve the Õ_p(Q^1/p) upper bound of Chen et al. to Õ_p(Q^2/(3p−1)) via a dimension-independent deterministic algorithm that returns an explicit tangent-residual certificate. We prove a matching Ω_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 Θ̃_p((L_pD^p/ε)^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.

Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities
Jun-Hyun Kim, Ahmet Alacaoglu
arXiv24 Sep 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Averaged proximal reflected gradient method for monotone variational inequalities
Xiaokai Chang, Jialin Li, Jun Yang
arXiv15 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
A Projection Anderson Acceleration Algorithm for Non-quasi-monotone Variational Inequalities with Hölder Continuous Terms
Xiaojun Chen, C. T. Kelley, Lei Wang
arXiv13 Oct 2026PreprintarXiv licenceFull textNumerical analysis & scientific computing Optimisation & controlarXiv
Optimal High-Order Methods for Solving Monotone Variational Inequalities
Xinliang Zhang, Lesi Chen, Linxuan Pan +3
arXiv20 Sep 2026PreprintarXiv licenceFull textOptimisation & control StatisticsarXiv
On Fixed-Time Stability of Continuous Dynamics for Non-Monotone Variational Inequalities
Sina Arefizadeh, Kunal Garg, Angelia Nedić
arXiv28 Sep 2026PreprintarXiv licenceFull textDynamical systems Optimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{zhang2026matching,
  title = {{Matching Higher-Order Oracle Complexity for Smooth Monotone Variational Inequalities}},
  author = {Haihan Zhang and Wendao Wu and Chenheng Zhang and Cong Fang and Haoxuan Li and Zhouchen Lin},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.13462},
  eprint = {2609.13462},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.13462},
}

RIS

TY  - UNPB
TI  - Matching Higher-Order Oracle Complexity for Smooth Monotone Variational Inequalities
AU  - Haihan Zhang
AU  - Wendao Wu
AU  - Chenheng Zhang
AU  - Cong Fang
AU  - Haoxuan Li
AU  - Zhouchen Lin
PY  - 2026
DA  - 2026/10/19
PB  - arXiv
DO  - 10.48550/arxiv.2609.13462
UR  - https://arxiv.org/abs/2609.13462
AB  - 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 Lip(D^p−1F)≤ L_p. Each feasible query returns the complete jet (F,DF,…,D^p−1F), and the goal is to find x with tangent residual dist(0,F(x)+N_X(x))≤ε. Writing Q=L_pD^p/ε, we improve the Õ_p(Q^1/p) upper bound of Chen et al. to Õ_p(Q^2/(3p−1)) via a dimension-independent deterministic algorithm that returns an explicit tangent-residual certificate. We prove a matching Ω_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 Θ̃_p((L_pD^p/ε)^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.
ER  -

Abstract

Related

Cite