Regularized Operator Extrapolation Method For Stochastic Bilevel Variational Inequality Problems

The bilevel variational inequality (BVI) problem is a broad framework covering optimal equilibrium selection and equilibrium problems with equilibrium constraints (EPECs). We propose Regularized Operator Extrapolation (R-OpEx), a single-loop first-order algorithm for smooth and nonsmooth BVIs with stochastic monotone operators. R-OpEx combines Tikhonov regularization with operator extrapolation, requires only one operator evaluation per iteration, and tracks a single sequence of iterates. We show that R-OpEx obtains an $\epsilon$-solution in $\mathcal{O}(\epsilon^{-4})$ iterations for nonsmooth stochastic BVIs. If the inner operator is smooth and stochastic, we show an improved complexity of $\mathcal{O}(\epsilon^{-2})$ for the outer level operator while maintaining $\mathcal{O}(\epsilon^{-4})$ complexity for the inner level operator. For a smooth deterministic inner level operator, the overall complexity reduces to $\mathcal{O}(\epsilon^{-2})$. Finally, we improve the complexities substantially when the outer level is strongly monotone. To our knowledge, this is the first work to establish such guarantees for nonsmooth stochastic BVIs. We validate our results through numerical studies.