Last-Iterate Convergence of Regularized Gradient Methods for Stochastic Monotone Variational Inequalities

Abstract

We study last-iterate convergence for stochastic smooth and monotone variational inequalities (VIs), a framework that captures convex-concave saddle points and Nash equilibrium computation in monotone games with noisy payoff feedback. In contrast to the well-understood average-iterate guarantees, anytime last-iterate guarantees in stochastic settings remain limited, despite their relevance for uncoupled learning dynamics that output a single current strategy. We analyze two single-call regularized methods, the \emph{regularized gradient (RG)} and the \emph{regularized optimistic gradient (ROG)} methods, and establish anytime last-iterate convergence rates in terms of the squared gap function. For monotone VIs, RG attains $O(t^{-2/5})$ while ROG achieves the variance-adaptive rate $O(\sigma^{4/5} t^{-2/5} + t^{-1})$, where $\sigma^2$ is the noise variance. For $\lambda$-strongly monotone VIs, ROG yields $O(\sigma^2 / (\lambda^2 t) + t^{-c})$ for any constant $c \ge 2$. These results give anytime last-iterate guarantees without knowing the horizon and show that optimism improves convergence in the low-noise regime.