Randomized Feasibility-Update Algorithms for Stochastic Variational Inequality Problems
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918162308530176 |
|---|---|
| author | Chakraborty, Abhishek Nedić, Angelia |
| author_facet | Chakraborty, Abhishek Nedić, Angelia |
| contents | This paper considers stochastic monotone variational inequalities whose feasible region is the intersection of a (possibly infinite) number of convex functional level sets. A projection-based approach or direct Lagrangian-based techniques for such problems can be computationally expensive if not impossible to implement. To deal with the problem, we consider randomized methods that avoid the projection step on the whole constraint set by employing random feasibility updates. In particular, we propose and analyze modified stochastic Korpelevich and Popov methods for solving monotone stochastic VIs. We introduce a modified dual gap function and prove the convergence rates with respect to this function. We illustrate the performance of the methods in simulations on a zero-sum matrix game. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_12613 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Randomized Feasibility-Update Algorithms for Stochastic Variational Inequality Problems Chakraborty, Abhishek Nedić, Angelia Optimization and Control This paper considers stochastic monotone variational inequalities whose feasible region is the intersection of a (possibly infinite) number of convex functional level sets. A projection-based approach or direct Lagrangian-based techniques for such problems can be computationally expensive if not impossible to implement. To deal with the problem, we consider randomized methods that avoid the projection step on the whole constraint set by employing random feasibility updates. In particular, we propose and analyze modified stochastic Korpelevich and Popov methods for solving monotone stochastic VIs. We introduce a modified dual gap function and prove the convergence rates with respect to this function. We illustrate the performance of the methods in simulations on a zero-sum matrix game. |
| title | Randomized Feasibility-Update Algorithms for Stochastic Variational Inequality Problems |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2509.12613 |