Related papers: Expected Variational Inequalities

Expected Variational Inequalities

URL: http://arxiv.org/abs/2502.18605v2
Date: Fri, 28 Feb 2025 00:54:47 GMT
Title: Expected Variational Inequalities
Authors: Brian Hu Zhang, Ioannis Anagnostides, Emanuel Tewolde, Ratip Emin Berker, Gabriele Farina, Vincent Conitzer, Tuomas Sandholm,
Abstract summary: Variational inequalities (VIs) encompass many fundamental problems in diverse areas ranging from engineering to economics and machine learning.<n>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.
Score: 85.07238533644636
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: 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.

Related papers

A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition [79.18735797001183]
Solving (Stampacchia) variational inequalities (SVIs) is a foundational problem at the heart of optimization. We introduce a new variant of the ellipsoid algorithm wherein hyperplanes are obtained after taking a gradient descent step from the center of the ellipsoid. We provide several extensions and new applications of our main results.
arXiv Detail & Related papers (2025-04-04T13:24:41Z)
Generalization Bounds for Causal Regression: Insights, Guarantees and Sensitivity Analysis [0.66567375919026]
We propose a theory based on generalization bounds that provides such guarantees. By introducing a novel change-of-measure inequality, we are able to tightly bound the model loss. We demonstrate our bounds on semi-synthetic and real data, showcasing their remarkable tightness and practical utility.
arXiv Detail & Related papers (2024-05-15T17:17:27Z)
Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions [21.681130192954583]
Single-call extragradient methods are one of the most efficient algorithms for solving large-scale min-max optimization problems. We provide convergence guarantees for two classes of VIPs: (i) quasi-strongly monotone problems (a generalization of strongly monotone problems) and (ii) weak Minty variational inequalities (a generalization of monotone and Minty VIPs) Our convergence analysis holds under the arbitrary sampling paradigm, which includes importance sampling and various mini-batching strategies as special cases.
arXiv Detail & Related papers (2023-02-27T18:53:28Z)
On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
We characterize the convergence of optimistic gradient descent (OGD) in time-varying games. Our framework yields sharp convergence bounds for the equilibrium gap of OGD in zero-sum games. We also provide new insights on dynamic regret guarantees in static games.
arXiv Detail & Related papers (2023-01-26T17:25:45Z)
Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
We show that Nash equilibrium (NE) is acceptable to all players in a multi-player game. We also show that no one can benefit unilaterally from the general theory step by step.
arXiv Detail & Related papers (2023-01-19T11:36:50Z)
Variational Inference with Holder Bounds [68.8008396694788]
We present a careful analysis of the thermodynamic variational objective (TVO) We reveal how the pathological geometry of thermodynamic curves negatively affects TVO. This motivates our new VI objectives, named the Holder bounds, which flatten the thermodynamic curves and promise to achieve a one-step approximation of the exact marginal log-likelihood.
arXiv Detail & Related papers (2021-11-04T15:35:47Z)
A Variational Inequality Approach to Bayesian Regression Games [90.79402153164587]
We prove the existence of the uniqueness of a class of convex and generalize it to smooth cost functions. We provide two simple algorithms of solving them with necessarily strong convergence.
arXiv Detail & Related papers (2021-03-24T22:33:11Z)
Fundamental Limits and Tradeoffs in Invariant Representation Learning [99.2368462915979]
Many machine learning applications involve learning representations that achieve two competing goals. Minimax game-theoretic formulation represents a fundamental tradeoff between accuracy and invariance. We provide an information-theoretic analysis of this general and important problem under both classification and regression settings.
arXiv Detail & Related papers (2020-12-19T15:24:04Z)
Invariant Risk Minimization Games [48.00018458720443]
In this work, we pose such invariant risk minimization as finding the Nash equilibrium of an ensemble game among several environments. By doing so, we develop a simple training algorithm that uses best response dynamics and equilibria in our experiments, yields similar or better empirical accuracy with much lower variance than the challenging bi-level optimization problem of Arjovsky et al.
arXiv Detail & Related papers (2020-02-11T21:25:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.