arXiv preprint ·
Polyak-Type Extragradient Methods for Monotone Root-Finding Problems
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study Polyak-type step-size selection for extragradient methods for solving deterministic and stochastic monotone root-finding problems. We show that the known projection-type correction for deterministic extragradient arises from minimizing an upper bound on the distance to a solution, paralleling the classical Polyak step-size construction. Using this viewpoint, we provide a unified deterministic analysis of the Polyak-type Extragradient Method (PolyakEG), based on a local critical condition controlling the variation of operator $F$ along the extrapolation direction. This analysis does not require global Lipschitz continuity, and covers sublinear convergence under broader conditions such as Hölder continuity or $(L_0, L_1)$-Lipschitzness and linear convergence under additional strong monotonicity, all through a single framework. We then study the stochastic extensions of this approach. We first prove convergence of a direct stochastic variant, PolyakSEG, when all stochastic component operators share a common solution. We also show that, without this condition, PolyakSEG with nonvanishing step-sizes may fail to converge to a zero of the mean operator. To address this limitation, we propose DecPolyakSEG, which combines decreasing step-sizes with Polyak-type updates, and establish a sublinear residual convergence result without requiring a common solution across the component operators. These results parallel recent developments in stochastic Polyak step-sizes from the convex minimization literature and establish an analogous research avenue in the broader root-finding regime.
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
Sample-Based Prophet Inequalities for Random Walks
ZO-COSMO: Index-Free One-Hop Mixing for Decentralized Zeroth-Order Optimization
Optimal Investment and Consumption in Financial Markets with Integrated Variance Clocks
Distributed Stochastic Approximation Algorithms and Heavy-Tailed Age of Information
Reliability Theory for AI Control
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.