Pith. sign in

REVIEW 3 major objections 4 minor 72 references

The paper proves that in general convex optimization, Local SGD provably outperforms Mini-batch SGD under a bounded-second-order-heterogeneity assumption, and its upper bounds are nearly tight against matching lower bounds.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-02 01:13 UTC pith:5GV4TPCX

load-bearing objection Solid proof of the general-convex conjecture with a genuinely new self-bounding analysis and near-tight rates, but the 'beats Mini-batch' claim in Remark 3 overstates what the constants support. the 3 major comments →

arxiv 2607.14731 v1 pith:5GV4TPCX submitted 2026-07-16 cs.LG math.OCstat.ML

What's in a Smoothness Constant? Tighter Rates for Local SGD with Bounded Second-order Heterogeneity

Kumar Kshitij Patel , Rustem Islamov , Sebastian U Stich , Aurelien Lucchi , Eduard Gorbunov , Lingxiao Wang This is my paper
classification cs.LG math.OCstat.ML
keywords Local SGDFederated Averagingsecond-order heterogeneityconvex optimizationminimax lower boundsclient driftcommunication-efficient distributed learningself-bounding analysis
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Local SGD (federated averaging) lets each client run several gradient steps before communicating, but theory has struggled to explain when this helps when clients have different data. This paper shows that a quantity it calls second-order heterogeneity—how much client curvatures differ, rather than how much their gradients differ at every point—is the right measure: under only a bound on curvature differences, vanilla Local SGD provably beats Mini-batch SGD. The proof introduces a trajectory-dependent control of client drift and closes it with a self-bounding recursion. The paper also gives new lower bounds, showing the rates are nearly optimal, and extends the lower-bound technique to serial SGD with replacement, where rare high-curvature clients create the worst-case smoothness barrier.

Core claim

The central claim is that for convex, H-smooth objectives where clients' gradient disagreements at the optimum are bounded by ζ⋆ and their second-order heterogeneity by τ (the gradient disagreement can move at most τ per unit distance), Local SGD achieves the rate (informal): HB²/KR + (Hτ²)^{1/3}B²/R^{2/3} + σB/√(MKR) + (Hζ⋆²B⁴)^{1/3}/R^{2/3} + (Hσ²B⁴)^{1/3}/(K^{1/3}R^{2/3}), together with a companion single-machine-mimicking rate. This is the first general-convex guarantee that captures the benefit of bounded second-order heterogeneity. A matching lower bound is nearly tight, leaving only a narrow regime unresolved. The proof replaces the usual uniform gradient-dissimilarity assumption by b

What carries the argument

The analysis is carried by a self-bounding loop over three quantities: Amax (expected distance of the average iterate to the optimum), Cmax (consensus error, how far local models drift from their average), and Vmax (gradient dissimilarity along the average trajectory). A recursion shows Cmax ≲ η²K²Vmax + η²Kσ² and Vmax ≤ 2τ²Amax + 2ζ⋆²; feeding these into the average-iterate descent lemma produces a closed inequality that bounds Amax and Cmax purely in terms of ζ⋆ and τ, provided the step-size is small enough relative to τ, K, and R. This is the 'self-bounding' mechanism that obviates the uniform first-order heterogeneity assumption.

Load-bearing premise

The self-bounding loop closes only when the step-size satisfies η ≤ (24H τ² K³ R)^{-1/3}; rearranged, this demands K³ R τ² be small enough. If client curvature differs more (larger τ) or clients compute too many local steps K over too long a horizon R, the proof's trajectory-dependent control fails, which is why the proven advantage of local computation is confined to a small-K regime.

What would settle it

Construct a problem in the class with τ substantially larger than H/√R and K large enough that K³Rτ² exceeds the allowed bound, and run vanilla Local SGD with the prescribed constant step-size. If the final gap is still the claimed rate, the theory is overly pessimistic; if the gap is larger than the claimed rate, the self-bounding step is necessary. Concretely, the paper's own phase diagram leaves a 'red' regime where upper and lower bounds differ; a counterexample there—or, conversely, a tightened argument matching the upper bound—would settle the question.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Local SGD provably beats Mini-batch SGD whenever K≫1, τ ≲ H/√R, ζ⋆ ≲ HB/√R, and σ ≲ HB√(K/R), under only curvature-level heterogeneity.
  • The lower bounds show the main rate terms cannot be improved in most of the parameter plane, so the advantage of local updates is not an artifact of the analysis.
  • The new upper bounds interpolate smoothly to the homogeneous and ζ-bounded settings, recovering single-machine SGD rates when ζ⋆=τ=0.
  • For serial SGD with replacement, second-order heterogeneity explains the worst-client smoothness barrier: one can have H≪ĥ with ĥ ≈ √M τ, so rare high-curvature clients force the standard ĥ-dependent rate.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The self-bounding technique looks transferable: the same trajectory-dependent control could yield improved rates for variance-reduced local methods, decentralized SGD, or non-convex objectives, though the paper does not claim this.
  • The unresolved red regime suggests the true minimax rate may interpolate differently between τ and ζ⋆; a concrete next step is to close that gap with a combined lower bound.
  • If the rates are tight, they give a practical design rule: when client curvature is known to be similar, more local steps are safe, whereas high-curvature heterogeneity forces more frequent communication—testable by measuring Hessian similarity of real federated datasets.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies vanilla Local SGD for general convex, H-smooth distributed objectives under a new combination of assumptions: bounded first-order heterogeneity at the optimum (ζ⋆) and bounded second-order heterogeneity along the trajectory (τ). The main theoretical contribution is a new upper bound (Theorem 6) that replaces the previous uniform-gradient-dissimilarity parameter ζ by ζ⋆ and τ, via a self-bounding recursion that couples the consensus error, the trajectory-wise gradient heterogeneity, and the average-iterate error. A second upper bound (Theorem 7) mimics single-machine SGD. The paper also proves new lower bounds (Theorems 4, 9, 10 and Corollary 1) that decouple first- and second-order heterogeneity, and a lower bound for serial SGD with replacement under heterogeneous client smoothness (Theorem 5/11). The authors claim that, together, these results nearly characterize the minimax rate of Local SGD over the class P^{H,B,σ}_{ζ⋆,τ} and resolve the conjecture of Patel et al. in the general convex setting.

Significance. If the proofs are correct, this is a substantial step forward for the theory of Local SGD. The self-bounding loop in §3.1 is a genuinely new technical mechanism: it avoids the restrictive uniform first-order heterogeneity assumption by letting the trajectory of the algorithm control its own drift. The lower-bound constructions are also valuable: they isolate first-order versus second-order heterogeneity effects and improve on the prior τB²/R lower bound. The phase-diagram comparison in Appendix G is honest about the remaining gap (the red regime), and Theorem 5 gives a fresh perspective on worst-client smoothness in serial SGD. The paper is detailed and largely self-contained, and the main upper-bound proofs are structured carefully. However, as detailed below, the central interpretive claim that Local SGD 'provably outperforms Mini-batch SGD' in the full parameter region stated in Remark 3 is not supported by the theorem as stated, and this affects the paper's headline significance.

major comments (3)
  1. [§3.1, Theorem 6 and Remark 3] Remark 3 is not established by Theorem 6 as stated. The formal theorem carries a factor 18 in front of all five terms. In the noiseless, ζ⋆=0 case, set τ = cH/√R, which is allowed by Remark 3's condition τ≲H/√R. Then (Hτ²)^{1/3}B²/R^{2/3} = c^{2/3}HB²/R, while the mini-batch baseline is HB²/R. The bound in Theorem 6 therefore becomes at least 18 c^{2/3} HB²/R + HB²/(KR), which beats the baseline only when c is smaller than (1/18)^{3/2} (for large K), not for all constants in the stated regime. The same saturation occurs at the ζ⋆ and σ boundaries: ζ⋆ ≈ HB/√R and σ ≈ HB√(K/R) produce heterogeneity terms proportional to the mini-batch rate. Thus the claim that Local SGD provably improves over Mini-batch SGD in the region listed in Remark 3 needs either explicit small constants in the parameter conditions or a comparison with the same universal constants. This is load-bearing because the ab
  2. [§3.1, Lemmas 9–10] The self-bounding loop closes only under the step-size constraint η ≤ (24Hτ²K³R)^{-1/3}. Rearranged, this requires K³R·τ² ≤ 1/(24Hη³). While the theorem's step-size choices always satisfy this constraint, the constraint itself is what limits the provable local-computation advantage to small K or small τ. In the saturated regime of Remark 3, the theorem's bound is dominated by the τ-dependent term rather than by HB²/(KR), so the advertised 'local computation helps' conclusion does not follow from the displayed rate. The paper should state this limitation explicitly and adjust the claimed regime in Remark 3 accordingly.
  3. [§4, Theorem 9 and Theorem 10] The two lower-bound constructions are plausible, but their combination into the final lower bound of Theorem 4 is described only informally. In particular, the second-order block has ζ⋆=0 and the first-order block has τ=0; the paper states that they can be combined on disjoint coordinates, but it does not track the allocation of the radius budget B among the blocks or verify that the combined instance satisfies ∥x⋆∥≤B and the Assumption 1 bound. This is not a fatal issue, but since Theorem 4 is a central claim, the coordinate-combining argument should be made explicit or a reference to the standard disjoint-coordinate technique should be supplied.
minor comments (4)
  1. [§2.1, Notation] The notation T is used throughout the main text (e.g., Lemma 1, Lemma 7) but is only defined as T=KR in the appendix. Please define T in Section 2.
  2. [Appendix G, Phase diagrams] The phase-diagram section contains several typos and unclear inequalities, e.g., 'x0 ≤ y2 0 ≥1' and 'y2 0 ≤y 2/3 0 ≥1' in Case 3 of §G.2. These should be rewritten for clarity.
  3. [Appendix I, Lemma 21] Lemma 21 is stated as a 'classical lower bound' without proof or reference. Since it is used in the proof of Theorem 11, a short proof or a precise citation would improve the appendix.
  4. [Throughout, lower-bound statements] The upper bounds are stated for the averaged iterate while the lower bounds are for the final iterate. The paper acknowledges this gap, but it would help to state in one place why this does not affect the claimed nearly-tight characterization in Figure 3.

Circularity Check

0 steps flagged

No significant circularity: the self-bounding recursion is a genuine fixed-point argument and the lower bounds are independent explicit constructions.

full rationale

The paper's core derivation is the self-bounding loop of Section 3.1: Eq. (8) bounds Amax in terms of Cmax, Eq. (9) bounds Cmax in terms of Vmax, and Eq. (10) bounds Vmax in terms of Amax. This is a legitimate system of inequalities, not a circular assumption of the conclusion: Lemma 9 closes the loop by imposing the step-size condition η ≤ (24Hτ²K³R)^{-1/3}, which makes the Amax coefficient on the right-hand side strictly less than 1, and then solves for Amax; Lemma 10 then substitutes the resulting bound into the consensus-error estimate. No step renames a fitted parameter as a prediction, and no theorem is assumed in its own proof. The lower bounds in Section 4 are supported by explicit hard instances (the two-client quadratic construction of Theorem 9 and the three-coordinate non-smooth construction of Theorem 10) whose heterogeneity parameters are computed from the construction, so they do not reduce to the upper bound by construction. Citations to Woodworth et al. [32], Patel et al. [26], and Patel et al. [1] supply standard lemmas and context, but the new argument does not rely on the truth of the conjecture being proved. The paper itself notes remaining gaps (Section 6, red region of Figure 3) and the step-size restriction in Lemma 9; these are limitations or potential overclaims, not circularity. In particular, Remark 3's 'beats Mini-batch' comparison may require more careful constant tracking, but that is a quantitative correctness concern, not a circularity.

Axiom & Free-Parameter Ledger

3 free parameters · 6 axioms · 0 invented entities

Upper bounds rest on standard convex-analysis machinery and the paper's own heterogeneity assumptions (Assumptions 1-3); the lower-bound constructions use hand-tuned scale parameters (α, λ, µ) typical of minimax constructions. No new entities are invented; no constants are fitted to data.

free parameters (3)
  • Angle parameter α (Theorem 9 lower bound) = (12R-1)/(12R+1)
    Chosen in the two-client quadratic construction to yield average-condition-number κ=12R; this makes the hard instance scale with R and produces the τB²/√R term.
  • Curvature scale λ (Theorem 9) = min{H, sqrt(3R)τ}
    Caps client Hessian norm at H and second-order heterogeneity at τ; balances the HB²/R and τB²/√R lower-bound terms.
  • Auxiliary curvature µ (Theorem 10) = 𝔗/(4B²), 𝔗 = min{HB², ζ⋆²/H, (Hζ⋆²B⁴)^{1/3}/R^{2/3}}
    Set to make the small-step-size regime contribute Ω(𝔗); chosen by hand so that the construction lies in the problem class.
axioms (6)
  • domain assumption Assumption 1: bounded first-order heterogeneity at the optimum (average ∥∇Fm(x⋆)∥² ≤ ζ⋆²)
    Defines problem class P^{H,B,σ}_{ζ⋆,τ}; used in Lemma 8 and throughout.
  • domain assumption Assumption 3: bounded second-order heterogeneity (average gradient-difference Lipschitz constant τ²)
    Central structural condition; controls Vmax via Amax in Lemma 8 and via Bmax in Lemma 11.
  • domain assumption Assumption 2: uniform first-order heterogeneity (ζ) for Theorem 8
    Used only in the complementary upper bound of §3.3.
  • standard math Standard convex-analysis facts: H-smoothness/co-coercivity (Baillon-Haddad), Jensen, AM-GM
    Used throughout the appendix; classical.
  • domain assumption M=2 is without loss of generality in lower bounds; hard instances combined on disjoint coordinates
    Standard simplification in distributed lower bounds; for odd M a dummy client with the average objective is added, weakening the bound by (M-1)/M.
  • domain assumption Lemma 21 (standard stochastic/first-order-heterogeneity lower bound) is assumed
    Stated without proof in Appendix I.3; classical mean-estimation construction.

pith-pipeline@v1.3.0-alltime-deepseek · 50538 in / 33326 out tokens · 257838 ms · 2026-08-02T01:13:53.341561+00:00 · methodology

0 comments
read the original abstract

Local SGD, also known as Federated Averaging, is a widely used distributed optimization algorithm. Although Local SGD often outperforms alternatives such as Mini-batch SGD in practice, theory still only partially explains when and why local updates help under realistic data heterogeneity. Recent work by [Patel et al., 2025] shows that a bounded second-order heterogeneity assumption captures the efficiency of Local SGD for strongly convex objectives, and conjectures that the same principle extends to the general convex setting. In this paper, we prove this conjecture by establishing an improved convergence guarantee for Local SGD on general convex objectives under bounded second-order heterogeneity. We also improve the best-known lower bounds for Local SGD in this setting, showing that our upper bounds are nearly tight. Together, these results provide a sharper, more fine-grained convergence theory for Local SGD. As a further application of our techniques, we provide a lower bound for serial SGD with replacement, showing how second-order heterogeneity captures the impact of rare high-curvature clients.

Figures

Figures reproduced from arXiv: 2607.14731 by Aurelien Lucchi, Eduard Gorbunov, Kumar Kshitij Patel, Lingxiao Wang, Rustem Islamov, Sebastian U Stich.

Figure 1
Figure 1. Figure 1: Illustration of the IC setting: M clients communicate R times with K units of computation in between. The baselines we consider in the paper all require K stochastic gradient computations between communication rounds on each client. An instance of Problem (1) can be characterized by the client distributions {Dm ∈ ∆(Z)}m∈[M] and a differentiable4 loss function f(·; z ∈ Z) : R d → R. We denote the set of all… view at source ↗
Figure 2
Figure 2. Figure 2: Two canonical distributed optimization baselines implemented in the intermittent communi [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The tightness of our upper and lower bounds, highlighted in the setting with [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Phase diagrams of the lower bound of Patel et al. [PITH_FULL_IMAGE:figures/full_fig_p013_4.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

72 extracted references · 21 linked inside Pith

  1. [1]

    Revisiting consensus error: A fine-grained analysis of local sgd under second-order data heterogeneity

    Kumar Kshitij Patel, Ali Zindari, Sebastian U Stich, and Lingxiao Wang. Revisiting consensus error: A fine-grained analysis of local sgd under second-order data heterogeneity. InThe Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025.(Cited on pages 1, 3, 6, 8, 10, 11, 12, 13, 16, 23, 34, 49, and 50)

    2025

  2. [2]

    Federated learning: Collaborative machine learn- ing without centralized training data, Apr 2017

    Brendan McMahan and Daniel Ramage. Federated learning: Collaborative machine learn- ing without centralized training data, Apr 2017. URL https://ai.googleblog.com/ 2017/04/federated-[]learning-[]collaborative.html.(Cited on page 2)

    2017

  3. [4]

    Diloco: Distributed low- communication training of language models.arXiv preprint arXiv:2311.08105, 2023.(Cited on pages 2, 3, and 5)

    Arthur Douillard, Qixuan Feng, Andrei A Rusu, Rachita Chhaparia, Yani Donchev, Adhiguna Kuncoro, Marc’Aurelio Ranzato, Arthur Szlam, and Jiajun Shen. Diloco: Distributed low- communication training of language models.arXiv preprint arXiv:2311.08105, 2023.(Cited on pages 2, 3, and 5)

    Pith/arXiv arXiv 2023

  4. [5]

    Imagenet classification with deep convolutional neural networks.Advances in neural information processing systems, 25, 2012

    Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks.Advances in neural information processing systems, 25, 2012. (Cited on page 2)

    2012

  5. [6]

    Federated learning of deep networks using model averaging.arXiv preprint arXiv:1602.05629, 2016

    H Brendan McMahan, Eider Moore, Daniel Ramage, and Blaise Agüera y Arcas. Federated learning of deep networks using model averaging.arXiv preprint arXiv:1602.05629, 2016. (Cited on page 2)

    Pith/arXiv arXiv 2016

  6. [7]

    Graph oracle models, lower bounds, and gaps for parallel stochastic optimization.Advances in neural information processing systems, 31, 2018.(Cited on pages 2 and 3)

    Blake E Woodworth, Jialei Wang, Adam Smith, Brendan McMahan, and Nati Srebro. Graph oracle models, lower bounds, and gaps for parallel stochastic optimization.Advances in neural information processing systems, 31, 2018.(Cited on pages 2 and 3)

    2018

  7. [8]

    Advances and open problems in federated learning

    Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. corr.arXiv preprint arXiv:1912.04977, 2019.(Cited on page 2)

    Pith/arXiv arXiv 1912

  8. [9]

    A field guide to federated optimization.arXiv preprint arXiv:2107.06917, 2021.(Cited on page 2)

    Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H Brendan McMahan, Maruan Al- Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, et al. A field guide to federated optimization.arXiv preprint arXiv:2107.06917, 2021.(Cited on page 2)

    Pith/arXiv arXiv 2021

  9. [10]

    Scaffold: Stochastic controlled averaging for federated learning

    Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pages 5132–5143. PMLR, 2020.(Cited on pages 2, 3, 5, and 7)

    2020

  10. [11]

    A stochastic newton algorithm for distributed convex optimization.Advances in Neural Informa- tion Processing Systems, 34, 2021.(Cited on page 2)

    Brian Bullins, Kumar Kshitij Patel, Ohad Shamir, Nathan Srebro, and Blake E Woodworth. A stochastic newton algorithm for distributed convex optimization.Advances in Neural Informa- tion Processing Systems, 34, 2021.(Cited on page 2)

    2021

  11. [12]

    To- wards optimal communication complexity in distributed non-convex optimization

    Kumar Kshitij Patel, Lingxiao Wang, Blake Woodworth, Brian Bullins, and Nathan Srebro. To- wards optimal communication complexity in distributed non-convex optimization. InAdvances in Neural Information Processing Systems, 2022.(Cited on pages 2, 3, 5, 8, 11, and 34)

    2022

  12. [13]

    Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally! InInternational Conference on Machine Learning, pages 15750–15769

    Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik. Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally! InInternational Conference on Machine Learning, pages 15750–15769. PMLR, 2022.(Cited on pages 2 and 3)

    2022

  13. [14]

    Fedsplit: An algorithmic framework for fast federated optimization.Advances in neural information processing systems, 33:7057–7066, 2020.(Cited on page 2) 59

    Reese Pathak and Martin J Wainwright. Fedsplit: An algorithmic framework for fast federated optimization.Advances in neural information processing systems, 33:7057–7066, 2020.(Cited on page 2) 59

    2020

  14. [15]

    Efficient large-scale distributed training of conditional maximum entropy models.Advances in neural information processing systems, 22, 2009.(Cited on pages 2 and 3)

    Ryan Mcdonald, Mehryar Mohri, Nathan Silberman, Dan Walker, and Gideon Mann. Efficient large-scale distributed training of conditional maximum entropy models.Advances in neural information processing systems, 22, 2009.(Cited on pages 2 and 3)

    2009

  15. [16]

    Optimal distributed online prediction using mini-batches.Journal of Machine Learning Research, 13(1), 2012.(Cited on page 2)

    Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao. Optimal distributed online prediction using mini-batches.Journal of Machine Learning Research, 13(1), 2012.(Cited on page 2)

    2012

  16. [17]

    Local sgd converges fast and communicates little.arXiv preprint arXiv:1805.09767, 2018.(Cited on pages 2, 3, 6, and 9)

    Sebastian U Stich. Local sgd converges fast and communicates little.arXiv preprint arXiv:1805.09767, 2018.(Cited on pages 2, 3, 6, and 9)

    Pith/arXiv arXiv 2018

  17. [18]

    Is local sgd better than minibatch sgd? In International Conference on Machine Learning, pages 10334–10343

    Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mcmahan, Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? In International Conference on Machine Learning, pages 10334–10343. PMLR, 2020.(Cited on pages 2, 3, 6, 7, 9, 10, 11, 19, 20, 28, and 34)

    2020

  18. [19]

    Communication-efficient distributed optimization using an approximate newton-type method

    Ohad Shamir, Nati Srebro, and Tong Zhang. Communication-efficient distributed optimization using an approximate newton-type method. InInternational conference on machine learning, pages 1000–1008. PMLR, 2014.(Cited on pages 3 and 8)

    2014

  19. [20]

    Distributed optimization based on gradient tracking revisited: Enhancing convergence rate via surrogation

    Ying Sun, Gesualdo Scutari, and Amir Daneshmand. Distributed optimization based on gradient tracking revisited: Enhancing convergence rate via surrogation. InSIAM Journal on Optimization, 2022.(Cited on pages 3 and 8)

    2022

  20. [21]

    Optimal gradient sliding and its application to optimal distributed optimization under similarity

    Dmitry Kovalev, Aleksandr Beznosikov, Ekaterina Dmitrievna Borodich, Alexander Gasnikov, and Gesualdo Scutari. Optimal gradient sliding and its application to optimal distributed optimization under similarity. InAdvances in Neural Information Processing Systems, 2022. (Cited on pages 3 and 8)

    2022

  21. [22]

    Mime: Mimicking centralized stochastic algorithms in federated learning.arXiv preprint arXiv:2008.03606, 2020.(Cited on page 3)

    Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank J Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning.arXiv preprint arXiv:2008.03606, 2020.(Cited on page 3)

    Pith/arXiv arXiv 2008

  22. [23]

    Bias-variance reduced local sgd for less heterogeneous federated learning.arXiv preprint arXiv:2102.03198, 2021.(Cited on pages 3 and 5)

    Tomoya Murata and Taiji Suzuki. Bias-variance reduced local sgd for less heterogeneous federated learning.arXiv preprint arXiv:2102.03198, 2021.(Cited on pages 3 and 5)

    Pith/arXiv arXiv 2021

  23. [24]

    Federated optimization with doubly regularized drift correction

    Xiaowen Jiang, Anton Rodomanov, and Sebastian U Stich. Federated optimization with doubly regularized drift correction. InProceedings of the 41st International Conference on Machine Learning, volume 235 ofProceedings of Machine Learning Research, pages 21912–21945. PMLR, 21–27 Jul 2024.(Cited on pages 3 and 8)

    2024

  24. [25]

    Stabilized proximal-point methods for federated optimization

    Xiaowen Jiang, Anton Rodomanov, and Sebastian U Stich. Stabilized proximal-point methods for federated optimization. InThe Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.(Cited on pages 3 and 8)

    2024

  25. [26]

    The limits and potentials of local sgd for distributed heterogeneous learning with intermittent communication

    Kumar Kshitij Patel, Margalit Glasgow, Ali Zindari, Lingxiao Wang, Sebastian U Stich, Ziheng Cheng, Nirmit Joshi, and Nathan Srebro. The limits and potentials of local sgd for distributed heterogeneous learning with intermittent communication. InThe Thirty Seventh Annual Confer- ence on Learning Theory, pages 4115–4157. PMLR, 2024.(Cited on pages 3, 5, 6,...

    2024

  26. [27]

    Parallelized stochastic gradient descent.Advances in neural information processing systems, 23, 2010.(Cited on page 3)

    Martin Zinkevich, Markus Weimer, Lihong Li, and Alex Smola. Parallelized stochastic gradient descent.Advances in neural information processing systems, 23, 2010.(Cited on page 3)

    2010

  27. [28]

    Parallel sgd: When does averaging help?arXiv preprint arXiv:1606.07365, 2016.(Cited on page 3)

    Jian Zhang, Christopher De Sa, Ioannis Mitliagkas, and Christopher Ré. Parallel sgd: When does averaging help?arXiv preprint arXiv:1606.07365, 2016.(Cited on page 3)

    Pith/arXiv arXiv 2016

  28. [29]

    Communication trade-offs for local-sgd with large step size.Advances in Neural Information Processing Systems, 32, 2019.(Cited on page 3)

    Aymeric Dieuleveut and Kumar Kshitij Patel. Communication trade-offs for local-sgd with large step size.Advances in Neural Information Processing Systems, 32, 2019.(Cited on page 3)

    2019

  29. [30]

    Tighter theory for local sgd on identical and heterogeneous data

    Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identical and heterogeneous data. InInternational Conference on Artificial Intelligence and Statistics, pages 4519–4529. PMLR, 2020.(Cited on pages 3 and 7) 60

    2020

  30. [31]

    A unified theory of decentralized sgd with changing topology and local updates

    Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. InInternational Conference on Machine Learning, pages 5381–5393. PMLR, 2020.(Cited on pages 3, 6, 7, 12, 13, 16, 49, and 50)

    2020

  31. [32]

    Blake E Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch vs local sgd for heteroge- neous distributed learning.Advances in Neural Information Processing Systems, 33:6281–6292, 2020.(Cited on pages 3, 5, 6, 7, 9, 10, 11, 16, 18, 19, 21, 30, 33, and 34)

    2020

  32. [33]

    Federated accelerated stochastic gradient descent.Advances in Neural Information Processing Systems, 33:5332–5344, 2020.(Cited on page 3)

    Honglin Yuan and Tengyu Ma. Federated accelerated stochastic gradient descent.Advances in Neural Information Processing Systems, 33:5332–5344, 2020.(Cited on page 3)

    2020

  33. [34]

    The min-max complexity of distributed stochastic convex optimization with intermittent communication

    Blake E Woodworth, Brian Bullins, Ohad Shamir, and Nathan Srebro. The min-max complexity of distributed stochastic convex optimization with intermittent communication. InConference on Learning Theory, pages 4386–4437. PMLR, 2021.(Cited on pages 3, 7, and 20)

    2021

  34. [35]

    The minimax complexity of distributed optimization.arXiv preprint arXiv:2109.00534, 2021.(Cited on pages 3 and 34)

    Blake Woodworth. The minimax complexity of distributed optimization.arXiv preprint arXiv:2109.00534, 2021.(Cited on pages 3 and 34)

    Pith/arXiv arXiv 2021

  35. [36]

    Sharp bounds for federated averaging (local sgd) and continuous perspective

    Margalit R Glasgow, Honglin Yuan, and Tengyu Ma. Sharp bounds for federated averaging (local sgd) and continuous perspective. InInternational Conference on Artificial Intelligence and Statistics, pages 9050–9090. PMLR, 2022.(Cited on pages 3, 6, 7, 11, 12, 13, and 34)

    2022

  36. [37]

    On the unreasonable effectiveness of federated averaging with heterogeneous data.arXiv preprint arXiv:2206.04723, 2022.(Cited on page 3)

    Jianyu Wang, Rudrajit Das, Gauri Joshi, Satyen Kale, Zheng Xu, and Tong Zhang. On the unreasonable effectiveness of federated averaging with heterogeneous data.arXiv preprint arXiv:2206.04723, 2022.(Cited on page 3)

    Pith/arXiv arXiv 2022

  37. [38]

    Federated online and bandit convex optimization

    Kumar Kshitij Patel, Lingxiao Wang, Aadirupa Saha, and Nathan Srebro. Federated online and bandit convex optimization. InInternational Conference on Machine Learning, pages 27439–27460. PMLR, 2023.(Cited on page 3)

    2023

  38. [39]

    On the still unreasonable effectiveness of federated averaging for heterogeneous distributed learning

    Kumar Kshitij Patel, Margalit Glasgow, Lingxiao Wang, Nirmit Joshi, and Nathan Srebro. On the still unreasonable effectiveness of federated averaging for heterogeneous distributed learning. InFederated Learning and Analytics in Practice: Algorithms, Systems, Applications, and Opportunities, 2023.(Cited on pages 3 and 34)

    2023

  39. [40]

    Refined analysis of constant step size federated averaging and federated richardson- romberg extrapolation

    Paul Mangold, Alain Oliviero Durmus, Aymeric Dieuleveut, Sergey Samsonov, and Eric Moulines. Refined analysis of constant step size federated averaging and federated richardson- romberg extrapolation. InProceedings of The 28th International Conference on Artificial Intelligence and Statistics, volume 258, pages 5023–5031, 2025.(Cited on page 3)

    2025

  40. [41]

    What makes local updates effective: The role of data heterogeneity and smoothness.arXiv preprint arXiv:2507.00195, 2025.(Cited on pages 3 and 34)

    Kumar Kshitij Patel. What makes local updates effective: The role of data heterogeneity and smoothness.arXiv preprint arXiv:2507.00195, 2025.(Cited on pages 3 and 34)

    Pith/arXiv arXiv 2025

  41. [42]

    Revisiting localsgd and scaffold: Improved rates and missing analysis.arXiv preprint arXiv:2501.04443, 2025.(Cited on pages 3, 6, 7, 9, 11, 16, 18, 19, 21, and 22)

    Ruichen Luo, Sebastian U Stich, Samuel Horvath, and Martin Takac. Revisiting localsgd and scaffold: Improved rates and missing analysis.arXiv preprint arXiv:2501.04443, 2025.(Cited on pages 3, 6, 7, 9, 11, 16, 18, 19, 21, and 22)

    Pith/arXiv arXiv 2025

  42. [43]

    Understanding outer optimizers in local sgd: Learning rates, momentum, and acceleration

    Ahmed Khaled, Satyen Kale, Arthur Douillard, Chi Jin, Rob Fergus, and Manzil Zaheer. Understanding outer optimizers in local sgd: Learning rates, momentum, and acceleration. arXiv preprint arXiv:2509.10439, 2025.(Cited on page 3)

    arXiv 2025

  43. [44]

    Communication-efficient language model training scales reliably and robustly: Scaling laws for diloco.arXiv preprint arXiv:2503.09799, 2025.(Cited on pages 3 and 5)

    Zachary Charles, Gabriel Teston, Lucio Dery, Keith Rush, Nova Fallen, Zachary Garrett, Arthur Szlam, and Arthur Douillard. Communication-efficient language model training scales reliably and robustly: Scaling laws for diloco.arXiv preprint arXiv:2503.09799, 2025.(Cited on pages 3 and 5)

    Pith/arXiv arXiv 2025

  44. [45]

    Muloco: Muon is a practical inner optimizer for diloco.arXiv preprint arXiv:2505.23725, 2025.(Cited on page 3)

    Benjamin Thérien, Xiaolong Huang, Aaron Defazio, Irina Rish, and Eugene Belilovsky. Muloco: Muon is a practical inner optimizer for diloco.arXiv preprint arXiv:2505.23725, 2025.(Cited on page 3)

    Pith/arXiv arXiv 2025

  45. [46]

    Sparsified sgd with memory

    Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. In Proceedings of Advances in Neural Information Processing Systems, 2018.(Cited on page 3) 61

    2018

  46. [47]

    Error feedback fixes signsgd and other gradient compression schemes

    Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. InProceedings of the 36th International Conference on Machine Learning (ICML 2019), 2019.(Cited on page 3)

    2019

  47. [48]

    EControl: Fast distributed optimization with compression and error control

    Yuan Gao, Rustem Islamov, and Sebastian U Stich. EControl: Fast distributed optimization with compression and error control. InThe Twelfth International Conference on Learning Representations, 2024.(Cited on page 3)

    2024

  48. [49]

    Federated learning with partial model personalization

    Krishna Pillutla, Kshitiz Malik, Abdel-Rahman Mohamed, Mike Rabbat, Maziar Sanjabi, and Lin Xiao. Federated learning with partial model personalization. InInternational Conference on Machine Learning, pages 17716–17758, 2022.(Cited on page 3)

    2022

  49. [50]

    Partially personalized federated learning: Breaking the curse of data heterogeneity.Transactions on Machine Learning Research, 2025

    Konstantin Mishchenko, Rustem Islamov, Eduard Gorbunov, and Samuel Horváth. Partially personalized federated learning: Breaking the curse of data heterogeneity.Transactions on Machine Learning Research, 2025. URL https://openreview.net/forum?id= 8tMMCf4YYn.(Cited on page 3)

    2025

  50. [51]

    The convergence of sparsified gradient methods

    Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. InProceedings of Advances in Neural Information Processing Systems, 2018.(Cited on page 3)

    2018

  51. [52]

    On maintaining linear con- vergence of distributed learning and optimization under limited communication

    Sindri Magnússon, Hossein Shokri-Ghadikolaei, and Na Li. On maintaining linear con- vergence of distributed learning and optimization under limited communication. In2019 53rd Asilomar Conference on Signals, Systems, and Computers, pages 432–436, 2019. doi: 10.1109/IEEECONF44664.2019.9049052.(Cited on page 3)

    arXiv 2019

  52. [53]

    Communication-computation efficient gradient coding

    Min Ye and Emmanuel Abbe. Communication-computation efficient gradient coding. In Jennifer Dy and Andreas Krause, editors,Proceedings of the 35th International Conference on Machine Learning, volume 80 ofProceedings of Machine Learning Research, pages 5610–5619. PMLR, 10–15 Jul 2018. URL https://proceedings.mlr.press/v80/ye18a.html.(Cited on page 3)

    2018

  53. [54]

    The error-feedback framework: Better rates for sgd with delayed gradients and compressed updates.Journal of Machine Learning Research, 2020.(Cited on page 3)

    Sebastian U Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for sgd with delayed gradients and compressed updates.Journal of Machine Learning Research, 2020.(Cited on page 3)

    2020

  54. [55]

    Asgrad: A sharp unified analysis of asynchronous-sgd algorithms

    Rustem Islamov, Mher Safaryan, and Dan Alistarh. Asgrad: A sharp unified analysis of asynchronous-sgd algorithms. InInternational Conference on Artificial Intelligence and Statis- tics, pages 649–657. PMLR, 2024.(Cited on page 3)

    2024

  55. [56]

    Federated learning with differential privacy: Algorithms and performance analysis.IEEE transactions on information forensics and security, 15:3454–3469, 2020.(Cited on page 3)

    Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and H Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis.IEEE transactions on information forensics and security, 15:3454–3469, 2020.(Cited on page 3)

    2020

  56. [57]

    Shuffled model of differential privacy in federated learning

    Antonious Girgis, Deepesh Data, Suhas Diggavi, Peter Kairouz, and Ananda Theertha Suresh. Shuffled model of differential privacy in federated learning. InInternational Conference on Artificial Intelligence and Statistics, pages 2521–2529. PMLR, 2021.(Cited on page 3)

    2021

  57. [58]

    Private non-convex federated learning without a trusted server

    Andrew Lowy, Ali Ghafelebashi, and Meisam Razaviyayn. Private non-convex federated learning without a trusted server. InInternational Conference on Artificial Intelligence and Statistics, pages 5749–5786. PMLR, 2023.(Cited on page 3)

    2023

  58. [59]

    Diff2: Differential private optimization via gradient differ- ences for nonconvex distributed learning

    Tomoya Murata and Taiji Suzuki. Diff2: Differential private optimization via gradient differ- ences for nonconvex distributed learning. InInternational Conference on Machine Learning, pages 25523–25548. PMLR, 2023.(Cited on page 3)

    2023

  59. [60]

    Efficient private federated non-convex optimization with shuffled model

    Lingxiao Wang, Xingyu Zhou, Kumar Kshitij Patel, Lawrence Tang, and Aadirupa Saha. Efficient private federated non-convex optimization with shuffled model. InPrivacy Regulation and Protection in Machine Learning, 2024.(Cited on pages 3 and 5)

    2024

  60. [61]

    Double momentum and error feedback for clipping with fast rates and differential privacy.arXiv preprint arXiv:2502.11682, 2025.(Cited on page 3) 62

    Rustem Islamov, Samuel Horvath, Aurelien Lucchi, Peter Richtarik, and Eduard Gorbunov. Double momentum and error feedback for clipping with fast rates and differential privacy.arXiv preprint arXiv:2502.11682, 2025.(Cited on page 3) 62

    arXiv 2025

  61. [62]

    Smoothed normalization for efficient dis- tributed private optimization.arXiv preprint arXiv:2502.13482, 2025.(Cited on page 3)

    Egor Shulgin, Sarit Khirirat, and Peter Richtárik. Smoothed normalization for efficient dis- tributed private optimization.arXiv preprint arXiv:2502.13482, 2025.(Cited on page 3)

    Pith/arXiv arXiv 2025

  62. [63]

    Byzantine stochastic gradient descent.Advances in neural information processing systems, 31, 2018.(Cited on page 3)

    Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li. Byzantine stochastic gradient descent.Advances in neural information processing systems, 31, 2018.(Cited on page 3)

    2018

  63. [64]

    Learning from history for byzantine robust optimization

    Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Learning from history for byzantine robust optimization. InInternational conference on machine learning, pages 5311–5319. PMLR, 2021. (Cited on page 3)

    2021

  64. [65]

    Byzantine-robust and differentially private federated optimization under weaker assumptions

    Rustem Islamov, Grigory Malinovsky, Alexander Gaponov, Aurelien Lucchi, Peter Richtárik, and Eduard Gorbunov. Byzantine-robust and differentially private federated optimization under weaker assumptions. InThe 42nd Conference on Uncertainty in Artificial Intelligence, 2026. (Cited on page 3)

    2026

  65. [66]

    On the outsized importance of learning rates in local update methods.arXiv preprint arXiv:2007.00878, 2020.(Cited on page 5)

    Zachary Charles and Jakub Konecny. On the outsized importance of learning rates in local update methods.arXiv preprint arXiv:2007.00878, 2020.(Cited on page 5)

    Pith/arXiv arXiv 2007

  66. [67]

    Don’t use large mini-batches, use local sgd.arXiv preprint arXiv:1808.07217, 2018.(Cited on page 5)

    Tao Lin, Sebastian U Stich, Kumar Kshitij Patel, and Martin Jaggi. Don’t use large mini-batches, use local sgd.arXiv preprint arXiv:1808.07217, 2018.(Cited on page 5)

    Pith/arXiv arXiv 2018

  67. [68]

    Accurate, large minibatch sgd: Training imagenet in 1 hour.arXiv preprint arXiv:1706.02677, 2017.(Cited on page 5)

    Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in 1 hour.arXiv preprint arXiv:1706.02677, 2017.(Cited on page 5)

    Pith/arXiv arXiv 2017

  68. [69]

    Collaborative pac learning

    Avrim Blum, Nika Haghtalab, Ariel D Procaccia, and Mingda Qiao. Collaborative pac learning. Advances in Neural Information Processing Systems, 30, 2017.(Cited on page 7)

    2017

  69. [70]

    On the effect of defections in federated learning and how to prevent them.arXiv preprint arXiv:2311.16459, 2023.(Cited on page 7)

    Minbiao Han, Kumar Kshitij Patel, Han Shao, and Lingxiao Wang. On the effect of defections in federated learning and how to prevent them.arXiv preprint arXiv:2311.16459, 2023.(Cited on page 7)

    Pith/arXiv arXiv 2023

  70. [71]

    Fedchain: Chained algorithms for near-optimal communication cost in federated learning.arXiv preprint arXiv:2108.06869, 2021.(Cited on page 13)

    Charlie Hou, Kiran K Thekumparampil, Giulia Fanti, and Sewoong Oh. Fedchain: Chained algorithms for near-optimal communication cost in federated learning.arXiv preprint arXiv:2108.06869, 2021.(Cited on page 13)

    Pith/arXiv arXiv 2021

  71. [72]

    Quelques propriétés des opérateurs angle-bornés et n-cycliquement monotones.Israel Journal of Mathematics, 26(2):137–150, 1977.(Cited on page 19)

    Jean-Bernard Baillon and Georges Haddad. Quelques propriétés des opérateurs angle-bornés et n-cycliquement monotones.Israel Journal of Mathematics, 26(2):137–150, 1977.(Cited on page 19)

    1977

  72. [73]

    The baillon-haddad theorem revisited.arXiv preprint arXiv:0906.0807, 2009.(Cited on page 19) 63

    Heinz H Bauschke and Patrick L Combettes. The baillon-haddad theorem revisited.arXiv preprint arXiv:0906.0807, 2009.(Cited on page 19) 63

    Pith/arXiv arXiv 2009