REVIEW 3 major objections 3 minor 22 references
Convergence Analysis of the ProbAbilistic Gradient Estimator Algorithm for Weakly Convex Finite-Sum Optimization
T0 review · 3 major / 3 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read This paper proves that PAGE, a single-loop stochastic algorithm, converges linearly under the Polyak–Łojasiewicz condition across the entire τ-weakly convex spectrum, with complexity improving continuously as τ decreases from L to 0.
desk verdict The core tau-weakly convex analysis and improved convex PŁ rate are plausible, but the printed step-size condition is algebraically inverted, so Theorem 2.1 as stated is unproven; one typo in condition (5) makes the central claim invalid as written, though the proof contains the correct reciprocal form. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The proof rests on a modified Lyapunov function Ψ_t (equation 2) that tracks the objective error, the squared gradient norm, and the squared error of the gradient estimator, with a carefully placed negative inner-product term. The key inequality (Lemma 2.1) bounds ‖∇g(x)−∇g(y)‖² by (L−τ)⟨∇g(x)−∇g(y), x−y⟩ + Lτ‖x−y‖², interpolating between cocoercivity at τ = 0 and Lipschitzness at τ = L; this generates cancellations that let the Lyapunov function contract. The convenient step-size bound (5) is imported from a cited lemma (Richtárik et al. 2021, Lemma 5) that is not restated in the paper.
What would settle it
Run PAGE on the one-dimensional quadratic f(x)=x²/2 with n = 1, τ = L, p = 0.5, using step size γ = (1/L)(1+√(4τ/(L+τ))) ≈ 2.41/L, the upper limit of the non-reciprocal reading of the printed bound (5). The method diverges (γ exceeds the 2/L gradient-descent stability limit), showing the theorem's condition cannot be meant as printed; with the reciprocal reading γ = 1/[L(1+√(4τ/(L+τ)))] ≈ 0.41/L it converges linearly.
Extended reading notes
Core claim
The paper's central claim (Theorem 2.1) is that PAGE converges linearly under the Polyak–Łojasiewicz condition for every L-smooth, τ-weakly convex finite-sum problem. With step size chosen as a constant fraction of the reciprocal of L(1+√(4τ(1−p)/(p(L+τ)))) and p ≈ 1/n, the gradient complexity to reach E[f(x̄)−f⋆] ≤ ε is O((κ + κ√(τn/L) + n) log(1/ε)), where κ = L/μ. Setting τ = 0 recovers the convex-regime complexity O((κ+n) log(1/ε)), improving the previous O((κ²+n) log(1/ε)) for this type of method and matching the order of more complex variance-reduced algorithms. The paper also proves (Theorem 2.3) a sublinear rate in the general weakly convex case, E‖∇f(x̃_T)‖² ≤ 2Ψ₀/(T(γ−γ²(L−τ))), wi
Load-bearing premise
The load-bearing premise is that the step-size bound (5), imported from a cited lemma not stated in the paper, is valid and intended in its reciprocal reading (γ ≤ 1/[L(1+√(···))]); the printed display omits the reciprocal parentheses, and only that small-step-size reading is consistent with known PAGE behavior and with the claimed complexity.
Editorial extensions
If this is right
- In the convex PŁ regime (τ = 0), PAGE achieves O((κ+n) log(1/ε)) gradient evaluations, matching the order of the best known variance-reduced methods without needing to know μ to choose p.
- In the nonconvex regime (τ = L), the bound recovers the known optimal O((√n·κ + n) log(1/ε)) complexity, making the new result a genuine interpolation rather than a separate case.
- The linear-rate analysis lets the initial gradient estimate g0 be set to 0 (or any vector of comparable norm) without hurting the complexity, avoiding the n-gradient initialization cost.
- For sublinear weakly-convex convergence, arbitrary initialization gives O(Δ₀ L n / ε) gradient complexity, while initializing with a full gradient gives the nonconvex-optimal O(Δ₀ L√n / ε + n) regardless of τ.
Reading between the lines
- If O((κ+n) log(1/ε)) is tight for convex PŁ finite sums, PAGE would be an optimal single-loop method in that regime; a matching lower bound would settle that conjecture, which the paper leaves open.
- The continuous improvement with τ suggests a practical adaptive policy: estimate the weak-convexity constant τ and set p (or γ) accordingly to balance per-iteration gradient cost against contraction, which the current fixed-probability analysis does not exploit.
- The cancellation mechanism behind the proof (Lemma 2.1) is about the component functions' geometry rather than PAGE specifically, so the same Lyapunov construction should extend to other stochastic gradient estimators to yield τ-interpolating rates.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript studies the PAGE stochastic gradient estimator for finite-sum minimization of L-smooth, τ-weakly convex functions. It introduces a Lyapunov function and claims two main results: (i) under the Polyak–Łojasiewicz condition, linear convergence with rate ρ and gradient complexity O((κ + κ√(τn/L) + n) log(1/ε)) when p ∝ 1/n, which specializes to O((κ+n) log(1/ε)) in the convex case τ=0; and (ii) sublinear convergence in the general weakly convex case, with complexity O(Δ₀L√n/ε) under a suitable initialization. The analysis is Lyapunov-based and uses a new gradient-difference inequality interpolating between cocoercivity and Lipschitzness. The paper also recovers known optimal nonconvex rates and claims improved convex rates.
Significance. If the step-size conditions are corrected, the results are significant: they would show that the simple single-loop PAGE algorithm matches more complex variance-reduced methods in the convex PŁ regime, improving the prior O((κ²+n) log(1/ε)) bound to O((κ+n) log(1/ε)). The τ-weak-convexity framework gives a unified interpolation between nonconvex and convex behavior, which is of independent interest. The Lyapunov argument is detailed and mostly self-contained, and the corollaries give explicit, falsifiable complexity claims. However, the paper's central theorems currently contain an algebraic error in the displayed step-size bound that invalidates the proofs as printed; the fix appears localized, but it must be made and checked before the results can be accepted.
major comments (3)
- [Theorem 2.1 and §4.2, Eq. (5)] The printed step-size condition is the inverse of the condition actually needed. The proof derives from Eq. (4) the sufficient bound γ ≤ 1 / (L + √(2(a+b)Lτ(1−p)/p)). Using a+b ≤ 2aL/(L+τ), this becomes γ ≤ 1 / [L(1 + √(4aτ/(L+τ) · (1−p)/p))]. The paper instead displays γ ≤ (1/L)(1 + √(...)), i.e., the reciprocal of the correct factor is omitted. For τ>0 and p<1, the displayed bound is >1/L, so Lγ−1>0; since the second term in the target inequality Lγ−1 + 2(a+b)γ²Lτ(1−p)/p ≤ 0 is nonnegative, the inequality cannot hold, and the contraction (6) is not established. The theorem's hypothesis as stated therefore does not imply the claimed convergence. The same erroneous display appears in Corollary 2.2's step-size choice. The correction to the reciprocal form is consistent with known PAGE behavior at τ=L (γ ∝ 1/(L√n)), whereas the printed form gives γ ∝ √n/L.
- [Theorem 2.3 and §4.3] Theorem 2.3 inherits the same step-size error: its condition γ ≤ (1/L)(1 + √(2τ/(L+τ))√((1−p)/p)) is again the non-reciprocal form. The proof of (7) relies on the same incorrectly simplified condition (5) to ensure the key coefficient is nonpositive. Since γ as stated can exceed 1/L, the telescoping argument that yields E‖∇f(x_t)‖² → 0 is not valid as written. The sublinear convergence theorem and its corollaries therefore also require the reciprocal correction.
- [§4.2, Eq. (4)] The proof of Theorem 2.1 delegates the crucial algebraic inequality to 'Richtárik et al., 2021, Lemma 5', but the lemma is not stated or proved. This is a load-bearing step: Eq. (4) is the bridge between the step-size choice and the Lyapunov contraction. Since the lemma is elementary, it should be stated in the paper (or in an appendix) so that the reader can verify the exact form of the sufficient condition. This would also have prevented the reciprocal error in Eq. (5).
minor comments (3)
- [Abstract and §2] The abstract states that PAGE's 'complexity improves as τ decreases' without qualification. This is contradicted by Corollary 2.5, whose complexity is explicitly 'regardless of τ'. The statement should be restricted to the linear PŁ regime or to the large-step-size regime with arbitrary initialization, and the τ-independent case should be acknowledged.
- [§1.1] Typo: 'a stepsize γ of order of order 1/L' should read 'of order 1/L'.
- [Theorem 2.1] If the step-size formula is corrected to the reciprocal form, the 'additional requirement γ < 1/L if τ=0' becomes the natural strict version for τ=0; for τ>0 the corrected bound automatically gives γ<1/L. The current text presents the non-reciprocal formula as the main condition and adds an ad hoc strictness condition, which is confusing.
Circularity Check
No significant circularity: the Lyapunov proof is a self-contained derivation; the printed step-size formula issue is a correctness concern, not circular reasoning.
full rationale
The paper's central claim is a convergence theorem for PAGE under L-smoothness, weak convexity, and the Polyak-Łojasiewicz condition. The proof defines a Lyapunov function, bounds its conditional expectation using a proven Lemma 2.1, and then chooses constants and a step-size condition to force contraction. No quantity is fitted to data, no target result is assumed, and no empirical prediction is renamed as a theorem. The cited external results (Li et al. 2021 for PAGE, Richtárik et al. 2021 for a descent lemma and a scalar sufficient condition) are published, parameter-free lemmas whose assumptions do not include the present theorem; the author overlap is a normal self-citation and does not reduce the argument to itself. The serious issue flagged in review is the printed step-size condition: Eq. (5) and Theorem 2.1 display a non-reciprocal bound, while the proof's Eq. (4) and the required inequality Lγ−1+...≤0 imply a reciprocal bound 1/(L(1+...)). As written, the theorem hypothesis may not imply the contraction (6), and the cited Lemma 5 is not stated. That is a correctness or completeness flaw in the paper as printed, not circularity, because it does not make the claimed result equivalent to its inputs. The derivation is honest and largely self-contained, so the circularity score is 0.
Assumptions & free parameters
assumptions (6)
- standard math Baillon-Haddad theorem: a differentiable convex function with (L+tau)-Lipschitz gradient has a 1/(L+tau)-cocoercive gradient
- standard math Descent lemma for L-smooth functions (Richtarik et al., 2021, Lemma 4)
- domain assumption Sufficient condition for the step size inequality (Richtarik et al., 2021, Lemma 5)
- domain assumption Polyak-Lojasiewicz condition with constant mu > 0 for the overall objective f
- domain assumption Each f_i is L-smooth and tau-weakly convex with a common tau in [0,L]
- domain assumption Lower boundedness of f (f* > -infinity)
Cite this review
Pith. "Pith review of Convergence Analysis of the ProbAbilistic Gradient Estimator Algorithm for Weakly Convex Finite-Sum Optimization." pith.science (2026). https://pith.science/paper/JJQG64GP
@misc{pith2026250900737,
author = {Pith},
title = {Pith review of: Convergence Analysis of the ProbAbilistic Gradient Estimator Algorithm for Weakly Convex Finite-Sum Optimization},
year = {2026},
howpublished = {\url{https://pith.science/paper/JJQG64GP}},
note = {Machine review of arXiv:2509.00737}
}
abstract
The ProbAbilistic Gradient Estimator algorithm (PAGE), a stochastic algorithm introduced by Li et al. in 2021, was designed to find stationary points for the average of smooth nonconvex functions. In this work, we study PAGE within the broad framework of $\tau$-weakly convex functions, providing a continuous interpolation between the general nonconvex $L$-smooth regime ($\tau=L$) and the convex regime ($\tau=0$). We establish new convergence rates for PAGE, showing that its complexity improves as $\tau$ decreases.
Reference graph
Works this paper leans on
- [1]
-
[2]
Y. Bai, Y. Liu, and L. Luo. On the complexity of finite-sum smooth optimization under the Polyak-- ojasiewicz condition. In Proc. of 41st International Conference on Machine Learning (ICML), volume PMLR 235, pages 2392--2417, 2024
work page 2024
-
[3]
H. H. Bauschke and P. L. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York, 2nd edition, 2017
2017
-
[4]
D. P. Bertsekas. Convex optimization algorithms. Athena Scientific, Belmont, MA, USA, 2015
work page 2015
-
[5]
S. Bhojanapalli, B. Neyshabur, and N. Srebro. Global optimality of local search for low rank matrix recovery. In Advances in Neural Information Processing Systems (NeurIPS), volume 29. Curran Associates, Inc., 2016
work page 2016
-
[6]
S. Bubeck. Convex optimization: A lgorithms and complexity. Found. Trends Mach. Learn., 8 0 (3--4): 0 231--357, 2015
2015
-
[7]
D. Davis and D. Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM J. Optimization, 29 0 (1): 0 207--239, 2019
work page 2019
-
[8]
Y. Han, G. Xie, and Z. Zhang. Lower complexity bounds of finite-sum optimization problems: the results and construction. Journal of Machine Learning Research, 25: 0 1--86, 2024
work page 2024
Show all 22 references
-
[9]
Karimi, J
H. Karimi, J. Nutini, and M. Schmidt. Linear convergence of gradient and proximal-gradient methods under the P olyak- ojasiewicz condition. In P. Frasconi, N. Landwehr, G. Manco, and J. Vreeken, editors, Machine Learning and Knowledge Discovery in Databases, pages 795--811, Ch...
2016
-
[10]
Kawaguchi
K. Kawaguchi. Deep learning without poor local minima. In Advances in Neural Information Processing Systems (NeurIPS), volume 29. Curran Associates, Inc., 2016
2016
-
[11]
Kovalev, S
D. Kovalev, S. Horv\'ath , and P. Richt\'arik . Don't jump through hoops and remove those loops: SVRG and Katyusha are better without the outer loop. In Proc. of 31st Int. Conf. Algorithmic Learning Theory (ALT), volume PMLR 117, pages 451--467, 2020
2020
-
[12]
B. Li, M. Ma, and G. B. Giannakis. On the convergence of SARAH and beyond. In Proc. of 23rd Int. Conf. Artificial Intelligence and Statistics (AISTATS), volume PMLR 108, pages 223--233, 2020
2020
-
[13]
Z. Li, H. Bao, X. Zhang, and P. Richt \'a rik. PAGE : A simple and optimal probabilistic gradient estimator for nonconvex optimization. In Proc. of 38th Int. Conf. Machine Learning (ICML), volume PMLR 139, pages 6286--6295, 2021
2021
-
[14]
L. M. Nguyen, J. Liu, K. Scheinberg, and M. Tak \'a c . SARAH: A novel method for machine learning problems using stochastic recursive gradient. In International conference on machine learning (ICML), pages 2613--2621, 2017
2017
-
[15]
Nurminskii
E. Nurminskii. The quasigradient method for the solving of the nonlinear programming problems. Cybernetics, 9 0 (1): 0 145--150, 1973
1973
-
[16]
Richt \'a rik, I
P. Richt \'a rik, I. Sokolov, and I. Fatkhullin. EF21 : A new, simpler, theoretically better, and practically faster error feedback. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, pages 4384--4396. Curran Associates, Inc., 2021
2021
-
[17]
Shalev-Shwartz and S
S. Shalev-Shwartz and S. Ben-David. Understanding machine learning: F rom theory to algorithms . Cambridge University Press, 2014
2014
-
[18]
S. Sra, S. Nowozin, and S. J. Wright. Optimization for Machine Learning. The MIT Press, 2011
2011
-
[19]
J. Sun, Q. Qu, and J. Wright. A geometric analysis of phase retrieval. In Foundations of Computational Mathematics (FoCM), pages 55--124. Springer, 2018
2018
-
[20]
Tyurin, L
A. Tyurin, L. Sun, K. Burlachenko, and P. Richt \'a rik. Sharper rates and flexible framework for nonconvex SGD with client and data sampling. Transactions on Machine Learning Research, 2023
2023
-
[21]
Woodworth and N
B. Woodworth and N. Srebro. Tight complexity bounds for optimizing composite objectives. In Advances in Neural Information Processing Systems (NIPS 2016), volume 29. Curran Associates, Inc., 2016
2016
-
[22]
P. Yue, C. Fang, and Z. Lin. On the lower bound of minimizing Polyak- ojasiewicz functions. In Proc. of Thirty Sixth Conference on Learning Theory, volume PMLR 195, pages 2948--2968, 2023
2023
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.