Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.09778 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908364260245504 |
|---|---|
| author | Khalafi, Mohammad Boob, Digvijay |
| author_facet | Khalafi, Mohammad Boob, Digvijay |
| contents | 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 $(\texttt{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 $\texttt{R-OpEx}$ gives $\mathcal{O}(ε^{-4})$ 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 $\mathcal{O}(ε^{-2})$ while maintaining the $\mathcal{O}(ε^{-4})$ 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 $\mathcal{O}(ε^{-2})$. Finally, in case the outer level is strongly monotone, we improve to $\mathcal{O}(ε^{-4/5})$ for general BVI and $\mathcal{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_09778 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Regularized Operator Extrapolation Method For Stochastic Bilevel Variational Inequality Problems Khalafi, Mohammad Boob, Digvijay Optimization and Control 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 $(\texttt{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 $\texttt{R-OpEx}$ gives $\mathcal{O}(ε^{-4})$ 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 $\mathcal{O}(ε^{-2})$ while maintaining the $\mathcal{O}(ε^{-4})$ 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 $\mathcal{O}(ε^{-2})$. Finally, in case the outer level is strongly monotone, we improve to $\mathcal{O}(ε^{-4/5})$ for general BVI and $\mathcal{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. |
| title | Regularized Operator Extrapolation Method For Stochastic Bilevel Variational Inequality Problems |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2505.09778 |