# Perseus: A Simple and Optimal High-Order Method for Variational Inequalities

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 120 references that are in the map.
- First posted on arXiv 6 May 2022.

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

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Convergence Analysis of Two-layer Neural Networks with ReLU Activation](https://mlsanity.com/paper/1705.09886/) (2017)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [An Alternative View: When Does SGD Escape Local Minima?](https://mlsanity.com/paper/1802.06175/) (2018)
- [A Variational Perspective on Accelerated Methods in Optimization](https://mlsanity.com/paper/1603.04245/) (2016)
- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization](https://mlsanity.com/paper/2011.00364/) (2020)
- [The Complexity of Constrained Min-Max Optimization](https://mlsanity.com/paper/2009.09623/) (2020)
- [Learning in games with continuous action sets and unknown payoff functions](https://mlsanity.com/paper/1608.07310/) (2016)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities](https://mlsanity.com/paper/2002.08872/) (2020)
- [Tight last-iterate convergence rates for no-regret learning in multi-player games](https://mlsanity.com/paper/2010.13724/) (2020)
- [Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation](https://mlsanity.com/paper/2011.02987/) (2020)
- [First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems](https://mlsanity.com/paper/1810.10207/) (2018)
- [An optimal randomized incremental gradient method](https://mlsanity.com/paper/1507.02000/) (2015)
- [Extragradient method with variance reduction for stochastic variational inequalities](https://mlsanity.com/paper/1703.00260/) (2017)
- [Accelerated Schemes For A Class of Variational Inequalities](https://mlsanity.com/paper/1403.4164/) (2014)
- [On the Convergence Properties of Non-Euclidean Extragradient Methods for Variational Inequalities with Generalized Monotone Operators](https://mlsanity.com/paper/1311.2776/) (2013)
- [Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities](https://mlsanity.com/paper/2103.04410/) (2021)
- [On Lower Iteration Complexity Bounds for the Saddle Point Problems](https://mlsanity.com/paper/1912.07481/) (2019)
- [Oracle Complexity of Second-Order Methods for Smooth Convex Optimization](https://mlsanity.com/paper/1705.07260/) (2017)
- [Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants](https://mlsanity.com/paper/1410.1628/) (2014)
- [Gradient Descent Finds the Cubic-Regularized Non-Convex Newton Step](https://mlsanity.com/paper/1612.00547/) (2016)
- [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)
- [Random gradient extrapolation for distributed and stochastic optimization](https://mlsanity.com/paper/1711.05762/) (2017)
- [A Simple Nearly-Optimal Restart Scheme For Speeding-Up First Order Methods](https://mlsanity.com/paper/1803.00151/) (2018)
- [Adaptive restart of accelerated gradient methods under local quadratic growth condition](https://mlsanity.com/paper/1709.02300/) (2017)
- [Local convergence of tensor methods](https://mlsanity.com/paper/1912.02516/) (2019)
- [Tensor methods for strongly convex strongly concave saddle point problems and strongly monotone variational inequalities](https://mlsanity.com/paper/2012.15595/) (2020)

## 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)
- [Multiple Greedy Quasi-Newton Methods for Saddle Point Problems](https://mlsanity.com/paper/2408.00241/) (2024)
- [Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis](https://mlsanity.com/paper/2210.12860/) (2022)
- [An Augmented Lagrangian Approach to Conically Constrained Non-monotone Variational Inequality Problems](https://mlsanity.com/paper/2306.01214/) (2023)
- [Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problems](https://mlsanity.com/paper/2411.15769/) (2024)

## Abstract (arXiv)

This paper settles an open and challenging question pertaining to the design of simple and optimal high-order methods for solving smooth and monotone variational inequalities (VIs). A VI involves finding x^star ∈ X such that langle F(x), x - x^starrangle ≥ 0 for all x ∈ X. We consider the setting in which F is smooth with up to (p-1)th-order derivatives. For p = 2, the cubic regularized Newton method was extended to VIs with a global rate of O(ε-1). An improved rate of O(ε-2/3loglog(1/ε)) can be obtained via an alternative second-order method, but this method requires a nontrivial line-search procedure as an inner loop. Similarly, high-order methods based on line-search procedures have been shown to achieve a rate of O(ε-2/(p+1)loglog(1/ε)). As emphasized by Nesterov, however, such procedures do not necessarily imply practical applicability in large-scale applications, and it would be desirable to complement these results with a simple high-order VI method that retains the optimality of the more complex methods. We propose a pth-order method that does textitnot require any line search procedure and provably converges to a weak solution at a rate of O(ε-2/(p+1)). We prove that our pth-order method is optimal in the monotone setting by establishing a matching lower bound under a generalized linear span assumption. Our method with restarting attains a linear rate for smooth and uniformly monotone VIs and a local superlinear rate for smooth and strongly monotone VIs. Our method also achieves a global rate of O(ε-2/p) for solving smooth and nonmonotone VIs satisfying the Minty condition and when augmented with restarting it attains a global linear and local superlinear rate for smooth and nonmonotone VIs satisfying the uniform/strong Minty condition.