Stochastic algorithm improves convergence rates for convex problems
Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities
Machine Learning
Summary
Solving complex mathematical problems that involve multiple players or variables often requires algorithms that can handle randomness and constraints efficiently. The authors studied a particular algorithm designed to work on these problems with uncertain or noisy feedback, improving how quickly it converges to a solution at each step. Their method uses fewer assumptions and simpler iterations while working on cases where the problem's scope might be very large or unbounded. This improvement means better performance and reliability when solving many practical problems modeled by these mathematical structures.
What this means in practice
- •For machine learning engineers: Improve training algorithms for competitive models that require handling noisy gradient feedback under constraints.
- •For optimization software developers: Develop faster solvers for complex variational inequality problems with large or unbounded feasible sets having uncertain input data.
Authors
Jun-Hyun Kim, Ahmet Alacaoglu
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.