{"id":"2bd7c32f-ebd6-4426-aadb-626d2b9ff96f","arxiv_id":"2412.13619","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new analysis of L-SVRP achieves O((nδ/µ + n) log 1/ε) iteration complexity under Hessian similarity and strong convexity, improving on prior O(δ²/µ² + n) bounds in the high-dissimilarity regime.","lead":"This paper proves a sharper convergence rate for the Loopless Stochastic Variance Reduced Proximal Point method (L-SVRP) under a Hessian similarity condition, improving the complexity from quadratic to linear in the condition number. The result matters for federated optimization theory because it shows an implicit variance-reduced method can beat plain SGD in communication when local functions are highly heterogeneous.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The iteration bound appears mathematically sound, but the claimed practical speedup depends on an unexamined exact-proximal-oracle assumption whose cost can dominate wall-clock time.","rationale":"I read the proof of Theorem 1 and the derivation of Corollary 1 in the appendix. The Lyapunov analysis is internally consistent: Lemma 1 provides the contraction of the ||x_k - x*||^2 term under strong convexity; Lemma 2 controls the ||w_k - x_k||^2 term; the Hessian similarity assumption is used exactly where the cross term is bounded; the constants in Corollary 1 satisfy the conditions of Theorem 1. The final complexity O((nδ/µ + n) log(1/ε)) for p=1/n follows from the maximum of 1/(1+µγ) and 1-p/4, with γ chosen as Θ(p/δ). I therefore do not see a fatal gap in the central mathematical claim. The paper does contain small presentational errors, such as the asymptotic simplification in Corollary 3 (it writes O(κ + 1/p) where O(κ/p + 1/p) is meant), but the preceding inequality K ≥ (1+1/p)(3κ+4) log already implies the advertised O(nκ + n) rate when p=1/n, and the appendix's proof supports it. These are typos, not structural flaws. The most consequential weakness is the one the reader identified: the iteration bound assumes an exact proximal oracle for every sampled f_i, and the paper's 'communication complexity' interpretation counts only outer rounds. If the prox is expensive, the claimed improvement over SGD in the high-δ regime may not materialize in wall-clock time. This does not invalidate the theorem, but it limits the practical significance of the advertised speedup and warrants a conditional or caveated reception. Since the reader's verdict is already CONDITIONAL and this concern does not move it further, I recommend UNCHANGED.","tokens_in":27182,"tokens_out":23117,"duration_ms":181312,"concrete_test":"Implement L-SVRP on a non-quadratic strongly convex finite-sum problem, e.g., ℓ2-regularized logistic regression with n=100, d=100 and Hessian dissimilarity δ/µ ≈ 100. Solve each prox_{γf_i} to high accuracy (1e-12 relative residual) with an inner Newton or FISTA-type solver, measuring both inner iterations and wall-clock time per outer round. Run until ||x_k - x*||^2 ≤ 1e-6 and compare total wall-clock time against full-gradient SGD with the same round-based communication model. If prox-solving time accounts for the dominant share of wall-clock time (e.g., >90%), the claimed communication improvement does not translate to practical speedup, confirming the concern.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central complexity claim in Corollary 3 and Remark 2 is a statement about the number of outer iterations of Algorithm 3, where each iteration requires the exact evaluation of prox_{γf_i} for the sampled function f_i. The paper counts communication rounds and compares with SGD, implicitly treating this proximal oracle as cheap. For general finite-sum losses, however, computing prox_{γf_i} means solving the implicit subproblem x_{k+1} = argmin_x { f_i(x) + (1/(2γ))||x - (x_k + γ(∇f_i(w_k) - ∇f(w_k))||^2 }. Even under µ-strong convexity and without smoothness, this subproblem has no closed form in general and can be as hard as a strongly convex optimization problem in its own right; its cost scales with the conditioning of f_i + (1/γ)||·||^2 and with the accuracy required. The paper's experiments use only quadratics, where the prox is a linear solve, so they do not expose this cost. Because the theorem is conditional on an exact oracle, the mathematical bound holds, but the practical message of a communication-complexity speedup over SGD is load-bearing on the oracle being cheap. The paper does not state or justify this, and its own Section 2.4 notes only the stability of implicit methods, not their per-iteration expense.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper revisits the Loopless Stochastic Variance Reduced Proximal Point method (L-SVRP) for ERM (1) under Hessian similarity (Assumption 1) and strong convexity (Assumption 2). It constructs a Lyapunov function Λ_k = ‖x_k − x*‖² + c‖w_k − x_k‖², proves a contraction in Theorem 1 under three coupled parameter conditions, and specializes the parameters in Corollary 1 to obtain a linear rate max{(1+μγ)^{-1}, 1−p/4} under the stepsize condition (17). Corollary 3 translates this into an iteration complexity O((nδ/μ + n) log(‖x0−x*‖²/ε)) when p = 1/n, claimed to improve on Khaled and Jin (2023) in the regime δ/μ ≥ n, with no smoothness assumption. The paper also gives a convex analogue (Corollary 2) and experiments on quadratic functions over 48 configurations.","tokens_in":27408,"tokens_out":12653,"duration_ms":98971,"significance":"If the central bound is correct, the paper yields the first analysis of L-SVRP achieving an O(nδ/μ) dependence under Hessian similarity, improving on the prior O(δ²/μ²) in the high-dissimilarity regime, and it does so without Lipschitz smoothness. The proof is concise and the stepsize is selected analytically with no fitted parameters; the contraction argument via Lemmas 1–2 appears sound. However, the current statement of Corollary 3 contains a stepsize mismatch that must be corrected, and the practical interpretation as a communication-speedup over SGD is conditional on an exact proximal oracle whose per-call cost is not analyzed. With those issues addressed, the result would be a meaningful contribution to the theory of stochastic proximal methods.","major_comments":[{"comment":"The stepsize displayed in Eq. (24) is not the stepsize used in the proof of Corollary 3. The proof (Appendix D) defines a = 2(3−p)²/(p²(p+1)) and verifies the condition (17) only for γ′ = 1/(δ√a) = (p/(3−p))·√((p+1)/2)/δ, which for small p is Θ(p/δ). The displayed γ in Eq. (24), with the square root over (3−p)/p, is Θ(1/(δ√p)) for small p, so the two differ by a factor Θ(√p). The advertised complexity O((nδ/μ + n) log) in Remark 2 is derived using γ′, not the displayed γ; moreover, with the displayed γ the condition (17) is generally violated when p = 1/n (its left-hand side becomes Θ(n)). Please correct Eq. (24) and ensure any experimental stepsize satisfies the condition used in the theory.","section":"Section 3.4 / Corollary 3 and Appendix D"},{"comment":"The paper's central claim is presented as an improvement in communication complexity over SGD, but each iteration of Algorithm 3 requires the exact solution of the implicit subproblem x_{k+1} = prox_{γ f_{i_k}}(x_k + γ(∇f_{i_k}(w_k) − ∇f(w_k))). For general finite-sum losses this proximal operator has no closed form and can be as expensive as solving a strongly convex optimization problem; Section 2.4 only notes the stability of implicit methods, not their per-iteration expense. The experiments use only quadratics (Section 4), where the prox reduces to a linear solve, so they do not expose this cost. Please state explicitly that the bound is measured in exact proximal-oracle calls (equivalently communication rounds), and discuss the implications for the wall-clock speedup suggested by the title and abstract.","section":"Algorithm 3, Sections 2.4 and 3"}],"minor_comments":[{"comment":"In the statements of Lemma 1 and Lemma 8, the term E[‖x_{k+1} − x̄_{k+1}‖²] should be written as a conditional expectation E[‖x_{k+1} − x̄_{k+1}‖² | x_k, w_k] to match the rest of the expression.","section":"Lemma 1 and Lemma 8"},{"comment":"The equivalence y = prox_{γg}(x) ⇔ y + γ∇g(y) = x requires differentiability of g; for nondifferentiable convex g the condition is x − y ∈ γ∂g(y). The surrounding text already mentions this, so only a short pointer is needed.","section":"Section 2.4, Eq. (6)"},{"comment":"The reference list contains two entries with identical titles (Richtárik et al., 2024a and 2024b); please clarify whether these are two distinct works or a duplicated citation.","section":"References"},{"comment":"The checklist states that code is provided (item 3a), but no URL or supplementary link appears in the text; please add it or mark the item as not applicable.","section":"Section 4"}],"recommendation":"major_revision","confidential_remarks":"The paper is a theoretical contribution from a group with a long track record in this area; the self-citations are used mainly as baselines rather than to establish the new result. The stepsize mismatch is fixable but is exactly the kind of error that must be resolved before publication. The proximal-oracle cost concern is a framing issue: for a pure complexity-theory paper the oracle model is standard, but the abstract's practical 'speeding up' claim goes beyond what is shown."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: the paper's main iteration bound for L-SVRP is probably right and is a real, if modest, improvement over the previous analysis of that algorithm. But the headline Corollary 3 has a stepsize mismatch, and the practical 'speedup' claim leans on an exact proximal oracle that the paper never discusses.\n\nThe genuinely new thing is the Lyapunov analysis. The cancellation of the Hessian dissimilarity term via the coefficient c is neat, and it removes the need for smoothness. Corollary 1's contraction is backed by a proof that checks out. So if you care about iteration complexity of stochastic proximal methods, this is a legitimate data point: O((nκ+n)) when p=1/n, versus O(κ²+n) from Khaled-Jin, in the regime κ≥n. The authors are honest that SVRS and SABER already achieve better rates; the contribution is to the analysis of L-SVRP specifically.\n\nThe soft spots are in the packaging. Corollary 3 states a stepsize γ=... that doesn't match the γ' used in the proof; the proof uses γ'=1/(δ√a). The stated γ is Θ(√p) or Θ(1) depending on how you read it, while the proof's γ' is Θ(p/δ). That's a concrete error in the main statement. Also, the simplification from √a to 3/p in the iteration count uses an inequality that fails for small p; the order is still O((κ/p)+(1/p)), so the asymptotic claim survives, but the constants are wrong as stated. Both are fixable in a revision.\n\nThe experiments are thin: quadratics only, no code or data link, no error bars, and Figures 3 and 4 look duplicated. They confirm linear convergence on easy instances, but they don't test the proximal oracle cost. The stress-test note about exact prox is a fair caveat: for general finite-sum losses, computing prox_{γf_i} can be as hard as solving a strongly convex problem, so the communication-round comparison with SGD may not translate to wall-clock time. The paper should either state this assumption explicitly or add experiments with nontrivial proximal evaluations.\n\nIf I were the editor, I'd send it to review: the core derivation is solid and the theorem is worth having, but it needs a corrected Corollary 3, a discussion of the oracle cost, and better artifacts. It's not a breakthrough, but it's a useful incremental step.","headline":"A sound but sloppy analysis of L-SVRP: the main bound holds, but the headline corollary has a stepsize mismatch and the practical speedup claim ignores the proximal oracle cost.","tokens_in":27997,"tokens_out":4090,"would_cite":true,"duration_ms":34150,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C15","90C06"],"pacs":[],"model":"deepseek-v4-flash","headline":"The loopless stochastic proximal point method L-SVRP converges in O((nδ/µ + n) log(1/ε)) iterations under Hessian similarity and strong convexity, improving the previous O(δ²/µ² + n) bound when δ/µ ≥ n and needing no smoothness assumption.","keywords":["stochastic proximal point method","variance reduction","Hessian similarity","loopless SVRP","strong convexity","communication complexity","federated learning","convergence rate"],"falsifier":"Run L-SVRP on a problem whose proximal steps have no closed form and must be solved by an inner iterative method, and compare total inner gradient evaluations against SGD to reach the same accuracy; if the total work does not decrease in the regime δ/µ ≥ n, the claimed communication speed-up does not translate into computational speed-up.","tokens_in":26942,"feed_emoji":"⚡","tokens_out":9287,"duration_ms":72510,"temperature":0.7,"pith_summary":"This paper revisits the Loopless Stochastic Variance Reduced Proximal Point method (L-SVRP) and gives a sharper convergence guarantee for expected risk minimization when the component losses have similar second derivatives. Under Hessian similarity (parameter δ) and strong convexity (parameter µ), the authors prove an iteration complexity of O((nδ/µ + n) log(1/ε)) when the snapshot probability is p = 1/n, improving on the prior O((δ/µ)² + n) bound in the regime δ/µ ≥ n. The analysis needs no Lipschitz smoothness assumption on the component losses, which broadens the class of problems the method is justified for. The proof works by choosing a Lyapunov function that combines the distance to the optimum with the distance between the two iterates and letting Hessian-similarity cross terms cancel exactly.","feed_headline":"Proximal method now scales linearly with Hessian dissimilarity","feed_subtitle":"New analysis drops smoothness assumptions and beats the old quadratic bound when δ/µ ≥ n.","key_machinery":"The argument is carried by the Lyapunov function Λ_k = ∥x_k − x*∥² + c∥w_k − x_k∥², where x_k is the current iterate and w_k is the snapshot point refreshed to x_k with probability p. Lemma 1 bounds the one-step contraction of the first term using strong convexity, producing an error term proportional to E⟨∇ψ_i(x̄_{k+1}) − ∇ψ_i(w_k), x_{k+1} − x̄_{k+1}⟩, where ψ_i = f_i − f. Lemma 2 controls the evolution of the second term and yields the compensating negative term −cpξ∥w_k − x̄_{k+1}∥², which cancels the Hessian-dissimilarity contribution bounded via Assumption 1. With the parameter choices c = 2p/((3−p)²(1+µγ)), ξ = 1/2, and ζ = p/(4−2p), the mixed terms telescope and the Lyapunov sequence contracts by max{1/(1+µγ), 1−p/4} each iteration.","core_discovery":"The central claim is that L-SVRP, the loopless variance-reduced proximal point method, converges to the exact minimizer of a strongly convex finite sum under Assumptions 1 and 2 (Hessian similarity and strong convexity) at a linear rate whose condition number appears to the first power of δ/µ rather than its square. Specifically, with stepsize γ = Θ(√p/δ) and snapshot probability p = 1/n, the number of iterations to guarantee E∥x_K − x*∥² ≤ ε is O((nδ/µ + n) log(∥x0 − x*∥²/ε)). This matches the order of magnitude of the best known rates for variance-reduced gradient methods under smoothness, but here it holds without any smoothness assumption on the individual losses. In the regime δ/µ ≥ n this bound is asymptotically smaller than the earlier O((δ/µ)² + n) complexity established for the same algorithm, and the paper interprets the iteration count as communication complexity in a federated setting.","pith_inferences":["The exact-prox oracle assumption is structurally separate from the convergence theorem: if evaluating prox_{γf_i} is itself expensive for a given problem class, the counted iterations may not translate into wall-clock savings, and a fair comparison would need to add the inner cost of each prox evaluation.","The cancellation mechanism that makes the Hessian-dissimilarity term disappear is generic and could plausibly be injected into other loopless proximal or primal-dual methods, such as monotone inclusion solvers, to obtain analogous linear-in-κ rates.","The paper's own experiments show empirical rates well above the theoretical ones, so deriving a tighter bound from that gap is a natural next step."],"forward_implications":["In the high Hessian dissimilarity regime δ/µ ≥ n, the new bound O((nδ/µ + n) log(1/ε)) is strictly better than the previous O((δ/µ)² + n) complexity for L-SVRP, so the method's advantage grows as data heterogeneity increases.","Because the proof avoids Lipschitz smoothness, the same rate applies to nonsmooth strongly convex losses whose proximal operators are available, a class for which gradient-based variance reduction would need extra assumptions.","When iterations are counted as communication rounds, for example in federated learning with n clients, the p = 1/n setting yields an O(nκ + n) communication complexity that improves on standard SGD's dependence on the smoothness constant.","The convex case (µ = 0) is covered as well, with an averaging bound showing E[f(x̄_K)] − f* ≤ ∥x0 − x*∥²/(2γK), giving a sublinear rate without smoothness."],"supporting_citations":[{"why":"Introduced L-SVRP and gave the O(κ² + n) complexity bound that this paper improves in the δ/µ ≥ n regime.","marker":"Khaled and Jin (2023)"},{"why":"Provided the loopless variance-reduction design (L-SVRG) that L-SVRP adapts to the proximal setting.","marker":"Kovalev et al. (2020)"},{"why":"Introduced the Hessian similarity condition (Assumption 1) that drives the improved dependence on δ/µ.","marker":"Shamir et al. (2014)"},{"why":"Analyzed the stochastic proximal point method whose update L-SVRP combines with variance reduction.","marker":"Asi and Duchi (2019)"},{"why":"Supplies the proof strategy for the one-iteration inequality (Lemma 1) via the DANE argument.","marker":"Jiang et al. (2024a)"},{"why":"Provides the proximal operator contraction property under strong convexity used in Lemma 6.","marker":"Bauschke and Combettes (2011)"},{"why":"The smoothness-free analysis template for stochastic proximal point methods that this work extends.","marker":"Richtárik et al. (2024b)"},{"why":"Gives the explicit δ² = ‖(1/n)Σ A_i² − Ā²‖ formula for quadratics used in the experimental validation.","marker":"Szlendak et al. (2022)"}],"fun_headline_variants":["L-SVRP hits linear rate without smoothness assumptions","Proximal method beats quadratic bound when δ/µ ≥ n","First-power Hessian term speeds up L-SVRP","No smoothness assumptions, L-SVRP improves complexity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The rate assumes an exact proximal operator for every f_i is evaluated at each iteration, so the iteration count is the real cost only if solving those subproblems is cheap; for general finite-sum losses a proximal step can be as expensive as the original problem.","fun_headline_variants_meta":{"raw":{"variants":["L-SVRP hits linear rate without smoothness assumptions","Proximal method beats quadratic bound when δ/µ ≥ n","First-power Hessian term speeds up L-SVRP","No smoothness assumptions, L-SVRP improves complexity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001013,"raw_usage":{"total_tokens":4242,"prompt_tokens":870,"completion_tokens":3372,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":486,"completion_tokens_details":{"reasoning_tokens":3303}},"tokens_in":486,"tokens_out":3372,"duration_ms":23782,"temperature":1.0,"reasoning_tokens":3303,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T12:58:25.854944+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run L-SVRP on a problem whose proximal steps have no closed form and must be solved by an inner iterative method, and compare total inner gradient evaluations against SGD to reach the same accuracy; if the total work does not decrease in the regime δ/µ ≥ n, the claimed communication speed-up does not translate into computational speed-up.","supporting_citations":[{"cited_title":"and Jin, C","cited_arxiv_id":null,"evidence_quote":"Introduced L-SVRP and gave the O(κ² + n) complexity bound that this paper improves in the δ/µ ≥ n regime."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provided the loopless variance-reduction design (L-SVRG) that L-SVRP adapts to the proximal setting."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduced the Hessian similarity condition (Assumption 1) that drives the improved dependence on δ/µ."},{"cited_title":"and Duchi, J","cited_arxiv_id":null,"evidence_quote":"Analyzed the stochastic proximal point method whose update L-SVRP combines with variance reduction."},{"cited_title":"and Combettes, P","cited_arxiv_id":null,"evidence_quote":"Provides the proximal operator contraction property under strong convexity used in Lemma 6."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the explicit δ² = ‖(1/n)Σ A_i² − Ā²‖ formula for quadratics used in the experimental validation."}],"review_version":1}