Optimal High-Order Methods for Solving Monotone Variational Inequalities

Abstract

We study second- and higher-order methods for solving smooth monotone variational inequalities (MVI). Monteiro and Svaiter (SIAM J. Optim., 2012) showed that a second-order method, NPE, converges at a rate of 𝒪(T^−1.5). For convex-concave minimax optimization, a subclass of MVI problems, Chen, Liu, Luo, and Zhang (COLT 2025) recently improved this rate to 𝒪̃( T^−1.75). However, the result has a substantial gap compared to the lower bound of Ω(T^−2.5) established by Chen et al. (2026). In this paper, we propose a novel second-order method that achieves the optimal rate of 𝒪(T^−2.5). Our algorithm also extends to higher-order methods: for any integer $ p \ge 1$, we obtain a pth-order method with a convergence rate of 𝒪(T^{−(3p−1)/2}), matching the known lower bounds and therefore establishing optimal rates across all orders.

Primal Methods for Constrained Variational Inequalities: Optimal Rates, Feasibility Trade-offs, and Lower Bounds
Yonghong Yao, Lateef O. Jolaoso, Yekini Shehu +1
arXiv26 Sep 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
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
Solving Quasi-Variational Inequalities Using the Progressive Decoupling of Linkages
Manoel Jardim, Claudia Sagastizábal, Mikhail Solodov
arXiv27 Aug 2026PreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{zhang2026optimal,
  title = {{Optimal High-Order Methods for Solving Monotone Variational Inequalities}},
  author = {Xinliang Zhang and Lesi Chen and Linxuan Pan and Chengchang Liu and Junchi Yang and Jingzhao Zhang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.23557},
  eprint = {2609.23557},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.23557},
}

RIS

TY  - UNPB
TI  - Optimal High-Order Methods for Solving Monotone Variational Inequalities
AU  - Xinliang Zhang
AU  - Lesi Chen
AU  - Linxuan Pan
AU  - Chengchang Liu
AU  - Junchi Yang
AU  - Jingzhao Zhang
PY  - 2026
DA  - 2026/09/20
PB  - arXiv
DO  - 10.48550/arxiv.2609.23557
UR  - https://arxiv.org/abs/2609.23557
AB  - We study second- and higher-order methods for solving smooth monotone variational inequalities (MVI). Monteiro and Svaiter (SIAM J. Optim., 2012) showed that a second-order method, NPE, converges at a rate of 𝒪(T^−1.5). For convex-concave minimax optimization, a subclass of MVI problems, Chen, Liu, Luo, and Zhang (COLT 2025) recently improved this rate to 𝒪̃( T^−1.75). However, the result has a substantial gap compared to the lower bound of Ω(T^−2.5) established by Chen et al. (2026). In this paper, we propose a novel second-order method that achieves the optimal rate of 𝒪(T^−2.5). Our algorithm also extends to higher-order methods: for any integer $ p \ge 1$, we obtain a pth-order method with a convergence rate of 𝒪(T^−(3p−1)/2), matching the known lower bounds and therefore establishing optimal rates across all orders.
ER  -

Abstract

Related

Cite