Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities

arXiv:2609.15257v1 Announce Type: cross Abstract: We analyze a stochastic algorithm with Halpern anchoring for constrained convex-concave problems and monotone variational inequalities. This algorithm is single-loop and single-call since it uses one unbiased sample of the gradient operator at every iteration to be applicable to monotone games with noisy feedback. With t denoting the iteration counter, we prove the anytime last-iterate convergence rate of O(t^{-1/4}) for both gradient-mapping norm and restricted gap, improving the best-known rate O(t^{-1/5}) that was obtained for the restricted gap function. Our rates cover constrained problems with a potentially unbounded feasible set as well as a structured class of stochastic oracles without a bounded variance.

Source: arXiv cs.LG | 2026-09-15