Regularized Operator Extrapolation Method For Stochastic Hierarchical Variational Inequality Problems

Mohammad Khalafi, Digvijay Boob
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:1387-1395, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-khalafi26a, title = { Regularized Operator Extrapolation Method For Stochastic Hierarchical Variational Inequality Problems }, author = {Khalafi, Mohammad and Boob, Digvijay}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {1387--1395}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/khalafi26a/khalafi26a.pdf}, url = {https://proceedings.mlr.press/v300/khalafi26a.html}, abstract = { 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. } }
Endnote
%0 Conference Paper %T Regularized Operator Extrapolation Method For Stochastic Hierarchical Variational Inequality Problems %A Mohammad Khalafi %A Digvijay Boob %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-khalafi26a %I PMLR %P 1387--1395 %U https://proceedings.mlr.press/v300/khalafi26a.html %V 300 %X 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.
APA
Khalafi, M. & Boob, D.. (2026). Regularized Operator Extrapolation Method For Stochastic Hierarchical Variational Inequality Problems . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:1387-1395 Available from https://proceedings.mlr.press/v300/khalafi26a.html.

Related Material