Polyak extragradient methods improve monotone root-finding convergence rates
Polyak-Type Extragradient Methods for Monotone Root-Finding Problems
Machine Learning
Summary
This paper looks at mathematical methods called extragradient methods used to solve certain equations where the goal is to find roots in a system that behaves predictably (monotone problems). The authors connect a classical way to pick step sizes, called Polyak step sizes, to existing correction techniques, providing a unified analysis that works under weaker conditions than before. They also extend these ideas to situations with randomness (stochastic settings) and propose a new technique that improves convergence even when the parts of the problem don’t share the same solution. These advances make solving these types of problems more reliable and efficient.
What this means in practice
- •For machine learning engineers: Design more reliable algorithms for training models under noisy conditions using improved step-size techniques for monotone problems.
- •For optimization software developers: Implement extragradient solvers with adaptive step sizes that converge faster without requiring strong assumptions about problem smoothness.
Authors
TaeHo Yoon, Sayantan Choudhury, Ezra Greenberg, Nicolas Loizou
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.