mlsanityData to 14 Oct 2026

Optimal High-Order Methods for Solving Monotone Variational Inequalities

arXiv 2609.23557 ↗First posted 20 Sep 2026math.OC cs.GT stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

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 O(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 tildeO( T-1.75). However, the result has a substantial gap compared to the lower bound of Omega(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 O(T-2.5). Our algorithm also extends to higher-order methods: for any integer p ≥ 1, we obtain a pth-order method with a convergence rate of O(T-(3p-1)/2), matching the known lower bounds and therefore establishing optimal rates across all orders.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 34 of its 61 references that are in the map. First posted on arXiv 20 Sep 2026.

Builds on

34 of 61 references.

References · 34

  1. 2022Generative Adversarial Networkscited by 5,627
  2. 2018Mitigating Unwanted Biases with Adversarial Learningcited by 663
  3. 2019On the convergence of single-call stochastic extra-gradient methodscited by 89
  4. 2020Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalitiescited by 61
  5. 2020An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applicationscited by 57
  6. 2021Stochastic Variance Reduction for Variational Inequality Methodscited by 47
  7. 2022Accelerated Single-Call Methods for Constrained Min-Max Optimizationcited by 32
  8. 2017Oracle Complexity of Second-Order Methods for Smooth Convex Optimizationcited by 24
  9. 2022Optimal and Adaptive Monteiro-Svaiter Accelerationcited by 24
  10. 2022The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimizationcited by 20
  11. 2022Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusioncited by 20
  12. 2022Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimizationcited by 20
22 more
  1. 2022Faster Matrix Multiplication via Asymmetric Hashingcited by 19
  2. 2018Near-optimal method for highly smooth convex optimizationcited by 16
  3. 2020Higher-order methods for convex-concave min-max optimization and monotone variational inequalitiescited by 16
  4. 2022Generalized Optimistic Methods for Convex-Concave Saddle Point Problemscited by 16
  5. 2021Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedbackcited by 15
  6. 2022Distributionally Robust Optimization via Ball Oracle Accelerationcited by 14
  7. 2017Lower Bounds for Higher-Order Convex Optimizationcited by 12
  8. 2018An Optimal High-Order Tensor Method for Convex Optimizationcited by 12
  9. 2023Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusionscited by 11
  10. 2018The global rate of convergence for optimal tensor methods in smooth convex optimizationcited by 10
  11. 2022Optimal Methods for Higher-Order Smooth Monotone Variational Inequalitiescited by 10
  12. 2024Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimizationcited by 8
  13. 2021Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothnesscited by 6
  14. 2022An Approximation-Based Regularized Extra-Gradient Method for Monotone Variational Inequalitiescited by 6
  15. 2023Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedbackcited by 6
  16. 2018Monotone Operator Theory in Convex Optimizationcited by 5
  17. 2021Monotone Inclusions, Acceleration and Closed-Loop Controlcited by 5
  18. 2023A search-free O(1/k3/2) homotopy inexact proximal-Newton extragradient algorithm for monotone variational inequalitiescited by 5
  19. 2024Second-Order Min-Max Optimization with Lazy Hessianscited by 5
  20. 2023High-Order Reduced-Gradient Methods for Composite Variational Inequalitiescited by 4
  21. 2024Exploring Jacobian Inexactness in Second-Order Methods for Variational Inequalities: Lower Bounds, Optimal Algorithms and Quasi-Newton Approximationscited by 2
  22. 2026Matching Higher-Order Oracle Complexity for Smooth Monotone Variational Inequalitiescited by 2

Built on by

Not cited yet.