# Expected Variational Inequalities

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 49 of its 102 references that are in the map.
- First posted on arXiv 25 Feb 2025.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [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)
- [Gradient Descent Learns Linear Dynamical Systems](https://mlsanity.com/paper/1609.05191/) (2016)
- [SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation](https://mlsanity.com/paper/2006.10311/) (2020)
- [Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2106.02326/) (2021)
- [Finding Mixed Nash Equilibria of Generative Adversarial Networks](https://mlsanity.com/paper/1811.02002/) (2018)
- [A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensions](https://mlsanity.com/paper/2112.06969/) (2021)
- [Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond](https://mlsanity.com/paper/1906.11985/) (2019)
- [Fast swap regret minimization and applications to approximate correlated equilibria](https://mlsanity.com/paper/2310.19647/) (2023)
- [Settling the complexity of computing approximate two-player Nash equilibria](https://mlsanity.com/paper/1606.04550/) (2016)
- [On the Finite-Time Complexity and Practical Computation of Approximate Stationarity Concepts of Lipschitz Functions](https://mlsanity.com/paper/2112.09002/) (2021)
- [A mean-field analysis of two-player zero-sum games](https://mlsanity.com/paper/2002.06277/) (2020)
- [Projected Reflected Gradient Methods for Monotone Variational Inequalities](https://mlsanity.com/paper/1502.04968/) (2015)
- [Generalized monotone operators and their averaged resolvents](https://mlsanity.com/paper/1902.09827/) (2019)
- [Solving Nonconvex-Nonconcave Min-Max Problems exhibiting Weak Minty Solutions](https://mlsanity.com/paper/2201.12247/) (2022)
- [Deterministic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2302.08300/) (2023)
- [Hindsight and Sequential Rationality of Correlated Play](https://mlsanity.com/paper/2012.05874/) (2020)
- [Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium](https://mlsanity.com/paper/2104.01520/) (2021)
- [Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems](https://mlsanity.com/paper/2302.09831/) (2023)
- [Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion](https://mlsanity.com/paper/2206.05248/) (2022)
- [Inapproximability of Nash Equilibrium](https://mlsanity.com/paper/1405.3322/) (2014)
- [Convergence of Proximal Point and Extragradient-Based Methods Beyond Monotonicity: the Case of Negative Comonotonicity](https://mlsanity.com/paper/2210.13831/) (2022)
- [Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Games](https://mlsanity.com/paper/2102.06973/) (2021)
- [Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions](https://mlsanity.com/paper/2302.14043/) (2023)
- [The Price of Anarchy in Auctions](https://mlsanity.com/paper/1607.07684/) (2016)
- [Beyond the Golden Ratio for Variational Inequality Algorithms](https://mlsanity.com/paper/2212.13955/) (2022)
- [Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games](https://mlsanity.com/paper/2412.20291/) (2024)

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

- [Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games](https://mlsanity.com/paper/2511.01852/) (2025)
- [An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to Phi-Regret Minimization](https://mlsanity.com/paper/2604.19592/) (2026)
- [On the Computational Complexity of Performative Prediction](https://mlsanity.com/paper/2601.20180/) (2026)
- [Swap Regret Minimization Through Response-Based Approachability](https://mlsanity.com/paper/2602.06264/) (2026)
- [Defensive Generation](https://mlsanity.com/paper/2602.21390/) (2026)

## Abstract (arXiv)

Variational inequalities (VIs) encompass many fundamental problems in diverse areas ranging from engineering to economics and machine learning. However, their considerable expressivity comes at the cost of computational intractability. In this paper, we introduce and analyze a natural relaxation -- which we refer to as expected variational inequalities (EVIs) -- where the goal is to find a distribution that satisfies the VI constraint in expectation. By adapting recent techniques from game theory, we show that, unlike VIs, EVIs can be solved in polynomial time under general (nonmonotone) operators. EVIs capture the seminal notion of correlated equilibria, but enjoy a greater reach beyond games. We also employ our framework to capture and generalize several existing disparate results, including from settings such as smooth games, and games with coupled constraints or nonconcave utilities.