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

arXiv: https://arxiv.org/abs/2304.04778 · HTML: https://mlsanity.com/paper/2304.04778/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 46 references that are in the map.
- First posted on arXiv 10 Apr 2023.

## Builds on (most cited first, 15 of 15)

- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities](https://mlsanity.com/paper/2002.08872/) (2020)
- [Golden Ratio Algorithms for Variational Inequalities](https://mlsanity.com/paper/1803.08832/) (2018)
- [Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimization](https://mlsanity.com/paper/1908.02734/) (2019)
- [Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation](https://mlsanity.com/paper/2011.02987/) (2020)
- [On the Convergence Properties of Non-Euclidean Extragradient Methods for Variational Inequalities with Generalized Monotone Operators](https://mlsanity.com/paper/1311.2776/) (2013)
- [Optimal Algorithms for Convex Nested Stochastic Composite Optimization](https://mlsanity.com/paper/2011.10076/) (2020)
- [Optimal Algorithms for Differentially Private Stochastic Monotone Variational Inequalities and Saddle-Point Problems](https://mlsanity.com/paper/2104.02988/) (2021)
- [New First-Order Algorithms for Stochastic Variational Inequalities](https://mlsanity.com/paper/2107.08341/) (2021)
- [Level-set methods for convex optimization](https://mlsanity.com/paper/1602.01506/) (2016)
- [Stochastic generalized Nash equilibrium seeking under partial-decision information](https://mlsanity.com/paper/2011.05357/) (2020)
- [Data-Driven Minimax Optimization with Expectation Constraints](https://mlsanity.com/paper/2202.07868/) (2022)
- [Optimal robust smoothing extragradient algorithms for stochastic variational inequality problems](https://mlsanity.com/paper/1403.5591/) (2014)
- [Exact Penalization of Generalized Nash Equilibrium Problems](https://mlsanity.com/paper/1811.10674/) (2018)

## Abstract (arXiv)

The monotone Variational Inequality (VI) is a general model with important applications in various engineering and scientific domains. In numerous instances, the VI problems are accompanied by function constraints that can be data-driven, making the usual projection operator challenging to compute. This paper presents novel first-order methods for the function-constrained Variational Inequality (FCVI) problem in smooth or nonsmooth settings with possibly stochastic operators and constraints. We introduce the AdOpEx method, which employs an operator extrapolation on the KKT operator of the FCVI in a smooth deterministic setting. Since this operator is not uniformly Lipschitz continuous in the Lagrange multipliers, we employ an adaptive two-timescale algorithm leading to bounded multipliers and achieving the optimal O(1/T) convergence rate. For the nonsmooth and stochastic VIs, we introduce design changes to the AdOpEx method and propose a novel P-OpEx method that takes partial extrapolation. It converges at the rate of O(1/√T) when both the operator and constraints are stochastic or nonsmooth. This method has suboptimal dependence on the noise and Lipschitz constants of function constraints. We propose a constraint extrapolation approach leading to the OpConEx method that improves this dependence by an order of magnitude. All our algorithms easily extend to saddle point problems with function constraints that couple the primal and dual variables while maintaining the same complexity results. To the best of our knowledge, all our complexity results are new in the literature