# Higher-order methods for convex-concave min-max optimization and monotone variational inequalities

arXiv: https://arxiv.org/abs/2007.04528 · HTML: https://mlsanity.com/paper/2007.04528/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jul 2020.

## Built on by (most cited first, 16 of 16)

- [Decentralized Local Stochastic Extra-Gradient for Variational Inequalities](https://mlsanity.com/paper/2106.08315/) (2021)
- [The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization](https://mlsanity.com/paper/2205.09647/) (2022)
- [Generalized Optimistic Methods for Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/2202.09674/) (2022)
- [Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods](https://mlsanity.com/paper/2211.01832/) (2022)
- [Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization](https://mlsanity.com/paper/2406.02016/) (2024)
- [Perseus: A Simple and Optimal High-Order Method for Variational Inequalities](https://mlsanity.com/paper/2205.03202/) (2022)
- [Second-Order Min-Max Optimization with Lazy Hessians](https://mlsanity.com/paper/2410.09568/) (2024)
- [A Fully Parameter-Free Second-Order Algorithm for Convex-Concave Minimax Problems](https://mlsanity.com/paper/2407.03571/) (2024)
- [Multiple Greedy Quasi-Newton Methods for Saddle Point Problems](https://mlsanity.com/paper/2408.00241/) (2024)
- [Beyond first-order methods for non-convex non-concave min-max optimization](https://mlsanity.com/paper/2304.08389/) (2023)
- [Halpern Iteration Achieves tildeO(ε-1/p) pth-Order Oracle Complexity for Monotone Variational Inequalities](https://mlsanity.com/paper/2608.08463/) (2026)
- [Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis](https://mlsanity.com/paper/2210.12860/) (2022)
- [Federated Composite Saddle Point Optimization](https://mlsanity.com/paper/2305.15643/) (2023)
- [Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problems](https://mlsanity.com/paper/2411.15769/) (2024)
- [Solving Convex-Concave Problems with tildeO(ε-4/7) Second-Order Oracle Complexity](https://mlsanity.com/paper/2506.08362/) (2025)
- [Optimal High-Order Methods for Solving Monotone Variational Inequalities](https://mlsanity.com/paper/2609.23557/) (2026)

## Abstract (arXiv)

We provide improved convergence rates for constrained convex-concave min-max problems and monotone variational inequalities with higher-order smoothness. In min-max settings where the pth-order derivatives are Lipschitz continuous, we give an algorithm HigherOrderMirrorProx that achieves an iteration complexity of O(1/T^fracp+12) when given access to an oracle for finding a fixed point of a pth-order equation. We give analogous rates for the weak monotone variational inequality problem. For p>2, our results improve upon the iteration complexity of the first-order Mirror Prox method of Nemirovski [2004] and the second-order method of Monteiro and Svaiter [2012]. We further instantiate our entire algorithm in the unconstrained p=2 case.