Regularized Operator Extrapolation Method For Stochastic Bilevel Variational Inequality Problems

The bilevel variational inequality (BVI) problem is a general model that captures various optimization problems, including VI-constrained optimization and equilibrium problems with equilibrium constraints (EPECs). This paper introduces a first-order method for smooth or nonsmooth BVI with stochastic monotone operators at inner and outer levels. Our novel method, called Regularized Operator Extrapolation (R-OpEx), is a single-loop algorithm that combines Tikhonov's regularization with operator extrapolation. This method needs only one operator evaluation for each operator per iteration and tracks one sequence of iterates. We show that R-OpEx gives O(ε⁻⁴) complexity in nonsmooth stochastic monotone BVI, where ε is the error in the inner and outer levels. Using a mini-batching scheme, we improve the outer level complexity to O(ε⁻²) while maintaining the O(ε⁻⁴) complexity in the inner level when the inner level is smooth and stochastic. Moreover, if the inner level is smooth and deterministic, we show complexity of O(ε⁻²). Finally, in case the outer level is strongly monotone, we improve to O(ε-4/5) for general BVI and O(ε-2/3) when the inner level is smooth and deterministic. To our knowledge, this is the first work that investigates nonsmooth stochastic BVI with the best-known convergence guarantees. We verify our theoretical results with numerical experiments.