Skip to content

Polyak-Type Extragradient Methods for Monotone Root-Finding Problems

Sep 2026 · arXiv.org · Vol abs/2609.26581 · 2 citations · 90 references
Computer Science Mathematics

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\"older 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.

View source

Similar papers

#machine learning Preprint Sep 2026

Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems

The Anchored Extra-Proximal (AEP) framework is introduced, which combines an anchored extrapolation step with an inexact anchored proximal update satisfying a relative-error condition to recover the composite Fast Extragradient method in the first-order setting.

Rui-Chen Jiang, Taeho Yoon · 0 citations
Preprint Oct 2026

Single-call Polyak-Type Extragradient Methods for Monotone Root-Finding Problems

We propose a single-call variant of Polyak extragradient, termed SPolyakEG, by recycling the previous extrapolation operator evaluation. Under a delayed critical condition, we establish that SPolyakEG achieves an $O(1/K)$ residual convergence rate for monotone operators and linear convergence under strong monotonicity....

Ke-Ke-Zhang-Shu-Han-,-Chen-Guang-Liang-,-Yang-Ming Li · 0 citations
Preprint Aug 2026

Mirror Polyak and a Primal-Dual Lifting

This work revisits a variant of the Polyak step-size based on Bregman projections due to Kiwiel (1997), and shows that mirror Polyak enjoys guarantees similar to its Euclidean counterpart, automatically adapting to relative notions of smoothness, Lipschitz continuity, or strong convexity.

Frederik Kunstner, Ryan D'Orazio, V. S. Portella et al. · 1 citation
Preprint Sep 2026

Projection-Free Algorithms for Nonsmooth Stochastic Convex-Concave Saddle-Point Problems

We study nonsmooth convex-concave saddle-point problems over compact convex sets, assuming access to stochastic subgradients of the payoff function. We develop single-loop projection-free algorithms that use linear minimization oracles over the primal and dual domains. Unlike prior projection-free approaches that rely...

Khanh-Hung Giang-Tran, Soroosh Shafiee · 0 citations
Preprint Sep 2026

An Adaptive Linesearch-free Method for Monotone Variational Inequalities under Local Lipschitz Continuity

The forward-reflected-backward (FRB) splitting solves inclusion problems involving the sum of a maximally monotone operator and a monotone Lipschitz continuous operator. Each iteration performs one resolvent step and one evaluation of the Lipschitz operator, plus a reflection term with coefficient one that reuses the p...

Hong-Jia Ou, Andreas Themelis, Puya Latafat · 1 citation · ⚡1
Open access Sep 2026

On convergence rates of stochastic gradient descent for linear inverse problems

Stochastic gradient methods have gained increasing attention for solving large-scale inverse problems due to their computational efficiency. However, their theoretical justification in the context of ill-posed problems remains underdeveloped, particularly regarding convergence rate analysis, where existing results typi...

Qi-Nian Jin, Xi-Liang Lu, Lin Tian · 0 citations

Related blog posts

MIT News · Artificial Intelligence Nov 17, 2026

Learning the language of machine learning

By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.