First-Order Methods for Stochastic Variational Inequality Problems with Function Constraints

We study monotone function-constrained variational inequalities (FCVIs) whose feasible region is the intersection of a projection-friendly set and several convex function constraints; both the operator and the constraint functions may be smooth, nonsmooth, and/or stochastic. Computing the projection operator is challenging for FCVIs. We introduce the adaptive operator extrapolation (AdOpEx) method, which employs an operator extrapolation on the Karush–Kuhn–Tucker operator of the FCVI in a smooth deterministic setting. Because 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 [Formula: see text] 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 a partial extrapolation. It converges at the rate of [Formula: see text] 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 also extend to solving saddle point problems with jointly convex function constraints that couple the primal and dual variables. Within this structured class of problems, our methods preserve their respective complexity guarantees, establishing what we believe to be the first such comprehensive complexity results. Funding: D. Boob and M. Khalafi were partially supported by the National Science Foundation [Grants 2245705 and 2340858]. D. Boob was partially supported by the Office of Naval Research [Grant N000142412749]. Q. Deng was partially supported by the National Natural Science Foundation of China [Grants 12571325 and 72394364/72394360] and the Natural Science Foundation of Shanghai [Grant 24ZR1421300].