Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities
Abstract
We analyze a stochastic algorithm with Halpern-type anchoring for constrained convex-concave problems and monotone variational inequalities. This single-loop and single-call algorithm 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 an anytime last-iterate convergence rate of O(t−1/4) for both the gradient-mapping norm and restricted gap, bypassing the O(t−1/5) constrained-anytime bottleneck in the literature. Specializing then to multi-point oracles, we use variance reduction to achieve the O(t−1/2) rate with an anytime single-loop algorithm using $2$ samples per iteration. Our results allow constrained problems with a potentially unbounded feasible set; as well as a structured class of stochastic oracles whose variance need not be uniformly bounded.
Related
- Convergence guarantees for stochastic algorithms solving non-unique problems in metric spaces
- Computation of Strong Solutions to Stochastic Variational Inequalities
- A note on the convergence guarantees of RLT-based algorithms for polynomial optimization
- PAC-Bayesian Reconstruction Guarantees for Time Series Variational Autoencoders
- Finite-sample guarantees for data-driven operator splitting methods via martingale inequalities
BibTeX
@misc{kim2026improving,
title = {{Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities}},
author = {Jun-Hyun Kim and Ahmet Alacaoglu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.15257},
eprint = {2609.15257},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15257},
}
RIS
TY - UNPB
TI - Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities
AU - Jun-Hyun Kim
AU - Ahmet Alacaoglu
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.15257
UR - https://arxiv.org/abs/2609.15257
AB - We analyze a stochastic algorithm with Halpern-type anchoring for constrained convex-concave problems and monotone variational inequalities. This single-loop and single-call algorithm 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 an anytime last-iterate convergence rate of O(t^−1/4) for both the gradient-mapping norm and restricted gap, bypassing the O(t^−1/5) constrained-anytime bottleneck in the literature. Specializing then to multi-point oracles, we use variance reduction to achieve the O(t^−1/2) rate with an anytime single-loop algorithm using $2$ samples per iteration. Our results allow constrained problems with a potentially unbounded feasible set; as well as a structured class of stochastic oracles whose variance need not be uniformly bounded.
ER -