{"id":"659179ba-6ec1-4f1e-8dc6-942f6d02fa4b","arxiv_id":"2509.00737","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"PAGE is shown to converge for weakly convex finite-sum problems with rates interpolating between nonconvex and convex cases, improving the known convex-case complexity.","lead":"This paper analyzes the PAGE stochastic optimization method for minimizing averages of smooth functions that may be weakly nonconvex. It proves convergence rates that improve as the problem becomes more convex, including a new linear rate under the Polyak-Lojasiewicz condition.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2.1's step-size bound is printed non-reciprocally; it contradicts the proof's own Eq. (4), which requires γ<1/L. As written, the theorem's hypothesis cannot satisfy the key contraction inequality.","rationale":"The paper has a plausible Lyapunov framework and the intended reciprocal step size would interpolate correctly between the convex (γ~1/L) and nonconvex (γ~1/(L√n)) regimes. However, the step-size condition as displayed in Theorem 2.1 and Corollary 2.2 is not merely ambiguous; it is internally inconsistent with the proof's own Eq. (4). The proof requires a bound of the form 1/(L+...), which is <1/L, while the theorem states (1/L)(1+...), which is >1/L for τ>0. This is a load-bearing error because the contraction (6) is only derived under the reciprocal condition. The external citation to Richtárik et al. 2021, Lemma 5 exacerbates the issue, but the algebra in Eqs. (4)-(5) is enough to locate the problem. The reader's weakest_assumption identified the same step-size condition as the soft spot; our analysis sharpens it from ambiguity to a concrete contradiction. Since the error appears correctable and the intended result is likely valid with the reciprocal form, the verdict remains CONDITIONAL rather than a flat rejection. The abstract's broad 'complexity improves as τ decreases' overclaim in the sublinear regime (Corollary 2.5) is a secondary issue but not the main load-bearing concern.","tokens_in":10733,"tokens_out":13736,"duration_ms":156911,"concrete_test":"Analytically re-derive the step-size condition: replace Eq. (5) by the reciprocal bound γ≤1/[L(1+√(4aτ/(L+τ))√((1−p)/p))] and verify that it is implied by Eq. (4); then test the printed non-reciprocal bound at τ=L, p=1/n and show it violates Lγ−1+2(a+b)γ²Lτ(1−p)/p≤0. If the printed bound admits no γ satisfying the proof's key inequality, the theorem statement must be corrected before the rates can be accepted.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central theorem rests on the step-size condition (5), but the displayed formula is not what the proof establishes. From the proof, the sufficient condition for Lγ−1+2(a+b)γ²Lτ(1−p)/p≤0 is the reciprocal bound γ≤1/[L+√(2(a+b)Lτ(1−p)/p)] (Eq. 4, citing Richtárik et al. 2021, Lemma 5). Since the denominator is >L, this forces γ<1/L whenever τ>0. The paper then 'simplifies' to Eq. (5): γ≤(1/L)(1+√(4aτ/(L+τ))√((1−p)/p)), which is algebraically the inverse of the reciprocal: it should be 1/[L(1+...)]. The printed bound is >1/L for τ>0. For example τ=L,p=1/n gives γ≈√(2n)/L, whereas Eq. (4) requires γ≲1/(L√(2n)); such a step size makes Lγ−1>0 and the second term nonnegative, so the key inequality cannot hold. Hence Theorem 2.1's stated hypothesis is not sufficient for the contraction (6), and Corollary 2.2 inherits the same erroneous γ. The underlying method may be correct with the reciprocal formula, but as printed the central claim is unproven. The external lemma (Richtárik et al. 2021, Lemma 5) is never stated, compounding the issue.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":11086,"tokens_out":9158,"duration_ms":109833,"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":[{"comment":"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.","section":"Theorem 2.1 and §4.2, Eq. (5)"},{"comment":"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.","section":"Theorem 2.3 and §4.3"},{"comment":"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).","section":"§4.2, Eq. (4)"}],"minor_comments":[{"comment":"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.","section":"Abstract and §2"},{"comment":"Typo: 'a stepsize γ of order of order 1/L' should read 'of order 1/L'.","section":"§1.1"},{"comment":"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.","section":"Theorem 2.1"}],"recommendation":"major_revision","confidential_remarks":"The reciprocal error appears to be a typo rather than a conceptual flaw, and the main complexity claims are likely recoverable after the correction. However, the error affects the statements of both main theorems and the corresponding corollaries, so the revision must be checked carefully. I also recommend asking the authors to state the cited Richtárik et al. lemma explicitly. If the corrected step-size bound still yields the claimed rates, the paper would be a solid contribution to the journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this paper has a real idea, but the central theorem as printed has a bad step-size condition. The proof actually derives the correct reciprocal bound, then—when simplifying—writes the inverse. So Theorem 2.1's hypothesis is not sufficient for the contraction, and Corollary 2.2 inherits the erroneous γ. That's load-bearing, but it looks like a typographical/algebraic slip, not a wrong algorithm. The proof's equation (4) is the right kind of bound, and the rest of the proof logic is coherent. Still, as is, the theorem is unproven.\n\nWhat is actually new: the tau-weakly convex framework for PAGE, a Lyapunov function combining both ||gt − ∇f(xt)||² and ||gt||², and the improved convex PŁ complexity O((κ+n) log(1/ε)) versus the prior O((κ²+n) log). The paper recovers the known optimal nonconvex rates and, with τ=0, matches the best known convex finite-sum rates. The proofs are detailed and mostly self-contained; the derivation of Lemma 2.1 is clean. Credit where due: this is a solid subfield contribution, not a paradigm shift.\n\nSoft spots beyond the step-size error: the cited 'Richtárik et al. 2021, Lemma 5' is neither stated nor proved, which makes the key sufficient condition hard to verify. The abstract's 'complexity improves as τ decreases' only holds under PŁ—their own sublinear results explicitly say the complexity does not improve with decreasing τ. That's an overclaim in the abstract. Also, the claim that g0=0 gives the same complexity as g0=∇f(x0) is plausible but should be verified with the corrected step-size, since Ψ0 changes.\n\nThe step-size error is the main issue. It should be fixable: replace the non-reciprocal formula in Theorem 2.1 and Corollary 2.2 with the reciprocal form. I'd recommend sending to peer review, because the underlying result is likely correct and worth having. A referee should demand the corrected condition and a statement of the external lemma. If the authors fix these, the paper could stand.\n\nWho is this for: researchers working on stochastic variance reduction or weakly convex optimization. A reading group could get a good discussion out of the step-size mistake—it's instructive.\n\nBottom line: deserves a serious referee, but expect heavy revision before acceptance.","headline":"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.","tokens_in":702,"tokens_out":842,"would_cite":false,"duration_ms":56510,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C15"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["PAGE","weakly convex optimization","Polyak–Łojasiewicz condition","finite-sum optimization","variance reduction","stochastic optimization","linear convergence","Lyapunov analysis"],"falsifier":"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.","tokens_in":10643,"feed_emoji":"🧮","tokens_out":12429,"duration_ms":134548,"temperature":0.7,"pith_summary":"This paper establishes convergence guarantees for the PAGE stochastic algorithm, a single-loop variance-reduced method, across the whole range of smooth weakly convex finite-sum problems. Its main result is linear convergence under the Polyak–Łojasiewicz condition, with a gradient-evaluation complexity that interpolates between the optimal nonconvex bound and a new convex-regime bound. Because PAGE evaluates only about three component gradients per iteration on average, the result means a very simple method can be as fast as much more elaborate variance-reduced schemes. The paper also gives sublinear rates for the general weakly convex case.","feed_headline":"A simple stochastic loop matches the best convex finite-sum rates","feed_subtitle":"Rates interpolate from optimal nonconvex to convex PŁ regimes in one algorithm.","key_machinery":"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.","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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 τ."],"supporting_citations":[{"why":"Introduces PAGE, the algorithm analyzed here, and supplies the baseline optimal nonconvex complexity that the paper recovers.","marker":"[Li et al., 2021]"},{"why":"Proposes PAGE under the name Loopless-SARAH and gives prior convex and strongly convex complexities that the paper improves upon.","marker":"[Li et al., 2020]"},{"why":"Cited for the descent lemma (Lemma 4) and the step-size condition (Lemma 5) that the proof invokes as black boxes.","marker":"[Richtárik et al., 2021]"},{"why":"Defines the Polyak–Łojasiewicz condition and the implication strong convexity ⇒ PŁ, the assumption underlying the linear rates.","marker":"[Karimi et al., 2016]"},{"why":"Provides the monotone-operator and Baillon–Haddad facts used to prove the key interpolation inequality (Lemma 2.1).","marker":"[Bauschke and Combettes, 2017]"},{"why":"Supplies the bound ‖∇f‖² ≤ 2L(f−f⋆) used to ensure the Lyapunov function is nonnegative and to relate Δ₀ to the initial gradient.","marker":"[Bubeck, 2015]"},{"why":"Gives the supermartingale convergence result used to turn the one-step contraction into almost-sure convergence.","marker":"[Bertsekas, 2015]"},{"why":"Shows that gradient descent is optimal for n = 1 PŁ problems, supporting the paper's conjecture that the convex-regime complexity is unimprovable.","marker":"[Yue et al., 2023]"},{"why":"Provides the strongly-convex finite-sum lower bound used in the discussion of how the new rates compare with known optimal methods.","marker":"[Woodworth and Srebro, 2016]"}],"fun_headline_variants":["PAGE algorithm bridges convex and nonconvex optimization","New rates for weakly convex sums: from nonconvex to convex in one method","Stochastic optimizer matches convex rates for weakly convex problems","PAGE's complexity improves as weak convexity fades","Linear convergence for weakly convex finite sums under PL condition"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["PAGE algorithm bridges convex and nonconvex optimization","New rates for weakly convex sums: from nonconvex to convex in one method","Stochastic optimizer matches convex rates for weakly convex problems","PAGE's complexity improves as weak convexity fades","Linear convergence for weakly convex finite sums under PL condition"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000312,"raw_usage":{"total_tokens":1591,"prompt_tokens":705,"completion_tokens":886,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":449,"completion_tokens_details":{"reasoning_tokens":803}},"tokens_in":449,"tokens_out":886,"duration_ms":10145,"temperature":1.0,"reasoning_tokens":803,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T13:17:51.161810+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}