Binary cyclic gradient coding improves exact recovery and resilience to compression
Binary Cyclic Gradient Coding: Exact Recovery and Robustness to Compression
Information Theory
Summary
Training AI models often involves many computers (workers) calculating parts of the work, but some workers can be slow or unreliable. The paper introduces a method called binary cyclic gradient coding (BCGC) that organizes data among workers in a special pattern to ensure the system can recover the full result even if some workers lag behind. BCGC is designed to handle data compression better than existing methods, keeping the training process stable and accurate. The authors also show that BCGC’s unique design allows it to perform exact recovery in scenarios where other approaches fail, confirmed by experiments on multiple datasets.
What this means in practice
- •For distributed machine learning engineers: Enable stable and exact gradient computation when some workers are slow or send compressed updates in distributed AI training systems.
- •For cloud infrastructure teams: Improve reliability and compression tolerance in large-scale distributed computations involving many nodes with variable speeds and data quality.
Authors
Hassan Ou-azzou, Imad Kissami, El Houcine Bergou
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)\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 $κ$ sparsification while the MDS codes diverge, and on heterogeneous data its partition diversity reduces the compression error and improves the accuracy.