Communication-Efficient Approximate Gradient Coding for Distributed Learning in Heterogeneous Systems
Heekang Song, and Wan Choi · 2026
Read Communication-Efficient Approximate Gradient Coding for Distributed Learning in Heterogeneous Systems by Heekang Song, and Wan Choi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-15890.txt.
Introduction
Heekang Song and Wan Choi propose a bandwidth-saving gradient coding scheme for mixed distributed learning. Their unified framework jointly optimizes gradient coding and quantization, cutting leftover error while staying unbiased. They derive a closed-form code structure with an optimal bit allocation strategy and a fast algorithm that nearly matches the optimum. Proofs cover convex and smooth functions. Experiments on the COCO dataset show the joint design speeds convergence and improves communication efficiency over existing baselines.
Catalog record
| CREATOR | Heekang Song, and Wan Choi |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 75398 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.15890
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Communication-Efficient Approximate Gradient Coding for Distributed Learning in Heterogeneous Systems Heekang Song, and Wan Choi Abstract We propose a communication-efficient optimally structured gradient coding scheme to jointly address straggler resilience and communication efficiency in heterogeneous distributed learning. By establishing a unified framework that simultaneously optimizes gradient coding and quantization, we formulate an optimization problem to minimize residual error subject to an unbiasedness constraint. We rigorously establish the joint global optimum by deriving a closed-form code structure coupled with an optimal bit allocation strategy, while simultaneously proposing a low-complexity bit allocation algorithm that efficiently yields near-optimal performance. We provide rigorous convergence analysis for convex and smooth functions. Experiments on the COCO dataset demonstrate that our joint design significantly accelerates convergence and enhances communication efficiency compared to existing baselines. I Introduction IN recent years, the rapid advancements in deep learning have underscored the significance of large datasets and large-scale AI models as critical components for performance enhancement. Breakthrough models have not only demonstrated unprecedented capabilities but have also transformed the industrial landscape, reshaping how AI technologies are applied across various domains. However, training these massive models demands immense computational resources that often exceed the capacity of a single facility. Consequently, the scope of model training has expanded beyond individual clusters to cross-datacenter environments, where resources from geographically distributed infrastructures are aggregated to overcome local computation bottlenecks. To support this scale, distributed computing has emerged as the fundamental solution. Building on the success of foundational frameworks like MapReduce [ 1 ] and Spark [ 2 ] , distributed computing has evolved to address the complexities of modern AI, solidifying its role in mitigating computation and communication constraints [ 3 , 4 ] . This evolution is particularly evident in the rise of distributed learning, which now frequently operates in cross-datacenter settings to accommodate the growing need for efficient, global-scale training. A typical distributed learning architecture consists of a central coordinator (master node) that minimizes a loss function using gradient-based optimization (e.g., Gradient Descent). The master node partitions the dataset and distributes tasks to worker nodes, which compute local gradients in parallel. The master then aggregates these gradients to update the model parameters. While this workload distribution enhances scalability, the cross-datacenter environment inherently introduces significant heterogeneity in computational speeds and network latencies. In such settings, the overall system performance is frequently dictated by the slowest node—known as a straggler —which creates severe bottlenecks and limits the efficiency of the training process. To mitigate the impact of stragglers in distributed learning, Gradient Coding (GC) has been extensively studied as a prominent solution [ 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 ] . Pioneered by [ 5 ] , this technique exploits data replication to encode partial gradients, enabling the exact reconstruction of the full gradient even in the presence of stragglers. While subsequent work [ 6 ] explored the trade-off between communication overhead and straggler resilience, these exact recovery methods typically rely on the unrealistic assumption of a known, fixed number of stragglers and necessitate high data redundancy, imposing a significant computational burden on worker nodes. To address these limitations, Approximate Gradient Coding (AGC) has emerged as a practical alternative, operating under more realistic probabilistic straggler models [ 7 , 8 , 9 , 10 , 11 , 12 ] . Unlike exact GC, AGC relaxes the requirement for perfect reconstruction, instead utilizing an estimated gradient sum for model updates. This relaxation is well-justified, as stochastic optimization algorithms like SGD are inherently robust to noise and approximation errors. By minimizing the residual error between the true and approximate gradients rather than enforcing exact recovery, AGC significantly reduces the computational overhead associated with data replication. Various strategies have been proposed to construct efficient AGC schemes. For instance, [ 7 ] utilized the normalized adjacency matrix of expander graphs, while [ 8 ] introduced a scheme based on sparse random graphs with Bernoulli sampling. The properties of Fractional Repetition (FR) codes were analyzed in [ 9 ] , although their application is constrained by specific divisibility requirements between nodes and replication factors. On the theoretical front, [ 10 ] characterized the fundamental trade-offs among replication factor, straggler count, and residual error. Building on these foundations, [ 11 ] recently proposed a dynamic decoding framework using expander graphs to further minimize residual error during training. While previous studies [ 7 , 8 , 9 , 10 , 11 ] primarily focused on minimizing the residual error between the estimated and true gradients, this metric alone does not necessarily guarantee model convergence. Addressing this gap, Stochastic Gradient Coding (SGC) [ 12 ] introduced a pairwise data distribution scheme to construct an unbiased gradient estimator, ensuring robust convergence even under severe straggler conditions where residual-error-focused methods often falter. However, SGC’s reliance on strict pairwise constraints can significantly increase implementation complexity depending on the system scale. Furthermore, given the iterative aggregation process in distributed learning, communication efficiency is as critical as computation. Yet, most existing works, including SGC, overlook the transmission overhead. A notable exception is 1-bit SGC [ 13 ] , which integrated 1-bit quantization into the SGC framework. However, this approach merely applies quantization sequentially to the straggler mitigation scheme, failing to analyze the joint impact of stragglers and quantization noise. Moreover, being restricted to extreme 1-bit quantization, it inevitably slows down convergence and fails to address the general trade-off between communication volume and convergence speed. In summary, previous studies have generally pursued two directions: minimizing residual error or ensuring unbiasedness via specific coding designs. However, most prior research relies on unrealistic homogeneous straggler assumptions, which can lead to dataset neglect and poor generalization in practical, heterogeneous settings. To address these issues, our previous work on AGC in heterogeneous systems [ 14 ] proposed a novel technique specifically designed to enhance stability and convergence in heterogeneous environments. Building on this foundation, this work extends the analysis to improve communication efficiency in heterogeneous systems by jointly incorporating gradient coding and quantization, a critical challenge not addressed in [ 14 ] . To the best of our knowledge, this is the first unified framework to jointly optimizes gradient coding and quantization for heterogeneous systems. Unlike prior attempts that simply apply limited 1-bit quantization sequentially, our approach integrates straggler mitigation with a flexible quantization scheme. This joint design maximizes both straggler resilience and communication efficiency simultaneously, adapting to any bit budget. II Preliminaries II-A Distributed Learning with Gradient Coding We consider a distributed learning framework with one master node and k worker nodes. Given a dataset \mathcal{D}=\{\mathcal{D}_{1},\ldots,\mathcal{D}_{n}\} partitioned into n data blocks, the master aims to find \bm{\beta}^{*}\in\mathbb{R}^{l} that minimizes \sum_{j=1}^{n}L(\mathcal{D}_{j},\bm{\beta}) . At iteration t , let g_{j}^{(t)}=\nabla L(\mathcal{D}_{j},\bm{\beta}_{t}) denote the gradient of partition \mathcal{D}_{j} , and let g^{(t)}=\sum_{j=1}^{n}g_{j}^{(t)} be the full gradient. The ideal gradient descent update is \bm{\beta}_{t+1}=\bm{\beta}_{t}-\gamma_{t}g^{(t)}, (1) where \gamma_{t} is the learning rate. In distributed learning, however, the master estimates g^{(t)} from the responses of worker nodes, some of which may become stragglers. Gradient coding mitigates this issue by assigning possibly overlapping data batches \mathcal{B}_{i}\subseteq\mathcal{D} to workers and linearly encoding their computed partial gradients. The procedure consists of data distribution, local computation, and gradient update. In the data distribution phase,