Abstract
The monotone Variational Inequality (VI) is a foundational problem in machine learning, often complicated by function constraints that may be data-driven or stochastic. In such cases, traditional projection operators become computationally prohibitive. This paper introduces novel first-order methods—AdOpEx, P-OpEx, and OpConEx—designed for function-constrained VI (FCVI) problems. These methods employ operator and constraint extrapolation to achieve optimal convergence rates across smooth, nonsmooth, and stochastic settings. Notably, these are simple single-loop procedures that do not require prior knowledge of Lagrange multipliers. We also extend these results to saddle-point problems with coupled function constraints, establishing many of these complexity bounds for the first time in the literature.
Introduction
Variational Inequalities (VIs) provide a robust framework for modeling diverse phenomena, from financial equilibria to Generative Adversarial Networks (GANs). However, a significant bottleneck in solving VIs arises when the feasible region is defined by complex function constraints ($g(x) \le 0$) rather than simple sets. Standard solvers rely on projection operators that become as difficult to compute as the original problem when constraints are complex or stochastic.
This work addresses the Function-Constrained VI (FCVI) problem by transforming it into a Karush-Kuhn-Tucker (KKT) system. By treating it as a saddle-point problem involving primal variables and Lagrange multipliers, the authors develop algorithms that navigate these boundaries without explicit projections.
Methodology
The authors propose three primary algorithmic frameworks to handle different problem characteristics:
- AdOpEx (Adaptive Operator Extrapolation): Tailored for smooth, deterministic problems. It utilizes a "two-timescale" approach to update primal and dual variables at different speeds, effectively bounding potentially unbounded Lagrange multipliers and achieving an optimal $O(1/T)$ rate.
- P-OpEx (Partial Operator Extrapolation): A robust variant for nonsmooth or stochastic environments. By extrapolating only the primal part of the operator, it maintains stability in the presence of data noise.
- OpConEx (Operator Constraint Extrapolation): The most sophisticated method, which linearizes constraints and applies extrapolation directly to them. This "look-ahead" mechanism significantly mitigates the impact of constraint noise and improves sensitivity to constraint sharpness.
Key Results
The paper establishes a new hierarchy of complexity results for FCVI, summarized in the table below. A major contribution is the OpConEx method, which improves the error dependence on the constraint Lipschitz constant ($M_g$) from $1/\sqrt{T}$ to $1/T$ in the deterministic component.
For smooth deterministic problems, AdOpEx achieves the optimal $O(1/T)$ rate. In nonsmooth and stochastic settings, the algorithms reach the $O(1/\sqrt{T})$ rate, which is the theoretical lower bound for first-order stochastic methods. These results represent the first time such optimal complexities have been achieved for general FCVI problems without requiring bounded Lagrange multipliers.
Discussion and Insights
- The Unbounded Multiplier Challenge: In FCVI, dual variables are not naturally bounded. The authors overcome this using an adaptive two-timescale design that forces multipliers to remain bounded without needing to know the solution space's radius a priori.
- Constraint Extrapolation: While extrapolation is standard for operators, this work demonstrates that extrapolating the constraints themselves is vital for handling stochasticity, reducing error dependence on constraint noise by an order of magnitude.
- Unified Framework: The proposed algorithms naturally extend to saddle-point problems with coupled constraints, providing the first known complexity results for such general cases.
Conclusion
This paper provides a comprehensive suite of first-order methods for function-constrained variational inequalities. While the current work assumes monotonicity and convex constraints, it sets a new benchmark for complexity in these settings. Future research may extend these adaptive extrapolation techniques to non-monotone or non-convex problems, further bridging the gap between equilibrium theory and modern machine learning applications.
Summary updated