Pith. sign in

REVIEW 4 major objections 4 minor 44 references

Pipelined Gradient Coding

T0 review · 4 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read The paper proposes pipelined gradient coding, which splits each worker's gradient evaluations across steps so distributed training tolerates s stragglers while computing one partition per worker per step, and proves geometric convergence fo

desk verdict The pipelining idea is genuinely useful and the experiments look credible, but the convergence proofs have load-bearing gaps: Lemma 1 and Lemma 3/Theorem 2 conflate an unbiased estimator with its mean, so the stated rates are not proven. read the letter →

arxiv 2607.20739 v1 pith:PT5SFUUM submitted 2026-07-22 cs.IT cs.LGmath.IT

Xian Su , Jun Li This is my paper
classification cs.ITcs.LGmath.IT MSC 68M1468W4090C25
keywords pipelinedgradientcodingstragglermitigationdistributeddescentstalegradientsfractionalrepetitioncycliccodedcomputationconvergenceanalysis
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Gradient coding gives distributed training a hard choice: either wait for stragglers, or have every worker compute c=s+1 dataset partitions per step and pay a c-fold cost that usually outweighs the savings. This paper argues the choice is false. By pipelining—each worker evaluates one partition per step, keeps its previous c−1 gradients, and combines them into a coded gradient—the same straggler tolerance is achieved at DGD-level per-step computation. The paper proves geometric convergence for both fractional-repetition and cyclic-repetition placements, and shows empirically that PGC cuts both wall-clock time and steps to target loss. The cyclic variant needs special care because naive decoding coefficients amplify stale-gradient errors; the proposed design keeps every partition's effective coefficient bounded by 2.

What carries the argument

The central mechanism is the rotating stale-gradient cache. Each worker cyclically evaluates its c assigned dataset partitions one per step, stores the most recent gradient of each, and forms a coded gradient from the fresh value plus c−1 stale values; the master waits only for the n−s fastest workers and decodes as in standard gradient coding. For CR, the key identity is that summing all workers' coded gradients reproduces each partition's gradient once per holder, and because each worker is equally likely to be among the received n−s, the normalized received sum is unbiased for the averaged stale-gradient sum. This, together with the bounded-coefficient design (each partition contributes l

What would settle it

For a simple quadratic objective with n = c = 2, compute the covariance between the gradients evaluated on the same dataset partition at two consecutive iterates; Lemma 4 predicts it vanishes because the copies are independent. If that covariance is non-negligible, the (nc+ξ) bound and the CR contraction rate do not follow from the stated assumptions.

Watch

Extended reading notes

Core claim

On its own terms, the paper claims that a stale-gradient pipeline is enough to make gradient coding efficient: the coded gradient at step t is, in expectation over the straggler pattern, an average of per-partition gradients evaluated at recent iterates, with staleness bounded by pipeline depth c. Under strong convexity, Lipschitz gradients, and bounded gradient variance, the training error contracts geometrically, with rates 1 − λ(1−γ)/(nL(n+ξ)) for FR and 1 − λ(1−γ)/(L(nc+ξ)) for CR. For CR, exact decoding is deliberately relaxed to a weighted sum whose expected coefficient per partition is 1 and whose per-partition weight never exceeds 2, so the error amplification of naive CR decoding (c

Load-bearing premise

The load-bearing premise is that all stored gradients—including the c copies of the same dataset partition computed at different model states—are conditionally independent unbiased estimates, so their cross terms vanish in the norm bound; those copies share data and a correlated model trajectory, so this independence is not automatic.

Editorial extensions

If this is right

  • For a fixed straggler tolerance s = c−1, PGC cuts per-step computation from c partitions to 1, so per-step wall-clock time stays near DGD regardless of s.
  • Because the coding is applied to gradients rather than to the data or model, PGC extends to any iterative gradient-based training procedure, not just linear operations.
  • The convergence theorems put PGC on the same theoretical footing as gradient coding: both achieve geometric contraction under standard convexity and smoothness assumptions, with PGC preserving the rate structure while reducing compute.
  • The empirical results indicate that replacing current gradients with mildly stale ones can speed convergence, and mixing stale gradients from different workers (CR) converges faster than using a single stale copy per partition (FR).
  • PGC remains compatible with the existing FR and CR dataset placements, so it can be dropped into systems already using gradient coding without changing the data layout.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the independence assumption in Lemma 4 is relaxed, the CR convergence guarantee may still hold but with a larger variance term: the c copies of the same partition are computed on identical data at nearby iterates, and their errors are likely positively correlated, which would inflate the cross terms rather than cancel them.
  • The bounded-coefficient property (every partition contributes less than twice its intended weight) suggests PGC-CR's robustness may extend beyond i.i.d. exponential straggler delays to heterogeneous or adversarial delay patterns, since the stale-error amplification depends only on coefficient magnitudes.
  • The observed convergence speed-up from mixing stale gradients hints that pipeline depth c and the rotation order could be tuned as a form of implicit variance reduction or regularization, independent of straggler protection.
  • The single warm-up step that evaluates all c partitions could be avoided by initializing the cache from one partition per step over the first c steps, at the cost of slightly higher initial staleness.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 4 minor

Summary. The paper proposes Pipelined Gradient Coding (PGC), a variant of gradient coding in which each worker evaluates gradients on only one dataset partition per step and forms a coded gradient from the fresh gradient plus c−1 stale gradients retained from previous steps. Two instantiations are given: PGC-FR (fractional repetition) and PGC-CR (cyclic repetition). The manuscript claims geometric convergence for both variants (Theorems 1 and 2), asserts that PGC matches DGD's per-step computational load while retaining GC's straggler tolerance, and supports this with simulations and cloud experiments on ResNet-18/CIFAR-10 and ImageNet. The central theoretical claim is that stale gradients introduce only a bounded bias controlled by constants γ, ξ ∈ [0,1), so that PGC converges at a rate comparable to GC.

Significance. If the convergence theorems were correct, PGC would be a meaningful contribution: it would remove the c-fold per-worker computation overhead of gradient coding while preserving straggler tolerance, and the empirical comparisons suggest real wall-clock gains. The paper has concrete strengths: the design motivation is clear, the observation that a naive CR pipelining amplifies staleness through large decoding coefficients is well illustrated (Section V-A, Fig. 6), and the cloud experiments control seeds and compare against several relevant baselines. However, the theoretical core is not sound. Lemma 1 is algebraically false as stated, Lemma 3 conflates the subset estimator with its full-sum average, and Lemma 4's independence claim is not justified by the stated assumptions. Because Theorems 1 and 2 rest directly on these lemmas, the paper's central guarantee is unsupported. The empirical findings may remain useful, but the manuscript in its current form cannot be accepted as a theory paper.

major comments (4)
  1. [Section IV-B, Lemma 1 and Appendix A] Lemma 1 is not derivable as written. The proof completes the square around the single reference gradient ∇F(β^{s(t,i)}) and asserts E[ĝ^{(t)} − ∇F(β^{s(t,i)})] = 0. But ĝ^{(t)} = (1/n)∑_{k=0}^{n-1} g_k^{s(t,k)}, so E[ĝ^{(t)}] = (1/n)∑_k ∇F(β^{s(t,k)}), which equals ∇F(β^{s(t,i)}) only when all staleness indices are equal. In general the cross term does not vanish, and the stated identity is false. Moreover, the lemma's RHS depends on an index i that does not appear on the LHS, so the statement is not even well-formed. Since Theorem 1's recursion uses Lemma 1, the geometric convergence claim for PGC-FR is not established.
  2. [Section V-C, Lemma 3 and Appendix F] Lemma 3 and its proof discard the variance due to randomly selecting the n−s responding workers. From E[ĝ^{(t)}] = ḡ^{(t)} one may write E‖∇̄^{(t)} − ĝ^{(t)}‖² = E‖ĝ^{(t)}‖² − E‖∇̄^{(t)}‖², but Appendix D instead writes E‖∇̄^{(t)} − ĝ^{(t)}‖² = E‖ḡ^{(t)}‖² − E‖∇̄^{(t)}‖². This is equivalent to E‖ĝ^{(t)}‖² = E‖ḡ^{(t)}‖², which is false because ĝ averages only the n−s received coded gradients while ḡ averages all n workers' coded gradients. A concrete counterexample with deterministic partition gradients (0,1,2), n=3, c=2, s=1 gives E‖ĝ‖² = 7/24 whereas ‖ḡ‖² = 1/4. The same conflation appears in Appendix F in the line E[‖ĝ^{(t)}‖²] = (1/(n²c²)) E[‖∑_{i,j} g_i^s‖²]; this identity holds for the full-sum average, not for the subset estimator. Theorem 2 relies on this second-moment bound, so its proof is invalid.
  3. [Section V-C, Lemma 4 and Appendix E] Lemma 4's proof asserts that cross terms vanish for any two distinct evaluations, including two holders of the same partition evaluated at different times, because each factor has zero conditional mean and the evaluations are independent. The assumption E[g_i^{(t)}] = ∇F(β^{(t)}) alone does not imply conditional independence of evaluations of the same data partition at different model iterates; the evaluation points are themselves random variables coupled through previous gradients. A valid proof would need to state explicitly that fresh independent mini-batches are drawn at every evaluation and then condition on the full trajectory. As written, the cross-term cancellation that produces the (nc+ξ) bound is unsupported.
  4. [Theorems 1 and 2 assumptions] Both theorems assume constants γ, ξ ∈ [0,1) with the staleness and gradient-noise bounds, but no derivation from c, η, or problem data is given. The text says γ 'is governed by c and η, vanishing as η→0' but provides no bound. Thus, even if the lemmas were correct, the stated geometric rates would not be a verifiable guarantee for a concrete problem; they would be conditional on unverified inequalities. This is a second, independent gap between the claims and the analysis.
minor comments (4)
  1. [Eq. (2)] The notation E in Eq. (2) is used for expectation over the straggler pattern only, with the realized gradients treated as fixed, while Lemma 3 uses E for the full expectation including gradient noise. This switch is a source of confusion and should be made explicit.
  2. [Fig. 3] The caption says 'Training time per step normalized by DGD' but the y-axis label reads 'loss'; either the caption or the axis is mislabeled. Similar label mismatches appear in the normalized bar charts of Figs. 7 and 10.
  3. [Experiments (Section VI)] The cloud experiment reports averages over 10 runs but no error bars or variance information. Given the natural variability of cloud stragglers, some measure of dispersion would materially support the claims that PGC is faster than the baselines.
  4. [References] References [12] and [14] appear to be duplicates, and reference [30] overlaps with [27] in content. Please consolidate.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: claims are conditional theorems plus empirical evaluation, not fits relabeled as predictions.

full rationale

The paper's central claims—geometric convergence of PGC-FR and PGC-CR, and reduced per-step computation—are not obtained from the quantities they predict. Theorems 1 and 2 are conditional: they assume bounds ξ,γ∈[0,1) and prove a contraction rate under those assumptions; neither ξ nor γ is fitted to the loss curves, so the convergence statements are not forced by the data. The design does make 'one partition per worker per step' true by construction, but that is a stated design property, not a disguised prediction. The only self-citations ([11], [39]) are a dissertation pointer and a baseline method; neither carries the proof. The proof of Lemma 3/Theorem 2 does contain a questionable substitution of E||ĝ||² with E||ḡ||² and Lemma 4 assumes independence of gradient copies on identical partitions, but these are correctness gaps in the derivation—the conclusion does not reduce to an input by definition, nor is a fitted parameter renamed as a prediction. Under the circularity standard (exhibit a specific reduction by construction or a load-bearing self-citation chain), no circular step is established.

Assumptions & free parameters 2 free parameters · 6 assumptions · 0 invented entities

The central convergence claims rest on unmeasured relative constants γ and ξ, and on an independence premise that is false for the c holders of a given partition. No new physical entities are introduced.

free parameters (2)
  • γ (relative staleness bias bound)
    Assumed in [0,1) in Theorems 1 and 2; it controls the contraction factor but is never derived from c, η, L, or measured. The paper asserts it vanishes as η→0 without a quantitative bound.
  • ξ (relative gradient-noise bound)
    Assumed in [0,1) in Lemmas 2 and 4; the relative variance bound is strong and unverified for deep-network gradients.
assumptions (6)
  • standard math F is λ-strongly convex and L-smooth
    Used in Theorems 1 and 2 to turn gradient-norm bounds into objective suboptimality contraction.
  • domain assumption Stochastic gradients are unbiased at their evaluation point: E[g_i]=∇F(β)
    Standard SGD assumption invoked in Lemmas 1 and 3.
  • domain assumption Gradient noise is bounded in relative norm: E[||g_i^s−∇F(β^s)||²]≤ξE[||∇F(β^s)||²]
    Assumed in Lemmas 2 and 4; not verified for the empirical models.
  • ad hoc to paper Staleness bias is bounded: E[||∇F(β^t)−∇F(β^s)||²]≤γE[||∇F(β^t)||²] (with analogous averaged bound for CR)
    The paper states staleness is bounded by pipeline depth, but γ is not derived from c, η, or L, and no measurement is offered. The convergence theorem needs γ<1.
  • ad hoc to paper Distinct evaluations, including same-partition copies, are independent so cross terms vanish
    Lemma 4/Appendix E cancels cross terms between all (i,j) pairs. Copies of the same partition are computed on identical data at different iterates and are not independent.
  • domain assumption Each worker is equally likely to be among the n−s fastest, so the CR estimator is unbiased over the straggler pattern
    Used in Eq. (2) to justify E[ĝ^t]=ḡ^t; reasonable under exchangeable delays but not stated as a formal condition in the experiments.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Pipelined Gradient Coding." pith.science (2026). https://pith.science/paper/PT5SFUUM

@misc{pith2026260720739,
  author       = {Pith},
  title        = {Pith review of: Pipelined Gradient Coding},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PT5SFUUM}},
  note         = {Machine review of arXiv:2607.20739}
}
read the original abstract

In large-scale machine learning, distributed training commonly involves multiple workers evaluating the gradients of the model on different dataset partitions. A common challenge is the presence of straggling workers, which may significantly slow down training. Traditional gradient coding (GC) addresses this by duplicating dataset partitions across workers, allowing for the replacement of missing gradients from stragglers. However, GC requires workers to evaluate gradients on multiple dataset partitions in each step, potentially increasing overall training time. In this paper, we propose to pipeline GC, such that gradient evaluation is segmented across multiple steps and each worker evaluates gradients on just a single dataset partition per step. We develop the pipelined version for fractional repetition (FR) and cyclic repetition (CR), two representative dataset placement schemes in GC, and prove convergence guarantees for both. Through extensive simulations and experiments on cloud infrastructure, our schemes not only significantly reduce training time but also accelerate convergence compared to GC and other baselines.

Figures

Figures reproduced from arXiv: 2607.20739 by the authors.

Figure 1
Figure 1. A comparison between distributed gradient descent and [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Illustrative examples of FR and CR, both with [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. Training time per step normalized by DGD when [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: A comparison between gradient coding and pipelined [PITH_FULL_IMAGE:figures/full_fig_p003_4.png]
Figure 5
Figure 5. Figure 5: The naïve PGC-CR construction for n = 4, c = 2. V. PIPELINED GRADIENT CODING WITH CYCLIC REPETITION A. Motivation Similar to PGC-FR, our initial attempt to build PGC-CR was to directly apply the pipelining principle to CR using the coding scheme from GC. This attempt, …
Figure 6
Figure 6. Figure 6: Training with PGC-FR and PGC-CR for n = 12, c = 6. The right axis shows the maximum and minimum decoding coefficients αm,k of the naïve PGC-CR design. consistent with the estimator analyzed in Theorem 2. This design also ensures 0 ≤ 1 µ |N (t) k | < 2. The lower bound …
Figure 7
Figure 7. Figure 7: Time per step when training ResNet-18 on ImageNet, [PITH_FULL_IMAGE:figures/full_fig_p006_7.png]
Figure 10
Figure 10. Figure 10: Time consumption training ResNet-18 on CIFAR-10, [PITH_FULL_IMAGE:figures/full_fig_p007_10.png]
Figure 8
Figure 8. Figure 8: Training loss over steps for ResNet-18 on ImageNet [PITH_FULL_IMAGE:figures/full_fig_p007_8.png]
Figure 9
Figure 9. Figure 9: Loss reduction over time when training ResNet-18 on [PITH_FULL_IMAGE:figures/full_fig_p007_9.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

44 extracted references · 5 linked inside Pith

  1. [1]

    Large scale distributed deep networks,

    J. Dean, G. Corrado, R. Monga, K. Chen, M. Devin, M. Mao, M. Ran- zato, A. Senior, P. Tucker, K. Yanget al., “Large scale distributed deep networks,”Advances in neural information processing systems, vol. 25, 2012

    2012

  2. [2]

    Optimal Dis- tributed Online Prediction Using Mini-Batches,

    O. Dekel, R. Gilad-Bachrach, O. Shamir, and L. Xiao, “Optimal Dis- tributed Online Prediction Using Mini-Batches,”Journal of Machine Learning Research, vol. 13, no. 1, 2012

    2012

  3. [3]

    Parallelized stochastic gradient descent,

    M. Zinkevich, M. Weimer, L. Li, and A. Smola, “Parallelized stochastic gradient descent,”Advances in neural information processing systems, vol. 23, 2010

    2010

  4. [4]

    Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication,

    Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication,” Proceedings of the 31st International Conference on Neural Information Processing Systems (NIPS), 2017

    2017

  5. [5]

    Speeding Up Distributed Machine Learning Using Codes,

    K. Lee, M. Lam, R. Pedarsani, D. Papailiopoulos, and K. Ramchandran, “Speeding Up Distributed Machine Learning Using Codes,” inIEEE Transactions on Information Theory, vol. 64, no. 3, 2018, pp. 1514– 1529

    2018

  6. [6]

    Gradient Coding: Avoiding Stragglers in Distributed Learning,

    R. Tandon, Q. Lei, A. G. Dimakis, and N. Karampatziakis, “Gradient Coding: Avoiding Stragglers in Distributed Learning,” inProceedings of International Conference on Machine Learning (ICML), vol. 70, 2017, pp. 3368–3376

    2017

  7. [7]

    MapReduce: Simplified Data Processing on Large Clusters,

    J. Dean and S. Ghemawat, “MapReduce: Simplified Data Processing on Large Clusters,”Communications of the ACM, vol. 51, no. 1, pp. 107–113, 2008

    2008

  8. [8]

    The Tail at Scale,

    J. Dean and L. A. Barroso, “The Tail at Scale,”Communications of the ACM, vol. 56, no. 2, pp. 74–80, 2013

    2013

Show all 44 references
  1. [9]

    Communication effi- cient distributed machine learning with the parameter server,

    M. Li, D. G. Andersen, A. J. Smola, and K. Yu, “Communication effi- cient distributed machine learning with the parameter server,”Advances in Neural Information Processing Systems, vol. 27, 2014

    2014

  2. [10]

    Straggler-aware Distributed Learningw Communication–computation Latency Trade-off,

    E. Ozfatura, S. Ulukus, and D. Gündüz, “Straggler-aware Distributed Learningw Communication–computation Latency Trade-off,”Entropy, vol. 22, no. 5, p. 544, 2020

    2020

  3. [11]

    Speeding Up Coded Distributed Machine Learning,

    X. Su, “Speeding Up Coded Distributed Machine Learning,” Ph.D. dissertation, The Graduate Center, City University of New York, 2024

    2024

  4. [12]

    Using straggler replication to reduce latency in large-scale parallel computing,

    D. Wang, G. Joshi, and G. Wornell, “Using straggler replication to reduce latency in large-scale parallel computing,”ACM SIGMETRICS Performance Evaluation Review, vol. 43, no. 3, pp. 7–11, 2015

    2015

  5. [13]

    Efficient Straggler Replication in Large-scale Parallel Computing,

    D. Wang, G. Joshi, and G. W. Wornell, “Efficient Straggler Replication in Large-scale Parallel Computing,”ACM Transactions on Modeling and Performance Evaluation of Computing Systems (TOMPECS), vol. 4, no. 2, pp. 1–23, 2019

    2019

  6. [14]

    Using Straggler Replication to Reduce Latency in Large-scale Parallel Computing,

    D. Wang, G. Joshi, and G. Wornell, “Using Straggler Replication to Reduce Latency in Large-scale Parallel Computing,”ACM SIGMETRICS Performance Evaluation Review, vol. 43, no. 3, pp. 7–11, nov 2015

    2015

  7. [15]

    Improving speedup and response times by replicating parallel programs on a snow,

    G. D. Ghare and S. T. Leutenegger, “Improving speedup and response times by replicating parallel programs on a snow,” inWorkshop on Job Scheduling Strategies for Parallel Processing. Springer, 2004, pp. 264– 287

    2004

  8. [16]

    Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding,

    Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding,”IEEE Transactions on Information Theory, vol. 66, no. 3, pp. 1920–1933, 2020

    1920

  9. [17]

    ‘Short-Dot’: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products,

    S. Dutta, V . Cadambe, and P. Grover, “‘Short-Dot’: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products,” IEEE Transactions on Information Theory, vol. 65, no. 10, pp. 6171– 6193, 2019

    2019

  10. [18]

    Dual Entangled Polynomial Code: Three- Dimensional Coding for Distributed Matrix Multiplication,

    P. Soto, J. Li, and X. Fan, “Dual Entangled Polynomial Code: Three- Dimensional Coding for Distributed Matrix Multiplication,” inProceed- ings of the 36th International Conference on Machine Learning, 2019, pp. 5937–5945

    2019

  11. [19]

    Local re-encoding for coded matrix multiplication,

    X. Su, J. Parker, X. Zhong, X. Fan, and J. Li, “Local re-encoding for coded matrix multiplication,”IEEE Open Journal of the Communica- tions Society, vol. 3, pp. 1265–1279, 2022

    2022

  12. [20]

    Anytime coding for distributed com- putation,

    N. S. Ferdinand and S. C. Draper, “Anytime coding for distributed com- putation,” in2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE, 2016, pp. 954–960

    2016

  13. [21]

    Coded distributed computing for inverse problems,

    Y . Yang, P. Grover, and S. Kar, “Coded distributed computing for inverse problems,”Advances in Neural Information Processing Systems, vol. 30, 2017

    2017

  14. [22]

    Coded Distributed Computing with Partial Recovery,

    E. Ozfatura, S. Ulukus, and D. Gündüz, “Coded Distributed Computing with Partial Recovery,”IEEE Transactions on Information Theory, vol. 68, no. 3, pp. 1945–1959, 2021

    1945

  15. [23]

    Rateless codes for near-perfect load balancing in distributed matrix-vector multiplication,

    A. Mallick, M. Chaudhari, U. Sheth, G. Palanikumar, and G. Joshi, “Rateless codes for near-perfect load balancing in distributed matrix-vector multiplication,” inAbstracts of the 2020 SIGMET- RICS/Performance Joint International Conference on Measurement and Modeling of Comput...

    2020

  16. [24]

    Improving Dis- tributed Gradient Descent Using Reed-Solomon Codes,

    W. Halbawi, N. Azizan, F. Salehi, and B. Hassibi, “Improving Dis- tributed Gradient Descent Using Reed-Solomon Codes,” inProceedings of IEEE International Symposium on Information Theory (ISIT). Insti- tute of Electrical and Electronics Engineers Inc., 2018, pp. 2027–2031

    2018

  17. [25]

    Communication-computation Efficient Gradient Coding,

    M. Ye and E. Abbe, “Communication-computation Efficient Gradient Coding,” inProceedings of 35th International Conference on Machine Learning (ICML), 2018, pp. 5610–5619

    2018

  18. [26]

    Speeding up distributed gradient descent by utilizing non-persistent stragglers,

    E. Ozfatura, D. Gündüz, and S. Ulukus, “Speeding up distributed gradient descent by utilizing non-persistent stragglers,” in2019 IEEE International Symposium on Information Theory (ISIT). IEEE, 2019, pp. 2729–2733

    2019

  19. [27]

    Distributed Gradient Descent with Coded Partial Gradient Computations,

    E. Ozfatura, S. Ulukus, and D. Gunduz, “Distributed Gradient Descent with Coded Partial Gradient Computations,” inProceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), vol. 2019-May. Institute of Electrical and Electronics Engineers ...

    2019

  20. [28]

    Heterogeneity-aware Gradient Coding for Tolerating and Leveraging Stragglers,

    H. Wang, S. Guo, B. Tang, R. Li, Y . Yang, Z. Qu, and Y . Wang, “Heterogeneity-aware Gradient Coding for Tolerating and Leveraging Stragglers,”IEEE Transactions on Computers, 2021

    2021

  21. [29]

    Sequential Gradient Coding for Straggler Mitigation,

    M. N. Krishnan, M. Ebrahimi, and A. Khisti, “Sequential Gradient Coding for Straggler Mitigation,”arXiv preprint arXiv:2211.13802, 2022

    2022 arXiv

  22. [30]

    Distributed gradient descent with coded partial gradient computations,

    E. Ozfatura, S. Ulukus, and D. Gündüz, “Distributed gradient descent with coded partial gradient computations,” inICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2019, pp. 3492–3496

    2019

  23. [31]

    Slow and stale gradients can win the race: Error-runtime trade-offs in distributed sgd,

    S. Dutta, G. Joshi, S. Ghosh, P. Dube, and P. Nagpurkar, “Slow and stale gradients can win the race: Error-runtime trade-offs in distributed sgd,” inInternational conference on artificial intelligence and statistics. PMLR, 2018, pp. 803–812

    2018

  24. [32]

    Adaptive distributed stochastic gradient descent for minimizing delay in the presence of stragglers,

    S. K. Hanna, R. Bitar, P. Parag, V . Dasari, and S. El Rouayheb, “Adaptive distributed stochastic gradient descent for minimizing delay in the presence of stragglers,” inICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2...

    2020

  25. [33]

    Revisiting distributed synchronous sgd,

    J. Chen, X. Pan, R. Monga, S. Bengio, and R. Jozefowicz, “Revisiting distributed synchronous sgd,”arXiv preprint arXiv:1604.00981, 2016

    2016 arXiv

  26. [34]

    Fundamental Limits of Approximate Gradient Coding,

    S. Wang, J. Liu, and N. Shroff, “Fundamental Limits of Approximate Gradient Coding,”Proceedings of the ACM on Measurement and Anal- ysis of Computing Systems, vol. 3, no. 3, pp. 1–22, 2019

    2019

  27. [35]

    Approximate gradient coding via sparse random graphs,

    Z. Charles, D. Papailiopoulos, and J. Ellenberg, “Approximate gradient coding via sparse random graphs,”arXiv preprint arXiv:1711.06771, 2017

    2017 arXiv

  28. [36]

    Erasurehead: Distributed gradient descent without delays using approximate gradient coding,

    H. Wang, Z. Charles, and D. Papailiopoulos, “Erasurehead: Distributed gradient descent without delays using approximate gradient coding,” arXiv preprint arXiv:1901.09671, 2019

    1901 arXiv

  29. [37]

    Stochastic Gradient Coding for Straggler Mitigation in Distributed Learning,

    R. Bitar, M. Wootters, and S. E. Rouayheb, “Stochastic Gradient Coding for Straggler Mitigation in Distributed Learning,”IEEE Journal on Selected Areas in Information Theory, vol. 1, no. 1, pp. 277–291, 2020

    2020

  30. [38]

    Gradient Coding from Cyclic MDS Codes and Expander Graphs,

    N. Raviv, I. Tamo, R. Tandon, and A. G. Dimakis, “Gradient Coding from Cyclic MDS Codes and Expander Graphs,”IEEE Transactions on Information Theory, vol. 66, no. 12, pp. 7475–7489, 2020

    2020

  31. [39]

    On Arbitrary Ignorance of Stragglers with Gradient Coding,

    X. Su, B. Sukhnandan, and J. Li, “On Arbitrary Ignorance of Stragglers with Gradient Coding,” in2023 IEEE 43rd International Conference on Distributed Computing Systems (ICDCS), 2023

    2023

  32. [40]

    Deep residual learning for image recognition,

    K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” inProceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 770–778

    2016

  33. [41]

    Learning multiple layers of features from tiny images,

    A. Krizhevsky, “Learning multiple layers of features from tiny images,” 2009. [Online]. Available: https://www.cs.toronto.edu/~kriz/ learning-features-2009-TR.pdf

    2009

  34. [42]

    Anyscale - Ray Distributed Computing - Anyscale

    “Anyscale - Ray Distributed Computing - Anyscale.” [Online]. Available: https://www.anyscale.com/ray-open-source

  35. [43]

    A downsampled variant of imagenet as an alternative to the cifar datasets,

    P. Chrabaszcz, I. Loshchilov, and F. Hutter, “A downsampled variant of imagenet as an alternative to the cifar datasets,”arXiv preprint arXiv:1707.08819, 2017. APPENDIXA PROOF OFLEMMA1 Completing the square inE[||∇F(β (t))−ˆg(t)||2 2]by adding and subtracting∇F(β (s(t,i))), E[...

    2017 arXiv

  36. [44]

    Substitutingβ (t+1) =β (t)−ηˆg(t), applying the polarization identity, and taking expectations, E[F(β (t+1))]≤E[F(β (t))]− η 2 E[||∇F(β (t))||2 2] − η 2n P i E[||g(s(t,i)) i ||2 2] + η 2n P i E[||g(s(t,i)) i − ∇F(β(t))||2 2] + Lη2 2 E[||ˆg(t)||2 2]. Applying Lemma 1, the stale...

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.