Polyak-Type Extragradient Methods for Monotone Root-Finding Problems
TaeHo Yoon, Sayantan Choudhury, Ezra Greenberg, Nicolas Loizou
math.OC · cs.LG
Quick verdict
EG's projection step recast as a Polyak step-size; clean unified rates for Hölder/(L0,L1) operators; stochastic guarantees lean on a localization assumption.
Summary
This paper transfers Polyak's classical step-size principle to the extragradient method for monotone root-finding. The authors show that the update step-size αk = ⟨F(x̂k), xk−x̂k⟩/‖F(x̂k)‖² — previously known as a projection-type correction — exactly minimizes a one-step upper bound on the distance to a solution, giving it a Polyak interpretation. A single 'critical condition' on the extrapolation step (‖F(x̂k)−F(xk)‖ ≤ A‖F(xk)‖) yields a unified convergence theorem without global Lipschitz continuity: O(1/K) squared-residual rates for monotone operators, linear rates under strong monotonicity (recovering the 1−μ/4L state of the art), and explicit sublinear guarantees for Hölder-continuous and (L0,L1)-Lipschitz operators; a backtracking line-search variant is parameter-free with provably bounded overhead. Stochastically, PolyakSEG converges under the interpolation condition, but a constructed counterexample shows failure without it under constant nonvanishing step-sizes; the proposed DecPolyakSEG attains O(K^{−1/2}) expected squared-residual convergence under a trajectory-localization assumption, which is removed when sample operators are strongly monotone. Experiments on synthetic affine, Hölder and (L0,L1) problems, and stochastic robust least squares, show competitive or superior performance against adaptive baselines. Main limitations: the core step-size formula is not new, stochastic analysis is restricted to uniformly Lipschitz components, the localization assumption is unverifiable a priori for merely monotone problems, and no code release is stated.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 2
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- The extragradient update step αk = ⟨F(x̂k), xk−x̂k⟩/‖F(x̂k)‖² is exactly the minimizer of a one-step upper bound on the squared distance to any solution, i.e., a Polyak step-size, coinciding with known projection-type corrections (§2).
- A single critical condition on the extrapolation step (Def. 3.1) yields sublinear O(1/K) residual convergence for monotone operators and linear convergence under strong monotonicity (rate 1 − μ/4L at A = 1/3) without any global Lipschitz assumption (Thm 3.4).
- The same framework gives explicit nonasymptotic rates for Hölder-continuous (O(ε^{−2/ν}) complexity) and (L0,L1)-Lipschitz operators, classes for which the projection-corrected EG previously lacked quantitative guarantees (Table 2, Eqs. 19–20).
- PolyakSEG converges at O(1/K) under interpolation and provably fails without it under constant nonvanishing step-sizes (Thm 4.3, Prop. 4.4); DecPolyakSEG achieves O(K^{−1/2}) expected squared-residual convergence without interpolation, under a trajectory-localization assumption removable under samplewise strong monotonicity (Thm 4.6, Cor. 4.7, Prop. 4.8).
- Backtracking line-search variants (Algs. 2 and 5) are parameter-free with total overhead bounded and dominated by the iteration complexity (Prop. 3.5, Cor. 4.7).
Strengths
Honest and precise novelty positioning
The paper explicitly states the update step-size (Eq. 9) coincides with projection-type corrections of Sun [71], Iusem–Svaiter [34], Solodov–Svaiter [68] and Pethick et al. [59], claiming only the Polyak interpretation, the unified condition and new rate regimes; Table 2 makes the comparison matrix explicit and flags exactly which guarantees are new.
Genuinely unified deterministic analysis
Definition 3.1's critical condition ‖F(x̂k)−F(xk)‖ ≤ A‖F(xk)‖ supports one theorem (Thm 3.4) covering Lipschitz (γk ≤ A/L), Hölder (γk ≤ (A/L)^{1/ν}‖F(xk)‖^{(1−ν)/ν}, giving O(ε^{−2/ν}) complexity matching Dang–Lan [14, Thm 4.4(a)]) and (L0,L1) operators (γk ≤ νA/(L0+L1‖F(xk)‖), νA = W(A)), with no global Lipschitz assumption.
Quantitatively sharp special cases
Parameter-free line-search with provable overhead
Carefully scoped stochastic theory with a counterexample
Weaknesses
Deterministic novelty is partly historical
Headline stochastic result is conditional on an unverifiable assumption
Stochastic theory retreats to uniform Lipschitz components
(L0,L1) rate is eventual and implicit
Small-scale empirical evidence, no code
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper (arXiv 2609.26581, Johns Hopkins) studies the monotone root-finding problem find x: F(x)=0 — the operator form of smooth convex minimization, convex-concave min-max (Eqs. 4–5), and monotone games (Eq. 6) — and proposes Polyak-type step-sizes for extragradient (EG) methods. Its claims: (1) the update step αk of Eq. (9), coinciding with the projection-type corrections of Sun [71], Iusem–Svaiter [34], Solodov–Svaiter [68] and Pethick et al. [59], is the exact minimizer of a one-step upper bound on ‖xk+1 − x*‖², i.e., a Polyak step-size (§2.1, Table 1); (2) a single critical condition (Def. 3.1: ‖F(x̂k) − F(xk)‖ ≤ A‖F(xk)‖) supports a unified theorem (Thm 3.4) delivering O(1/K) squared-residual rates for monotone F and linear convergence under strong monotonicity, without global Lipschitz continuity; instances recover the Hölder complexity O(ε^{−2/ν}) of Dang–Lan [14, Thm 4.4(a)] and give (L0,L1) rates (Eq. 19–20); (3) parameter-free PolyakEG-LS (Alg. 2) has bounded backtracking overhead (Prop. 3.5); (4) PolyakSEG converges under interpolation (Thm 4.3) and provably fails without it under constant γ (Prop. 4.4, via F1=x+1, F2=x−1); DecPolyakSEG reaches O(K^{−1/2}) expected squared residual under localization (Thm 4.6, Cor. 4.7), with localization provable under samplewise strong monotonicity (Prop. 4.8, Eq. 46).
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is the Polyak step-size for the extragradient method?
PolyakEG updates with αk = ⟨F(x̂k), xk−x̂k⟩/‖F(x̂k)‖², the value that minimizes a one-step upper bound on the squared distance from the new iterate to any solution of F(x)=0. Geometrically it projects the current iterate onto a halfspace that monotonicity guarantees contains the solution set. Unlike the classical Polyak step-size in minimization, it requires no knowledge of an optimal function value.
Does PolyakEG require knowing the Lipschitz constant of the operator?
No. Fixed-step variants need L, ν, L0 or L1 to choose the extrapolation step γk, but the line-search variant PolyakEG-LS (Algorithm 2) enforces the critical condition by backtracking without any problem constants. Proposition 3.5 bounds the total number of backtracking trials, so its oracle complexity matches the parameter-aware versions.
When does stochastic extragradient with Polyak step-sizes fail to converge?
PolyakSEG is guaranteed only under interpolation, i.e., when all component operators share a common zero. Proposition 4.4 gives a concrete 1D counterexample (F1(x)=x+1, F2(x)=x−1, mean operator F(x)=x) where constant nonvanishing step-sizes keep the iterates away from the root forever. The proposed DecPolyakSEG fixes this by decreasing both step-sizes, achieving O(1/√K) expected residual convergence under a bounded-trajectory assumption.
What convergence rates does this paper prove?
For monotone F: O(1/K) on squared residual norms, without global Lipschitz continuity. Under μ-strong monotonicity: linear rate 1 − μ/4L (with A = 1/3), matching the best known extragradient rate. For Hölder-continuous operators: O(ε^{−2/ν}) oracle complexity to reach residual ε. For the stochastic DecPolyakSEG without interpolation: O(K^{−1/2}) on the expected squared residual of the averaged iterate.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Figures are available only as captions plus a few quoted values; the curves in Figs. 3–5 could not be independently verified from the extracted text.
- Light OCR artifacts (e.g., 'H¨older', flattened sub/superscripts) are present; theorems were cross-checked against their inline proofs where possible.
- The extracted text contains no appendix; some proof steps (e.g., end of Prop. 3.5(b)) appear abridged.
- No code-availability statement appears in the extracted text; absence of released code is inferred from that silence.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.