Optimal High-Order Methods for Solving Monotone Variational Inequalities
En palabras de los autores
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 . For convex-concave minimax optimization, a subclass of MVI problems, Chen, Liu, Luo, and Zhang (COLT 2025) recently improved this rate to . However, the result has a substantial gap compared to the lower bound of established by Chen et al. (2026). In this paper, we propose a novel second-order method that achieves the optimal rate of . Our algorithm also extends to higher-order methods: for any integer , we obtain a th-order method with a convergence rate of , matching the known lower bounds and therefore establishing optimal rates across all orders.
Apareció: martes, 22 de septiembre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: Improve our previous note in https://arxiv.org/abs/2608.08463 and achieve optimal complexity