{"id":"00b820cb-cd7e-4d34-a141-09571014996a","arxiv_id":"2501.04443","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"LocalSGD gains a proven speedup over minibatch SGD for weakly convex objectives under standard gradient similarity, and SCAFFOLD gains a speedup for non-quadratic functions.","lead":"This paper proves new convergence rates for LocalSGD and SCAFFOLD, two popular distributed optimization methods, and shows they can beat minibatch SGD under weaker heterogeneity assumptions than previously known. The results clarify when local training steps help in federated learning and other communication-constrained settings.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4's absorption step is unjustified: the stated step-size bound is too weak by a factor growing with tau, so the SCAFFOLD speedup does not follow from the proof as written.","rationale":"The reader's CONDITIONAL verdict is reasonable, but I identify a different and more concrete load-bearing concern than the one named in the reader's weakest_assumption. The reader focused on the parameter regime needed for the LocalSGD speedup (zeta^2 = O(1/R), rho << L), which is a presentation/qualification issue. My concern is an internal proof gap in the SCAFFOLD analysis: the step-size condition used to absorb a batch-gradient drift term in Theorem 4 appears too weak by a factor growing with tau. If my coefficient calculation is correct, the displayed SCAFFOLD rate does not follow from the proof, even in the favorable regime the reader assumes. This is the most load-bearing issue because the paper's third headline contribution is the first SCAFFOLD speedup for non-quadratic functions, and that claim depends directly on Theorem 4. I am not asserting final rejection: the gap may be fixable by a smaller step size, and the corrected rate may still show a speedup when delta << L. That is why I keep the verdict CONDITIONAL rather than REJECT. The LocalSGD theorems and the paper's other contributions are not affected by this specific objection, and the variance trick is a genuine technical idea. The proposed concrete test is a direct algebraic re-derivation of the disputed absorption step, which settles the matter without new experiments or external assumptions.","tokens_in":29738,"tokens_out":21741,"duration_ms":196347,"concrete_test":"Independently recompute the coefficient of the batch-gradient term in the proof of Theorem 4 (Appendix A.3.1, around Lemmas 18-19). Substitute gamma = 1/(3(tau-1)) and eta = 1/(4*sqrt(L*delta*tau)) into the inequality leading to the line 'Then, for eta <= ...' and evaluate the constant multiplying (1/T)*sum E||(1/n)sum_i grad f_i||^2 for tau = 50. If the constant exceeds 1/2, the absorption step is invalid. Then compute the largest eta that makes the constant <= 1/2, recompute 2*Delta/(eta*T) with T = R*tau, and compare the resulting optimization term with the MbSGD term L*Delta/R. This will show whether the SCAFFOLD speedup survives in modified form or whether the theorem's rate needs a substantial correction.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central SCAFFOLD claim rests on Theorem 4, but its proof contains an algebraic gap in the step where the batch-gradient drift term is dropped. In Lemma 19, E[Xi(t)] is bounded by a term of the form 3*gamma^{-2}*(1+gamma^{-1})*eta^4*delta^2 * sum_{l<k} E||(1/n)sum_i grad f_i(x_i^{(r tau + l)})||^2. When this is substituted into Lemma 18 and multiplied by 2L^2/T and summed over r and k, the coefficient of the batch-gradient sum is at least on the order of 162*L^2*delta^2*eta^4*(tau-1)^3*tau (up to the exact factor from gamma). To move this term to the left-hand side of (46), where the coefficient of the batch-gradient term is 1/2, one needs 162*L^2*delta^2*eta^4*(tau-1)^3*tau <= 1/2, i.e. eta <= const/(sqrt(L*delta)*tau) for large tau. The proof instead uses eta <= 1/(4*sqrt(L*delta*tau)), which is larger by roughly sqrt(tau). For tau = 50 the resulting coefficient exceeds 1 by three orders of magnitude, so the displayed 'Then, for eta <= ...' step in the proof of Theorem 4 is not justified. Consequently the claimed optimization term (L/tau + sqrt(L*delta) + rho)*Delta/R for SCAFFOLD on non-quadratic functions, and with it the first non-quadratic speedup claim, is not established by the manuscript. This concern is independent of the regime conditions flagged by the reader: even with zeta^2 = O(1/R) and rho << L, the absorption step fails. The LocalSGD theorems (Theorems 1-3) appear to use different estimates and are not implicated by this specific gap.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper revisits the convergence analysis of LocalSGD and SCAFFOLD for distributed non-convex optimization under standard assumptions: gradient similarity, Hessian similarity, weak convexity, and Lipschitz continuity of a function in the convex hull of the local objectives. It claims new upper bounds in which the optimization term is improved from O(L Delta / R) to O((L/tau + rho) Delta / R) for LocalSGD and to O((L/tau + sqrt(L delta) + rho) Delta / R) for SCAFFOLD, together with refinements under higher-order similarity. The appendix contains detailed proofs, and Section 6 reports synthetic experiments intended to validate the dependence on the similarity parameters. The main advertised contributions are the first communication-round speedup analyses of LocalSGD for non-convex functions and of SCAFFOLD for non-quadratic functions.","tokens_in":30123,"tokens_out":12354,"duration_ms":113545,"significance":"If the claimed rates were fully established, the paper would resolve two well-known open questions in distributed non-convex optimization: it would show speedup of LocalSGD beyond the MbSGD baseline under standard gradient similarity, and it would extend the SCAFFOLD speedup beyond quadratic objectives. The authors also make a useful technical contribution with the 'variance trick' and the noiseless-sequence construction, and they provide code for the experiments. However, the load-bearing SCAFFOLD proof contains an algebraic absorption gap, and the LocalSGD speedup claim is conditional on regime assumptions that are not stated in the theorem or the abstract. The significance of the paper therefore depends on whether these issues can be repaired without worsening the claimed rates.","major_comments":[{"comment":"The absorption step in the proof of Theorem 4 is not justified. After substituting Lemma 19 into Eq. (46), the batch-gradient drift term has coefficient C = 162 L^2 delta^2 eta^4 (tau-1)^3 tau on (1/T) sum_{r,k} E ||(1/n) sum_i nabla f_i(x_i^{(rtau+k)})||^2, with gamma = 1/(3(tau-1)) and after moving from the inner sums over l < k to full sums. The left-hand side of (46) has coefficient 1 on that same (1/T) sum, so absorption requires C <= 1, i.e. eta = O(1/(sqrt(L delta) tau)) for large tau. The step-size bound eta <= 1/(4 sqrt(L delta tau)) used in the proof is larger by roughly sqrt(tau). For tau = 50 and L = delta = 1 it gives C on the order of 1.5 x 10^3, so the displayed 'Then, for eta <= ...' step cannot be valid. Consequently the rate (19) for SCAFFOLD on non-quadratic functions is not established by this proof.","section":"Appendix A.3.1, Proof of Theorem 4 (Eq. (46) and Lemma 19)"},{"comment":"The abstract and the contribution bullets claim that LocalSGD converges faster than MbSGD for weakly convex functions, but the theorem itself does not state the regime in which this follows. The rate in (16) contains the terms (L Delta zeta / R)^{2/3} and (L Delta sigma)^{2/3} tau^{1/3} R^{-2/3}; unless zeta^2 = O(1/R) and the noise terms are subordinate, the bound is no better than the MbSGD bound in Lemma 1. Remark 8 acknowledges the zeta^2 condition, but the theorem statement and abstract do not, and the improved first term also requires rho << L and tau > 1. Please state these conditions explicitly in the theorem and abstract, or qualify the speedup claim accordingly.","section":"Section 5.1, Theorem 1 and Remark 8; abstract"},{"comment":"The proof of Theorem 5 repeats the same absorption problem as Theorem 4. After applying Lemma 7 and Lemma 19, it must absorb a drift term with coefficient 1296 eta^4 bar-delta^2 delta^2 (tau-1)^3 tau, and the step-size bound eta <= 1/(6 sqrt(bar-delta delta tau)) is too weak by a factor that grows with tau. Thus the claimed improved optimization term (L/tau + sqrt(bar-delta delta) + rho) Delta / R is also not established as proved.","section":"Section 5.2, Theorem 5 and Appendix A.3.2"}],"minor_comments":[{"comment":"The statement of Lemma 6 is missing the factor 1/n: the variance trick should read Xi <= (1/n) sum_i ||x_i - y||^2. The later use in Eq. (21) applies the correct version, but the lemma as stated is not the inequality used in the proofs.","section":"Appendix A.1, Lemma 6"},{"comment":"The sentence 'Suppose there are 2R communication rounds, i.e., 2R = T/tau' is confusing because Algorithm 1 has R outer loops, each containing 2tau local steps, and the proofs average only over the tau variance-reduced steps in the second half of each outer loop. Please define T, R, and the index t consistently in the SCAFFOLD section and in Lemma 18.","section":"Section 3.2, SCAFFOLD notation"},{"comment":"The last line of the proof of Theorem 5 says 'Finally, (15) follows from the following assignment', but it should refer to the display for Theorem 5, not to Eq. (15) of Lemma 5.","section":"Appendix A.3.2, Proof of Theorem 5"},{"comment":"The proof of Lemma 12 is deferred with the text 'The proof is similar to the proof of Lemma 16', but Lemma 16 appears later in the appendix. Reordering the lemmas or inserting a forward reference would improve readability.","section":"Appendix A.2, Lemma 12"}],"recommendation":"major_revision","confidential_remarks":"The LocalSGD analysis appears to be a genuine technical contribution, but the SCAFFOLD theorem is the main advertised extension and its proof has a concrete algebraic gap. I would ask the authors to redo the absorption step with a correct eta condition and then check whether the stated rate, or a modified rate, still follows. The paper's 'first speedup' claims also need to be aligned with the explicit zeta^2 = O(1/R), rho << L, and tau > 1 regime conditions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear [Colleague],\n\nShort version: the LocalSGD half of this paper is a genuine step forward; the SCAFFOLD half has a load-bearing gap in the absorption step of Theorem 4, and Theorem 5 inherits the same problem. The non-quadratic SCAFFOLD speedup claims do not follow from the proofs as written.\n\nWhat is actually new: Theorem 1 gives the first speedup analysis of LocalSGD for weakly convex nonconvex functions under standard gradient similarity, with the optimization term improving from LΔ/R to (L/τ+ρ)Δ/R. Theorem 2 removes the uniform gradient similarity requirement from the convex analysis, replacing ¯ζ with ζ, which is a strict improvement over Woodworth et al. Theorem 3 shows LocalSGD can exploit Hessian similarity and a Lipschitz Hessian. The \"variance trick\" is a nice proof device: it unrolls the local iteration to get a tighter bound on worker variance. The appendix is detailed, and the LocalSGD proofs are coherent at the level I checked.\n\nThe soft spot is Theorem 4. Lemma 19 bounds the worker drift by a sum of batch-gradient norms with coefficient proportional to η⁴δ²(τ-1)³. After substituting into Lemma 18, the coefficient on the batch-gradient term becomes 162 η⁴ L² δ² (τ-1)³ τ. To absorb that into the left-hand side, which has coefficient 1/2 on that same term, you need roughly η ≤ constant/(√(Lδ)·τ). The paper instead uses η ≤ 1/(4√(Lδτ)), which is larger by about √τ. For τ=50 the coefficient exceeds 1/2 by three orders of magnitude. So the step where the batch-gradient term is dropped is not justified. Theorem 5 has the same structure and fails the same way. The paper transparently states it analyzes a simplified SCAFFOLD variant, which is fine, but the claimed speedup rates for it are not established.\n\nThis does not implicate the LocalSGD theorems; they use different drift estimates. But the SCAFFOLD contributions need either a smaller step-size (which would likely kill the speedup claim) or a genuinely different argument. Until that is fixed, the abstract and Table 1 overstate the SCAFFOLD results.\n\nWho this is for: distributed optimization theorists, especially anyone building on LocalSGD analysis. The paper deserves a serious referee because the LocalSGD results are significant enough to warrant attention, and the SCAFFOLD gap needs to be caught. I would engage with it, but I would insist the authors fix or prune the SCAFFOLD claims before anything is cited.\n\nBest,","headline":"LocalSGD results are a real improvement; the SCAFFOLD theorems have a clear step-size absorption gap that invalidates the non-quadratic speedup claims as written.","tokens_in":30682,"tokens_out":5957,"would_cite":true,"duration_ms":48268,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C15","68W15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Local steps can provably beat minibatch SGD in non-convex distributed optimization.","keywords":["LocalSGD","SCAFFOLD","minibatch SGD","federated learning","distributed non-convex optimization","weak convexity","gradient similarity","Hessian similarity"],"falsifier":"Find any family of problems satisfying Assumptions 1 and 3 (L-smooth, weakly convex local functions with standard gradient similarity constant $\\zeta$) together with a stepsize obeying the conditions of Theorem 1 for which the empirical quantity $\\frac1T\\sum_{t=0}^{T-1}\\|\\nabla f(\\bar x_t)\\|^2$ exceeds the right-hand side of (16); a direct simulation on two weakly convex quadratics with known $\\zeta$ and $\\rho$ would settle whether the derived rate is actually attained.","tokens_in":29533,"feed_emoji":"📉","tokens_out":8720,"duration_ms":72801,"temperature":0.7,"pith_summary":"This paper attempts to close a gap between practice and theory for two workhorse algorithms of federated learning, LocalSGD and SCAFFOLD, by proving that both can converge faster than minibatch SGD (MbSGD) in distributed non-convex optimization. The central target is the optimization term in the convergence rate: MbSGD pays $L\\Delta/R$, while the paper derives $(L/\\tau+\\rho)\\Delta/R$ for LocalSGD and $(L/\\tau+\\sqrt{L\\delta}+\\rho)\\Delta/R$ for SCAFFOLD, where $\\tau$ is the number of local steps per communication round, $\\rho$ measures non-convexity, and $\\delta$ measures Hessian dissimilarity. If correct, these are the first speedup analyses for LocalSGD on non-convex functions and for SCAFFOLD beyond quadratic objectives, needing only standard (not uniform) gradient or Hessian similarity. The reason to care: communication, not computation, is the bottleneck in large-scale distributed training, so a provable communication-round speedup explains when taking more local steps actually helps.","feed_headline":"Local steps can provably beat minibatch SGD in non-convex settings","feed_subtitle":"New convergence rates give LocalSGD and SCAFFOLD a communication-round speedup when heterogeneity is mild.","key_machinery":"The argument rests on a 'variance trick' (Lemma 6): instead of bounding the worker deviation $\\Xi_t=\\frac1n\\sum_i\\|x_i^t-\\bar x_t\\|^2$ by the worst-case distance to the last averaged point, the authors bound it by $\\frac1n\\sum_i\\|x_i^t-\\bar x_{t-1}+\\eta\\nabla f(\\bar x_{t-1})\\|^2$ and unroll the recursion, exploiting the symmetry of the workers. A second piece is a 'noiseless sequence' $\\hat x_i^t$, which decouples the stochastic noise from the gradient discrepancy so that quadratic terms like $\\Xi_t^2$ can be controlled deterministically. Two structural lemmas carry the improvements: Lemma 9 shows that weak convexity makes local gradient steps contract like $1+O(\\rho\\eta)$ rather than $1+O(L\\eta)$, and Lemma 7 bounds the gap between the averaged local gradients and the true gradient by $8\\bar\\delta^2\\Xi_t+\\frac{M^2}{2}\\Xi_t^2$ using a convex-hull representative $\\hat f$ with $M$-Lipschitz Hessian. Together these let the heterogeneity term stay at the MbSGD level while the optimization term gains the $1/\\tau$ factor.","core_discovery":"On the paper's own terms, the discovery is that weak convexity is enough to make local steps pay off: Theorem 1 gives LocalSGD the rate $$O\\!\\left(\\left(\\frac{L}{\\tau}+\\rho\\right)\\frac{\\$\\Delta$}{R}+\\sqrt{\\frac{L\\$\\Delta$\\$sigma^{2}$}{n\\tau R}}+\\left(\\frac{L\\$\\Delta$\\zeta}{R}\\right)^{2/3}+(L\\$\\Delta$\\$\\sigma$)^{2/3}\\frac{\\$tau^{{1/3}}$}{$R^{{2/3}}$}\\right),$$ with the first term improving the MbSGD optimization term $L\\Delta/R$ by a factor $1/\\tau$ plus the weak-convexity parameter $\\rho$, while the remaining terms match the previous best LocalSGD bound. Theorems 4 and 5 do the same for SCAFFOLD, replacing the previous quadratic-only speedup with one that holds for general non-quadratic functions under standard Hessian similarity and weak convexity, and Theorem 3 shows LocalSGD also benefits from Hessian similarity and a Lipschitz-continuous Hessian through a term $(\\bar\\delta\\Delta\\zeta/R)^{2/3}$ and a fifth-order term in $M$. The paper states these are the first speedup analyses of LocalSGD for non-convex functions and of SCAFFOLD for non-quadratic functions.","pith_inferences":["A practical reading the authors leave implicit: the speedup regime is precisely when the data heterogeneity satisfies $\\zeta^2\\lesssim L\\Delta/R$, so one can estimate $\\zeta$ from the workers' gradients in advance and decide whether local steps or larger mini-batches are the better use of communication.","The variance trick is not specific to these two algorithms; it should transfer to decentralized SGD, partial participation, or asynchronous protocols, where the same worst-case-versus-average deviation gap appears.","The SCAFFOLD analysis shows that the simplified variant with a single stepsize retains the speedup, suggesting that the extra features of the original proposal (different local and global stepsizes, using the last update for variance reduction) are not needed for the rate.","If the theorems are tight, the fifth-order term $(M^2\\Delta^4\\zeta^4/R^4)^{1/5}$ in Theorem 3 predicts a distinct slow-down shape in the heterogeneity-dominated regime; measuring the convergence curve's exponent in $R$ there would test the higher-order smoothness assumption independently."],"forward_implications":["With $\\tau>1$ and $\\rho\\ll L$, LocalSGD's optimization error term shrinks from $O(L\\Delta/R)$ to $O((L/\\tau+\\rho)\\Delta/R)$, so the same gradient-norm accuracy is reached in fewer communication rounds.","SCAFFOLD obtains the analogous speedup with $(L/\\tau+\\sqrt{L\\delta}+\\rho)\\Delta/R$ for non-quadratic functions, using standard Hessian similarity instead of uniform; when a representative in the convex hull has zero Lipschitz Hessian constant, the $\\sqrt{\\bar\\delta\\delta}$ improvement of Theorem 5 applies.","For convex functions, Theorem 2 replaces the uniform gradient-similarity constant $\\bar\\zeta^2$ by the standard $\\zeta^2$ in the heterogeneity term, weakening the condition needed for the previously known convex speedup.","Under Hessian similarity and Lipschitz-continuous Hessians, LocalSGD matches MbSGD under the looser conditioning $\\bar\\delta^2\\zeta^2+M^2\\zeta^4=O(1/R)$, instead of $\\zeta^2=O(1/R)$."],"supporting_citations":[{"why":"Provides the MbSGD rate (Lemma 1) that the new bounds must beat to claim speedup.","marker":"Dekel et al. (2012)"},{"why":"Gives the previous non-convex LocalSGD rate (Lemma 2) whose optimization term the paper improves.","marker":"Koloskova et al. (2020)"},{"why":"Establishes the convex speedup of LocalSGD under uniform gradient similarity, the assumption Theorem 2 weakens.","marker":"Woodworth et al. (2020b)"},{"why":"Provides the quadratic-only SCAFFOLD speedup and the open question the paper resolves for non-quadratic functions.","marker":"Karimireddy et al. (2020)"},{"why":"Supplies the standard smoothness and weak-convexity inequalities (Lemma 8) used in the contraction arguments.","marker":"Nesterov (2003)"}],"fun_headline_variants":["Weak convexity unlocks LocalSGD speedup over minibatch SGD","First proof: LocalSGD beats minibatch for non-convex","SCAFFOLD speedup extends beyond quadratics","Local steps pay off with weak convexity and Hessian similarity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The speedup conclusion depends on the heterogeneity and noise terms in the bound staying below the improved optimization term; in particular the heterogeneity term $(L\\Delta\\zeta/R)^{2/3}$ only keeps the MbSGD rate when $\\zeta^2=O(1/R)$, a conditioning stated in Remark 8 rather than in Theorem 1 or the abstract.","fun_headline_variants_meta":{"raw":{"variants":["Weak convexity unlocks LocalSGD speedup over minibatch SGD","First proof: LocalSGD beats minibatch for non-convex","SCAFFOLD speedup extends beyond quadratics","Local steps pay off with weak convexity and Hessian similarity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000702,"raw_usage":{"total_tokens":3207,"prompt_tokens":1021,"completion_tokens":2186,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":637,"completion_tokens_details":{"reasoning_tokens":2121}},"tokens_in":637,"tokens_out":2186,"duration_ms":15443,"temperature":1.0,"reasoning_tokens":2121,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:34:29.721946+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find any family of problems satisfying Assumptions 1 and 3 (L-smooth, weakly convex local functions with standard gradient similarity constant $\\zeta$) together with a stepsize obeying the conditions of Theorem 1 for which the empirical quantity $\\frac1T\\sum_{t=0}^{T-1}\\|\\nabla f(\\bar x_t)\\|^2$ exceeds the right-hand side of (16); a direct simulation on two weakly convex quadratics with known $\\zeta$ and $\\rho$ would settle whether the derived rate is actually attained.","supporting_citations":[],"review_version":1}