Solving Stochastic Variational Inequalities without the Bounded Variance Assumption

Ahmet Alacaoglu, Junhyun Kim
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:1647-1679, 2026.

Abstract

We analyze algorithms for solving stochastic variational inequalities (VI) without the bounded variance or bounded domain assumptions, where our main focus is min-max optimization with possibly unbounded constraint sets. We focus on two classes of problems: monotone VIs; and structured nonmonotone VIs that admit a solution to the weak Minty VI. The latter assumption allows us to solve structured nonconvex-nonconcave min-max problems. For both classes of VIs, to make the expected residual norm less than $\varepsilon$, we show an oracle complexity of $\widetilde{O}(\varepsilon^{-4})$, which is the best-known for constrained VIs. In our setting, this complexity had been obtained with the bounded variance assumption in the literature, which is not even satisfied for bilinear min-max problems with an unbounded domain. We obtain this complexity for stochastic oracles whose variance can grow as fast as the squared norm of the optimization variable.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-alacaoglu26a, title = {Solving Stochastic Variational Inequalities without the Bounded Variance Assumption}, author = {Alacaoglu, Ahmet and Kim, Junhyun}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {1647--1679}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/alacaoglu26a/alacaoglu26a.pdf}, url = {https://proceedings.mlr.press/v306/alacaoglu26a.html}, abstract = {We analyze algorithms for solving stochastic variational inequalities (VI) without the bounded variance or bounded domain assumptions, where our main focus is min-max optimization with possibly unbounded constraint sets. We focus on two classes of problems: monotone VIs; and structured nonmonotone VIs that admit a solution to the weak Minty VI. The latter assumption allows us to solve structured nonconvex-nonconcave min-max problems. For both classes of VIs, to make the expected residual norm less than $\varepsilon$, we show an oracle complexity of $\widetilde{O}(\varepsilon^{-4})$, which is the best-known for constrained VIs. In our setting, this complexity had been obtained with the bounded variance assumption in the literature, which is not even satisfied for bilinear min-max problems with an unbounded domain. We obtain this complexity for stochastic oracles whose variance can grow as fast as the squared norm of the optimization variable.} }
Endnote
%0 Conference Paper %T Solving Stochastic Variational Inequalities without the Bounded Variance Assumption %A Ahmet Alacaoglu %A Junhyun Kim %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-alacaoglu26a %I PMLR %P 1647--1679 %U https://proceedings.mlr.press/v306/alacaoglu26a.html %V 306 %X We analyze algorithms for solving stochastic variational inequalities (VI) without the bounded variance or bounded domain assumptions, where our main focus is min-max optimization with possibly unbounded constraint sets. We focus on two classes of problems: monotone VIs; and structured nonmonotone VIs that admit a solution to the weak Minty VI. The latter assumption allows us to solve structured nonconvex-nonconcave min-max problems. For both classes of VIs, to make the expected residual norm less than $\varepsilon$, we show an oracle complexity of $\widetilde{O}(\varepsilon^{-4})$, which is the best-known for constrained VIs. In our setting, this complexity had been obtained with the bounded variance assumption in the literature, which is not even satisfied for bilinear min-max problems with an unbounded domain. We obtain this complexity for stochastic oracles whose variance can grow as fast as the squared norm of the optimization variable.
APA
Alacaoglu, A. & Kim, J.. (2026). Solving Stochastic Variational Inequalities without the Bounded Variance Assumption. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:1647-1679 Available from https://proceedings.mlr.press/v306/alacaoglu26a.html.

Related Material