mlsanityData to 14 Oct 2026

Expected Variational Inequalities

arXiv 2502.18605 ↗First posted 25 Feb 2025cs.GT cs.LG math.OCcited by 5

Not on the map. Why?

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.

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

49 of 102 references.

References · 49

  1. 2021Convex optimizationcited by 2,515
  2. 2019Introduction to Online Convex Optimizationcited by 803
  3. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 96
  4. 2020The Complexity of Constrained Min-Max Optimizationcited by 82
  5. 2016Learning in games with continuous action sets and unknown payoff functionscited by 81
  6. 2016Gradient Descent Learns Linear Dynamical Systemscited by 79
  7. 2020SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolationcited by 67
  8. 2021Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problemscited by 62
  9. 2018Finding Mixed Nash Equilibria of Generative Adversarial Networkscited by 49
  10. 2021A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensionscited by 39
  11. 2019Near-Optimal Methods for Minimizing Star-Convex Functions and Beyondcited by 36
  12. 2023Fast swap regret minimization and applications to approximate correlated equilibriacited by 32
37 more
  1. 2016Settling the complexity of computing approximate two-player Nash equilibriacited by 31
  2. 2021On the Finite-Time Complexity and Practical Computation of Approximate Stationarity Concepts of Lipschitz Functionscited by 31
  3. 2020A mean-field analysis of two-player zero-sum gamescited by 28
  4. 2015Projected Reflected Gradient Methods for Monotone Variational Inequalitiescited by 27
  5. 2019Generalized monotone operators and their averaged resolventscited by 27
  6. 2022Solving Nonconvex-Nonconcave Min-Max Problems exhibiting Weak Minty Solutionscited by 27
  7. 2023Deterministic Nonsmooth Nonconvex Optimizationcited by 26
  8. 2020Hindsight and Sequential Rationality of Correlated Playcited by 22
  9. 2021Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibriumcited by 22
  10. 2023Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problemscited by 21
  11. 2022Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusioncited by 20
  12. 2014Inapproximability of Nash Equilibriumcited by 17
  13. 2022Convergence of Proximal Point and Extragradient-Based Methods Beyond Monotonicity: the Case of Negative Comonotonicitycited by 16
  14. 2021Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Gamescited by 15
  15. 2023Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditionscited by 14
  16. 2016The Price of Anarchy in Auctionscited by 12
  17. 2022Beyond the Golden Ratio for Variational Inequality Algorithmscited by 12
  18. 2024Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Gamescited by 12
  19. 2022First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problemscited by 9
  20. 2023Polynomial-Time Linear-Swap Regret Minimization in Imperfect-Information Sequential Gamescited by 9
  21. 2024A Lower Bound on Swap Regret in Extensive-Form Gamescited by 8
  22. 2017Accelerated Methods for α-Weakly-Quasi-Convex Problemscited by 7
  23. 2013Query Complexity of Approximate Nash Equilibriacited by 6
  24. 2021Semi-Anchored Multi-Step Gradient Descent Ascent Method for Structured Nonconvex-Nonconcave Composite Minimax Problemscited by 6
  25. 2022Exploitability Minimization in Games and Beyondcited by 6
  26. 2023Accelerated Stochastic Optimization Methods under Quasar-convexitycited by 6
  27. 2023Bayes correlated equilibria, no-regret dynamics in Bayesian games, and the price of anarchycited by 5
  28. 2023Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methodscited by 5
  29. 2024First-order (coarse) correlated equilibria in non-concave gamescited by 5
  30. 2024Improved Hardness Results for Min-Max Optimization with Coupled Constraintscited by 5
  31. 2017Learning Generalized Nash Equilibria in a Class of Convex Gamescited by 4
  32. 2023Constrained Phi-Equilibriacited by 4
  33. 2024Polynomial-Time Computation of Exact Phi-Equilibria in Polyhedral Gamescited by 4
  34. 2023Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Extensive-Form Gamescited by 3
  35. 2022Tight Inapproximability for Graphical Gamescited by 2
  36. 2023Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Propertycited by 2
  37. 2024On Tractable Phi-Equilibria in Non-Concave Gamescited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 4.

5 papers.

  1. 2025Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Gamescited by 3
  2. 2026An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to Phi-Regret Minimizationcited by 3
  3. 2026On the Computational Complexity of Performative Predictioncited by 2
  4. 2026Swap Regret Minimization Through Response-Based Approachabilitycited by 2
  5. 2026Defensive Generationcited by 1