Approximate Gradient Coding for Distributed Learning with Heterogeneous Stragglers
Authors: Heekang Song
Wan Choi
Venue: NeurIPS 2025 poster ()
Keywords: Distributed Learning
Straggler Mitigation
Gradient Coding
Optimal Structure
Primary area: infrastructure

Abstract: In this paper, we propose an optimally structured gradient coding scheme to mitigate the straggler problem in distributed learning. Conventional gradient coding methods often assume homogeneous straggler models or rely on excessive data replication, limiting performance in real-world heterogeneous systems. To address these limitations, we formulate an optimization problem minimizing residual error while ensuring unbiased gradient estimation by explicitly considering individual straggler probabilities. We derive closed-form solutions for optimal encoding and decoding coefficients via Lagrangian duality and convex optimization, and propose data allocation strategies that reduce both redundancy and computational load. We also analyze convergence behavior for $\lambda$-strongly convex and $\mu$-smooth loss functions. Numerical results show that our approach significantly reduces the impact of stragglers and accelerates convergence compared to existing methods.

Approximate Gradient Coding for Distributed Learning with Heterogeneous Stragglers
Heekang Song
Korea Advanced Institute of Science and Technology School Electrical Engineering hghsong@kaist. .c.
Wan Choi
Scoul National University
Department of Electrical and Computer Engineering wancho fanchoi@snu.c @snu ac kr
Abstract
In this paper, propose optimally structured gradient coding scheme mitigate the straggler problem distributed learning. Conventional gradient coding methods often assume homogeneous straggler models rely excessive data replication, limiting performance in real-world heterogeneous systems. To address these limitations, formulate optimization problem minimizing residual error while ensuring unbiased gradient estimation by explicitly considering individual straggler probabilities. We derive closed-form solutions for optimal encoding and decoding coefficients via Lagrangian duality and convex optimization, and propose data allocation strategies that reduce both redundancy and computation load. We also analyze convergence behavior for A-strongly convex and j-smooth loss functions. Numerical results show that our approach significantly reduces the impact of stragglers and accelerates convergence compared to existing methods.
Introduction
In recent years, the rapid advancements deep learning have underscored the significance of large datasets and large-scale Al models as critical components for performance enhancement. Break- through models such as ChatGPT, Gemini, and SORA have not only demonstrated unprecedented capabilities but have also transformed the industrial landscape, reshaping how AI technologies applied across various domains. These models are commonly trained using gradient-descent based algorithms, but the training process for such large-scale models demands immense computational resources, such as GPUs and NPUs, leading to computation bottleneck. To address these challenges, building foundational frameworks like MapReduce (1] and Spark 2,, distributed computing (3]4 has emerged as promising and practical solution, and evolving into distributed learning, which mitigates computation and communication bottlenecks in large-scale training scenarios.
distributed learning architecture typically consists of a central coordinator (master node) that trains an Al model using gradient-based optimization (e.g., Gradient Descent (GD) to minimize given loss function, partitions and distributes the dataset to worker nodes for parallel computation of local gradients, and aggregates these local gradients to approximate the global gradient and update model parameters. However, heterogeneity in computational and communication resources can cause bottlenecks, particularly due to the slowest worker node, known straggler, impairing overall efficiency and scalability.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Motivated by this aspect, Gradient Coding, a specialized technique for mitigating stragglers in distributed learning, has been extensively studied [SH The concept was first introduced in [5]. where data replication enables coding of partial gradients. Assuming known number of stragglers, it designed linear encoding and decoding schemes and identified fundamental data replication limits. Its extension [6] explored trade-offs between communication overhead and resilience to stragglers, proposing gradient coding schemes that reduce overhead at the expense of lower resilience. However, these methods assume prior knowledge of straggler counts- unrealistic in practice- and require extensive data replication, placing a heavy computational burden on worker nodes.
To overcome limitations associated with unrealistic straggler models and high computational costs, Approximate Gradient Coding has emerged as a practical solution under probabilistic straggler models, explored in prior works [7H12). Unlike exact gradient coding [5] o which precisely reconstructs the true gradient sum, approximate gradient coding relies on estimated gradient sum for model updates. This relaxation is justified since optimization methods, such as Stochastic Gradient Descent (SGD), naturally tolerate approximations and noise, still ensuring convergence. By alleviating the computational burden of exact recovery, approximate gradient coding improves efficiency and mitigates straggler impacts through minimizing the residual error between true and approximate gradient sum.
The authors of 7 introduced the approximate gradient coding framework by leveraging the normal- ized adjacency matrix of an expander graph to construct encoding and decoding schemes. Similarly, 8 proposed an approximate gradient coding scheme based on sparse random graphs, where gradient components are assigned to worker nodes via Bernoulli sampling and the residual error is controlled through probabilistic guarantees. The study [9] further analyzed the residual error of Fractional
Repetition (FR) codes, originally introduced in [ noting that these codes can only be constructed when the number of distributed nodes is a multiple of the data replication factor. Additionally, [TO] examined the fundamental trade-off among the data replication factor, the number of stragglers, and the residual error in approximate gradient coding. Building on these advancements, the authors of
[1] proposed novel approximate gradient coding scheme that leverages expander graphs while dynamically optimizing decoding coefficients to minimize residual error.
While previous studies [ primarily aimed to reduce residual errors between the gradient estima- tor and the true gradient, this focus alone does not necessarily ensure model convergence. Therefore, robust convergence guarantees become essential when using approximate gradient sums in gradient- descent algorithms. Stochastic Gradient Coding (SGC) 12 addressed this by introducing a pairwise data distribution scheme, where the number of worker nodes sharing any two data partitions is proportional to the product of their respective replication factors. SGC designs its encoding coef- ficients to ensure unbiased gradient estimator using binary decoding and provides a thorough convergence analysis. Empirical results showed that SGC performs robustly even under severe straggler conditions, where residual-error-for focused methods (7-11) may falter. Unlike exact gradient coding- which requires each data partition to be replicated more than the number of stragglers- SGC enforces constraints on pairwise data distribution. Consequently, depending on the total number of data partitions, their replication factors, and the number of workers, it can become challenging or even infeasible to satisfy the pairwise distribution constraints.
In summary, previous studies have generally pursued two directions. The first focuses on minimizing the residual error but often lacks rigorous convergence analysis or relies on binary encoding/decoding coefficients for analytical simplicity. The second ensures the gradient estimator's unbiasedness by carefully designing encoding coefficients while using binary decoding coefficients. Observing the progress in both directions, we believe that integrating these approaches can potentially yield improved performance. Moreover, most prior research assumes homogeneous straggler scenarios with uniform straggling probabilities across worker nodes, which is unrealistic given the varying computation and communication capacities encountered in practical settings. Under non-uniform probabilistic model, gradient updates may consistently neglect certain datasets, increasing generalization errors and the risk of converging to local optima. To address these issues, we propose novel approximate gradient coding technique specifically designed for heterogeneous straggler environments.
2

---

2 Preliminaries
2.1 Distributed Learning with Gradient Coding
Consider a distributed learning, where a master node aims to solve an optimization problem using a gradient-descent-lik algorithm across & worker nodes. Given dataset D (D+) consisting of data partitions, the goal is to learn parameter 3 E IR' that minimizes a loss function L(D, (). This process involves iteratively solving:
3 arg min LDD
(1)
8
by approximating the parameter update:
Bz+1 Br 7t- g(),
(2)
where (+)) represents the aggregated gradient iteration t,
( VL(D.
Σ V.)...3.).
(3)
and "t is a learning rate. In a distributed framework, the master node divides the dataset D into and distributes each data batch B, to its corresponding worker node
k batches (B1, ..., Bxx where data batches may overlap and do not necessarily have the same size. Each worker node j then computes the local partial gradient V (B Be) in parallel, and then the master node aggregates these to approximate the global gradient. Stragglers, however, can impede this process; gradient coding combats them by injecting redundancy and applying coding across batches to tolerate slow or failed worker nodes.
................................
The gradient coding procedure consists of three phases data distribution, local computation, and gradient update phase. data distribution phase, the master node replicates each partition D; d worker nodes to tolerate stragglers. This redundancy enables worker nodes to send encoded partial gradients (via linear combinations), so the master node can recover the true gradient sum even some worker nodes straggle. This process introduces the parameter d = 1 E di known as the computation load (or replication factor), which quantifies the average redundancy in computation (or data replication). Hereinafter, will refer to the replication factor as the computation load.
Subsequently, in local computation phase, each worker node computes the partial gradient from its assigned data batch B;, i.e., {1, VD; E B:)- Using the computed partial gradients, each worker node generates an encoded message, which is then sent the master node:
f((B))
Σ ai 9
(4)
DjEB.
where dij E represents the encoding coefficient used by worker node for the gradient gj VL(D;, 3r), which corresponds to data partition Dj.
(1)
Then, in gradient update phase, the master node aggregates all the received responses from non- straggling worker nodes with the decoding coefficients:
(1))
Σ I. w. ((()))
(5)
where w; E R is the decoding coefficient for worker node and II; the indicator function for worker node i being non-straggler, i.c.,
1, if worker node is non-straggler,
(6)
0, otherwise.
Unlike the homogeneous straggler assumptions in 7-13, adopt heterogeneous model: each worker node i independently straggles at each iteration with probability ps. so [E[TT,] = p:- This reflects real-world variability in computational and communication capacities. The parameter update follows the process outlined in (2); however, instead of the true gradient sum g(*), an estimated gradient sum g()) from gradient decoding is used for the update. Once updated, the parameters B are distributed to the worker nodes. Once the data distribution is done, the local computation and gradient-update phases repeat every iteration until convergence.
3

---

9. t. oigo
4u1 a. wigh
(a)
(b)
Figure 1: Motivating example of gradient coding.
2.2 Motivations
Figure [ illlustaate motivating example. Without replication coding, single straggler forces the master node to update using only the remaining gradients- e.g. in Figure [(a) G is updated with gi + 92- By contrast, in Figure ebch partition is assigned to worker nodes, which compute and linearly encode their gradients into fi / 2 + 92. /2 = 93. and ʃa / + 93- Even if the third worker node becomes a straggler, the master node still recovers the true gradient 91 + 92 + 93 by computing 2f1 - f2. This perfect recovery nullifies the impact of stragglers, ensuring seamless gradient-descent updates.
From this perspective, exact gradient coding provides a systematic way to choose the encoding coefficients @i,j and the decoding coefficients w; so that each worker node encodes its gradients into fi, and the master node recovers the true gradient sum from non-straggling messages. Representing the encoding matrix A and decoding vector w, the goal is satisfy Aw g(t) (()), Moreover, tolerate up stragglers, the computation load d must satisfy d 2 + 1, which represents fundamental limit.
ensuring
To address the high computation load and the impractical requirement of knowing the exact number of stragglers, approximate gradient coding was developed based on the homogeneous probabilistic straggler model (p1 P2
P&)). Unlike exact recovery under deterministic straggler scenarios illustrated in Figure [(b] approximate gradient coding focuses on designing the encoding matrix A and decoding vector to minimize the average residual error between the true gradient sum g(t) and its estimated counterpart g Prior studies have demonstrated that smaller residual errors and higher computation load typically improve convergence behavior. Nevertheless, highlighted in [12, exclusively minimizing residual error may lead to degraded convergence performance in environments with frequent straggling events. In contrast, ensuring an unbiased gradient estimator provides robust convergence properties even under severe straggler conditions.
3 Optimally Structured Gradient Coding
Building these insights, gradient coding approach aims not only to reduce both the overall residual error and the variance of the estimator but also to leverage the unbiasedness of gradient estimators in heterogeneous straggler environments! [ By addressing these factors, the proposed method enhances convergence performance, achieving faster convergence with stronger theoretical guarantees. Accordingly, the encoding matrix and decoding vector w, each comprising the encoding coefficients {ai.). j and decoding coefficients {w,, Vi}, are designed by optimizing the problem:
(P1) minimize A.w
E, [lg - (01)
subject to [.)) = (())
(8)
where [.]:] [ represents the expectation over the random behavior of the stragglers in the t-th iteration, conditioned the model parameter 3r. Since straggler effects are i.i.d. across iterations, the optimized encoding and decoding coefficients remain fixed, eliminating the need to re-optimize (P1) at every heeation-unless the underlying straggler statistics change.
With unbiased gradient estimator, the residual error equals its variance.

---

However, problem (P1) is not directly solvable, as it requires knowledge of the true gradient values, necessitating the dynamic design of gradient codes each iteration an impractical requirement for constructing gradient codes.
To address this challenge, leverage mild assumption of the true gradient: Assumption 1. (Boundedness of gradient) There exists constant C' such that
VV( B.)l 1, C.Vj [1:n].
Note that this approach remains practical, it accommodates constraints imposed by activation functions or gradient clipping techniques, as outlined in [12 Accordingly, we introduce the following lemma.
Lemma 1. Suppose that Assumption is satisfied and gradient estimator ()t) is unbiased. Then,
aia )
Elllg g0t) S C
Σ P.(1 p:)
(10)
The proof is provided in Appendix
Since the objective is for the gradient estimator affected by straggler behavior of worker nodes to mimic the target gradient computed by gradient- based algorithms at each iteration, based on the given data partitions D and model parameter Br, the source of randomness lies in the straggler behavior at each iteration. Consequently, we have
72
Bg
Σ j=1
9
E
Σ
I W;Oi.
(11)
To ensure that this expected value matches the true gradient sum g = Eド= (0) specific values of of the following unbiasedness condition must be satisfied individually:
regardless the
E
Σ [1 p.) waas, = vj E [1:
(12)
where the equality comes from the fact that [.[L] 1 Pi-
From these observations, the original problem (P1) can be reformulated
(22)
minimize A,
Σ bm
aij
(13)
1=1
1=1
subject to
W = 1, Vj E n1:
(14)
where w; = (1- p:) w; and p./(1 p:). apparent that the optimization problem (P2) is non-convex, primarily due to the strong coupling between the encoding and decoding variables. However, both the objective function and the constraints exhibit similar structure with respect to the combined variables ū.ب..j- By defining of Wads.jj (P2) can, without loss of optimality, be transformed into
2
P3)
minimize
Σ
8,
ag
(15)
k Σ
subject to
af 1, Vj E [1:
(16)
where is the matrix whose (i,j) element af. Problem (P3) is convex problem with respect to the transformed variables a and can be solved by the standard convex optimization tool, such as CVX [15) and YALMIP [16]
5

---

Subsequently, for given a, the encoding and decoding coefficient can be obtained with randomly generated W; (w; 0) as:
and Wy
P Vi,
(17)
Note that the entry af is relevant to the encoding and decoding coefficient of the partial gradient computed from partition D, that is attributed to worker node i. This representation facilitates efficient management of data distribution and redundancy across multiple worker nodes within the gradient coding framework: specifically, ag * O means data partition Dj is allocated to worker node i. Thus, the structure of matrix a explicitly encodes how data partitions are distributed among worker nodes.
3.1 Optimal Structure of Gradient Coding
While problem (P3) can be solved using convex optimization tools, we also provide an opportunity to uncover the optimal structure of gradient codes that minimize the residual error while satisfying the gradient estimator's unbiasedness. This structure facilitates the development of a closed-fort form solution for gradient code design. To begin, we present the optimal structure of gradient codes that minimizes (P3).
Theorem 1. The optimal structure of optimization problem (P3) satisfies the conditions below:
&:
Σ a = Yi.ViE [1: and Σ
(18)
where Y; =0 6,1 プJ=
and 5,¹ 1-p: for all i E [1:
The proof is provided in Appendix F22 Note that the row-wise sum constraint, Σx= ag = 1 for all E [1 ni). ensures the unbiasedness of the gradient estimator. The values of the matrix that satisfy the optimal structure of gradient coding are determined by Y, which, in turn, depends on the straggler probabilities of all worker nodes. As result, the gradient code is directly influenced by the straggling characteristics of the distributed nodes.
According to Theorem any gradient code satisfying the optimal structure adheres to the following lemma:
For any gradient codes satisfying the optimal structure described in Theorem 1 the residual error of gradient estimator is bounded by
Lemma 2.
Exllg 10 S n²C
(19)
Σ 8-1
and squared norm of the gradient estimator is bounded by
E. [lgg < n²c (1
(20)
Li=1 8
The proof is provided in Appendix F3
3.2 Optimally Structured Gradient Code Construction
There may be multiple configurations of that can adhere to the optimal structure outlined in Theorem In this subsection, we detail two closed-form configurations- tht not only satisfy the optimal structure but also reduce the computation load.
Scheme and Scheme
Throughout, without loss of generality, we assume that P1 S P2 ... S Pk- To effectively capture more gradient information across the dataset on average, it is ad advatageouus to allocate more data to worker nodes with lower likelihood becoming stragglers. Accordingly, gradient coding strategy can be designed so that worker nodes with lower indices are assigned proportionally larger share of the data. Let b, 2 b2 2 ... > by denote the number of partitions assigned worker nodes 1 through k. selected from distinct and non-overlapping data partitions For both Scheme / and Scheme II,
"The data distribution parameters b,...., bu-1 can be adjusted based on the straggler probabilities and the available storage (or computing) capacity.

---

Yi
Vi
1
4 11
(a)
(b)
Figure 2: Illustrative example of the proposed schemes: (a) Scheme I and (b) Scheme II.
the values b, are chosen to satisfy Σ by n + which ensures that the & batches collectively cover all n partitions, with each adjacent pair of worker nodes sharing exactly one partition. This design reduces the overall computation load individual worker nodes.
Scheme A single, specific data partition (Di) is a common partition shared by all workers, while the remaining partitions are assigned exclusively individual workers. This scheme has centralized sharing structure. The data allocation is performed as:
Worker node 1 is assigned the first by data partitions: B1 {Di, D2, D.
Worker node [2 k - 1] is assigned batch that includes the shared data partition Di. along with b; additional data partitions that are exclusive to worker node i and not shared with any other worker node. Specifically, for 2 S
1, B, {Di } U
{Dz, Di.+1..... Dr where ' = 2. and for 2 2, the starting index is recursively
defined as 1 = f-11 + b,-1 - 1, ensuring that each worker node receives the next by 1 unassigned, non-overlapping data partitions.
Worker node k is assigned only the shared data partition: B {D1}.
Given the data distribution in Scheme 1, we set the elements of a to meet the optimal structure, which can be divided into three cases:
If partition D, is not distributed to worker node i (i.e., Dj & B,), we set a² = 0.
If a partition Dj is distributed exclusively to worker node i (i.e., Dj E B, but Dj & B, for any ( i), we set af 1, which satisfies the unbiasedness condition.
If partition Dj is distributed to all worker nodes, i.c., D3 D1. of is set to be Y, - b, 1, ensuring that Theorem is satisfied.
Consider n = data partitions and & = 3 worker nodes. One feasible The batches in Scheme / become B, (D1, D2, Dz}, B2 = (D1, D and B3- = (D Here all worker nodes share D1, worker node exclusively has
Example (Figure 2(a)]:
choice of (b:) is 3, b2 2, by
D2, D3. and worker node 2 exclusively has D4. The assignments for this example are:
Y1 -
1)
0
Y2 0
-
0
(21)
07
Y33
where each column sum (for Dj, af + ay a Y1 +2 Y.3 - 1; for D2, D3, Da. the sum is trivially since each is only held by one worker node), and each row sums to Y.
Scheme Each worker shares exactly one data partition with the worker of the adjacent index. so every partition is held by at most two workers. This scheme has sequential and decentralized sharing structure. The data distribution as follows:
Worker node I is assigned the first b data partitions: B, (Di, D2.... ..... P.

---

Worker node i E [2: k 1] is assigned b; consecutive data partitions, starting from the last partition of the previous worker node's batch ensure exactly one sharing partition between adjacent worker nodes. Specifically, we define B; = (Di Di,+1, ......... Di + 11+t,-11,, 1),, where I and I 1-1++ +4-1 for 2. By this construction, each batch B; shares exactly one partition with the preceding batch _ (specifically, partition Di, = Dig 1 + Consequently, each data partition D resides on at most two worker nodes, being either exclusive to one worker node or shared between two consecutive worker nodes.
Worker node k is assigned the last by data partition. i.e., B& {Dn)-
Given the data distribution Scheme II, we determine the elements of a to satisfy the optimal structure specified in Theorem I which can be categorized into the three cases:
If' partition Dj is not distributed to worker node i (i.c., Dj & Bi), we set a² = 0.
If partition Dj is distributed exclusively to worker node i (i.c., Dj B, but Dj Be for any + i), we a: 1, which maintains the unbiasedness condition.
If partition Dj shared between worker node i and worker node i+ (i.c., Dj = B,nB, 1).
ay and a.+1 are carefully assigned to ensure that of df+1 = L, ΣØ= ag = Y, and
Σj=1 of = Y++1 from the conditions in Theorem To construct such matrix a, we can recursively determine the nonzero elements row by row. Starting from worker node 1, we assign the first b - elements in the row as 1 (corresponding exclusive partitions),
and set the last element bi Yi Σb-11 - of to satisfy the row-wise sum constraint,
Ej- Y, Then, since partition Dr, is shared with worker node 2, the corresponding entry set as a² = 02 = 1 a The same procedure is repeated recursively: for each 4 worker node i, once a is determined by the previous row, the remaining values in the row are to satisfy the row-wise sum constraint Σ}= 04 Y, This recursive process ensures that all entries of a satisfy both the optimal row-sum and column-sum conditions.
Example (Figure 2(b): Consider n 4 and = 3 with b = 3, b2 = 2, by 1. This yields the batches B1 (Di, D2, Ds). B2 {D3, Da}, and B3 {Da}. Here, D3 is stored by both worker node and worker node 2, and D4 is stored by both worker node 2 and worker node 3. The corresponding matrix can be constructed as:
1 Y
2
0 Y1+Y2 -3 4- Y2
a ag
0
3
Y1
(22)
0 0
where 4 - Y1 - Y2 equals to Y3 (since Σ Y;
Σラ 5- = n). It is evident that the sum of each row i equals Y; and the sum of each column is 1, respectively, thus confirming that this construction adheres to the optimal structure outlined in Theorem [
6,
8
The closed-form expressions of both schemes are provided in Appendix A
Code construction and computation load Based on the matrix a, we construct the encoding and decoding coefficient by using (17). For both Schemes I and II, the computation load d remains strictly less than 2, i.e., 2. This indicates that robust performance achieved without placing an excessive computational burden the worker nodes. The efficiency of this code design is underscored by the fact that the computation load is d = 1 k-1 Since the number of computing nodes is generally less than or equal the size of the dataset (i.e", le < ni), the resulting computation load d remains below 2. This low value reflects efficient resource utilization, minimizing redundant computation while maintaining a balanced workload across the nodes.
Theoretical analysis of convergence behavior Due to the page limit, the theoretical convergence analysis of our proposed method is provided in Appendix B

---

Procaok
0--
(b)
1.2
12
L0KE
00
350
05
04-
04-
23
23
Easitoon
Rexaton
(c)
(d)
Figure 3: Convergence graph with respect to the training iteration T: (a) Teh = 1.1 (k: = 10) (b)
Tth 1.5 (k- 10) (c) Tth 1.1 (k- 100) (d) Tth 1.5 (k 100).
Experiments
In this section, demonstrate the effectiveness of the proposed optimally structured gradient coding scheme for straggler mitigation in distributed learning. We numerically evaluate its performance on the large-scale COCO dataset [21). In experiments, employ the MobileNetV3 model, and the learning rate is set to % = 0.01. Suppose Tи denote the response time limit for each training iteration. A worker node [1 k) is classified
straggler if its overall delay т; for local gradient computation and communication exceeds this limit, i.e., Tú > Teh- Then, the straggler probability of each worker node [1: can be modeled by
Pt -L
(23)
where th represents the straggling parameter of the worker node i and Te 2 18 19 In
these experiments, the straggling parameter is sampled from the uniform distribution [1]] i.c.,
v/ ~ Uniform(#/nn Mmax). We set k 10, t'min = 0.1, 4/max = 2, and Tth = 1.1, unless stated otherwise. The experimental results obtained by averaging the outcomes of 10 simulation runs.
We compare our design with centralized learning- based GD, Strrgglls SGD (IS-SGD), Bernoulli Gradient Coding (BGC) 8 ERASUREHEAD (EHD) (9, Optimal Decoding (OD)
Stochastic Gradient Coding (SGC) 12 The implementation details are in Appendix D
Figure shows the model convergence as a function of the training iteration and the per-iteration re- sponse time limit 7th Throughout the experiments, the loss represents the overall training objective of the object-detectin model-the sum of classification and bounding-boo regression losses-computee on the COCO validation set. The bounding-boo term is computed Smooth-LI regression on the predicted center offsets and log-scale width/height adjustments with respect to each ground-truth box. In Figure ((a) we illustrate the convergence behavior for 10 and Tü, 1.1. Except for which guarantees unbiasedness of the gradient estimator- all benchmark methods suffer from poor convergence due to the adverse impact of stragglers. In particular, for IS-SGD, when straggler tendencies are high, the learning speed can be severely compromised, underscoring the necessity of gradient coding techniques for straggler mitigation in distributed learning. Moreover, merely ensuring unbiasedness is not sufficient for optimal performance; further reducing the estimator's residual

---

08
05
0.-
04-
Compobaitniin load
Comcosaitn load
(b)
Figure 4: Convergence graph with respect to the computation load d: (a) Tsh = 1.1 (b) Tah = 1.5.
error (and variance) leads to additional improvements. Both the proposed schemes, Scheme and Scheme (referred Proposed-I and Proposed-II), detailed in Section 3.2] not only adhere the optimal structure but also demonstrate rapid convergence. They closely emulate the behavior of GD in environments unaffected by straggler effects. In particular, Figure 3(b presents the convergence for & 10 and Tea 1.5. As the per-iteration response time limit Tth increases, the likelihood of straggling decreases (due the straggler model (23)). thereby accelerating the convergence of the benchmark methods. Nevertheless, our proposed schemes still achieve faster convergence rate, closely matching that of GD. Additionally, Figs. ((c and 3 show the convergence for larger distributed system with & = 100, for demonstrate that our proposed approach effectively mitigates the impact of stragglers regardless k-1 2)
1.1 and = 1.5, respectively. 'hese results
of the number of distributed nodes, even with lower computation load (i.e., d compared to the benchmarks.
In Figure 4 plot the model convergence with respect the computation load d when Ti 1.1 and Tth 1.5. These results normalize convergence behavior by computation load, emphasizing the computational requirements necessary for each gradient coding method achieve convergence. The simulation result consistently demonstrates that our proposed method surpasses benchmark performances, achieving rapid convergence with reduced computational effort.
Although centralized Bearning-based GD can achieve rapid convergence with the same level of computation load, largely because it is unaffected by stragglers, it necessitates processing the entire dataset sequentially on single device, which considerably extends the per-iteration runtime. In contrast, its distributed version, IS-SGD, which partitions the dataset into disjoint batches and assigns them to different worker nodes without redundancy, experiences substantial performance degradation due the adverse impact of stragglers in distributed learning environments. Consequently, proposed method not only reduces the time per iteration relative to centralized learning but also effectively mitigates the detrimental effects of stragglers without incurring excessive computational overhead distributed settings, thereby delivering superior performance compared to traditional benchmarks.
Conclusions
We proposed optimally structured gradient coding scheme for mitigating stragglers in heteroge- neous distributed learning systems. By deriving optimal encoding and decoding coefficients, our method minimizes residual error while maintaining unbiased gradient estimator. Theoretical analysis and simulations showed that it consistently outperforms benchmarks, achieving high effi- ciency with low computation load, even in computation-limite scenarios. These results highlight its practicality for real-world distributed learning with rapid, redundancy-efficien updates.
6 Acknowledgements
This work was supported by the National Research Foundation of Korea(NRF) grant funded by the Korea govermment (MSIT) RQS-202-NNR050011
10

---

References
[1] J. Dean and S. Ghemawat, "MapReduce: Simplified data processing on large clusters," Commun. ACM, vol. 51, no. I, pp. 107-113, 2008.
[2] M. Zaharia, M. Chowdhury, M. Franklin, S. Shenker, and Stoica, "Spark: Cluster computing with working sets," Proc. 2nd USENIX Conf. Hot Top. Cloud Comput., Boston, MA, USA, Jun. 2010, pp. 107-113.
[3] K. Son and W. Choi, "Coded matrix computation wireless network," " IEEE Trans. Wireless Commun., vol. 23, no. 6, pp. 6394-6410, Jun. 2024.
[4] H. Song, K. Son, and W. Choi, "Joint design of shuffling and function assignment for heteroge- neous coded distributed computing," IEEE Trans. Signal Process., vol. 70, pp. 2560-2575, May 2022.
[5] R. Tandon, Q. Lei, A. G. Dimakis, and N. Karampatziakis, "Gradient coding: Avoiding strag- glers in distributed learning," in Proc. Int. Conf. Mach. Learn. (ICML), 2017, pp- 3368-3376.
[6] M. Ye and E. Abbe, CCmmmnication-compaaan efficient gradient coding," in Proc. Int. Conf. Mach. Learn. (ICML), 2018, p. 9716.
[7] N. Raviv, Tamo, R. Tandon, and A. Dimakis, "Gradient coding from cyclic MDS codes and expander graphs," in Proc. Int. Conf. Mach. Learn. (ICML), 2018, pp. 4302-4310.
[8] Z. Charles, D. Papailiopoulos, and J. Ellenberg, "Approximate gradient coding via sparse random graphs," arXiv preprint 17..7:17 2017.
[9] H. Wang, Z. Charles, and D. Papailiopoulos, "ErasureHead: Distributed gradient descent without delays using approximate gradient coding," arXiv preprint arXiv:1901.09671. 2019.
[10] S. Wang, J. Liu, and N. Shroff, "Fundamental limits of approximate gradient coding," arXiv preprint T.W::1901.016600 2019.
[11] M. Glasgow and M. Wootters, "Approximate gradient coding with optimal decoding," IEEE J. Sel. Areas Inf. Theory, vol. 2, no. 3. pp. 855-866, Sept. 2021.
[12] R. Bitar, M. Wootters, and S. Rouayheb, "Stochastic gradient coding for straggler mitigation in distributed learning," IEEE J. Sel. Areas Inf. Theory, vol. 1, no. 1, pp. 277-291, May 2020.
[13] C. Li and M. Skoglund, "Distributed learning based on 1-bit gradient coding in the presence of stragglers," IEEE Trans. Commun., vol. 72, no. 8, pp. 9903-4916, Aug. 2024.
[14] S. Park and W. Choi, "Regulated subspace projection based local model update compression for communication-effiieenn federated learning," IEEE J. Sel. Areas Commun., vol. 41, no. 4, pp. 964-976, Apr. 2023.
[15] M. Grant and S. Boyd, "CVX: Matlab software for disciplined convex programming, v2.1," Mar. 2014. [Online]. Available: lttt::///vve: http:////vxr.com//vxx
[16] Löfberg, "YALMIP: toolbox for modeling and optimization in MATLAB," Proc. IEEE Int. Conf. Robot. Autom., May 2004, pp. 284-289.
[17] B. Buyukates and S. Ulukus, "Timely distributed computation with stragglers," IEEE Trans. Commun., vol. 68, no. 9, pp. 5273-5282, Sept. 2020.
[18] K. Lee, M. Lam, R. Pedarsani, D. Papailiopoulos, and K. Ramchandran, "Speeding up dis- tributed machine learning using codes," IEEE Trans. Inf. Theory, vol. 64, no. 3, pp. 1514-1529, Mar. 2018
[19] A. Reisizadeh, S. Prakash, R. Pedarsani, and A. S. Avestimehr, "Coded computation over heterogeneous clusters," IEEE Trans. Inf. Theory, vol. 65, no. pp. +227-4242, July 2019.
[20] A. Rakhlin, O. Shamir, and K. Sridharan, "Making gradient descent optimal for strongly convex stochastic optimization," arXiv preprint arXiv: 109.v:1109.5647, 2011.

---

[21] T.-Y. Lin et al., "Microsoft COCO; Common objects in context," in Proc. Eur. Conf. Comput. Vis., 2014, pp. 740-755.
[22] O. Shamir and Zhang, "Stochastic gradient descent for non-smooth optimization: Conver- gence results and optimal averaging schemes," in Proc. Int. Conf. Mach. Learn. (ICML), 2013, pp. 71-79.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims we have made in abstract and introduction are elaborated and achieved the main paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss the limitations in Appendix C.5
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification; The proof's of the mentioned theorems and mathematical claims are all provided in appendix section.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: All the required information for running the experiments are provided in the paper and anonymous github repository.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide the code for our paper and its instructions in anonymous github repository.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: All experimental details are provided in Section and Appendix D
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: We have repeated experiments with different seeds and reported the averaged performance.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
13

---

Justification: We include the details in Appendix
D
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httcpp:://earrsss..cp/bblb/////a
Answer: [Yes]
Justification: We are following all the ethics provided by NeurIPS.
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: We believe this work does not have negative impact on the social communities.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We work with open source data and model that are publicly available and we cited them properly.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects. 15. Institutional review board (IRB) approvals or equivalent for rescarch with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact core methodology, scientific rigorousness, originality of the research, declaration is not required.
14

---

Answer: [NA]
The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Justification:
15

---

A Closed-form Expressions of the Proposed Schemes
A.1 Scheme
We obtain the following closed-form expression for the elements of a that meet the conditions specified in Theorem
I
For all [1: : k).
a3 =
Y1 by + 1, 1,
j j=1,
(24)
jE : +b - 2].
Otherwise, for all E [1 k] and VD, & Bi, =0 =0.
A.2 Scheme II
We derive the closed-form expression for the elements of a that satisfy Theorem T For i
1.
E [1: b1 1].
of
(25)
Yi
b
11 j = b
For i E [2: k - 1],
0-11
j= 4.
1,
j 11 1 + bj - 2),
(26)
Yi
+ a - b, +1,
j = 4 + b, - 1.
For i = k,
a = Ys.
(27)
Otherwise, for all E [1 k] and VD, & B, a. = 0.
16

---

B Theoretical Analysis
In this section, conduct convergence analysis of optimally structured gradient coding scheme across a variety of loss functions. To facilitate the derivation, we impose certain assumptions on the loss function
Assumption 2. (A-strongly convexity) The loss function is X-strongly convex for all B, E IR.,
X
L(B) 2 + (VL(3), (3) +
(28)
Assumption 3. (p-smoothness) The loss function L is p-smooth for all 3. E R. 220 0,
L(3) - L(B" + 3 + セリ 3 B1
(29)
Here, ( denotes the inner product operation. Note that Assumptions 2 and regarding the loss function are commonly satisfied by wide range of standard learning models, such logistic regression and softmax classifiers.
We first derive the convergence proof for X-strongly convex loss function, presented in the following theorem.
Theorem 2. Suppose the loss function L satisfies Assumptions and holds for any optimally structured gradient codes that
Then, by setting "r 1/(At).
4n²C
(1
B1 - 33 S X
1+
(30)
2im 5,
where 571
1-pi Ps
The proof is provided in Appendix F.4 Theorem 2 shows that with strongly convex loss and decaying learning rate 7/4 the proposed method achieves convergence rate of O(1/T), comparable to classical SGD. Notably, the error bound reflects straggler heterogeneity through
the scaling term [1+ [ ),- ensuring robust convergence even with non-uniform straggling.
Ei,,
Importantly, convergence depends only straggler probabilities, not computation load, meaning even minimal data replication suffices. This contrasts with SGC [12, where convergence relies on the minimum computation load min.e[[:A] d, highlighting the stronger robustness of our approach.
Next, we extend our convergence analysis to p-smooth loss functions address non-convex settings.
Based on the Assumption 3
we establish the following theorem.
Theorem Suppose the loss function satisfies Assumptions and
Then, holds for any
optimally structured gradient codes:
By setting Tt = 1/(T + 1)2/2,
1
T
Bill 113) L(Bo) L(3")
C (1
Σ
+
1+
)
(31)
T+
1)1/2
(T' + 1)2/2
2
Σ
where the following limit holds:
(
L(Bo) L(g*) + un2C
1+
2
Ei=
lim T-000
0.
(32)
(T + 1)1/2
By setting 7t = 11(11++))1
un²C(1+ + 1)232)
1 1+ Σiz 5,
T+I I B (1 L(Bo) L(
(33)
(T + 1)1/2
(T + 1)11/2
where the following limits hold:
pn²C(1 log(T 11)1/2)
L(Gb) L(
E E 8-
(34)
T-200
+T+ 1)1/2
17

---

The proof is provided in Appendix F.5
Theorem shows that for p--mmooth loss functions. the proposed gradient coding scheme guarantees convergence to a stationary point. Specifically, whether constant learning rate = (I +1)-77 or a decaying learning rate "/t (++1)172 is employed, the average squared gradient norm approaches
the number of iterations increases. This result confirms that the algorithm remains effective even in non-convex settings.
Lastly, conduct extended analysis for loss functions that satisfy both A-strong convexity and j--smoothness, as detailed below.
Theorem 4. Suppose the loss function satisfies Assumptions optimally structured gradient codes that
and 3
Then, it holds for any
E 1--1-111111 - 11 187-8- 3
(1 Σ
II (1 (1-7g (35)
o.
-=
p=0
@=p+1
By setting 7/2 >
lim B[1| - 33112] 6+
<
n²C
(1+
(36)
X2
Σイ 0,
By setting "/ = 1/(1t),
lim BillB++1 11000
3 < O.
(37)
The proof is provided in Appendix F66
Theorem shows that under optimally structured gradient coding in heterogeneous straggler setting, the model error comprises two parts: one diminishing with the learning rate and strong convexity, and another reflecting accumulated variance from stragglers. With constant learning rate (% y < 1/A), the algorithm quickly converges to bounded neighborhood of the optimum, where the neighborhood size depends on straggler variability. In contrast, decaying rate (7/ 1/(A() ensures convergence to the true optimum over time. This highlights a key trade-off: constant rates yield faster initial progress, while decaying rates achieve asymptotic optimality.
18

---

Discussions
C.1 Practical Example of Probabilistic Straggler Modeling
Suppose denote the response time limit for each training iteration. A worker node E [1 :]] classified as straggler its overall delay 7, for local gradient computation and communication exceeds this limit, i.e., Ti > Tth and the straggler probability of worker node i can be obtained by
ps = Pr(t. > Tek).
(38)
The modeling of stragglers depends on the system's primary wotteneck-whetthr lies in computa- tion or communication. For instance, in communication-liman wireless networks is often modeled by an exponential distribution [17]. contrast, for computation- limited settings, computing latency is typically characterized by shifted-exponential distribution
environments, straggler behavior in
18 19.
Intuitively, a worker node's likelihood of becoming a straggler is influenced not only by its inherent stochastic latency-driven by factors such as computation and communication capacity- but also by the response time threshold, Teh- tighter threshold increases the probability of stragglers but accelerates each training iteration. This reveals a fundamental trade-off between mitigating straggler effects and achieving faster model updates. Our experiments empirically demonstrate this trade-off and show that the proposed scheme achieves an effective balance between the two.
C.2 Worst-Case Computation Load
The maximum computation load on single worker is a critical metric for practical deployment, and framework is explicitly designed to address this. In our schemes, each worker i's computation load b; the number of assigned data partitions. Thus, the worst-case computation load is max4e(1:A] 4;-
Our method allows for flexible-thougl not entirely aebitrary-adjustmeen of the parameters b,,...,by based on straggler probabilities and the computational capacity of each worker. The proposed Schemes I and II leverage the constraint Σie[l:N] 6; = + k 1 to reduce the compu- tation load, which inherently imposes mathematical upper bound on the worst-case computation load, given by [1:k, b; S n + 2. For instance, this bound can be achieved by assigning b, 1: 2, by 2, ...... bb-1 2, and by 1. Moreover, assuming the total dataset can be partitioned into subsets of approximately equal size, the number of data partitions can also be selected accordingly. Under this scenario, choosing = & ensures that the worst-case computation load is at most 2.
Thus, system designers can flexibly constrain max by based on specific hardware limitations, effectively preventing any single worker from becoming overloaded while still optimizing overall system performance. For example, the example (Figure 2) in Section (3.2 presents scenario with n = 4 data partitions and = 3 worker nodes, where the allocation parameters are set as b1 = 3, b2 2, and by 1. In this case, the worst-case computation load is [a: b; 3. To reduce this worst-case load, the parameters can be rebalanced to by = 2, b2 = 2, and by = 2, resulting in a lower worst-case computation load of m 0, 2.
Importantly, the average computation load d = (n m k 1)/n remains strictly below 2 (since k < rt), ensuring overall efficiency. In summary, our framework offers both per-worker load control and high average efficiency, making it well-suited to heterogeneous real real-world systems.
C.3 Sparsity of Optimally Structured Gradient Coding
The number of non-zero entries in the matrix a corresponds to those in the encoding matrix A, which directly determines the computation load on each distributed node. Therefore, constructing a sparse a matrix is equivalent to reducing the computation load.
In this context, we focus on constructing sparse matrix. The matrix a can represented as a bipartite graph G (R, C, E), where the row and column indices of a form two disjoint vertex sets, R and C, respectively. An edge (i,j) exists between i R and j E C and only if of A with the corresponding edge weight given by af To preserve the optimal structure of the gradient coding scheme, the graph must satisfy two constraints: for each vertex E R, the sum of the weights of
19

---

edges incident to i must equal Y;; and for each vertex j E C, the sum of the weights of edges incident to j must equal I.
Assume that G contains o disjoint and connected subgraphs, denoted as S1, S...... So S G. Fach subgraph S consists of row vertex set R S R and column vertex set Ct E C, respectively. According to the optimal structure, for each subgraph St. AI E [1 o). the sum of edge weights incident to each vertex E R2 must equal Y, and the sum of edge weights incident each vertex j E C1 must equal 1. Therefore, the total edge weight in any connected subgraph is EieR, Y, which is equal to EEE,, 1. Thus, we have
(39)
IER,
iEC,
where this structural dependency arises because the row-wise sum and column- sum are combi- natorially coupled. Note that the graph G always satisfies the connectivity rule, i.c., EieR R Y; [C], = n and |C| = n. It is well known that any
since Eien Y; = E/ - o5
"
connected graph St, for I E o). must contain at least [R|] + |Cr] - edges. In Section 3.2 we introduced a gradient code construction method for the case in which the overall graph connected and contains exactly + k 1 edges-the the minimum required for connectivity. This approach can naturally be extended to connected subgraphs. Specifically, for each connected subgraph, a submatrix is constructed using only the row indices in R2 and column indices in C₁. following the same con- struction strategy. Therefore, to maximize the sparsity of the optimally structured gradient code, the overall graph G should be partitioned into the largest possible number of connected subgraphs, each containing the minimum number of edges required for connectivity.
Based on these observations, we introduce sparse code construction algorithm. Inspired by the binary tree structure, the algorithm recursively partitions the graph into two disjoint subgraphs, ensuring that the sum of edge weights in each subgraph remains an integer to satisfy the connectivity constraints. Equivalently, this can be viewed as dividing the values YI...., that the sum within each group is positive integer.
......,Y, Yy into two groups such
Initially, we define a working set of subgroups, denoted V, and initialize it as y {Yi..... Vz]. At each iteration, every subgroup 3) ) is split into two disjoint subgroups. 2n and 2022) such that Exexpo Y, Σ for all j E 1,2. These two subgroups then replace Vi in the set y.
This recursive partitioning process continues until no further valid subdivisions are possible. At this point, for each remaining subgroup V E V/ we define the corresponding row vertex set as R = (ily; E M/-- Starting with = 1, we construct the corresponding column vertex set C by sequentially selecting EiER, Y. elements from the global column vertex set C. Finally, the submatrix of a corresponding to each subgraph St is constructed using the method described in Section 3.2 Further details can be found in Algorithm
If the maximum number of subgraphs is Omax. the computation load is computed as
d Eie( [100m))) ([Rg) + |C|| 1)
(40)
n
C.4 Extensions
C.4.1 Extension to Mini-Batch SGD
Our method fundamentally builds upon and analyzes GD-like algorithms, but it can readily be extended to mini- SGD algorithms. In distributed learning, each distributed node can apply our proposed method by computing gradients using mini-batch sampling their local data partitions (D E B,). This approach can effectively reduce the update time per training iteration.
However, batch sampling introduces randomness at each iteration. Hence, the expectation must now represent expectations over both the randomness from stragglers and mini-batch sampling at the (-th iteration, conditioned on the model parameter. Since the behaviors of stragglers and mini-batch sampling are independent, the expectation [-[-] now represents the expectation over both. The objective from problem (P1) is to minimize the residual error of the aggregated stochastic gradient
20

---

Algorithm The Sparse Code Construction Algorithm
Calculate Y1, Y2,,., Yu.
y (Y,, Y2, ,,,, Yis and y" 0.
while D # |3 do
V" < and =
for }/ E ) do
Search the two disjoint groups 21 ,,(²)) from V/ satisfying Exero Y,E 2,, Vj {1,2).
y y' ") end for end while for 3/2 e y do Construct the subgraph St with R = {i Y E )i) and C = {ili E E EiER, Y;
EiER, Yi)
Construct the submatrix of a corresponding to the subgraph Si as in Section 3.2 end for
estimator, g(t) = Ei, [w " where of the stochastic gradient computed from mini-batch 21 The residual
within data partition Dy. The objective function is thus to minimize E, [119(*) |0 error can be decomposed as:
E2 1000 -00
13000
1
E,
( gg())
+ (g
-
|| g(())
|| | g(
E,
E
(D Straggler Variance
(ID Sampling Variance
This separation is valid because the cross-term is zero, as Esampee (g - g(t)] = unbiasedness).. First, Term (I) the original error from the paper, which is bounded as:
(due to the
E2 1
SC
5
Second, for Term (II), we first take the expectation over the independent mini-batch samples:
E, (0(0)
3001 = E.
Σ
1 - ))
k
27
Eeample 11050
|13
Eurragler
93 Tawaass
27 g7.
12
S
2
Estageler
Lwgais
where 2² denotes an upper bound on the variance of the mini-batch gradients, that is, Esampte 119)
(1) | < o². Using || (B[XX) and the unbiasedness condition Σ, (1-p111puu p.)aaaa
21

---

Σ, af = 1, the inner expectation becomes:
)
| Var
27
+ +(B
Larsann 1)
Estngller
Σ Lewran.)
Σ Uwwarss
Σ
k
(a))2
Pi
+12 + 2
+
dz(ag)e
1 p3
im
iml
Thus, Term (II) is bounded by 0² Σラ=ı (1+ Ei= ) o2n 0² Σ 8, (a))
Combining the bounds for both terms, the total objective is to minimize the upper bound. After dropping the constant term o²n, which does not affect the solution, the objective becomes min- imizing Eie(LA) 6, [)E(tm](a)) + ((EjE(Im)) )²) subject to the unbiasedness constraint
Eielish 0² 1.
This reformulated optimization problem, adapted to the mini-batch SGD setting, can be explicitly solved using the KKT conditions. This yields dense, closed-form solution:
6
(a))
Vi [1: k). e :..
(41)
Eiepraj 8,
While this solution is theoretically optimal, requires full data replication across all worker nodes (d = kt), meaning that each node must store the entire dataset. This assumption is often impractical in distributed systems due to excessive storage and computation costs.
On the other hand, our proposed schemes (Schemes I and If), which are formulated and constructed based on the GD algorithm, are specifically designed to maintain a low data replication factor, ensuring d < 2 in both schemes. When our proposed schemes, which are optimized for the full-batch GD setting, are directly applied to mini-batch SGD, the resulting gradient estimator does not achieve the theoretical minimum residual error with respect to the true gradient. Nonetheless, approach maintains the important advantage of significantly reduced data replication under the mini-batch SGD setting.
This observation highlights a trade-off when applying mini-batch SGD in distributed learning. Achiev- ing the theoretically minimum residual error requires each worker node to handle substantially increased computation load, which can accelerate convergence. contrast, by utilizing our optimally constructed GD- gradient codes and applying mini-batch sampling over the data partitions assigned to each worker, one may not reach the theoretical minimum of the residual error, but can substantially reduce the computation load per worker node. Note that since the mini-batch SGD pro- cess introduces an inherent variance from sampling, our gradient coding scheme, which is optimized for the GD) algorithm, does not perfectly mitigate this particular sampling variance.
In particular, implementing mini-batcl SGD using our proposed schemes results in a residual
error bounded by n²C 6, + no² (1+ Σt 8, This introduces an additional term,
n -- ), due batch sampling, compared the result in Lemma 2 of the paper; however, within our convergence analysis (Theorems 2 and 4h, the scaling term C (1+ + Et_ 5-1) is
only slightly modified to n²CC. (1+ 2is no² remains essentially unchanged.
and thus the convergence rate
ΣE. 6,
C.4.2 Extension to Adaptive Gradient Method
Our proposed method improves convergence speed by ensuring unbiasedness in the gradient estimator while reducing variance. This has been effective for maddient-escent-Ile optimizers, which use only the first moment estimator for updates. However, in adaptive gradient methods, which also utilize the squared gradients for second-moment estimation, maintaining unbiasedness while reducing variance faces inherent limitations in decreasing the variance term of the second moment. The reason is that preserving unbiasedness inevitably causes Eillg - Øll2] to accumulate as variance. This, in turn, systematically inflates the denominator in Adam 's update rule, leading to excessive
22

---

step shrinkage and possible performance degradation. In summary, this is manifestation of the bias-variance tradeoff: foreing bias zero can hinder squared gradient estimation, which inherently contains both bias and variance components.
To address this, we additionally propose two-track decoding approach. This scheme preserves the first-moment estimation of the original method while, for the second moment, allowing a slight bias to reduced the variance, thereby leading to a more accurate second- moment estimate overall. The implementation introduces negligible overhead, as the encoding remains unchanged and the master node simply uses two decoding vectors during decoding.
Since the encoder is fixed, we focus on designing the decoder. Designing a decoder that reduces both bias and variance leads to solving the following problem, where is used instead of w for notational clarity:
min A I -
Ea-
1E p. p1 p.)o Σ
a1.))²
(42)
The first term corresponds to bias reduction, the second to variance reduction, and A determines the relative emphasis on reducing bias. The solution can be derived by:
nd
(43)
pi a1 and) A
Using the proposed Schemes I II generate the encoding matrix A, the master node applies the original w for the first-moment estimation and the above v for the second-moment estimation, decoding each separately to obtain the gradient estimators. These are then used to update the model following the update rule of optimizers such as Adam. In Appendix E. Figure 7 demonstrates that because conventional gradient coding techniques are designed for cradient-descent-ike methods, which primarily rely on the first moment, they face inherent challenges in adaptive gradient methods that also require stable second moment. The results also highlight the effectiveness of the two-track decoding technique for these adaptive methods, indicating a need for further research and analysis into gradient coding schemes that are compatible with various optimizers.
C.4.3 Extension to Non-Smooth Loss Function
For the non-smooth case, while not explicitly detailed in the paper, our method's convergence is guaranteed under the well-established analysis in [22). Specifically, the convergence analysis presented in [22 holds as long as two key assumptions are satisfied both of which are met by our method:
Unbiased estimator:
Our method is designed to provide an unbiased estimator of the gradient (t) as enforced by the condition in Equation (12).
Bounded variance: Our optimally structured coding scheme ensures a formal upper bound
on the estimator's 's variance, proven in Lemma 2
Since our algorithm meets these conditions, the convergence guarantees established by (22 for non-smooth settings can directly apply our method. This confirms the theoretical robustness of our proposed method for a broad range of practical applications.
C.5 Limitations
One important limitation of our approach is the substantial communication overhead incurred during the initial distribution of large datasets: because each data partition D; must be replicated to d worker nodes before training begins, network load grows with both dataset size and replication factor. Additionally, our design relies on knowing each worker node's straggler probability p; a priori, yet obtaining reliable estimates is challenging because existing straggler models cannot fully capture the diverse, interacting factors- such as network congestion, CPU/GPU heterogeneity, energy throttling, or transient OS interrupts- that actually cause worker nodes to slow down drop out. Exploring and validating more practical, multifactor straggler models therefore remains an important avenue for future work.
Nonetheless, to overcome this limitation, a practical estimation approach can be applied in a real- world distributed learning environment:
23

---

The most practical approach is for the master node to estimate each worker's is straggler probability by simply counting how often a worker exceeds the deadline, based on historical logs, and updating this estimate periodically. For example, the master can track how many times each worker was late out of the most recent tasks, and use this frequency as the current estimate of the straggler probability. This method is commonly known as empirical maximum likelihood estimation (MLE).
Another practical approach is estimate each worker node's straggling probability p; using a well-modeled estimator, as proposed in [18] [9]. Specifically, task completion times can be modeled using parametric probability distributions, such the shifted-expon shifted-epponentall distribution employed in [18]. By fitting this distribution to observed runtime data, we obtain reliable estimates of Pt, Vi, representing the probability that worker fails meet the deadline. These estimated values can then be directly integrated into our coding scheme as fixed parameters. Experimental results 18] conducted on a real EC2 cluster, demonstrate the effectiveness of this method in enhancing the speed and robustness of distributed learning systems. In our own experiments, we adopted this same estimation approach for p3 and based our evaluations on the resulting values.
24

---

D Implementation Details
The experiments are conducted on one NVIDIA GeForce RTX 3060 GPU (12 GB), six NVIDIA GeForce GTX 1080 GPUs (8 GB each), and twelve NVIDIA Tesla P100 GPUs (16 GB each) (pro- vided through Kaggle Cloud). Due to the memory limit, we use the gradient accumulation technique, which divides each training batch into smaller sub- batches processed sequentially; gradients are accumulated over these steps before performing a single parameter update, effectively simulating larger batch size without exceeding GPU memory constraints.
We compare design with benchmarks follows:
GD: GD updates parameters using the true gradient g which makes it immune straggler effects and represents an ideal centralized learning scenario.
IS-SGD Seemore-Stragglle SGD): IS-SGD assigns disjoint data partitions to each node (i.e., d = 1) to avoid redundancy, yet it remains subject to straggler effects, which it does not mitigate but essentially ignores.
BGC g
(Bernoulli Gradient Coding): BGC, each encoding coefficient generated according to Bernoulli distribution, i.e., Gi,j ~ Bernoulli(d/K) for all i,j, while all decoding coefficients are fixed u:
EHD (ERASUREHEAD); EHD constructs encoding coefficients using the FR code [5] and sets the decoding coefficients uniformly to for all nodes.
OD [1] (Optimal Decoding): OD determines the encoding coefficients aij E {0, 1} using a random graph, and dynamically computes optimal decoding coefficients w; for the straggler effect reduction in each iteration.
SGC [2] (Stochastic Gradient Coding): SGC employs the pair- data distribution strategy to build an unbiased gradient estimator, with redundancy determined as in [12]. To accommodate heterogeneous straggler scenarios, we modify the approach by setting for all i, j. while keeping
dijj [1]
for all nodes.
The methods BGC, EHD, OD, and SGC incorporate the data redundancy of approximately d
25

---

STOP
STOP
STOP
STOP
(a)
(b)
(c)
(d)
STOP
STOP
STOP
(c)
g
Figure 5: Detected objects of sampled image: (a) GD (b) Proposed (c) SGC (d) EHD (e) BGC (f) OD (g) IS-SGD.
Go
2.000
04-
Comppladionoad
Compovation
(a)
(b)
Figure 6: Convergence graph with respect to the computation load with RetinaNet: (a) Tih. 1.1
(b) Tp = 1.5.
E Additional Experiment Results
Figure 5 displays the detection results on representative image from the COCO validation set. The straggler-free GD identifies three objects-two parking meters and one car-and the proposed design detects exactly the same three objects, with no extras. In contrast, SGC erroneously splits one parking meter into two overlapping detections and therefore returns only one car and one (duplicated) parking meter. EHD, BGC, and OD each find just single parking meter, missing the car and another parking meter, while IS- SGD mistakes one parking meter for two separate instances. These results demonstrate that our method delivers GD-level detection quality while simultaneously neutralising straggler effects.
Since the achieved performance depends on the specific model or dataset employed, we have additionally conducted supplementary experiments using the state-of-the-art RetinaNet model to benchmark performance. RetinaNet, with approximately 34 million parameters, is roughly 6.3 times
larger than the model (5.4 million parameters) employed our experiments (Section 4 Figures 6(a) and ((b))((llsse illustrates the convergence behavior with respect to the computation load d for à = 10
26

---

AlI'
0-002
08-
B402
04-
Beardon
Figure 7: Convergence graph with respect to the training iteration T with Adam optimizer (Ti 1.1 and 7/- 0.001).
and Teh = 1.1 and 1.5, respectively. Based on these results, it can be seen that the proposed method consistently maintains the performance trends identified Section regardless the model size.
Moreover, in Figure 7 we evaluate the convergence behavior with respect to the training iteration 7 to assess the performance of the two-track decoder with A 1 detailed in Appendix C.4.2) We observe that gradient coding schemes for the first moment exhibit slower convergence speed compared centralized Adam. However, the performance gap between the baselines notably smaller with the Adam optimizer than with GD. This reduced difference is primarily due to Adam's 's intrinsic noise suppression effect. In contrast, the proposed two-track decoding mitigates the second-moment estimation егror inherent in conventional gradient coding. While this approach yields significant performance improvements and shows extendability, a more comprehensive analysis of these results required in future research.
27

---

Proofs
F.1
Proof of Lemma
From the equations
12p. we have
27
Eellgg
= E
Σ
0j
1
Σ
Is waass
(44)
1=1
1=1
1 waas.,i ) (1
(8)
Eg
Σ Wydijj
(45)
11
12
i=1
(a)
E2 Σ waaii Σ wiaiia
1 W;
)
Σ 1 w
12
(46)
E> j==1
E.
I Waajj
I wed -11.
(47)
where (a) and (b) come from the boundedness assumption of the gradient and the unbiasedness of the gradient estimator, respectively. Furthermore,
]
1
Σ 11 u,aaija
(48)
c
1 + E,
Li wa W22 ai O22.j2
Σ
I
w as
af
aisz
(49)
1=
1= 1,
i=1
k 21 - p.) wFat aitz
(1 pi)² n as 01jz +
(50)
1=1
2=1
where (c) because E, [ I,] Ee [T],, and (d) is due
E
Σ
Mú, Tbg wi, Wirai aiz.3z
Σ Σ
(1-ph) pt,)(1 pbo) Wig0ii aig.j
i2
(51)
Pit) wii aigvi Σ
(1 Pia) wiy aiz.3
(1 p²) u unaa,,h 0i,j
(52)
1- - p.)2 w ai as,d2
(53)
Putting together, have
& 1
Σ ai,j )
E, -1000
Σ
p.(1 p.) wp
(54)
i=1
1=1
F.2
Proof theorem
The Lagrangian function of (P3) is
((a)
5,
Σ
59
(55)
j=l
1=1
where Cj is Lagrangian multiplier.
28

---

By Karush-Kuhn- Tucker (KKT) conditions, we have
ac 26; 0a E i= of 1,
EE= at)
+ =,
(56)
From the KKT condition on stationarity, we have
81
82
Σ
a
8n
Σ
o
(57)
Then, let X 6, Eo a/. vi and using the primal feasibility, i.e., Σ ii=1 og 1, Vj, we have
d
n
x 6,
Σ
= =n
(58)
==1
and thus,
X
(59)
Accordingly, the optimal gradient codes, which minimize the gradient estimation error under the unbiasedness constraint, be obtained when matrix satisfies the following conditions:
Σ (af))= = Yt, Vi, and Σ (at) 1,
(60)
where (a?)* is the optimal ag and Y; 0,-1 Σ 6
F.3 Proof of lemma
From Lemma and Theorem we can easily derive the bounded residual error of gradient estimator for any optimally structured gradient codes in the following:
)
27
(lllg
g(+) [3]
C
Σ
6,
Σ
(a))-)
(61)
)=1
Sn²C.
(62)
Σ 5-1
where a² = wraai (a represents the optimal az. and 5,11 1-a. Furthermore, the squared norm of the gradient estimator for any optimally structured gradient codes is bounded by
E. 3
(0 - ( 1221 + 12
(63)
> E(a25") )
5, cC n² Σo.
(64)
i=1
= n²C. (1+
(65)
Σラ 8-1
F,4
Proof of theorem
Our proof builds upon the result from 200 which demonstrates that any algorithm utilizing an unbiased estimator of the true gradient achieves convergence rate of O(1/T):
Lemma 3. (Lemma 1 in (201) Suppose the loss function is X-strongly convex and the gradient estimator is unbiased. Furthermore, assume Eellgg() (t)
[ < G. Then, by setting "tt = 1/(xt), the
following holds for any T that
4G
Bll| - 1111)11
(66)
XT
29

---

Building on the result from Lemma] 2 we can conclude that
(1 (1+
E. EIlgl S n²c
(67)
Li=1
Thus, by replacing G with the right-hand side of the above inequality, Lemma
3 yields
4n²C
1
Br 3-11 -
1
(68)
X²T
Σ 8,
where 6-
1-ps
F.5
Proof of theorem
From the property of p-smoothness,
L(3++1) L(3, To. -g(0
(69)
S L(B))) - (090 n7 g001)
107
1 12
(70)
By taking the expectation E,[-] conditioned on the previous iteration on both hand sides, we have
E, (T( [(B,) (g Ee[g("))
+
pn
E
(71)
2
@ - - 71 (lg pnZneC
1
(72)
2
Σ
where (a) comes from the unbiasedness of gradient estimator and Lemma [|] on both sides and rearranging, we obtain
2
Taking full expectation
wyin²C 7 (1 E[L(B.] - B(L(G,
(1 (1+
(73)
Σラ 0,
Based on this inequality, we have
Um²C
(
Σ 7/- [lg ( L(B)) B[L(BT+1)]
78
2
(74)
2
Σ i==1
6,
(b) $ L(Bb) L(B3) + cn²C
(1+
1
T
2
(75)
2
Σ
8-1
1=0
where (b) is due to ([L(Gr++1) 2 L(B"). the learning rate is fixed, i.c., 7tt = = 1/(T + 1/2 we have
T
Bilg (9 1131 < L(Bo) L(3))
un²C (1
1
(76)
(T'
(T + 1)1/2
Σt= 5-1)
T=U
where the following limit holds:
L(B)) L(3*) + untC.
1+ 2 2i 6,
lim
0.
(77)
(T + 1)
Moreover, if the learning rate is decaying, i.., 7 1/(t + 1)2/2
we have
" > (T + 1)12
Σ
(78)
(t 1)122
30

---

Thus, using this relations,
Elllg 11 _ L(Bb) (180)-((8))
1
1
(1
1+
T+1
(T+
(T + 1)1/2
2
Ei=1o
i+1
(79)
pn pn² + log + 1)1
1
( T.(3)) - T((g')
Σ5
(80)
(T 1)
1
where (c) is due to the fact Et= limit holds:
I T-i
S 2 + log(( (T + 1). Since lim
log
0, the following
pn + log (T + +11122
I(Go) - L(
Σx 2i-1 57
lim T-200
0.
(81)
(T + 1)
(T + 1) 1)1//
F.6
Proof of theorem
Since B:-1 - Br 12.-70 g((0)
1 = 113, - 33 - ni 1
(82)
Then, by taking expectation of both side conditioned on B..
E. ||+ 33' = 1; 3 -
(83)
|| 13 27 [3) (3) ,े- E. [1] 1|21
(84)
(a)
||3 3 + 27 (L(8r) L(Bi) 2/ 11... 11) + n²C (1+
(1+5
Σイ
07
(85)
= (1 - -()) 1| - -311 + 2T (I(B*) I(Bi)) + + nnC. (1
(86)
Σk i=
5,
S (1 7:A) ||B. - 33
(b)
7t (0 + 2/ n²C
11
1
(87)
Σ 8,
< (1 xc) 1|. 132 . n²C (1+
(88)
where (a) holds from the X-strongly convexity and Lemma function L. Specifically,
2 (b) due to p-smoothness of the loss
1 VI(BB) < I(B.) I ( P
1 VI(()) + " - VI
VL((.),
(89)
P
P
= L(3))
(90)
2/
Using the relationship L(B') L B: AVL(8)).
L(B") - L(B)) -
VL(3))]
(91)
2μ
Taking full expectation of both side in 87 we have
r2 n²C. (1+
Ell| 3-11 < (1 - n>) E B - 3
(92)
E 5,1
31

---

Then, using this inequality recursively, the following inequality holds.
-1111+1--01111 < 1110--91122 II (1 () ( (+ Ex=
II 11
07
p=0
g=p+1
(93)
If Jt - < 1/A, V and 00.
(1-)))tt)t + m2²
A (1
Ei=18 8, )
lim E|1|
lim 13 - 33-12 (1 72) t-00
1
(1 -
t1000
(94)
n²C x2
[
(95)
Furthermore, if Tt = 1/(21) and - 00,
- !
p) + n²C. ( (1+
lim B11 -31 < 60000
lim Billg - 311 +000
x
Σ ΣΣ
II
(1-1) 1
1
p=1 X2p
q
22t2
q=p-1
(96)
lim O
(97)
1 t-100
0.
(98)
32


Reviews:
[{"review_id": "VJoFhcwIBV", "reviewer": "Reviewer_uuQF", "summary": "The paper studies distributed gradient descent with the presence of straggler nodes. Linear coding is used to combat stragglers, by allocating segment $i$ of the data to $d_i$ workers, and sharing a linear combination of the gradients with a central server. The gradients are then (approximately) decoded (linearly) from the set of non-straggler nodes. The main technical problem the authors solve is: design the encoding and decoding matrices such that the gradient variance is minimized under the constraint that the gradient estimate is unbiased.\nUnder bounded gradient assumption, the optimization problem (variance and unbiasedness conditioin) is rewritten as a function of the encoding/decoding coefficients and formulated as a convex optimization problem.", "questions": "Could the authors discuss the worst-case computation load across nodes?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength:\n1. The paper is well-written and easy to follow.\n2. The authors propose optimal (minimizing variance) encoding schemes that also have a low computation load (average number of replicates across partitions).\n3. The condition of unbiased gradient is reasonable as it guarantees convergence of GD.\n4. The authors additionally prove properties for the optimal encoding scheme.\n5. Simulation results show better GD convergence compared to baselines.\n\nWeakness:\n1. The authors look for an encoding scheme with low computation load. However, the computation load is defined as the average number of repetitions for each partition, and does not take into account how these repetitions are allocated across nodes. Another important quantity is the load per worker node; namely: the maximum number of partitions allocated to a single worker.\n2. While the original formulation of P2 is non-convex due to the multiplication between $w$'s and $a$'s. The products can be absorbed into a single variable to reach a convex optimization problem.", "was_revised": true, "final_justification": "The authors have addressed my concerns. I choose to remain the original rating.", "rebuttal": "We thank the reviewer for their thoughtful comments and questions. Below is our detailed response to address the concerns raised: \n    \n***[Weakness-1 and Question-1]***\n\nWe agree that the maximum computation load on a single worker is a critical metric for practical deployment, and our framework is explicitly designed to address this. In our schemes, each worker $i$’s computation load is $b_i$, the number of assigned data partitions. Thus, the worst-case computation load is $\\max_{i \\in [1:k]} b_i$.\n\nOur method allows for flexible—though not entirely arbitrary—adjustment of the parameters $b_1, \\ldots, b_k$ based on straggler probabilities and the computational capacity of each worker. The proposed Schemes I and II leverage the constraint $\\sum_{i \\in [1:k]} b_i = n+k-1$ to reduce the computation load, which inherently imposes a mathematical upper bound on the worst-case computation load, given by $\\max_{i \\in [1:k]} b_i \\leq n-k+2$. For instance, this bound can be achieved by assigning $b_1 = n-k+2$, $b_2 = 2, \\ldots, b_{k-1} = 2$, and $b_k = 1$. Moreover, assuming the total dataset can be partitioned into subsets of approximately equal size, the number of data partitions $n$ can also be selected accordingly. Under this scenario, choosing $n = k$ ensures that the worst-case computation load is at most $2$.\n\nThus, system designers can flexibly constrain $\\max_{i \\in [1:k]} b_i$ based on specific hardware limitations, effectively preventing any single worker from becoming overloaded while still optimizing overall system performance. For example, Appendix A presents a scenario with $n = 4$ data partitions and $k = 3$ worker nodes, where the allocation parameters are set as $b_1 = 3$, $b_2 = 2$, and $b_3 = 1$. In this case, the worst-case computation load is $\\max_{i \\in [1:k]} b_i = 3$. To reduce this worst-case load, the parameters can be rebalanced to $b_1 = 2$, $b_2 = 2$, and $b_3 = 2$, resulting in a lower worst-case computation load of $\\max_{i \\in [1:k]} b_i = 2$.\n\nImportantly, the average computation load $d = (n + k - 1)/n$ remains strictly below 2 (since $k \\leq n$), ensuring overall efficiency. In summary, our framework offers both per-worker load control and high average efficiency, making it well-suited to heterogeneous real-world systems.\n\n***[Weakness-2]***\n\nThe reviewer is correct in observing that the non-convex problem (P2) can be made convex via variable substitution. This is precisely the procedure we present in our paper to motivate our solution.\nOur narrative was structured to show the logical progression from the initial problem formulation to a solvable one.\n- We first formulate the problem (P2) and explicitly identify it as non-convex due to the strong coupling between the encoding and decoding variables.\n- We then introduce the variable substitution $\\alpha_i^j=(1-p_i) \\cdot w_i a_{i,j}$ stating that (P2) can, without loss of optimality, be transformed into (P3), which is a convex problem.\n\nOur core contribution is not the transformation itself, but the steps that follow:\n- Deriving the optimal structure (Theorem 1) that characterizes any solution to this convex problem.\n- Using this structure to develop two novel, closed-form code construction schemes (Scheme I and II) that are computationally efficient, bypass the need for a runtime convex solver, and have a low computation load.\n\nWe thank the reviewer for allowing us to emphasize that the convex transformation is a key methodological step that enables our main contributions."}, {"review_id": "AyPThODnYZ", "reviewer": "Reviewer_4m6P", "summary": "This paper studies the structured gradient coding scheme to mitigate the straggler issue in distributed learning without relying on homogeneous straggler models or data replication. The authors derive closed-form solutions for the optimal coding and decoding coefficients and propose data allocation strategies to reduce the computation load.", "questions": "The questions are primarily included in the weaknesses part.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n* The paper has a good motivation of improving the training efficiency in distributed learning, and gradient coding is important technique in distributed computing. \n* The proposed method does not require too much additional data allocation.\n* The theoretical analysis in section 3.1 is clear and easy to follow. \n\nWeaknesses:\n* We usually use (mini-batch) SGD for training in practice, and this paper also mentions batch sampling. However, it seems that the gradient $g^{(t)}$ is defined as the aggregated gradient at iteration $t$. It is unclear why the later analysis is not affected by the use of mini-batch gradients.\n* The writing in section 3.2 could be further improved, I think the amount of data sharing and allocation is still a little bit confusing. \n* The optimal structured gradient requires the known probability $p_1$ to $p_n$, which would be hard to predict during real application.\n* The experimental setup is somewhat insufficient. The model used in the experiments is relatively small, especially in the context of the current LLM era. I would suggest that the authors include some scaling-up experiments to better demonstrate the practicality of the proposed method. \n* Moreover, is the proposed method limited to gradient coding with SGD/GD optimizer? If so, it should be a limitation of the method for practical usage as well.", "was_revised": true, "final_justification": "After the rebuttal, I would like to maintain my positive score of 4.", "rebuttal": "We sincerely thank the reviewer for their insightful feedback. We appreciate the opportunity to clarify these important aspects of our work.\n\n***[Weakness-1]***\n\nWe thank the reviewer for their insightful question regarding mini-batch SGD. This prompted a deeper analysis that clarifies the trade-off between theoretical optimality and system efficiency, further highlighting the contribution of our work.\n\nOur method fundamentally builds upon and analyzes GD-like algorithms, but it can readily be extended to mini-batch SGD algorithms. In distributed learning, each distributed node $i$ can apply our proposed method by computing gradients using mini-batch sampling on their local data partitions ($\\mathcal{D}_j, \\forall j \\in \\mathcal{B}_i$). This approach can effectively reduce the update time per training iteration.\n\nHowever, batch sampling introduces randomness at each iteration. Hence, the expectation must now represent expectations over both the randomness from stragglers and mini-batch sampling at the $t$-th iteration, conditioned on the model parameter. Since the behaviors of stragglers and batch sampling are independent, the objective in problem (P3) can, after straightforward derivations, be reformulated as minimizing $\\sum_{i \\in [1:k]} \\delta_i (\\sigma^2 \\sum_{j \\in [1:n]} (\\alpha_i^j)^2 + C (\\sum_{j \\in [1:n]} \\alpha_i^j)^2)$ subject to the unbiasedness constraint $\\sum_{i \\in [1:k]} \\alpha_i^j = 1$. Here, $\\sigma^2$ denotes an upper bound on the variance of the mini-batch gradients, that is, $\\mathbb{E}_\\text{sample}[\\lVert g^{(t)}_j - \\bar{g}^{(t)}_j\\rVert_2^2] \\le \\sigma^2$, where $\\bar{g}^{(t)}_j$ is the  gradient computed from the mini-batch within data partition $\\mathcal{D}_j$.\nThe detailed derivations will be included in the revised version.\n\nThis reformulated optimization problem, adapted to the mini-batch SGD setting, can be explicitly solved using the KKT conditions. This yields a dense, closed-form solution:\n$(\\alpha_i^j)^* = \\frac{\\delta_i^{-1}}{\\sum_{l \\in [1:k]} \\delta_l^{-1}}, \\forall i \\in [1:k], j \\in [1:n]$. \nWhile this solution is theoretically optimal, it requires full data replication across all worker nodes ($d = k$), meaning that each node must store the entire dataset. This assumption is often impractical in distributed systems due to excessive storage and computation costs.\n\nOn the other hand, our proposed schemes (Schemes I and II), which are formulated and constructed based on the GD algorithm, are specifically designed to maintain a low data replication factor, ensuring $d<2$ in both schemes.  When our proposed schemes, which are optimized for the full-batch GD setting, are directly applied to mini-batch SGD, the resulting gradient estimator does not achieve the theoretical minimum residual error with respect to the true gradient. Nonetheless, our approach maintains the important advantage of significantly reduced data replication under the mini-batch SGD setting. \n\nThis observation highlights a trade-off when applying mini-batch SGD in distributed learning. Achieving the theoretically minimum residual error requires each worker node to handle a substantially increased computation load, which can accelerate convergence. In contrast, by utilizing our optimally constructed GD-based gradient codes and applying mini-batch sampling over the data partitions assigned to each worker, one may not reach the theoretical minimum of the residual error, but can substantially reduce the computation load per worker node.\n\nIt is important to note that implementing mini-batch SGD using our proposed schemes results in a residual error bounded by $n^2 C \\cdot  \\frac{1}{\\sum_{i=1}^k \\delta_i^{-1}} + n \\sigma^2 \\bigg( 1+ \\frac{n}{\\sum_{i=1}^k \\delta_i^{-1}}\\bigg)$.\nThis introduces an additional term, $n \\sigma^2 (1 + \\frac{n}{\\sum_{i=1}^k \\delta_i^{-1}})$, due to batch sampling, compared to the result in Lemma 2 of the paper; however, within our convergence analysis (Theorems 2, 3, and 4), the scaling term $n^2 C \\cdot  ( 1+ \\frac{1}{\\sum_{i=1}^k \\delta_i^{-1}})$ is only slightly modified to $n^2 C \\cdot  ( 1+ \\frac{1}{\\sum_{i=1}^k \\delta_i^{-1}} ) + n \\sigma^2 (1+  \\frac{n}{\\sum_{i=1}^k \\delta_i^{-1}})$ and thus the convergence rate remains essentially unchanged.\n\n***[Weakness-2]***\n\nThe goal of Section 3.2 is to present two specific data allocation and code design methods (Schemes I and  II) that satisfy the optimal conditions proven in Theorem 1, while also reducing the computation load caused by data redundancy in a practical distributed system.\nThe key difference between the two schemes lies in their data sharing structure:\n- Scheme I: A single, specific data partition ($\\mathcal{D}_1$) is a common partition shared by all workers, while the remaining partitions are assigned exclusively to individual workers. This scheme has a centralized sharing structure.\n- Scheme II: Each worker shares exactly one data partition with the worker of the adjacent index, so every partition is held by at most two workers. This scheme has a sequential and decentralized sharing structure.\n\nFor further clarity, explicit construction examples of the matrix $\\alpha$  for both schemes are provided in Appendix A. \nBoth schemes are designed to reduce the computation load to $d=(n+k-1)/n$ by ensuring the total number of partitions held by each worker ($b_i$) sums to $\\sum_{i \\in [1:k]} b_i =n+k-1$.\nThis is an efficient structure where only $k-1$ additional data replications are needed across the entire system, ensuring that each partition is computed $d$ times on average.\nThrough these structural designs, we aimed to minimize the excessive data duplication and computational burden that can occur in real-world systems while maintaining theoretical optimality. \nReflecting your feedback, we will improve our writing and add a new illustrative figure clearly demonstrating both sharing schemes with a concrete example, which should avoid any remaining confusion.\n\n***[Weakness-3]***\n\nWe acknowledged this as a limitation and  explicitly mentioned this issue in Appendix C.3 (Limitations) of our paper.\nNonetheless, to overcome this limitation, a practical estimation approach can be applied in a real-world distributed learning environment: \n- The most practical approach is for the master node to estimate each worker's straggler probability by simply counting how often a worker exceeds the deadline, based on historical logs, and updating this estimate periodically. For example, the master can track how many times each worker was late out of the most recent tasks, and use this frequency as the current estimate of the straggler probability. This method is commonly known as empirical maximum likelihood estimation (MLE).\n- Another practical approach is to estimate each worker node’s straggling probability $p_i$ using a well-modeled estimator, as proposed in [18, 19]. Specifically, task completion times can be modeled using parametric probability distributions, such as the shifted-exponential distribution employed in [18]. By fitting this distribution to observed runtime data, we obtain reliable estimates of $p_i, \\forall i$, representing the probability that worker $i$ fails to meet the deadline. These estimated values can then be directly integrated into our coding scheme as fixed parameters. Experimental results in [18], conducted on a real EC2 cluster, demonstrate the effectiveness of this method in enhancing the speed and robustness of distributed learning systems. In our own experiments, we adopted this same estimation approach for $p_i$ and based our evaluations on the resulting values.\n\n***[Weakness-4]***\n\nThank you for your valuable suggestions. Since the achieved performance depends on the specific model or dataset employed,  to address reviewer's concern, we have newly conducted  supplementary experiments using the state-of-the-art RetinaNet model to benchmark performance. RetinaNet, with approximately 34 million parameters, is roughly 6.3 times larger than the model (5.4 million parameters) originally employed in our paper. Due to restrictions on PDF uploads for this review, we  directly provide the  experimental results of each method. Specifically, we have reproduced the experiments depicted in Fig. 3 of the submitted paper with the new model. After 50 training iterations, \nfor the threshold $\\tau_{th}=1.1$, the loss values are as follows: GD achieves 0.1875, the proposed records 0.2178, SGC is 0.2485, EHD is 0.8201, BGC is 0.8840, OD is 0.8533, and IS-SGD reaches 1.1073.\nFor $\\tau_{th}=1.5$, GD remains at 0.1875, while the proposed achieves 0.2144, SGC is 0.2389, EHD is 0.2520, BGC is 0.2567, OD is 0.2839, and IS-SGD records 0.4120. \nBased on these results, it can be seen that the proposed method consistently maintains the performance trends identified in the paper, regardless of the model size.\n\n***[Weakness-5]***\n\nWe thank the reviewer for this insightful comment. We agree that evaluating our method with modern optimizers like Adam is important. We would like to clarify that our proposed framework is not limited to GD/SGD optimizer. This is because gradient descent-based optimizers—including GD, SGD, and Adam, and RMSProp—first compute a gradient or its estimator, and then update the model parameters according to their own specific update rules using this information. \nOur core contribution is an optimizer-agnostic method for generating a high-quality gradient estimate in heterogeneous straggler environments. The problem is formulated to find an unbiased estimator that minimizes the residual error (i.e., variance). This optimization and the resulting coding structure (Theorem 1) depend only on the straggler probabilities, not on how the gradient estimate is later used by an optimizer.  Therefore, the proposed method for calculating the estimator remains unchanged when using other gradient descent-based optimizers, while the achieved performance may vary depending on the choice of optimizer."}, {"review_id": "QvGUkIXFae", "reviewer": "Reviewer_eHLb", "summary": "This paper proposes an optimally structured gradient coding scheme to mitigate the straggler problem in distributed learning. To tackle with the stragglers in the real-world heterogeneous systems, an optimization problem is formulated in this paper to minimize the residual error while ensuring unbiased gradient estimation by explicitly considering individual straggler probabilities. Theoretical analysis of convergence is provided for strongly convex and smooth functions. The experiments show that the proposed algorithm can significantly mitigate the impact of stragglers and accelerates convergence.", "questions": "1. Is it possible to extend the theoretical analysis to non-convex or non-smooth functions?\n\n2. Is the proposed algorithm also compatible to Adam optimizer?", "limitations": "Yes, the authors adequately addressed the limitations and potential negative societal impact of their work", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. This paper proposes an optimally structured gradient coding scheme to mitigate the straggler problem in distributed learning. To tackle with the stragglers in the real-world heterogeneous systems, an optimization problem is formulated in this paper to minimize the residual error while ensuring unbiased gradient estimation by explicitly considering individual straggler probabilities.\n\n2. Theoretical analysis of convergence is provided for strongly convex and smooth functions.\n\n3. The experiments show that the proposed algorithm can significantly mitigate the impact of stragglers and accelerates convergence.\n\nWeaknesses:\n\n1. The theoretical analysis is limited to the strongly convex and smooth functions, which is less practical for real-world applications.\n\n2. For the experiments, the optimizers are limited to SGD, which is not widely used these days compared to Adam.", "was_revised": true, "final_justification": "The authors's feedback has addressed my concerns. The additional results on Adam looks good.\nIn overall, I don't see any major weakness.\nThus, I keep the positive score.", "rebuttal": "We sincerely thank the reviewer for their valuable feedback and insightful questions. We are encouraged that the reviewer found merit in our work. We address the specific weaknesses and questions below.\n\n***[Weakness-1 and Question-1]***\n\nWe thank the reviewer for their insightful comment regarding practical optimization settings.\nWe would first like to clarify that our analysis already covers non-convex functions. Theorem 3 in our paper provides a formal convergence guarantee for general $\\mu$-smooth, non-convex loss functions, ensuring our method converges to a stationary point.\nFor the non-smooth case, while not explicitly detailed in the paper, our method's convergence is guaranteed under the well-established analysis in [Shamir et al.]. Specifically, the convergence analysis presented in [Shamir et al.] holds as long as two key assumptions are satisfied—both of which are met by our method:\n- Unbiased estimator: Our method is designed to provide an unbiased estimator of the gradient ($g^{(t)}$), as enforced by the condition in Equation (12).\n- Bounded variance: Our optimally structured coding scheme ensures a formal upper bound on the estimator's variance, as proven in Lemma 2.\n\nSince our algorithm meets these conditions, the convergence guarantees established by [Shamir et al.] for non-smooth settings can directly apply to our method. This confirms the theoretical robustness of our proposed method for a broad range of practical applications.\nWe appreciate the opportunity to clarify this important theoretical connection and will add this discussion to the revised version of the paper.\n\n(O. Shamir and T. Zhang, ‘‘Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes,’’ in Proc. Int. Conf. Mach. Learn. (ICML), 2013, pp. 71–79.)\n\n***[Weakness-2 and Question-2]***\n\nWe appreciate the reviewer’s insightful comment and agree that evaluating our method with modern optimizers such as Adam is important. We would like to clarify that our framework is not restricted to GD/SGD; rather, it is compatible with any gradient-based optimizer. This is because optimizers like Adam and RMSProp first compute a gradient (or its estimator) and then apply their own update rules using this information.\nOur main contribution is an optimizer-agnostic approach for producing high-quality, unbiased gradient estimates in heterogeneous straggler environments. The optimization problem and resulting coding structure in Theorem 1 depend solely on straggler probabilities and are independent of how the gradient estimate is subsequently used. As a result, our method remains fully applicable when used with Adam or other gradient-based optimizers, while the achieved performance may vary depending on the optimizer used."}, {"review_id": "yGMgaLHLp3", "reviewer": "Reviewer_dCZy", "summary": "This paper propose a gradient coding scheme for distributed machine learning, which minimizes residual error and maintaining an unbiased gradient estimator. Theoretical analysis and simulations are provided.", "questions": "**Questions**:\n\n1. How does the paper get the conclusion that (P2) is non-convex and (P3) is convex quickly? Can you provide more details. Are there some rules to help you get these conclusions quickly. I am curious about this.\n\n2. Lines 219-220:\n\n   > This design reduces the overall computation load on individual worker nodes.\n\n   Can you kindly explain this in detail?\n\n**Suggestions**:\n\n1. The font size of the appendix seems smaller than the font size of the main body. It may be better to use the same font size for both.\n2. Equation (61): For me, Equation (61) is unnecessary. From Equation (60) to Equation (62) is straightforward by Equations (58) and (59).\n\nI cannot guarantee a high score (for example, 5 and 6), as I am not sure whether this simple way is appreciated by the experts in gradient coding.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n\n1. This paper proposed one method that minimizes the residual error and ensures the gradient estimator's unbiasedness.\n2. This paper is very well-written, well-organized.\n3. This paper is self-contained and very clear. This is the first paper I read about gradient coding, however, it is very easy for me to follow the main idea of this paper.\n\n**Weaknesses**:\n\nAfter checking all the proofs (except the convergence analysis, i.e., Theorems 2 and 3) carefully, I have not found any serious weaknesses.", "was_revised": true, "final_justification": "The rebuttal addressed my concerns.\n\nGiven that this paper is solid, simple and clear, I maintain my positive rating.\n\nI hope that the authors will revise the paper as promised to improve the readability further.\n\nAs said in my initial review, I am unfamiliar with gradient coding. This is the only reason that I did not give a higher rating.", "rebuttal": "Thank you for the detailed review. We appreciate the time and energy you put on this work. We reply to your questions one by one.\n\n***[Question-1]***\n\nThe conclusions are drawn from standard principles of optimization theory.\n- For (P2): The of non-convexity is the presence of bilinear terms involving products of optimization variables, specifically $w_i a_{i,j}$. Bilinear terms generally lead to non-convex formulations because such terms break the positive semidefinite structure required for convexity. In our formulation, the multiplication of variables $w_i$ and $a_{i,j}$ directly results in these non-convex interactions.\n- For (P3): To restore convexity, we applied a reparameterization by defining new composite variables $\\alpha_i^j=(1-p_i) \\cdot w_i a_{i,j}$. With this transformation, the optimization variables become linearly coupled in the constraints, and the objective function reduces to a convex quadratic form in these new variables. Specifically, after reparameterization, the constraints are affine, and the objective becomes a convex quadratic function with positive semidefinite structure, clearly demonstrating convexity.\n\\end{itemize}\n\n***[Question-2]***\n\nIn both proposed schemes, we set $\\sum_{i=1}^k b_i = n + k - 1$, ensuring that each data partition is stored on at most two distinct workers. This construction ensures minimal redundancy.\n\nAs a result, the average computation load (i.e., data replication factor) per partition is $d = 1 + \\frac{k-1}{n}$, so each worker handles on average less than twice the amount of data compared to the ideal ($k \\le n$). This replication factor is significantly lower than that of exact gradient coding schemes, which require at least $s+1$ data replicas per partition, where $s$ denotes the number of stragglers.\n\nBy sharing only one partition between each worker pair, we achieve the necessary redundancy for straggler mitigation with the minimum overhead—reducing both per-node computation and memory requirements.  \n\n***[Suggestion-1 and Suggestion-2]***\n\nWe thank the reviewer for these valuable suggestions to improve the paper's presentation.\n- Font Size: We will ensure the font size is consistent between the main body and the appendix in the revised version.\n- Equation (61): We agree that the step from Equation (60) to (62) is straightforward. Your suggestion is well-taken; we will remove the intermediate Equation (61) to make the proof in Appendix F.3 more concise and clear.\n\nLastly, we would like to address the reviewer’s concern regarding the perceived simplicity of our approach. We respectfully contend that this simplicity is, in fact, a key strength—reflecting both elegance and practical utility. In contrast to prior works, which (i) were unable to accommodate heterogeneous straggler probabilities, limiting their applicability in real-world systems; (ii) relied on heavy data replication or binary coding schemes with inefficiencies; and (iii) focused solely on either residual-error minimization or unbiasedness of the gradient estimator, our work addresses all these limitations within a unified framework. Specifically, we are the first to explicitly formulate the optimal gradient coding problem under heterogeneous straggler settings, derive a universal optimal structure via Lagrangian analysis (Theorem 1), and propose two closed-form schemes (Schemes I and II) that operate with computation load $d < 2$.\n\nOur method ensures unbiased gradient estimation, near-minimal data replication, and provable convergence for both convex and non-convex objectives—all without requiring any runtime solver. Thus, the seemingly simple structure of our solution directly overcomes the key inefficiencies and limitations of prior approaches. We believe this integration of theoretical novelty and practical effectiveness constitutes a meaningful contribution to the field. Accordingly, we respectfully ask that the significance of these advancements be considered in the overall evaluation."}]

Author rebuttal:

Meta-review: This paper proposes an optimally structured gradient coding scheme to mitigate the straggler problem in distributed learning. To tackle this in real-world heterogeneous systems, an optimization problem is formulated to minimize the residual error while ensuring unbiased gradient estimation by explicitly considering individual straggler probabilities. Theoretical analysis of convergence is provided for strongly convex and smooth functions. The experiments show that the proposed algorithm can significantly mitigate the impact of stragglers and accelerates convergence.

The reviewers noted the practical applicability of solving the ‘straggler problem’ in distributed learning, and therefore faster learning overall. The reviewers appreciated the clarity of the work, and the theoretically proven optimality of the encoding under the statistical assumptions (bounded gradient).  The optimization (min-variance and unbiased estimation) is written as a function of the encoding/decoding coefficients and convexity is shown, and the optimizer is relatively low complexity.  The primary contribution of the paper was considered to be the theoretical analysis and derivation of an optimal approach with guarantees. 

There was considerable author-reviewer interaction and in final scoring all reviewers regarded the work positively.  

The reviewers raised some secondary questions regarding applicability beyond SGD, such as when applying mini-batch and/or Adam.  They also wondered about robustness for non-smooth cases, and applicability for larger size model problems.  These are good areas for potential follow on research by the authors.
Decision: Accept (poster)