Binary Cyclic Gradient Coding: Exact Recovery and Robustness to Compression
Abstract
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)| 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 κ sparsification while the MDS codes diverge, and on heterogeneous data its partition diversity reduces the compression error and improves the accuracy.
Related
- Superlinear Convergence of Cyclic Gradient Methods with Historical Ritz Step Sizes
- The Functional Structure of Post-Compression Recovery in Low-Rank LLMs
- Blind Deconvolution of Binary and Pattern Images with Pixel Intensity Constraints and Sparse Gradient Prior
- A family of spectral conjugate gradient algorithms derived by least-squares approximations based on a modified quasi--Newton update with application to a revised robust binary classification model
- Scaled-Gradient Hard Thresholding Algorithms for Sparse Signal Recovery
BibTeX
@misc{ouazzou2026binary,
title = {{Binary Cyclic Gradient Coding: Exact Recovery and Robustness to Compression}},
author = {Hassan Ou-azzou and Imad Kissami and El Houcine Bergou},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.20087},
eprint = {2610.20087},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.20087},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Binary Cyclic Gradient Coding: Exact Recovery and Robustness to Compression
AU - Hassan Ou-azzou
AU - Imad Kissami
AU - El Houcine Bergou
PY - 2026
DA - 2026/10/25
PB - arXiv
DO - 10.48550/arxiv.2610.20087
UR - https://arxiv.org/abs/2610.20087
AB - 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)| 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 κ sparsification while the MDS codes diverge, and on heterogeneous data its partition diversity reduces the compression error and improves the accuracy.
ER -