REVIEW 3 major objections 4 minor 1 cited by
Revisiting LocalSGD and SCAFFOLD: Improved Rates and Missing Analysis
T0 review · 3 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read Local steps can provably beat minibatch SGD in non-convex distributed optimization.
desk verdict 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. 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 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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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)$.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [Appendix A.3.1, Proof of Theorem 4 (Eq. (46) and Lemma 19)] 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 5.1, Theorem 1 and Remark 8; abstract] 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 5.2, Theorem 5 and Appendix A.3.2] 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.
minor comments (4)
- [Appendix A.1, Lemma 6] 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 3.2, SCAFFOLD notation] 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.
- [Appendix A.3.2, Proof of Theorem 5] 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.
- [Appendix A.2, Lemma 12] 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.
Circularity Check
No circularity: the new LocalSGD/SCAFFOLD rates are derived from stated assumptions and compared against an external MbSGD baseline; no fitted parameter is renamed as a prediction.
full rationale
I walked the derivation chain for Theorems 1-5. Each claimed rate is proved in Appendix A from the stated Assumptions 1-4 using self-contained lemmas (e.g., Lemmas 10-19); no parameter is fitted to a subset of data and then reported as a prediction. The MbSGD comparator in Lemma 1 is an external result (Dekel et al. 2012), and the speedup claims are defined by comparing the displayed upper bounds to that baseline, not by construction from the bounds themselves. Several cited baselines (Koloskova et al. 2020; Karimireddy et al. 2020; Woodworth et al. 2020b) share coauthors with this paper, but they are used as contextual prior results and open-problem statements, not as the source of the new estimates; the critical estimates such as Lemmas 7, 9, 12, 13, and 19 are proven in the appendix. The 'variance trick' (Lemma 6) is a standard convexity inequality, not a renamed target result, and it is used as a proof device rather than as an assertion of the theorem. No uniqueness theorem is imported from the authors' prior work, and no ansatz is smuggled in by citation: Assumptions 1-4 are introduced as explicit conditions in Section 3. I also checked the skeptic's concern about Theorem 4: the step where the batch-gradient drift term is dropped uses the bound eta <= 1/(4 sqrt(L delta tau)), while the appearing coefficient 162 eta^4 L^2 delta^2 (tau-1)^3 tau would require a bound of order 1/(sqrt(L delta) tau) to be dominated. That is an algebraic gap in the proof as written, but it is a correctness issue, not a circularity: the claimed rate is not equivalent to an input by definition, nor is it forced by a self-citation chain. For this reason the circularity score is 0, with the proof-gap concern noted separately as a correctness risk.
Assumptions & free parameters
assumptions (6)
- domain assumption Each f_i has L-Lipschitz continuous gradient
- domain assumption Stochastic oracle is unbiased with variance bounded by σ²
- domain assumption Standard gradient similarity (Assumption 1)
- domain assumption Hessian similarity (Assumptions 2 and 2+)
- domain assumption Weak convexity (Assumption 3)
- domain assumption Convex-hull Lipschitz Hessian (Assumption 4)
Cite this review
Pith. "Pith review of Revisiting LocalSGD and SCAFFOLD: Improved Rates and Missing Analysis." pith.science (2026). https://pith.science/paper/QOEWSYLC
@misc{pith2026250104443,
author = {Pith},
title = {Pith review of: Revisiting LocalSGD and SCAFFOLD: Improved Rates and Missing Analysis},
year = {2026},
howpublished = {\url{https://pith.science/paper/QOEWSYLC}},
note = {Machine review of arXiv:2501.04443}
}
read the original abstract
LocalSGD and SCAFFOLD are widely used methods in distributed stochastic optimization, with numerous applications in machine learning, large-scale data processing, and federated learning. However, rigorously establishing their theoretical advantages over simpler methods, such as minibatch SGD (MbSGD), has proven challenging, as existing analyses often rely on strong assumptions, unrealistic premises, or overly restrictive scenarios. In this work, we revisit the convergence properties of LocalSGD and SCAFFOLD under a variety of existing or weaker conditions, including gradient similarity, Hessian similarity, weak convexity, and Lipschitz continuity of the Hessian. Our analysis shows that (i) LocalSGD achieves faster convergence compared to MbSGD for weakly convex functions without requiring stronger gradient similarity assumptions; (ii) LocalSGD benefits significantly from higher-order similarity and smoothness; and (iii) SCAFFOLD demonstrates faster convergence than MbSGD for a broader class of non-quadratic functions. These theoretical insights provide a clearer understanding of the conditions under which LocalSGD and SCAFFOLD outperform MbSGD.
Figures
Forward citations
Cited by 1 Pith paper
-
What's in a Smoothness Constant? Tighter Rates for Local SGD with Bounded Second-order Heterogeneity
Local SGD provably improves over Mini-batch SGD under bounded second-order heterogeneity in the general convex setting, with nearly tight upper and lower bounds.
Reference graph
Works this paper leans on
-
[1]
(37) obviously holds for k = 0
-
[2]
We assume all the vectors are in Rd. Lemma 6 (variance trick). For any y ∈ Rd, Ξ ≤ n∑ i=1 ‖ ‖xi − y ‖ ‖2 2 . (21) Proof. Since∑ n i=1 ‖ ‖xi − y ‖ ‖2 2 is strongly convex in y, let y∗ = arg miny∈ Rd ∑ n i=1 ‖ ‖xi − y ‖ ‖2
-
[6]
Then, d (∑ n i=1 ‖ ‖xi − y ‖ ‖2 2 ) dy ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ y∗ = 2( y − ¯x)|y∗ = 0, and we have y∗ = ¯x. Remark 12. We will use this variance trick frequently in our analysis. For instance , when upper bounding Ξ t+1 recursively, we can use the following inequality: Ξ t+1 ≤ 1 n n∑ i=1 ‖ ‖xi t+1 − ¯xt + η∇f (¯xt) ‖ ‖2 2 . Lemma 7. Under Assumptions 2+ and 4, we hav...
work page 2003
-
[8]
We assume (37) holds for k, where k ≤ τ − 2. Then for η ≤ 2 L , E [Ξ t+1] (21) ≤ 1 n n∑ i=1 E ‖ ‖xi t − ηgi t − (¯xt − η∇f (¯xt)) ‖ ‖2 2 ≤ 1 n n∑ i=1 E ‖ ‖xi t − η∇fi(xi t) − (¯xt − η∇f (¯xt)) ‖ ‖2 2 + η2σ 2 (6) ≤ 1 n n∑ i=1 (1 + γ) E ‖ ‖xi t − η∇fi(xi t) − (¯xt − η∇fi(¯xt)) ‖ ‖2 2 + (1 + γ − 1)η2 ζ2 + η2σ 2 (28) ≤ (1 + γ) E [Ξ t] + (1 + γ − 1)η2ζ2 + η2σ ...
-
[9]
(40) obviously holds for k = 0
-
[10]
We assume (40) holds for k, where k ≤ τ − 2. Then, since η ≤ 1 2L(τ − 1) , E ‖ ‖xi t+1 − ˆxi t+1 ‖ ‖2 2 ≤ E ‖ ‖xi t − η∇fi(xi t) − ˆxi t + η∇fi(ˆxi t) ‖ ‖2 2 + η2σ 2 (29) ≤ (1 + Lη)2 E ‖ ‖xi t − ˆxi t ‖ ‖2 2 + η2σ 2 ≤ (1 + γ)2 · E ‖ ‖xi t − ˆxi t ‖ ‖2 2 + η2σ 2, (41) and by induction hypothesis, we have E ‖ ‖xi t+1 − ˆxi t+1 ‖ ‖2 2 (40) ≤ (1 + γ)2(k+1) · ...
-
[11]
(43) obviously holds for k = 0
-
[12]
We assume (43) holds for k, where k ≤ τ − 2. Then, since η ≤ 1 3L(τ − 1) , ˆΞ t+1 (31) ≤ 1 n n∑ i=1 (1 + γ) ‖ ‖ ˆxi t − η∇fi(ˆxi t) − (ˆxt − η∇fi(ˆxt)) ‖ ‖2 2 + (1 + γ − 1)η2 ζ2 (29) ≤ (1 + γ) · (1 + Lη)2 ˆΞ t + (1 + γ − 1)η2ζ2 ≤ (1 + γ)3 · ˆΞ t + (1 + γ − 1)η2ζ2. (44) and by induction hypothesis, we have ˆΞ t+1 (43) ≤ (1 + γ)3(k+1) · k · 3(τ − 1)η2ζ2 + (...
work page 2024
Show all 12 references
-
[684]
Tak´ aˇ c, M., Bijral, A., Richt´ arik, P., and Srebro, N
PMLR. Tak´ aˇ c, M., Bijral, A., Richt´ arik, P., and Srebro, N. (2013). Mini-batch primal and dual methods for svms. In In 30th International Conference on Ma- chine Learning, ICML 2013 . Wang, J., Das, R., Joshi, G., Kale, S., Xu, Z., and Zhang, T. (2024). On the unreasonabl...
2013
-
[1282]
Mishchenko, K., Malinovsky, G., Stich, S., and Richtarik, P
PMLR. Mishchenko, K., Malinovsky, G., Stich, S., and Richtarik, P. (2022). ProxSkip: Yes! Local gradi- ent steps provably lead to communication accelera- tion! Finally! In Proceedings of the 39th Interna- tional Conference on Machine Learning , volume 162 of Proceedings of Mac...
2022
-
[4157]
Patel, K
PMLR. Patel, K. K., Wang, L., Woodworth, B., Bullins, B., and Srebro, N. (2022). Towards optimal communica- tion complexity in distributed non-convex optimiza- tion. In Advances in Neural Information Processing Systems. Recht, B., Re, C., Wright, S., and Niu, F. (2011). Hog- w...
2022 arXiv
-
[7881]
Nesterov, Y
PMLR. Nesterov, Y. (2003). Introductory lectures on convex optimization: A basic course , volume 87. Springer Science & Business Media. Nguyen, L. M., Nguyen, P. H., van Dijk, M., Richt´ arik, P., Scheinberg, K., and Tak´ aˇ c, M. (2018). Sgd and hogwild! convergence without t...
2003
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.