# Learning Variational Inequalities from Data: Fast Generalization Rates under Strong Monotonicity

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 50 references that are in the map.
- First posted on arXiv 28 Oct 2024.

## Builds on (most cited first, 22 of 22)

- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [StarCraft II: A New Challenge for Reinforcement Learning](https://mlsanity.com/paper/1708.04782/) (2017)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [Stability and Generalization of Learning Algorithms that Converge to Global Optima](https://mlsanity.com/paper/1710.08402/) (2017)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Data-Dependent Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/1703.01678/) (2017)
- [Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/2002.00057/) (2020)
- [Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling](https://mlsanity.com/paper/2003.10162/) (2020)
- [Train simultaneously, generalize better: Stability of gradient-based minimax learners](https://mlsanity.com/paper/2010.12561/) (2020)
- [Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity](https://mlsanity.com/paper/2107.00052/) (2021)
- [Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)](https://mlsanity.com/paper/2103.12024/) (2021)
- [Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity](https://mlsanity.com/paper/2110.04261/) (2021)
- [Stochastic Extragradient: General Analysis and Improved Rates](https://mlsanity.com/paper/2111.08611/) (2021)
- [Generalization Bounds for Stochastic Saddle Point Problems](https://mlsanity.com/paper/2006.02067/) (2020)
- [A variational inequality framework for network games: Existence, uniqueness, convergence and sensitivity analysis](https://mlsanity.com/paper/1712.08277/) (2017)
- [Last-Iterate Convergence of Saddle-Point Optimizers via High-Resolution Differential Equations](https://mlsanity.com/paper/2112.13826/) (2021)
- [Solving Constrained Variational Inequalities via a First-order Interior Point-based Method](https://mlsanity.com/paper/2206.10575/) (2022)
- [Addressing Rotational Learning Dynamics in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2410.07976/) (2024)

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

- [Finite-sample guarantees for data-driven forward-backward operator methods](https://mlsanity.com/paper/2512.19172/) (2025)

## Abstract (arXiv)

Variational inequalities (VIs) are a broad class of optimization problems encompassing machine learning problems ranging from standard convex minimization to more complex scenarios like min-max optimization and computing the equilibria of multi-player games. In convex optimization, strong convexity allows for fast statistical learning rates requiring only Theta(1/ε) stochastic first-order oracle calls to find an ε-optimal solution, rather than the standard Theta(1/ε2) calls. This note provides a simple overview of how one can similarly obtain fast Theta(1/ε) rates for learning VIs that satisfy strong monotonicity, a generalization of strong convexity. Specifically, we demonstrate that standard stability-based generalization arguments for convex minimization extend directly to VIs when the domain admits a small covering, or when the operator is integrable and suboptimality is measured by potential functions; such as when finding equilibria in multi-player games.