Research map / Optimization / Distributed and compressed
Leveraging partial stragglers within gradient coding
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a gradient coding protocol that leverages partial work by slow workers via a small amount of PS-worker interaction, enabling communication-efficient exact and approximate gradient coding with numerical stability, plus a chunk-ordering algorithm for N=m regular assignments.
Problem
Gradient coding for distributed learning wastes the partial work of slow workers (partial stragglers), and existing communication-efficient exact GC relies on numerically unstable polynomial/Lagrange interpolation; approximate communication-efficient GC has hardly been studied.
Approach
Workers report processed-chunk counts to the PS, which broadcasts a state vector and an encode-and-transmit signal; each worker then independently solves a minimum-norm least-squares problem with a shared random matrix R to compute encoding coefficients for length d/ℓ messages, and a max-bipartite-matching based algorithm orders chunks within workers to minimize worst-case processed chunks Q_max.
Key results
- For exact gradient reconstruction the proposed protocol is roughly 2x faster than original gradient coding in simulation (N=m=200, delta=8, cyclic and graph-based assignments).
- For approximate reconstruction on random regular graph assignments (m=200, degree 8), the MSE is several orders of magnitude lower than original GC with ℓ=1 across T.
- Lagrange-interpolation-based exact GC is shown to be numerically unstable already at m around 22-32 with ℓ=2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| leverage work completed by partial stragglers | Partial-straggler GC · Exact GC, cyclic and G1 assignments | completion time: around 2× faster | Helped |
| leverage partial work and reconstruct approximate gradients | Partial-straggler GC · Approximate GC, G1 and G2 assignments | MSE: several orders of magnitude lower | Helped |
| use ℓ=2 or ℓ=3 instead of ℓ=1 (ablation) | Partial-straggler GC · Approximate GC, G1 and G2 assignments | MSE | Helped |
| use optimal chunk ordering instead of random ordering (ablation) | Partial-straggler GC · Approximate GC, G1 and G2 assignments, ℓ=1,2,3 | MSE: multiple orders of magnitude lower | Helped |
| use optimal chunk ordering instead of random ordering (ablation) | Partial-straggler GC · Exact GC, G1 assignment | completion time | Helped |
| use Lagrange interpolation for exact recovery | Original GC · Exact GC, ℓ=2 and m=22, 27, 32 | numerical error | Hurt |
Limitations
- Chunk-ordering algorithm is provably optimal only when N=m and all gamma_i=delta_i=delta; no optimal construction for ℓ>1.
- Evaluation is via simulation of the cluster, so communication-time reductions on real clusters are not measured.
- Requires extra interactive communication (count reports and broadcast) between workers and PS.
Experimental setup
Metrics: mean-squared error completion time
Baselines: original gradient coding (cyclic assignment) communication-efficient gradient coding with Lagrange interpolation random chunk ordering
Builds on: gradient coding communication-efficient gradient coding approximate gradient coding
Closest papers by meaning
- Approximate Gradient Coding for Distributed Learning with Heterogeneous Stragglers (NeurIPS 2025 · similarity 0.93)
- Gradient Coding: Avoiding Stragglers in Distributed Learning (ICML 2017 · similarity 0.93)
- Sequential Gradient Coding For Straggler Mitigation (ICLR 2023 · similarity 0.91)
- Gradient Coding from Cyclic MDS Codes and Expander Graphs (ICML 2018 · similarity 0.91)
- Coded Computing for Resilient Distributed Computing: A Learning-Theoretic Framework (NeurIPS 2024 · similarity 0.87)
- Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity (NeurIPS 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.