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

• 成果类型: Article; Early Access
• 署名作者: Boob, Digvijay; Deng, Qi; Khalafi, Mohammad
• 署名单位: Southern Methodist University; Shanghai Jiao Tong University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X; 1526-5471
• DOI: 10.1287/moor.2024.0531
• 发表日期: 2026-01-06
• 关键词: variational Inequality; function constraints; stochastic first-order methods; saddle point problems; extragradient methods; Approximation methods; CONVERGENCE; COMPLEMENTARITY; equilibrium; algorithms; gradient; DESIGN

摘要

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 O(1/T) convergence rate. For the nonsmooth and stochastic VIs, we introduce design changes to the AdOpEx method and propose a novel Vffiffiffi P-OpEx method that takes a 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 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.