Solving Stochastic Variational Inequalities without the Bounded Variance Assumption

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.

Many machine learning systems are trained by repeatedly using noisy information to decide how to update their parameters. Standard theory often assumes that this noise stays under control and that the problem has a clean structure. But important min-max problems, which appear in robust learning and adversarial training settings, can violate both assumptions: the noise can grow larger as the algorithm moves, and the problem may have a more complicated structure than the standard well-behaved cases. We study whether algorithms can still be trusted in this harder setting. Instead of requiring the strongest global structure, we use a weaker condition called the weak Minty condition, which covers monotone problems and also allows certain structured nonmonotone problems. Instead of assuming uniformly bounded noise, we allow the noise to grow with the size of the current iterate. We then analyze three algorithms and prove that they converge under these weaker assumptions. Our results give the best-known theoretical guarantees for constrained stochastic min-max and variational inequality problems under this more realistic setting. This helps close the gap between clean optimization theory and the messier problems that arise in modern machine learning.