Learning Variational Inequalities from Data: Fast Generalization Rates under Strong Monotonicity
This work provides a theoretical framework for faster learning in variational inequalities, which is incremental as it extends known convex optimization results to a broader class of problems, benefiting researchers in optimization and machine learning dealing with complex scenarios like min-max optimization.
The paper tackles the problem of achieving fast statistical learning rates for variational inequalities (VIs) by showing that under strong monotonicity, similar to strong convexity in convex optimization, one can obtain Θ(1/ε) rates instead of the standard Θ(1/ε²). It demonstrates that stability-based generalization arguments extend directly to VIs in cases like small covering domains or integrable operators, applicable to scenarios such as multi-player game equilibria.
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 $Θ(1/ε)$ stochastic first-order oracle calls to find an $ε$-optimal solution, rather than the standard $Θ(1/ε^2)$ calls. This note provides a simple overview of how one can similarly obtain fast $Θ(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.