arXiv preprint ·
Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Optimization & Control
An explicit solution of the five-expert prediction PDE and the exact optimality set of COMB
Learning Choice Model Trees for Feature-Based Multi-Product Pricing: Exact Optimization and Field Evidence
Steady-State Convergence of Stochastic Approximation
Optimization over covariance matrices with a parameterized metric
Distributed Fast Fixed-Point Algorithms for Composite Monotone Inclusions over Networks
Get the few papers worth your time in Optimization & Control every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.