First-order methods for Stochastic Variational Inequality problems with Function Constraints

Digvijay Boob, Qi Deng

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:

  1. 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.
  2. 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.
  3. 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.

Table 1: Convergence rates and complexity results for the proposed algorithms across different problem settings.

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

Abstract

The monotone Variational Inequality (VI) is an important problem in machine learning. In numerous instances, the VI problems are accompanied by function constraints which can possibly be data-driven, making the projection operator challenging to compute. In this paper, we present novel first-order methods for function constrained VI (FCVI) problem under various settings, including smooth or nonsmooth problems with a stochastic operator and/or stochastic constraints. First, we introduce the~{\texttt{OpConEx}} method and its stochastic variants, which employ extrapolation of the operator and constraint evaluations to update the variables and the Lagrangian multipliers. These methods achieve optimal operator or sample complexities when the FCVI problem is either (i) deterministic nonsmooth, or (ii) stochastic, including smooth or nonsmooth stochastic constraints. Notably, our algorithms are simple single-loop procedures and do not require the knowledge of Lagrange multipliers to attain these complexities. Second, to obtain the optimal operator complexity for smooth deterministic problems, we present a novel single-loop Adaptive Lagrangian Extrapolation~(\texttt{AdLagEx}) method that can adaptively search for and explicitly bound the Lagrange multipliers. Furthermore, we show that all of our algorithms can be easily extended to saddle point problems with coupled function constraints, hence achieving similar complexity results for the aforementioned cases. To our best knowledge, many of these complexities are obtained for the first time in the literature.
BibTeX
@misc{boob2023first,
  author = {Digvijay Boob and Qi Deng},
  title = {{First-order methods for Stochastic Variational Inequality problems with Function Constraints}},
  year = {2023},
  eprint = {2304.04778},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2304.04778},
}
Figure