PaperlayerView exact revision on arXiv

Source-linked AI summary

Binary Cyclic Gradient Coding: Exact Recovery and Robustness to Compression

Hassan Ou-azzou, Imad Kissami, El Houcine Bergou

arXiv:2610.20087v1cs.ITmath.IT

TL;DR

Distributed gradient coding must handle stragglers while reducing communication, but compression can disrupt exact decoding. This paper introduces BCGC, which uses binary cyclic supports and class-sum recovery; experiments report robustness under sparsification and accuracy gains on heterogeneous data.

  • Problem

    Gradient coding must address stragglers, while high-dimensional messages make communication costly and nonlinear compression can disrupt the linear structure needed for decoding.

    Source: §I · p. 1

  • Method

    BCGC assigns data through binary cyclic supports and recovers the full gradient by summing one complete worker class, with a circulant or nearly circulant encoding matrix.

    Source: §I · p. 2

  • Results

    BCGC stays within 0.022 of its uncompressed metric under top κ sparsification, while Gaussian MDS and Reed–Solomon codes diverge; on heterogeneous data, it improves accuracy over GFRC by 5.0 points on MNIST and 4.9 points on EMNIST.

    Source: A. Robustness of compressed gradient… · p. 15, B. Partition diversity on… · p. 16

  • Takeaways & Limitations

    For contractive compressors, FRC, GFRC, and BCGC share the standard convergence guarantee while differing in their data partitions, and a BCGC partition can recover an exact gradient when FRC and GFRC partitions cannot.

    Source: §I · p. 3

Abstract

from arXiv · show

We introduce binary cyclic gradient coding (BCGC), an exact gradient coding scheme for $n$ workers and up to $s$ stragglers. Its encoding matrix is binary, circulant when $(s+1)\mid n$ and nearly circulant otherwise, and the master decodes by a single summation. Like the fractional repetition coding scheme (FRC) and its generalized version (GFRC), BCGC splits the workers into $s+1$ classes that each cover the whole dataset, but it assigns the data through cyclic supports. Its encoding matrix has rank $n-s$, and $n-s-1$ workers keep the balanced load $s+1$, which is the largest possible number. We prove that encoding matrix of BCGC is not permutation-equivalent to those of FRC and GFRC schemes. Moreover, We also prove that a binary coded scheme with compression is equivalent to an uncoded compressed scheme on a coarser partition of the data. This explains why binary schemes remain stable under compression, whereas the large decoding coefficients of MDS codes amplify the compression error and lead to divergence in our experiments. For every contractive compressor, the standard convergence guarantee of compressed gradient descent holds on each coarse partition. FRC, GFRC and BCGC therefore share the same convergence guarantee and differ only in their partitions, with one partition for FRC, two for GFRC and $s+1$ distinct partitions for BCGC. Choosing among these partitions can recover the exact gradient in cases where FRC and GFRC cannot. Experiments on four datasets confirm the theory. BCGC matches GFRC, keeps its accuracy under top $\kappa$ sparsification while the MDS codes diverge, and on heterogeneous data its partition diversity reduces the compression error and improves the accuracy.

I. INTRODUCTION

Distributed gradient descent faces both high-dimensional communication costs and stragglers, while compression can complicate exact decoding. BCGC combines binary summation decoding with cyclic data assignments and supports exact recovery and stable compression across distinct data partitions.

I. INTRODUCTION

  • Gradient communication and stragglers are the two main efficiency limits in distributed gradient descent.Compression reduces communication, but nonlinear compression can disrupt the linear structure required for decoding.Source: §I · p. 1
  • BCGC uses binary cyclic supports and recovers the full gradient by summing one complete worker class.It tolerates any s stragglers at threshold n-s; its matrix is circulant when (s + 1) divides n and nearly circulant otherwise.Source: §I · p. 2
  • BCGC is not permutation-equivalent to FRC or GFRC and has s + 1 distinct data partitions, versus one for FRC and two for GFRC.For contractive compressors, these schemes share the compressed-gradient-descent guarantee; a BCGC partition can recover an exact gradient when FRC and GFRC partitions cannot.Source: §I · pp. 2–3
  • Binary coded compression is equivalent to uncoded compressed computation on a coarser data partition, while MDS decoding coefficients can amplify compression error.Experiments report BCGC matching GFRC under top κ sparsification and improving accuracy over GFRC on heterogeneous data.Source: §I · pp. 2–3

A. Gradient coding

Gradient coding distributes partial gradients across workers so the master can recover the full gradient from responding workers. The encoding and decoding vectors are chosen to make that recovery exact despite up to s stragglers.

A. Gradient coding

  • The master partitions data into chunks, workers compute assigned partial gradients, and the master aggregates their messages into the full gradient.The chunks need not have equal sizes for exact recovery, though the experiments use equal-sized chunks.Source: A. Gradient coding · pp. 3–4
  • A scheme tolerates s stragglers when the master can exactly recover the full gradient from any n-s responding workers.The smallest number of responses that guarantees exact recovery is the recovery threshold.Source: A. Gradient coding · p. 3
  • The encoding matrix B and a response-dependent decoding vector a_I must satisfy a_I B = 1, with the decoder supported only on responding workers.This condition ensures that the weighted worker messages reconstruct the full gradient.Source: A. Gradient coding · pp. 3–4

B. Binary gradient coding

Binary gradient coding restricts encoding and decoding to 0/1 entries, allowing workers to sum partial gradients and the master to recover by summing selected messages. A partition of workers into s + 1 classes provides a sufficient condition for this recovery.

B. Binary gradient coding

  • With binary encoding and decoding, workers sum assigned partial gradients and the master reconstructs the full gradient by summing selected responses.This avoids solving a linear system online and avoids error amplification from large decoding coefficients.Source: B. Binary gradient coding · p. 4
  • If each of s + 1 worker classes collectively covers every data chunk, any n-s responses contain a complete class whose messages recover the full gradient.The decoder selects that class by summing its indicator vector against the encoding matrix.Source: B. Binary gradient coding · p. 4
  • FRC divides workers into equal-sized classes and repeats a uniform block assignment, with each class covering the dataset.When s + 1 divides n, each class assigns disjoint supports of size s + 1 across its workers.Source: B. Binary gradient coding · p. 4

III. BINARY CYCLIC GRADIENT CODING: THE DIVISIBLE

BCGC combines cyclic supports with binary encoding, while retaining class-based exact recovery. Each of its s + 1 worker classes collectively holds the entire dataset.

III. BINARY CYCLIC GRADIENT CODING: THE DIVISIBLE

  • BCGC uses cyclic supports with binary coefficients, and summing any complete class recovers the full gradient.Its supports differ from FRC and GFRC; the encoding matrix is circulant when s + 1 divides n and near-circulant otherwise.Source: §III · p. 4

A. The encoding scheme

BCGC assigns cyclic supports so each of the s + 1 worker classes covers the dataset, enabling exact recovery by summing one complete class. It tolerates any s stragglers at the optimal threshold n − s.

A. The encoding scheme

  • Each worker’s cyclic support contains s + 1 consecutive chunks, and the supports within each congruence class partition the dataset.The resulting matrix is circulant when (s + 1) divides n.Source: A. The encoding scheme · p. 5
  • BCGC’s binary recovering sets are exactly its s + 1 classes, whereas FRC has more binary recovering sets that can combine workers across classes.Both schemes tolerate any s stragglers with the same load and decoding cost; FRC can need fewer responses on average with early stopping.Source: A. The encoding scheme · pp. 5, 7
  • Any n − s responses suffice to recover the full gradient, and no decoder can recover it from fewer responses.Each data chunk is held by exactly s + 1 workers, so if those workers straggle, the received messages do not depend on that chunk's gradient.Source: A. The encoding scheme · pp. 5–6
  • The master decodes by counting arrivals until one class is complete, then summing its messages; each response takes O(1) operations.The final sum of ℓ messages of dimension d costs O(ℓd).Source: A. The encoding scheme · p. 6

B. Algebraic structure and comparison with the FRC scheme

The row space of BCGC’s encoding matrix is a cyclic code of dimension n − s. Its rank distinguishes BCGC from FRC under the stated parameter range.

B. Algebraic structure and comparison with the FRC scheme

A. The encoding scheme

When s + 1 does not divide n, BCGC retains cyclic supports and partitions the data within each worker class. This construction preserves exact recovery at threshold n − s while concentrating irregular loads on one worker per class.

A. The encoding scheme

  • The first n − s − 1 rows are cyclic shifts of one row, while the final s + 1 rows have irregular weights, making B near-circulant.The irregular workers have loads r or s + 1 + r.Source: A. The encoding scheme · p. 8
  • The supports within each class partition the dataset, so every column has weight s + 1 and the total load is n(s + 1).Only the last worker of each class has load different from s + 1; the other n − s − 1 workers retain that balanced load.Source: A. The encoding scheme · p. 8
  • Any n − s responses suffice for exact recovery, and the threshold cannot be lowered even with real-valued or nonlinear decoding.Each chunk belongs to exactly s + 1 supports, one in each class.Source: A. The encoding scheme · pp. 8–9
  • The decoder counts arrivals until a class is complete, then sums its messages; each response takes O(1) operations.It waits for at most n − s responses, and the final sum costs O((ℓ + 1)d).Source: A. The encoding scheme · p. 9
  • For n = 11 and s = 2, the threshold is 9 responses; if workers 0, 1, and 2 straggle, no decoder can recover the gradient.The chunk indexed 2 is held only by those three workers.Source: A. The encoding scheme · p. 10

B. Algebraic structure and comparison with GFRC

BCGC and GFRC use different support assignments when s + 1 does not divide n. Their ranks differ in the stated parameter range, while BCGC keeps more workers at load s + 1 by accepting a wider load range.

B. Algebraic structure and comparison with GFRC

  • GFRC uses one partition for classes of size ℓ + 1 and another for classes of size ℓ, while BCGC’s class partitions start at different chunks.Thus BCGC can have s + 1 distinct class partitions, compared with GFRC’s two partition types.Source: B. Algebraic structure and comparison… · p. 10
  • In the n = 8, s = 2 example, BCGC has rank 6 while GFRC has rank 4.GFRC’s repeated rows arise because classes of the same size use the same partition.Source: B. Algebraic structure and comparison… · p. 11
  • For s ≥ 2 and n ≠ s + 2, BCGC has rank n − s while GFRC has rank at most 2ℓ, so the matrices are not permutation-equivalent.The matrices are also not permutation-equivalent in the critical cases for n ≥ 4; they coincide when n = 3.Source: B. Algebraic structure and comparison… · p. 11
  • BCGC and GFRC have equal minimal total load deviation, ds(B) = ds(BGFRC) = 2r(s + 1 − r), but BCGC has a wider load range.That wider range is the price of retaining the maximum number of workers at load s + 1.Source: B. Algebraic structure and comparison… · p. 11

V. COMPATIBILITY WITH GRADIENT COMPRESSION

Binary decoding turns a compressed coded update into ordinary compressed computation on a coarser data partition. The paper proves convergence on these partitions and shows that BCGC offers more distinct partition choices than FRC or GFRC.

V. COMPATIBILITY WITH GRADIENT COMPRESSION

  • Large decoding coefficients can amplify compression errors, while binary decoding avoids this amplification.For a binary decoding vector, the stated error bounds use unit maximum coefficients.Source: §V · p. 12
  • Binary decoding makes the compressed coded update equivalent to naive compression on a coarser partition of the data.The coarse blocks are the unions of chunks assigned to each selected worker.Source: §V · p. 12
  • Under the stated smoothness, additivity, and contractivity assumptions, compressed gradient descent has a convergence guarantee on every coarse partition.For FRC, GFRC, and BCGC, the guarantee applies under any pattern of at most s stragglers and for every complete class decoded at each round.Source: §V · pp. 13–14
  • FRC, GFRC, and BCGC share the convergence guarantee but differ in their induced partitions: one for FRC, two for GFRC, and up to s + 1 for BCGC.For ℓ ≥ 2, BCGC's partitions are pairwise distinct and none refines another.Source: §V · p. 14
  • BCGC's cyclic supports make exactly one class separate each adjacent chunk pair, yielding distinct partitions that can produce different compressed updates.In the stated examples, a BCGC class recovers the exact gradient when FRC or GFRC's partition does not.Source: §V · p. 14

VI. EXPERIMENTS

The experiments compare BCGC with uncoded, binary, and MDS schemes on four datasets using top-κ sparsification. Without compression, the exact schemes agree, while the reported MDS behavior includes numerical instability at higher straggler load.

VI. EXPERIMENTS

  • The comparison uses n = 100 workers, four datasets, and top-κ sparsification with κ = ⌊0.05 d⌋ over 100 Nesterov-accelerated iterations.The schemes include naive, GFRC, Gaussian MDS, and Reed–Solomon; exactly s workers are delayed at each iteration.Source: §VI · p. 14
  • The reported accuracies are 0.915 on MNIST, 0.925 on EMNIST, and 0.617 on 20 Newsgroups; MDS codes reach the same values at s = 20.At s = 24, the complex decoding of RS is numerically unstable, and its accuracy falls to 0.02 on 20 Newsgroups without compression.Source: §VI · p. 15
  • At s = 24, complex RS decoding is numerically unstable, including an accuracy of 0.02 on 20 Newsgroups without compression.The experiments use Nesterov accelerated gradient descent, unlike the plain gradient descent analyzed in Proposition V.7, so they illustrate rather than formally fall under that analysis.Source: §VI · pp. 14–15

A. Robustness of compressed gradient coding

Across four datasets, the binary schemes retain accuracy under top-κ sparsification, whereas the MDS codes diverge or become numerically unstable. BCGC matches GFRC at s = 24 and is at most 17% slower at s = 20.

A. Robustness of compressed gradient coding

  • About 27 s on Amazon versus 46 to 56 s for MDS codes, the binary schemes are the fastest coded schemes for the reported runs.Figure 2 compares total wall time for 100 iterations with and without top-κ sparsification at s = 20 and s = 24.Source: Figure 2 · p. 15, A. Robustness of compressed gradient… · p. 15
  • Under top-κ sparsification (κ = ⌊0.05d⌋, n = 100), binary schemes remain stable and within 0.022 of their uncompressed metric on all four datasets; Gaussian MDS and RS codes diverge at s = 20 and become numerically unstable at s = 24.Source: Table I · p. 15, A. Robustness of compressed gradient… · p. 16
  • At s = 24, BCGC and GFRC have the same performance; at s = 20, BCGC is at most 17% slower than GFRC on 20 Newsgroups.The reported difference at s = 20 is attributed to a larger load assigned to a few BCGC workers.Source: A. Robustness of compressed gradient… · p. 16

B. Partition diversity on heterogeneous data

The minimum-error decoder tests whether BCGC’s partition diversity helps under top-κ sparsification, comparing i.i.d. and non-i.i.d. data partitions. BCGC’s advantage appears on heterogeneous data with substantial compression error.

B. Partition diversity on heterogeneous data

  • On non-i.i.d. data, BCGC’s total compression error is 15 to 19% lower than GFRC’s on Amazon, MNIST, and EMNIST, improving accuracy by 5.0 points on MNIST and 4.9 points on EMNIST.The improvement removes about half the accuracy lost to compression at the same wall time of about 40 s.Source: B. Partition diversity on… · p. 16, Table III · p. 16
  • On i.i.d. partitions, BCGC and GFRC give the same results; on Amazon and 20 Newsgroups, they agree to within 0.001.The comparison uses top κ sparsification with κ = ⌊0.05 d⌋, n = 100, and s = 24.Source: B. Partition diversity on… · p. 16
  • Partition choice has little effect when compression loses little information or data chunks are similar; BCGC is never worse than GFRC by more than 0.001.The reported gain requires both heterogeneous data and significant compression error.Source: B. Partition diversity on… · p. 16

VII. CONCLUSION

BCGC combines cyclic binary supports and exact single-summation recovery with robustness to stragglers. The paper relates binary coding under compression to uncoded compressed computation on coarse partitions and reports stability and accuracy benefits in its experiments.

VII. CONCLUSION

  • BCGC uses a circulant or nearly circulant binary encoding matrix, with exactly s + 1 classes as recovering sets, tolerating any s stragglers at threshold n−s and decoding by one summation.Its total load is n(s + 1).Source: §VII · p. 16
  • For 2 ≤ s ≤ n−2, BCGC is neither MDS nor permutation-equivalent to FRC or GFRC..Source: §VII · p. 16
  • Binary gradient coding with compression is equivalent to uncoded compressed computation on a coarser partition, while MDS decoding coefficients amplify compression error.For every contractive compressor, FRC, GFRC, and BCGC share the same convergence guarantee and differ in their partitions.Source: §VII · p. 16
  • Across four datasets, BCGC matches GFRC in robustness and accuracy, runs faster than the two MDS codes, and remains stable under compression while they diverge.On heterogeneous data, selecting the complete class with the smallest compression error improves accuracy by up to 5 points over GFRC at the same cost.Source: §VII · p. 16

Related papers

Loading 2610.20087v1…