Research map / Optimization / Distributed and compressed
Approximate Gradient Coding for Distributed Learning with Heterogeneous Stragglers
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 an optimally structured approximate gradient coding scheme for heterogeneous stragglers that enforces unbiased gradient estimation while minimizing residual error, with closed-form data allocation (Schemes I and II) at computation load below 2.
Problem
Gradient coding for distributed learning under heterogeneous, non-uniform straggler probabilities, where prior approximate schemes assume homogeneous stragglers or require heavy data replication and may fail to converge.
Approach
Formulate a convex problem minimizing residual error subject to unbiasedness with per-worker straggler probabilities p_i, derive the optimal row-sum structure Y_i via Lagrangian duality, and construct sparse closed-form codes (Scheme I centralized shared partition, Scheme II chained sharing) with computation load d = 1 + (k-1)/n < 2.
Key results
- Proposed Scheme I and II converge faster than IS-SGD, BGC, EHD, OD and SGC on COCO object detection with k=10 workers and tau_th=1.1, closely matching centralized GD.
- Computation load of the proposed schemes is d = 1 + (k-1)/n, strictly below 2 for k <= n.
- Convergence bounds: O(1/T) for strongly convex losses with gamma_t = 1/(lambda t), error scaling with (1 + 1/sum delta_i^{-1}).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Proposed-I or Proposed-II instead of the benchmark gradient-coding methods | Distributed learning with MobileNetV3 on COCO · COCO validation set | training loss | Helped |
| Use Proposed-I or Proposed-II instead of benchmark methods | Distributed learning with MobileNetV3 on COCO · COCO validation set, computation-load comparison | training loss | Helped |
| Use Proposed-I or Proposed-II instead of methods that do not ensure an unbiased gradient estimator | Distributed learning under stragglers · COCO validation set, k=10, τ_th=1.1 | training loss | Helped |
| Increase the response-time limit τ_th | Benchmark methods · COCO validation set, k=10 | convergence speed | Helped |
| Use Proposed-I or Proposed-II with a larger distributed system | Distributed learning with MobileNetV3 · COCO validation set, k=100 | convergence speed | Helped |
| Rely on unbiasedness alone without further reducing estimator residual error | Stochastic Gradient Coding (SGC) · COCO validation set, k=10, τ_th=1.1 | convergence speed | Hurt |
Surprising findings
- Merely ensuring unbiasedness (SGC) is not sufficient for best performance; further reducing residual error and variance improves convergence further.
- Applying the GD-optimized codes to mini-batch SGD does not reach the theoretical minimum residual error, leaving a sampling-variance term.
Limitations
- Theory assumes bounded gradient norms (Assumption on C), which is an approximation in practice.
- Results are for GD-like full-batch setting; mini-batch SGD extension does not achieve minimum residual error.
- Experiments use simulated straggler model with exponential-parameter sampling and averaged over 10 runs; no error bars reported.
Experimental setup
Datasets: COCO
Benchmarks: COCO
Metrics: training loss vs iteration training loss vs computation load
Baselines: GD IS-SGD BGC ERASUREHEAD Optimal Decoding SGC
Builds on: Stochastic Gradient Coding Gradient Coding Approximate gradient coding with expander graphs
Closest papers by meaning
- Gradient Coding: Avoiding Stragglers in Distributed Learning (ICML 2017 · similarity 0.94)
- Leveraging partial stragglers within gradient coding (NeurIPS 2024 · similarity 0.93)
- Gradient Coding from Cyclic MDS Codes and Expander Graphs (ICML 2018 · similarity 0.92)
- Communication-Computation Efficient Gradient Coding (ICML 2018 · similarity 0.92)
- Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity (NeurIPS 2026 · similarity 0.88)
- Accelerated Methods with Compressed Communications for Distributed Optimization Problems Under Data Similarity (AAAI 2025 · similarity 0.88)
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.