# A search-free O(1/k3/2) homotopy inexact proximal-Newton extragradient algorithm for monotone variational inequalities

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Aug 2023.

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

- [Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization](https://mlsanity.com/paper/2406.02016/) (2024)
- [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)
- [Halpern Iteration Achieves tildeO(ε-1/p) pth-Order Oracle Complexity for Monotone Variational Inequalities](https://mlsanity.com/paper/2608.08463/) (2026)
- [Optimal High-Order Methods for Solving Monotone Variational Inequalities](https://mlsanity.com/paper/2609.23557/) (2026)

## Abstract (arXiv)

We present and study the iteration-complexity of a relative-error inexact proximal-Newton extragradient algorithm for solving smooth monotone variational inequality problems in real Hilbert spaces. We removed a search procedure from Monteiro and Svaiter (2012) by introducing a novel approach based on homotopy, which requires the resolution (at each iteration) of a single strongly monotone linear variational inequality. For a given tolerance ρ>0, our main algorithm exhibits pointwise Oleft(frac1ρright) and ergodic Oleft(frac1ρ2/3right) iteration-complexities. From a practical perspective, preliminary numerical experiments indicate that our main algorithm outperforms some previous proximal-Newton schemes.