Convergence of Proximal Point and Extragradient-Based Methods Beyond Monotonicity: the Case of Negative Comonotonicity

Eduard Gorbunov, Adrien Taylor, Samuel Horváth, Gauthier Gidel

Abstract

Algorithms for min-max optimization and variational inequalities are often studied under monotonicity assumptions. Motivated by non-monotone machine learning applications, we follow the line of works [Diakonikolas et al., 2021, Lee and Kim, 2021, Pethick et al., 2022, Böhm, 2022] aiming at going beyond monotonicity by considering the weaker negative comonotonicity assumption. In particular, we provide tight complexity analyses for the Proximal Point, Extragradient, and Optimistic Gradient methods in this setup, closing some questions on their working guarantees beyond monotonicity.

Introduction

In machine learning, many complex problems such as Generative Adversarial Networks (GANs) and adversarial training are modeled as min-max games or Variational Inequality Problems (VIPs). Standard convergence analyses for these problems typically rely on the assumption of monotonicity—the property that the operator always points towards the solution. However, real-world applications often violate this condition. To bridge this gap, recent research has focused on negative comonotonicity, a weaker and more flexible assumption that allows for certain non-monotone behaviors while still providing a structured framework for analysis.

Methodology: Computer-Aided Performance Estimation

The authors utilize a modern "computer-aided" approach to establish tight convergence bounds. By formulating the search for worst-case performance as a semi-definite program (SDP), they leverage the PEPit Python package to numerically identify the limits of standard algorithms.

This numerical exploration is complemented by a spectral interpretation of negative comonotonicity. The authors demonstrate that this condition effectively restricts the eigenvalues of the operator's Jacobian, preventing them from falling into a specific "danger zone" near the origin. To prove the tightness of their derived bounds, they analytically construct specific 2D rotational operators that represent the absolute worst-case scenarios identified by the computer.

Key Insights: The Step-Size Threshold and Tightness

A critical finding of this work concerns the Proximal Point (PP) method. In many optimization contexts, smaller stepsizes are considered safer. However, under negative comonotonicity, the authors prove that the stepsize $\gamma$ must exceed $2\rho$. If the stepsize is too small, the algorithm fails to converge and instead spirals away from the solution.

Worst-case trajectories for the Proximal Point method with $\rho=1$. When the stepsize $\gamma$ is close to the $2\rho$ threshold (e.g., $\gamma=2.05$), the trajectory exhibits significant spiraling behavior.

Furthermore, the research establishes that the $O(1/N)$ convergence rate is the fundamental limit for these methods in this regime. The authors also show that negative comonotonicity implies a convex solution set, suggesting that while it is weaker than monotonicity, it still cannot model landscapes with multiple isolated local optima.

Summary of Results

The primary contribution of this paper is the "tightening" of convergence guarantees for three foundational methods: Proximal Point (PP), Extragradient (EG), and Optimistic Gradient (OG).

Summary of convergence results and comparison with existing literature. The green highlights indicate the improved bounds and ranges established in this work.

Key achievements include:

  • Proximal Point (PP): Established the first non-asymptotic $O(1/N)$ last-iterate convergence rate.
  • Extragradient (EG): Improved the range for last-iterate convergence to $\rho < 1/8L$ (previously $1/16L$).
  • Optimistic Gradient (OG): Extended the last-iterate convergence range to $\rho \leq 5/62L$.
  • Divergence Limits: Proved that for $\rho \geq 1/2L$, both EG and OG can diverge regardless of the stepsize.

Conclusion and Future Directions

This work provides a definitive analysis of standard optimization methods under negative comonotonicity. While it pushes the boundaries of what we know about non-monotone optimization, the requirement of a convex solution set remains a limitation for deep learning. Future research will focus on extending these tight analyses to stochastic settings and identifying even broader structural assumptions that can handle the complex, non-convex landscapes of modern neural networks.

Summary updated

Abstract

Algorithms for min-max optimization and variational inequalities are often studied under monotonicity assumptions. Motivated by non-monotone machine learning applications, we follow the line of works [Diakonikolas et al., 2021, Lee and Kim, 2021, Pethick et al., 2022, Böhm, 2022] aiming at going beyond monotonicity by considering the weaker negative comonotonicity assumption. In particular, we provide tight complexity analyses for the Proximal Point, Extragradient, and Optimistic Gradient methods in this setup, closing some questions on their working guarantees beyond monotonicity.
BibTeX
@inproceedings{gorbunov2023convergence,
  author = {Eduard Gorbunov and Adrien Taylor and Samuel Horváth and Gauthier Gidel},
  title = {{Convergence of Proximal Point and Extragradient-Based Methods Beyond Monotonicity: the Case of Negative Comonotonicity}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=2WJ8cvLQ0O},
}
Figure