# Halpern Iteration Achieves tildeO(ε-1/p) pth-Order Oracle Complexity for Monotone Variational Inequalities

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 63 references that are in the map.
- First posted on arXiv 9 Aug 2026.

## Builds on (most cited first, 30 of 36)

- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [Mitigating Unwanted Biases with Adversarial Learning](https://mlsanity.com/paper/1801.07593/) (2018)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Norm](https://mlsanity.com/paper/2102.07922/) (2021)
- [Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2106.02326/) (2021)
- [Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities](https://mlsanity.com/paper/2002.08872/) (2020)
- [An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications](https://mlsanity.com/paper/2004.04250/) (2020)
- [Accelerated Single-Call Methods for Constrained Min-Max Optimization](https://mlsanity.com/paper/2210.03096/) (2022)
- [Oracle Complexity of Second-Order Methods for Smooth Convex Optimization](https://mlsanity.com/paper/1705.07260/) (2017)
- [Optimal and Adaptive Monteiro-Svaiter Acceleration](https://mlsanity.com/paper/2205.15371/) (2022)
- [Optimal Black-Box Reductions Between Optimization Objectives](https://mlsanity.com/paper/1603.05642/) (2016)
- [The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization](https://mlsanity.com/paper/2205.09647/) (2022)
- [Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion](https://mlsanity.com/paper/2206.05248/) (2022)
- [Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization](https://mlsanity.com/paper/2208.05925/) (2022)
- [Faster Matrix Multiplication via Asymmetric Hashing](https://mlsanity.com/paper/2210.10173/) (2022)
- [ODE Analysis of Stochastic Gradient Methods with Optimism and Anchoring for Minimax Problems](https://mlsanity.com/paper/1905.10899/) (2019)
- [Near-optimal method for highly smooth convex optimization](https://mlsanity.com/paper/1812.08026/) (2018)
- [Higher-order methods for convex-concave min-max optimization and monotone variational inequalities](https://mlsanity.com/paper/2007.04528/) (2020)
- [Generalized Optimistic Methods for Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/2202.09674/) (2022)
- [Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback](https://mlsanity.com/paper/2112.02856/) (2021)
- [Distributionally Robust Optimization via Ball Oracle Acceleration](https://mlsanity.com/paper/2203.13225/) (2022)
- [Lower Bounds for Higher-Order Convex Optimization](https://mlsanity.com/paper/1710.10329/) (2017)
- [An Optimal High-Order Tensor Method for Convex Optimization](https://mlsanity.com/paper/1812.06557/) (2018)
- [Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions](https://mlsanity.com/paper/2310.02987/) (2023)
- [The global rate of convergence for optimal tensor methods in smooth convex optimization](https://mlsanity.com/paper/1809.00382/) (2018)
- [Optimal Methods for Higher-Order Smooth Monotone Variational Inequalities](https://mlsanity.com/paper/2205.06167/) (2022)
- [Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization](https://mlsanity.com/paper/2406.02016/) (2024)
- [Tensor methods for strongly convex strongly concave saddle point problems and strongly monotone variational inequalities](https://mlsanity.com/paper/2012.15595/) (2020)
- [Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness](https://mlsanity.com/paper/2112.01118/) (2021)
- [An Approximation-Based Regularized Extra-Gradient Method for Monotone Variational Inequalities](https://mlsanity.com/paper/2210.04440/) (2022)

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

- [Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems](https://mlsanity.com/paper/2609.30212/) (2026)

## 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 the rate of O(T-1.5). For convex-concave minimax optimization, a subset of MVI problems, Chen, Liu, Luo, and Zhang (COLT 2025) recently improved the complexity to tildeO( T-1.75) . However, it is open whether the conjectured complexity for MVI can be improved. In this paper, by using a large-step inexact Halpern iteration, we propose a novel Halpern-NPE method that achieves an even faster rate of tildeO(T-2) for solving MVIs. We also provide the pth-order generalization of our method. We first introduce an Anchored Tensor Method (ATM) that achieves the rate of O(T-(p-1)), and then combine it with the Halpern iteration to achieve a faster convergence rate of tildeO(T-p). This improves all prior results for p ≥ 2 and matches the classical extragradient method for p=1.