Leveraging partial stragglers within gradient coding
Authors: Aditya Ramamoorthy
Ruoyu meng
Vrinda S Girimaji
Venue: NeurIPS 2024 poster (2024)
Keywords: gradient coding
stragglers
communication-efficient
Primary area: infrastructure
TL;DR: We propose a novel gradient coding protocol that efficiently utilizes partial stragglers and is simultaneously computation-efficient and communication-efficient.

Abstract: Within distributed learning, workers typically compute gradients on their assigned dataset chunks and send them to the parameter server (PS), which aggregates them to compute either an exact or approximate version of $\nabla L$ (gradient of the loss function $L$). However, in large-scale clusters, many workers are slower than their promised speed or even failure-prone. A gradient coding solution introduces redundancy within the assignment of chunks to the workers and uses coding theoretic ideas to allow the PS to recover $\nabla L$ (exactly or approximately), even in the presence of stragglers. Unfortunately, most existing gradient coding protocols are inefficient from a computation perspective as they coarsely classify workers as operational or failed; the potentially valuable work performed by slow workers (partial stragglers) is ignored. In this work, we present novel gradient coding protocols that judiciously leverage the work performed by partial stragglers. Our protocols are efficient from a computation and communication perspective and numerically stable. For an important class of chunk assignments, we present efficient algorithms for optimizing the relative ordering of chunks within the workers; this ordering affects the overall execution time. For exact gradient reconstruction, our protocol is around $2\times$ faster than the original class of protocols and for approximate gradient reconstruction, the mean-squared-error of our reconstructed gradient is several orders of magnitude better.

Leveraging partial stragglers within gradient coding
Aditya Ramamoorthy
Ruoyu Meng
Vrinda S. Girimaji
Department of Electrical and Computer Engineering Iowa State University
Ames, IA 50010.
{adityar, rmeng, vrindasg)eiastate. edu
Abstract
Within distributed learning, workers typically compute gradients on their assigned dataset chunks and send them to the parameter server (PS), which aggregates them to compute either an exact or approximate version of VL (gradient the loss function L). However, in large-scale clusters, many workers slower than their promised speed or even failure-pron redundancy within the assignment of chunks to the workers and uses coding theo- retic ideas to allow the PS to recover L (exactly or approximately). even in the presence of stragglers. Unfortunately, most existing gradient coding protocols are inefficient from a computation perspective as they coarsely classify workers as operational or failed: the potentially valuable work performed by slow workers (par- tial stragglers) is ignored. In this work, we present novel gradient coding protocols that judiciously leverage the work performed by partial stragglers. Our protocols are efficient from a computation and communication perspective and numerically stable. For an important class of chunk assignments, we present efficient algorithms for optimizing the relative ordering of chunks within the workers; this ordering affects the overall execution time. For exact gradient reconstruction, our protocol is around 2x faster than the original class of protocols and for approximate gradient reconstruction, the rean-squared-errrr of our reconstructed gradient several orders of magnitude better.
gradient coding solution introduces
Introduction
Large scale distributed learning is the workhorse of modern day machine learning (ML) algorithms.
The sheer size of the data and the corresponding computation needs, necessitate the usage of huge clusters for the purpose of parameter fitting in most ML problems of practical interest: deep learning [ etc. A typical scenario consists of a dataset D = {(xx v:)) of Ñ data points, where x, is and y: 's are the features and labels respectively. We wish to minimize 1= [(x;, Vs. w) with respect to w E Rd (w: parameter vector, I: prediction error). When D large, we can perform the learning task in distributed manner 3
M. low-rank matrix completion
loss function L = Σ
Background: We partition D into N equal-sized chunks denoted D;, E [N] (mz) denotes the set .I)...,,)),,.. where a chunk a subset the data points and distinct chunks are disjoint. Within each chunk, the assignment of the data points to the workers is identical. Suppose that there are m workers Wi ......, Wm and parameter server (PS).
distribute the chunks to the different workers and let them compute the gradients on the data points assigned to them. The PS coordinates the training by aggregating the (partial) gradients from the workers and transmitting an updated parameter vector to the workers at each iteration. In the "bascline" scheme, N m, W, is assigned D, and computes ΣiED, Vi(x,, Br. w:) (a vector length-d) and sends it to the PS. Using these, the
PS computes the desired gradient VL ΣA
N = Vi(xi, Mis w.) and the updated parameter Wr+-1
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

thereafter. Unfortunately, in many large scale clusters, workers are often slower than their promised speed or even prone to failure. This especially true in cloud platforms, where the load often fluctuates depending on system load and spot instance pricing 4 explicitly builds in the possibility of job preemption. To address these issues, gradient coding (GC) introduced in [5] incorporates redundancy within the assignment of chunks to the workers. Once given worker calculates the gradient on all its assigned chunks, it computes a specified linear combination of these gradients and sends it to the PS. An exact gradient coding solution allows the PS to exactly recover V L even in the presence of limited node failures.
Let A E I. Nx m be matrix such that As, o O if and only if D; is assigned to Wj; henceforth, we call this the assignment matrix. Let nnz(v) denote the number of non-zero entries in vector v. Let Vi and 6, denote mnz(A(i;:) and nnz(A((; j)) (using MATLAB notation). These correspond respectively to the number of times DD appears in the cluster (replication factor) and the number of chunks assigned to W (load factor). We assume that at most workers out of m are stragglers.
Let Le, = EIED, VI(x; yr, We). so that VL Σ}= 9D, At iteration t, worker W, calculates JD. for all i E supp (()))) (non-zero entries in J): and linearly combines them to obtain Bj Σi ALgSD. It subsequently transmits Bj to the PS. For decoding VI, the PS picks decoding vector r which is such that r- = 0 W, has not transmitted gy (we say that W, is straggling in this case). It subsequently calculates
N
Σ
9D.
t=1
Under the original GC model [5), for exact gradient coding, we want that Ar (the all-ones vector) under any choice of at most stragglers. This means that the PS can perform a full gradient update. For exact GC, we need % 2 + 1 for all E [N]. This setting has been studied extensively 6 7 g g 10 M. Approximate gradient coding [6] considers the scenario where the full gradient either not required (e.g.. SGD 12] works with an inexact gradient) or too costly to work with because of the high replication factor needed. In this setting, we want to design A such that || 1||2 (42-norm) is small over all possibilities for the straggling workers. Prior work demonstrates constructions from expander graphs (6) sparse random graphs [13 and [14], block designs [5 16 and the like. Within distributed training. a significant time cost is associated with the transmission of the computed gradients (vectors of length-d) by the workers to the PS
Related Work:
[8) e.g., deep learning usually operates in the highly over- parameterized regime [19 (d > N). For exact GC, if 7; 2 8 + for E [V]. then the dimension of the transmitted vectors from the workers can be lowered to d/L e (20) 21). thus saving on communication time. This is referred to as communication-eflieent GC and allows us to trade-off communication for computation. However, both 20 and 21 use polynomial interpolation in their solution. This Ieads to significant numerical instability 22 to the extent that their solution is essentially unusable for systems with twenty or more workers. This point is also acknowledged within the papers: Section V of [2]] and Section II of 20 Some work considering these issues appears in 23 under restrictive parameter assumptions.
The usage of the partial work performed by stragglers has been considered [10 24 25 26 27
28
only within exact GC (i.e., approximate GC has not been considered); some of these apply in the communication--fficieee setting. However, these approaches use multiple messages from the workers to the PS and thus incur a higher communication cost per iteration.
Consider Fig. Ta where the edge labels indicate the encoded gradients. Note that under ideal operating conditions when each worker operates the same speed, the overall gradient can be computed as long as each W/ processes its first chunk D; for i = 1..... 3. Thus, it is quite wasteful for the workers continue processing their second assigned chunk as specified in the original GC scheme; it would double the computation time. In addition, the original GC formulation ignores partial work by slow but not failed workers; in the sequel, we refer to these as "partial stragglers" For instance, in Fig. la we consider a scenario, where W1 is slow and W3 is failed. The state of the computation such that there is enough information for the PS to obtain the full gradient. However, under the original GC model, W, will either wait until it processes D2 before generating the encoded gradient to be sent to the PS, or the PS will treat W, as failed and will have to settle for an approximate gradient.
Motivation:

---

W3
W4
Wa
17
IP
Z7
27
27g
27g
27
27g
274
2;
W
W2
W
27
Di
D2
2>
Dg
Da
D1
(90, 900,
+ 20p,
+ 200s
P8
PS
(b)
Figure I: Green/red means that the worker did/didn't 't process chunk. (a) System with N = 3. Each
worker assigned two chunks that they process in top-to-bottom order. W3 failed Wi is slow. (b) arbitrary assignment of chunks to the workers (example also appears in 21).
Gradient coding can be viewed as application of coding- theore- techniques [29] to distributed learning: it allows the PS to resilient failures with very little coordination the cluster. We note here that within classical coding theory [29] most constructions of erasure codes do not consider feedback from the receiver to the sender since such feedback may be expensive or noisy when the sender and receiver
remote locations not even necessary ((30), Chap. 7). However, feedback quite easy to implement in the distributed learning setup.
We present new GC protocol that exploits a small amount of additional interactive communication to/from the P$ and the workers. greatly improves the computation- efficiency and communication-efficiee within the cluster. Specifically, our protocol efficiently leverages the chunks processed by partial stragglers. Prior work that potentially applies in our setting suffers from the serious problem of numerical instability. In contrast, our protocol provably numerically stable.
Main Contributions:
of GC while continuing to allow for efficient coordination
To our best knowledge, despite the importance of communication--fficienney there are hardly any schemes for cttpuuuiiiiaiioffffffeeeeee approximate GC. Our protocol provides an elegant way to address this problem, which in addition allows the PS to obtain an accurate estimate of the mean- square-error of the reconstructed gradient at any given point in the computation.
Prior work in the GC area ignores the relative ordering of the chunks within the workers. As our protocol leverages partial work performed by the workers, the relative ordering of the chunks within the workers is an important factor the performance of the algorithm. For large class of assignment matrices, we present an efficient polynomial-time algorithm that returns the optimal ordering of the chunks within workers.
2 Gradient Coding for partial stragglers
Our GC protocol operates under the following assumptions: (i) the workers know the assignment matrix and the ordering of the chunks within the workers, (ii) regular intervals the workers keep communicating to the PS, the number of chunks they have processed, and (iii) the PS wants the workers to communicate vectors of length d/& for integer 1.
We now provide a top-level description of our protocol; a formal statement appears in Algorithm At the beginning the training process, the PS generates a random x m matrix R with i.i.d. entries from standard normal distribution, NT.. 1) and shares it with all the workers. The workers keep reporting the number of chunks that they have processed an iteration. The PS keeps monitoring these counts, and at certain point, it broadcasts to all the workers an "encode-and -nrtrddsmn-- signal and an integer vector v length-mn that specifies number of chunks that have been processed by each node. This shares the global system state amongst the workers. For exact GC, the PS sends the mccoe-andd-transmi signal when at least copies of each D, have been processed across the cluster. For approximate GC, the PS can send the signal even earlier.

---

Algorithm 1 Findd-EncodingCoefff
Input: 8 x m matrix R. m-length state vector 15, 6; the number of chunks processed by W,.
Output: Encoding coefficients for the i-th worker EG.
1: W; forms the indeterminate matrix m x NE matrix B based on sb
2: W3 extracts the columns of B that correspond to its processed chunks. This matrix is called B
(cf. (4).
3: Worker W; solves the following minimum-fz-norm least-squares problem, where the variables are the indeterminates in B,
min min||17 @ 4 RB.
(5)
4: Set E2 B(i,:).
Following this, the workers need to decide their own encoding coefficients for the gradients that they have computed. Each gradient gD; block-partitioned into l disjoint parts gD, [k][k, k: o,..., 1. Each worker forms a matrix B of dimension m x NE that consists of indeterminates that specify the encoding coefficients of all the workers (see example in the upcoming Section 2.2). Matrix B consists of N block coolmmc,,, where each block-column itself consists of & columns of length-m,
i.e., B = (1) ((2) |... B The j-th block column, B(i) is associated with 9D. [M]],
O,...., l 1. Based on the global state vector e all workers know whether a chunk D E [N] has been processed by worker & E [m]] If DD has been processed by W,, then the i-th row of B is populated with indeterminates, otherwise these entries are set zero. Once the indeterminates found (see Algorithm T for a description), worker We encodes its gradients as
N
t-1
93
Σ
B i
9.j
[i]-
(2)
1=1
1=0
Let ē; denote the i-th canonical basis vector of length- -, i.c., it contains a 1 at location i E { 1} and zeros elsewhere. We denote
--
N copies of c.
2, N 6 E
where @ denotes the Kronecker product and N denotes the all-ones vector of length N. Recall that in the exact GC scenario, the PS wants to obtain Σ 9D, [k] for k O....., L 1. This is equivalent to requiring that
of E row-span (B), ior = 8
Our protocol is such that each W; can independently calculate their encoding coefficients, such that collectively all the workers agree on the same matrix B with the same values assigned to all the indeterminates. Towards this end, let B, denote the submatrix of B that is relevant to W,, i.e., the block-columns in which the processed chunks of W, participate. For instance, suppose that W, has processed oj < 6, chunks Diy Dia, where 1 S in < 12 < .... < inz < N. Then,
(4) W; then solves a minimum- noom ceast-squares solution to determine its encoding coefficients (see (5) in Algorithm []. This ensures the solution is unique [31 even if the corresponding problem is under-determined. Thus, the workers automatically agree on the same solution.
B B
B
B (12
B (B,,))]
Remark 1. If = 1, then it is possible to arrive at protocol whereby the workers agree to transmit appropriately weighted partial sums of their gradients. so that the PS can exacttyapproximaatly recover the sum. However, in the communication -efffifiaattn-effiiettt setting when E > 1, the encoding is no longer straightforward. Thus, ε > 1 is the main scenario we consider in what follows.
Remark 2. We discussed that each worker can form the To X N matrix of indeterminates B for the sake of ease of explanation. In fact, W; only works with Bj, which is of size at most m x SE.
Remark 3. The additional communication assumed in our protocol is only O(m) against the parameter vector of length-d and ((m) & d. Thus, the additional communication cost of our algorithm is minimal.

---

2.1 Analysis of Algorithm
is evident from our description and Algorithm that upon receiving the encode-and aosoode-nn-tiee -nd-r--nnn--tt-mtttt signal and the vector ę), each worker can independently create the matrix of indeterminates B.
Exact GC analysis: Suppose that each ;, E [M] has been processed at least & times across the cluster, and suppose that W; has processed Dj. This means that there is block-column B such that each column within B has least A indeterminates that need be assigned values. For one column within B W; will solve system of equations that is specified by É x A submatrix of R. denoted X (an example appears in Section 2.2). Note that the columns of will be linearly independent with high probability owing to the choice of R. and since A f, solution is guaranteed to exist. Let K2 (2MM) denote the condition number of matrix M. For a random & A matrix with ii.d. (0,, 1) entries, it is known that Elog (x)) O(log A) [32]. Thus, each such system of equations is well-conditioned with very high probability. In the under-determined case when A > L, each worker will still agree the same values of the corresponding indeterminates since enforce that we work with the (unique) minimum -n-n solution; no additional communication between the workers is required.
Approximate GC analysis: It is possible that the PS sends the encode-and -tran-mmamttt vector when some D; has been processed A < é- times. In this case, the corresponding step for B in (5) will be over-determined least-squares procedure, which implies that there will be non-zero enror associated with it. Let be the relevant x A submatrix of R where we have < l now, and recall that all entries of X are i..d. (0,0 1) random variables. The squared error corresponding to (
31 Let X USVT where U and V are orthogonal matrices of dimension & and A x A respectively and S [D 0)" where D is a A A matrix with positive entries on the diagonal, and 0 represents A (E A) matrix of zeros. Then, X VDD-1 OUR². It is well known (B3). Remark 5.2.8) that for a matrix with i.idd (0,, 1) entries, the singular vectors are uniformly distributed on the unit-sphere. Therefore, the expected squared error becomes
can be expressed as Σ (-1
denote the SVD of X. == || | 2 (X' denotes the pseudo-invers
B( 8-A
Bl|lxxa 1121 Ell
(6)
j=At1
j=A+1
The last step above follows since each uy is uniformly distributed over the sphere of dimension & Therefore, we have the Bl = 1/E since |1y| and each Uy.k, ...... distributed. We conclude that if DD appears A, < f - times, then its error contribution is A and the overall error is therefore Σ max(0, A.).
identically
Complexity analysis: The time complexity of each least-squares problem is O(A2() [3] and the i-th worker solves at most lō; of them independently and in parallel. The marginal cost of this calculation as against the calculation of the actual gradients will be very small in most practical settings.
2.2 Illustrative Example
Consider Fig. Tb (fom (1I) where the dataset consists of chunks Di...., Dr and are assigned in monnuniiorm fashion to workers W Wi...., WG. Suppose that the PS wants the exact gradient with {= 2. As two copies of each chunk have been processed, the PS broadcasts the encode-and-trame transmitt signal and the vector da [5 0 2 3) to all the workers which indicates, e.g., that W1 has processed all its chunks, W3 is failed etc. The matrix B of indeterminates for this example and the corresponding Bi)ss, s, turn out to be
B
B
(1)
B
(2)
B
(3)
B
(4)
B
To
02
44
as
07
0g
@10
b
44
0
0
0
0
0
0
0
0
0
0
0
0
0
(8)
0
C3
C4
C5
C6
0
0
0
d1
d2
0
0
0
d7
dg
dg
d1o
In this example, W; has processed D1, D4, Ds so that Bs
[B()
B(O)
B(3) Note that the
requires the vectors [ef o
6
and [eff
ol
JT
o
to lie in the row-space of B that
5

---

Wi
22
W
W4
Wi
W2
W
W4
D1
D2
D3
24
D1
D2
D3
D4
D4
D1
D2
D3
D3
D6
D2
D3
D3
Da
D5
D6
D
D
2
Do
(b)
Two different relative orderings of the chunks within workers for the same assignment matrix. Individual figures show the calculation Q5. Similarly, other Q; values can be computed. Qmax Qs for both assignments. Thus, (a) max 10. (b) Qmax = 9.
Figure 2:
recover E Si=1 9D, [k], 0, from the encoded gradients. Towards this end, e.g., W3 solves (5) in Algorithm 1
with the matrix Bs, i.e.,
min L R(
11
(9)
where the decision variables are 01 022 (17; ag, 0g 010. by b2 and d1, d2, d7, dg, dg, dio- For instance, corresponding to the first column of (1), Ws's problem becomes determining the minimum fn-norm solution of the under-determined least-squares problem
roi
T02
Fus
Q1 bj
(10)
F11
T12
115
dj
We emphasize that the same minimization will be independently performed at workers Wi and W2 as well. After each Wj determines its encoding coefficients and transmits for = =1, 1,...,5, 5, the PS
casily recover Σ SD, [K] > Tkj9j for lt 0, 1.
Algorithm works as is, even in the case when the PS is interested in an approximate gradient. For instance, suppose that the PS sends the encode-and-tranee trannsmit signal when the vector & 24 so that only one copy of D, has been processed in the cluster. The corresponding encoding coefficients can still be computed using Algorithm The only difference will be that the relevant indeterminate matrix becomes
a
ag
d'j
d's
0
a4
d'3
0
b
6
by
64
0
0
0
0
B'
0
0
0
0
0
0
0
(11)
0
&
c/
6
C6
0
d2
0
0
0
0
df
d'
d'
do
This means, e.g., when Ws is trying to find dg then it will be solving over-determined least-squares
ros
[1]
problem:
d'
It is evident, that all the workers can still agree the same solution.
ros
0
3 Chunk Ordering Algorithm
Note that the assignment matrix only specifies the assignment chunks workers but says nothing about the relative order of chunks within a worker. When taking into account partial stragglers, relative ordering of the D,'s s within worker is crucial. Therefore, an important question when leveraging partial stragglers within GC is one of how to determine this chunk ordering within workers for a given assignment matrix. This will in general depend on models worker speeds. However, is a difficult task obtain accurate models on the worker speeds within a cloud cluster as conditions can change dynamically.
We work instead with combinatorial metric that depends on the total number of chunks that the cluster has to process in the worst case, such that least a single copy of each D; processed; this was also used in B5 36 in coded matrix computation context. This metric minimizes the worst case number of chunks that the cluster needs to process the case when
In particular, for given D,, let Q: denote the maximum number of chunks that can be processed by the cluster such that none of the copies D, are processed (see Figs. 2a and 2h) and let Qmax max;= Q;- Thus, 1 + Qmax is metric that quantifies the worst-case number of chunks that need to be processed

---

Algorithm 2 Shunk-Ordering
Input: Assignment matrix A such that N = and = 6; = 8 for all E [m]] Output: An optimal ordering matrix O.
{1
if Ac, #0 and g(2) = d. otherwise.
1: Let ( E {0, 1 such that A0
2: for ranges from 1 to do
3: Apply Claim | with A and g6+) and solve the max-bipartite matching problem Claim
Let the permutation matrix be P..
4: Let A(++1 == ( - P. and g(++1) = 516) - -1
5: end for
6: Set O = EiE iP.
before at least a single copy of every D; is guaranteed to be processed. Here, the worst-case is over the speeds of the different workers. We say that an assignment is optimal it achieves the lowest possible Q max for given assignment matrix. Indeed, Figs. 2a and 2b show two different orderings for the same assignment matrix with different values of Qmax-
From the point of view of leveraging partial stragglers, for exact GC it can be shown that the ordering imposed by the cyclic assignment scheme (in (5]) is optimal ((ef. Remark in work (35)) for this Qmax metric. However, for approximate GC, when the number of stragglers can be much higher, other assignments, e-g., those based on regular graphs perform better (6 37.. In particular, these cases, the assignment matrix A is chosen as the adjacency matrix of the relevant graphs and is such presents an
that N m and 7/ = 6; = 8 for [m]. For such assignment matrices, Algorithm 2
optimal algorithm for determining the ordering of the chunks within each worker in Q mmxx-metrce Corresponding to the assignment matrix A, we can associate an ordering matrix which is such that F O, it means that D, is the a-th
Oig = if Ai.j 0 and Oz,j E [5] otherwise. Thus, if Oz,j chunk in W,. e.g., a implies that the chunk is at the top and a = å means that it at the bottom. Let (O) denote the maximum number of chunks that can be processed across the cluster, such that no copy of D; has been processed. Then, upon inspection, we can see that
Q:
Σ 100 (Ots 1) + (m 5)6 = Σ 1o) Ois + (m 8 --1) jE[m]
jE[m]
where the notation 1y denotes the indicator of Y. Next, let Qmax (0) max Qo(O). Thus, given assignment matrix A, goal find ordering matrix, such that Qmax is minimized. As (m - - 1)6' is a constant, this optimization is equivalent to the following min-max problem.
minimize max O
Ori
(12)
(E[m)
jE(m)
Each column of O has exactly 5 non-zero entries, with each value in [o] appearing exactly once. Counting the sum of the entries in O two different ways yields
88 + 11
Ois mQQuax (O), that Qmax (0) 8(8 +1)
Σ
m 2
xE(m].jE[m]
turns out that this bound is in fact achievable. Let Ā = A(1) (defined in Algorithm 2 Define G(A)= = (V, E) as a bipartite graph on vertex set = X KUT Y such that XX = | = m, X Xny = and deg(v) 8 for all E XUY. For X, v Y, we have that v) E E if and only An, 1. Thus, Á in one-to-one correspondence with G G(A). Algorithm decomposes G(A) into a collection of disjoint perfect matchings (38] which are then assigned values in [8]. This gives us the required ordering.
Claim 1. Let À (0, 1mmmm be such that both i-th row sum and j-th column sum of À are ô for all i [m]. Then there exists permutation matrix P E {0, 1]mxm such that A P E {0, mm
and both i-th row sum and j-th column sum of À are for i,j E [m].
Proof. We claim that G(A) has a X X-perfect matching. Let S C X arbitrary and N(S) C Y denote its neighborhood. Let denote the average degree of the vertices in N (S) in the subgraph
7

---

109
orash Aosggn ong.
iraph noean rondalos
10a2
Lyclic ung.o..
Cyclic Aesign Port Gf
10
Pertial GC Est. It=1]
Completion Tima
Portial
10
Portial GC Est. (f=3]
Orig. GC
10-8
Portial GC I/
10-10
Partial -t
10-12
10
25
(b)
Figure 3: (a) Mcan- error (MSE) T for approximate GC scenario. Bluc curves: proposed protocol with 8 = 1, 2,3, 3, purple curves: corresponding MSE estimates, and red curve: original GC protocol with e 1. Error bars correspond
standard deviation. (b) Completion time for exact GC scenario with two different assignment matrices. Blue curves: proposed protocol. green curves: original GC protocol. standard deviation.
Error hars correspond
induced by S (S). Then, we have
8| お|se
N(S) 8IN(S)), that |S| [N(S)
The first inequality above follows because the degree of each node in ((S) in G(A) is Thus,
Hall's condition (39 holds and the claim follows. Since |X] = YY] this actually a perfect matching
M. Then, this perfect matching M gives the desired P: Pa,e = 1 if (u, v) E M and Pu,v 0 if
(u, r) M. Removing the matching M from G(A) results in bi-regular bipartite graph with degree 5 which corresponds Å P.
The proposed algorithm above finds the optimal ordering when considering the case of ==1 with = m (number of chunks equal to number of workers); it only applies when = m. While this algorithum expected have better performance than a randomly chosen ordering the case of higher É, we do not have an optimal construction in this case.
Remark 4.
Algorithm 2 Analysis: The algorithm gives å permutation matrices {Pi (Pilvejs) such that A= A=E P.. i.e., the set of non-zero entries of the P,'s are disjoint. Since O = EiEta i P.. this implies that each column has exactly d non-zero entries such that these entries consists of elements of [ő]. Therefore, O is an ordering matrix. In addition, each row has ō non-zero elements from [8]. so that all row sums and Q (O) equal 6(6+1) A maximum matching can be in time O(m²d) by converting it to max-flow problem (38], our overall complexity is O(m² 82). The complexity can potentially be reduced further by using more efficient max-flow algorithms.
Numerical Experiments and Comparisons
Our proposed protocol in Section utilizes additional communication between the and the
workers. We note here that ideas in 21 that are based on Lagrange interpolation can potentially be adapted to arrive at an exact GC protocol within our setting. However, the numerical instability of Lagrange interpolation is serious issue with this solution, since it can be shown that the degree of the polynomial to be interpolated is at least m - f. Even for values such as & and m 22, 27, 32, the error in Lagrange interpolation is too high for the technique to be useful (see Appendix A
In what follows, we present comparisons with the original GC protocol via simulation of the distributed system for both the exact and approximate GC scenarios. All software code for recreating these results can found 40). These simulations were performed within a MacBook Pro (MI chip, 16 GB RAM). In both scenarios, we simulated node failures and slow-downs. We generated random vector of length-m where a workers uniformly at random are chosen be failed (a chosen based on the scenario). For the other workers, the amount of time taken to process chunk is

---

chosen i.i.d. from an exponential distribution with parameter μ = 1. The entries of the matrix R are chosen i.i.d from the standard normal N [N, 1).
Approximate GC simulation: We considered two different random regular graphs, G = 1,2 with sizes m 200, 300 and degree = 8. These graphs have second-largest absolute value of cigenvalues: 5.14 and 5.23. i.c., less than 2 - I so they can be considered as Ramanujan graphs 41 (these were used in 66 ). Their adjacency matrices were used as the assignment matrix. The number of failures a was set to V 1.
For the original GC protocol with arbitrary assignment matrices, [2]] provides communication- efficient approximate GC method that relies on rational interpolation. However, even for m = 100, these will result in very complex basis functions. Furthermore, there are numerical results in [1] (or posted software) and the approximation guarantees depend on the form of the function to be interpolated, i.e., the guarantees cannot be expressed in terms of the system parameters. Thus, in our comparison, we only consider the original GC protocol with {= 1.
For the original GC protocol, we compute the least squares solution é for minimizing || 1 1 Here, f such that f; = 0 if W; has not completed processing all its chunks at time T. For our proposed protocol, we leverage partial work completed by T, as described in Section 2 The overall error is computed as the sum of the errors for the least-squares solution for each 2!"
O..... E 1. Each data point the curves was chosen by performing 1000 simulations of failures and slow-downs. We have also plotted the expected value of the error, derived in (6)
Fig. 3a shows the mean-squared-eree partial GC approach for l 1, 2, 3 for graph G1 (see Appendix [ for G2 results). As can observed, the MSE for our approach is several orders of magnitude lower with increasing T. Crucially, our estimate (6) closely tracks the behavior of the error of our method. Thus, it can easily be used by message. We emphasize that our approach, even with & 2 2 actually has a lower MSE than the original approach (that operates with f 1). Note that with f 2 2, will enjoy lower communication time in real-world distributed cluster. However, as we are working with a simulation of the distributed system, at this time we do not have precise figures for the reduction in communication time actual clusters.
(MSH) comparing the original GC approach with / = 1 and our
the PS as a way to decide when to send the
In Fig. Glin Appendix B we compare the performance of our approach under the optimal ordering (ef. Section 3) and an appropriately chosen random ordering. The random ordering is picked as follows. We generated 100 independent random orderings and selected the one with the best (smallest) Q Qmax (O). Our optimal ordering, which can be found efficiently, clearly has better performance.
We considered (i) the cyclic assignment (5] with N m 200 and 5 3 8, and (ii) the assignment based on graph G2 discussed above. The number of failures a in the simulations is set
Exact GC simulation:
l so that exact gradient reconstruction is possible. For both approaches, we determined the time T such that each chunk is processed at least & times across the cluster (for original GC we only consider workers that have processed all their chunks). These values were averaged over 1000 runs for each value of f. In Fig. 3b we clearly observe that the exact gradient can be computed using our method is approximately half the time as compared to the original GC protocol. We note that the average completion time for the original GC protocol -Gy-based assignment) for l = is about 7 = 6 time units. However, the MSE for the original GC protocol in the approximate scenario continues to be high at T 24. The reason is that there are y 1 failures that are introduced in the simulation. The approximate GC recovery operates by solving a least-squares problem for the fixed G based assignment. Thus, the MSE does not necessarily drop zero even if one copy of each chunk has been processed in the cluster. However, there are exact recovery algorithms that one can use in this case. We note here that when & > 2, the known techniques for exact recovery for the original GC protocol are based on Lagrange interpolation and are numerically unstable. Thus, the gradient recovered using the original approach will in general not be useful.
Fig. 7 in Appendix compares the completion times of random vs. optimal ordering; the optimal ordering is clearly better.
Limitations of our work
Our chunk ordering algorithm (Section optimal only in the case when the assignment matrix
has N and 744 6, 8 for i E m] While several well known gradient coding schemes,
9

---

especially those from regular graphs, satisfy this property, there are others that do not. Our results in Section[4 f 2 2 are simulations of the actual distributed cluster and indicate lower MSE than the original GC protocol. However, we do not have actual cloud platform statistics on the reduction in communication time within our method. We do however expect this reduction be quite significant.
Conclusions
We presented novel gradient coding protocol that leverages the work performed by partial stragglers. Our protocol is simultaneously computation-efficien and communication-eliciinnn,, and numerically stable. Furthermore, we present rigorous analyses of the protocol's correctness and performance guarantees. Our protocol is one of the first to provide a satisfactory solution to the problem of communication-effiieenn, approximate gradient coding for general assignment matrices.
Acknowledgments and Disclosure of Funding
We would like to the anonymous reviewers and area chair whose helpful comments and suggestions helped improve the paper. This work was supported in part by the National Science Foundation (NSF) under grant CCF-2115200
References
[1] Ian J. Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, Cambridge, MA, USA, 2016. htttp://wxxt wwtp://wwwdeeeeeinbbbbooooo org
[2] Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating minimization. Proceedings of the forty-fifth Annual ACM Symposium on Theory of Computing (STOC), pages 665-674, 2013.
[3] Mu Li, David G Andersen, Jun Woo Park, Alexander Smola, Amr Ahmed, Vanja Josifovski. James Long, Eugene J Shekita, and Bor- Yiing Su. Scaling distributed machine learning with the parameter server. In 1/th USENIX Symposium on operating systems design and implementation (OSDI 14), pages 583-598, 2014.
[4] Google Spot Virtual Machines.
[5] Rashish Tandon, Qi Lei, Alexandros Dimakis, and Nikos Karampatziakis, Gradient coding: Avoiding stragglers in distributed learning, In Intl. Conf. Mach. Learn. (ICML), pages 3368- 3376, August 2017.
[6] Netanel Raviv, Rashish Tandon, Alex Dimakis, and Itzhak Tamo. Gradient coding from cyclic MDS codes and expander graphs. In Intl. Conf. Mach. Learn. (ICML), pages 4302-4310, July 2018.
[7] Wael Halbawi, Navid Azizan, Fariborz Salehi, and Babak Hassibi. Improving distributed gradient descent using reed-sof solomon codes. In IEEE Intl. Symp. on Info. Th., pages 2027-2031, 2018.
[8] Tianyi Chen, Georgios Giannakis, Tao Sun, and Wotao Yin. Lag: Lazily aggregated gradient for communication-effccienn distributed learning. Adv. in Neural Inf. Process. Syst. (NeurIPS), 31, 2018.
[9] Shanuja Sasi, Lalitha, Vaneet Aggarwal, and Sundar Rajan. Straggler mitigation with tiered gradient codes. IEEE Trans. on Comm., (888):4632-4644 2020.
[10] Baturalp Buyukates, Emre Ozfatura, Sennur Ulukus, and Deniz Gündüz. Gradient coding with dynamic clustering for straggler-tolerant distributed learning. IEEE Trans. on Comm., 7166)331773332, 2023.
[11] Neophytos Charalambides, Hessam Mahdavifar, and Alfred O. Hero. Numerically stable binary gradient coding. In IEEE Intl. Symp, on Info. Th.. pages 2622-2627, 2020.
10

---

[12] Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-311 May 2018.
[13] Zachary Charles, Dimitris Papailiopoulos, and Jordan Ellenberg. Approximate gradient coding via sparse random graphs. 2017 [Online] arxiv:1711.066 1.06771.
[14] Margalit Glasgow and Mary Wootters. Approximate gradient coding with optimal decoding. IEEE J. Select. Areas Info. Th., 2(3):855-866) 2021.
[15] Swanand Kadhe, O. Ozan Koyluoglu, and Kannan Ramchandran. Gradient coding based on block designs for mitigating adversarial stragglers. In IEEE Intl. Symp. on Info. Th., pages 2813-2817, 2019.
[16] Animesh Sakorikar and Lele Wang. Soft bibd and product gradient codes. IEEE J. Select. Areas Info. Th., 3(2):229-240, 2022.
[17] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication-effiica sgd via gradient quantization and encoding. Adv. in Neural Inf. Process. Syst. (NeurIPS), 30, 2017.
[18] Jue Wang, Yucheng Lu, Binhang Yuan, Beidi Chen, Percy Liang, Christopher De Sa, Christopher Re, and Ce Zhang. Cocktailsgd: Fine-tuning foundation models over 500mbps networks. In Intl. Conf. Mach. Learn, (ICML), pages 36058-36076, 2023.
[19] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical bias variineie trade-off. Proceedings of the National Academy of Sciences, 116(32):15849 15854, July 2019.
[20] Min Ye and Emmanuel Abbe. communication-compuaatie efficient gradient coding, In Intl. Conf. Mach. Learn. (ICML), pages 5610-5619, 2018.
[21] Tayyebeh Jahani-Nezhad and Mohammad Ali Maddah-Ali: Optimal communication- computation trade-off in heterogeneous gradient coding. IEEE J. Select. Areas Info. Th., 100) 2021.
[22] V. Pan. How Bad Are Vandermonde Matrices? SIAM Jour on Mat. Analysis and Appl., 37(2):676-694 2016.
[23] Swanand Kadhe, O. Ozan Koyluoglu, and Kannan Ramchandran. Communication-cffieee efffciient gradient coding for straggler mitigation in distributed learning. In IEEE Intl. Symp. on Info. Th., pages 2634-2639, 2020.
[24] Lev Tauz and Lara Dolecek. Multi-message gradient coding for utilizing non-persistent strag- glers. 20/9 53rd Asilomar Conference on Signals, Systems, and Computers, pages 2154-2159, 2019.
[25] Hankun Cao, Qifa Yan, Xiaohu Tang, and Guojun Han. Adaptive gradient coding. IEEE/ACM Trans. Networking, 30(2):717-734, 2022.
[26] Haozhao Wang, Song Guo, Bin Tang, Ruixuan Li. Yutong Yang, Zhihao Qu, and Yi Wang. Heterogeneity-awarr gradient coding for tolerating and leveraging stragglers. IEEE Trans. on Comp., 714)77977 2022.
[27] Qi Wang, Ying Cui, Chenglin Li, Junni Zou, and Hongkai Xiong. Optimization--asee block coordinate gradient coding. 2021 IEEE Global Communications Conference (GLOBECOM), 2021.
[28] Nuwan Ferdinand, Benjamin Gharachorloo, and Stark C. Draper. Anytime exploitation of stragglers in synchronous stochastic gradient descent. In IEEE Intl. Conf. on Mach. Learning and Appl. (ICMLA), pages 141-146, 2017.
[29] S. Lin and D. Costello, Error Control Coding, 2nd Ed. Prentice Hall, Upper Saddle River, 2004.
11

---

[30] Thomas M. Cover and Joy A. Thomas. Elements of Information Theory 2nd Edition (Wiley Series in Telecomnunications and Signal Processing). Wiley-Interscience, 2006.
[31] Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, 2012.
[32] Zizhong Chen and Jack J. Dongarra. Condition numbers of gaussian random matrices. SIAM Journal Matrix Analysis and Applications, 27(3):603-622 2005.
[33] Roman Vershynin. High-dimensional probabilit:: An introduction with applications in data science, volume 47. Cambridge University Press, 2018.
[34] S. Boyd and L. Vandenberghe. Comvex Optimization. Cambridge University Press, 2004.
[35] Anindya Bijoy Das, Li Tang, and Aditya Ramamoorthy. LES Codes for coded computation that leverage stragglers. IEEE Info. Th. Workshop, pages 1-5, 2018.
[36] Anindya Bijoy Das and Aditya Ramamoorthy. Coded sparse matrix computation schemes that leverage partial stragglers. IEEE Trans. Info. Th., 6856):41564418,, 2022.
[37] Zachary Charles and Dimitris Papailiopoulos. Gradient coding via the stochastic block model, 2018 [Online] arxiv: 1805. 10378 [s.)t.MI.J.
[38] J. Kleinberg and E. Tardos. Algorithm Design. Pearson, 2005.
[39] J. H. Van Lint and R. M. Wilson. A Course in Combinatorics. Cambridge University Press, New York, 2001.
[40] Aditya Ramamoorthy, Ruoyu Meng, and Vrinda S. Girimaji. Leveraging partial stragglers within gradient coding- software repository. htttps://githbb cww/fllllaeoc Enreraging-partial--e
within- weate-rgdiiinttttiieeee 2024.
[41] R. K. Chung, Spectral Graph Theory. American Mathematical Society, Rhode Island, 1997.
12

---

Appendix A Numerical Instability of Lagrange Interpolation.
Even for values such as l and m 22, 27, 32, the error in Lagrange interpolation too high for the technique of [2I] be useful. To this consider Fig. 4 which shows the error (averaged over 100 random trials) in first interpolating and then evaluating the interpolated Lagrange polynomial (degrees 20, 25 and 30) at specific points (as is done in (21;; the r--ais is the precision. It can be observed that the error even with full preciiiieinonn is too high for the technique to useful.
Appendix B Additional numerical experiments
Fig. 5 shows the mean-sqqured-error (MSE) comparing the original GC approach with / = 1 and our partial GC approach for = 1, 2, 3 for graph G2 with m 300 vertices. The results are similar in spirit to the results for the case of G1 that has 200 vertices. Namely, our MSE is orders of magnitude lower than the original GC approach, even when we consider {
In Figs, 6a and 6b we study the impact of chunk ordering within the workers for the assignment matrices corresponding to graphs Gi and G2 respectively. Each data point on the curves corresponds to 1000 simulations (setup described in Section 4 In particular, in Fig. 66a correspoond to the case of ( 2, for G1. we observe that the MSE of the optimal ordering consistently remains lower than the MSE of the random ordering and can in fact be multiple orders of magnitude lower when the
Lagrange Interpolation Error
107
Reconstruction Error
10*
10P
Full Predisaas
No. of decimal places in evaluation
Figure 4: Error in Lagrange interpolation the number of decimal places (precision) in the evaluation values.
The three curves correspond to polynomials of degree 20, 25 and 30 (average of 100 trials).
10a
10-2
Partial Est. (1-1)
10-1
Partil GC Fst. (f=2)
MSE
10-6
Est. (7-3)
Orig GC
10-9
Partial
Partial (2=2) 21
10-10
Partial GC (2
10-12
10-14
Figure 5: Mean- Seunre error (MSE) vs. T for an approximate GC scenario corresponding to an assignment matrix stemming from graph Gz. Error bars correspond to one standard deviation. Blue curves: proposed protocol with f = 1, 2, 3, purple curves: corresponding MSE estimates, and red curve: original GC protocol with f
13

---

109
109
Opt.
Rand. Ord. (f- 11
Randd. Ord. il 1)
10
10
Rand. Ord. (t-2)
Rand. Ord. -)
10
Ord.
Rand, 3]
Rand. Ord. I|
10
MSE
10-8
10-3
10-10
10-10
10-12
10-12
10-14
10-14
10
10
15
Figure 6: Mlcan-qquree error (MSE) T for the approximate GC scenario when considering random chunk ordering and optimal chunk ordering within our protocol with = 1, 3. Error bars correspond to one standard deviation. (a) Assignment matrix corresponding graph C1. (a) Assignment matrix corresponding to graph G2.
encode-and-transmii signal is sent at certain time intervals. A similar pattern can be observed in Fig. which shows the case of L 1, 2,3 and G2.
6b
Fig. shows the results of a similar experiment comparing the random chunk ordering and our optimal chunk ordering in terms of completion time for exact GC. The assignment matrix corresponds to the graph G₁ discussed in Section ! The random ordering is chosen by sampling 100 independent random orderings and selecting running 1000 simulations with the selected random ordering. The results indicate that in an average sense, the completion time of the optimal ordering is clearly lower.
with the smallest (0en(()) data point then generated by
Graph Assign.: Opt. Ord.
Graph Assign.: Rand.
Completion Time
Figure 7: Completion time vs. for the exact GC scenario with random chunk ordering and optimal chunk ordering. Error bars correspond to one standard deviation.
14

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: We present a new gradient coding algorithm. We have discussed the as- sumptions underlying the algorithm and outlined the main contributions of our work. The contributions are substantiated within the body of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
We have section titled Limitations in the paper that discusses these issues. Computational complexity has been discussed for all our algorithms.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
15

---

Answer: [Yes]
The paper presents protocols and algorithms that are relevant to gradient coding. Within the main body of the paper, have included analyses of these protocols and algorithms. The analyses include proof of correctness, performance analysis and computational complexity analysis. Guidelines:
Justification:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
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 affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We have provided complete descriptions of all our protocols and algorithms. In addition, we also have an example of the main protocol that guides the reader through the main steps.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
16

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We have uploaded commented code that recreates the main experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurlPS code and data submission guidelines (https://nips.cr
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
gwwol//siggiiie///eeeeeooso CodeSubmiee ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: Our protocols and algorithms do not have any hyperparameters that need to be tuned. All experimental settings and details are available in the body the paper itself.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
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:
[Yes]
Justification: We have included error bars for the relevant plots.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
17

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
This information is provided on the section on Numerical Experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https:
Answer: [Yes]
Justification: Yes. We have read the Code of Ethics and our submission conforms to it.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: There are no negative social impacts of our work. Our work allows for faster distributed training on cloud platforms. The positive societal impact is that it will save computational cycles on such platforms.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
18

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
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:
We do not have such risks because the paper about distributed training.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We do not use any existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
19

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We are not releasing any new assets in this work.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing 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: Our work is not related to crowdsourcing nor research with human subject
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research 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 equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Our work does involve human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
20

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
21


Reviews:
[{"review_id": "suTBazdFQX", "reviewer": "Reviewer_ryxi", "summary": "This paper addresses inefficiencies in gradient coding protocols for distributed learning systems, specifically targeting the issue of stragglers—workers that are slower than expected or fail to complete their tasks. The authors introduce novel gradient coding protocols that incorporate the partial work performed by \"partial stragglers\". The proposed protocols are designed to be both computation and communication efficient while remaining numerically stable.  \n\nFor exact gradient reconstruction, the new protocol is approximately a constant factor faster than existing protocols, and for approximate gradient reconstruction, the mean-squared-error (MSE) of the reconstructed gradient is significantly reduced. Additionally, the paper presents efficient algorithms for optimizing the order of data chunks within workers, enhancing further the performance of the gradient coding protocol. The authors provide theoretical analysis of the proposed algorithms as well as numerical experiments that demonstrate significant improvements in MSE and execution time compared to traditional gradient coding methods.", "questions": "- A major contribution of this work revolves around ensuring numerical stability. Could the authors elaborate more on the the measures taken to ensure the numerical stability of their protocols? \n- You mention that the additional communication cost is minimal compared to the length of the parameter vector. It would be very interesting to capture the effects of this overhead on experiments either in simulations or in real-world experiments. Although it is not necessary I think that the inclusion of such experiments would strengthen this paper.", "limitations": "The authors adequately addressed the limitations of their work.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The authors study a relevant problem of interest for the ML community.\n- The paper is well-structured and clearly explains the problem, the proposed solutions. It is easy to read and understand its main points.\n- The paper introduces innovative gradient coding protocols that leverage the partial contributions of slow workers, addressing a gap in existing methods that typically ignore these partial stragglers. Additionally, the approach of optimizing the order of data chunks within workers is a novel contribution that enhances the protocol’s efficiency.\n- The proposed protocols are theoretically analyzed for their computational and communication efficiency, as well as their numerical stability. The theoretical analysis is further supported by empirical results.\n- The protocols offer substantial improvements in gradient reconstruction performance, reducing mean-squared-error by several orders of magnitude and halving the execution time for inexact gradient reconstruction compared to existing methods. Further, the minimal additional communication introduced by the protocols ensures they have practical real-world applications.", "weaknesses": "- Although the paper is introducing a novel approach -as also mentioned by the authors - a part of this work builds heavily on existing works (long literature on GC as well as [34,35, 37,38]) which limits somewhat the novelty of this work.\n- The focus of this work is mostly theoretical without providing extensive experiments. Importantly, actual cloud platform statistics on the communication time reduction achieved by the proposed method are missing. This potentially limits the practicality of the proposed methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "_[Weakness-1]_-We would like to respectfully disagree with the assertion about limited novelty. While the original gradient coding protocol and the follow-up works have made several contributions in our understanding of the area, they all suffer from the major limitation that the training takes unnecessarily long when the cluster is operating normally (cf. discussion in the Motivation section (pg. 2)). Note that failures are a relatively rare event and protecting against them should not come at the cost of increased job execution times even when the workers are operating in an ideal fashion. Our work is the first to modify the protocol, so that gradient coding is simultaneously computation-efficient, communication-efficient and numerically stable. We believe that considering limited feedback in the application of coding-theoretic techniques to distributed computing problems will have more applications in the future.\n\n_[Question-1]_ - For the exact gradient recovery case, the only other known technique that works with arbitrary assignments is the work of [21] which operates by polynomial interpolation, which is well-known to be numerically unstable (see Appendix A).\nWe emphasize that we do not include comparisons with [21] in Section 4 of our manuscript, since their error is way too high to be useful.\n\n In contrast, in our work, the matrix $\\mathbf{R}$ is generated with i.i.d. Gaussian $N(0,1)$ entries. This ensures that the system of equations that each worker has to solve for determining the encoding coefficients is well conditioned (see lines 158 - 165 on pg. 5). Once the coefficients are determined with very low numerical error, the PS can recover the exact gradient, as explained in lines 199-200 on pg. 6. Thus, there is essentially no numerical error in this case.\n\n For the approximate gradient recovery case, once again, we leverage the fact the random Gaussian system of equations are well conditioned (lines 166 - 180 on pg. 5). In particular, we use the fact that the singular vectors of a random Gaussian matrix are distributed uniformly on the unit-sphere. This allows us to calculate the expected error in the least-squares estimate (cf. eq. (6)). This, then translates into an estimate of the overall MSE of recovering the gradient. As can be seen in Fig. 3(a), our estimate closely tracks the actual MSE; we point this out in line 300 of the manuscript (pg. 9).\n\n\nIn essence, our technique is numerically stable since we work with random Gaussian systems of equations.\n\n_[Weakness-2 and Question-2]_- We acknowledge this fact and have stated this upfront in the Section 5 (Limitations of our work).  A theoretical calculation of the overhead in a realistic scenario appears in our response to Question-2 of reviewer TBo9.\n\nNevertheless, to partially address this point we implemented a simple baseline scheme with a PS and $m=30$ workers within AWS with t2.medium instances. We used the MNIST dataset with a CNN model with 1,199,882 parameters. The dataset is divided into $N=m$ chunks and the workers are given disjoint chunks. However, in our system, we also had each worker transmit an integer when it finished processing its assigned chunk. In the global PDF, Fig. 2, we have plotted the average amounts of time it takes for computing the gradient, transmitting the gradient and also transmitting the integer from the workers to the PS. As can be observed, the time to communicate the integer is about four orders of magnitude lower than the time to communicate the gradient. Thus, even if this communication is repeated 10 - 50 times, the overall communication time will change only by a tiny negligible amount. Furthermore, for models with hundreds of millions of parameters, this additional communication will be even smaller.\n\nWe acknowledge that a full simulation, that compares different protocols on a larger dataset with a larger model, would make the point more forcefully. However, we hope that this serves to convince the reviewer that both our theoretical arguments and the numerical experiments indicate that the communication overhead of our scheme is negligible.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BGBOAleASY", "reviewer": "Reviewer_TBo9", "summary": "This paper considers the gradient coding (GC) framework for distributed learning systems to address the issue of stragglers. Compared to the standard GC protocol, the authors propose new approaches that utilize the partial work done by partial stragglers. These protocols aim to enhance computation and communication efficiency while providing guarantees of numerical stability.", "questions": "1. The authors may want to justify why, when coordination is allowed, and the encoding is decided after knowing the straggler pattern, there are still benefits of encoding the results rather than directly feeding uncoded sums of non-overlapping partial gradients to the central node (e.g., in computation cost, communication, numerical performances).\n\n2. Remark 2 suggests that the communication cost only takes into account the overall load. If we take into account the rounds of communication, its cost could potentially be significantly larger than the classical gradient coding.", "limitations": "See weakness and questions.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The proposed protocols leverage partial stragglers, an aspect often ignored in traditional gradient coding methods. If the proposed computing design does not require a significantly stronger model from the communication perspective, it can potentially speed up the training process.", "weaknesses": "1. The issue of this work is the mismatch between the proposed computation design and the formulation. The idea used in the purpose framework is based on the concept of forward error correction, which means when redundancy is injected into the computation ahead of time in a certain way, the central node can retrieve the full gradient without communicating back to the individual workers. Such a communication framework is consistent with the earlier gradient coding paper, where the computation is one-shot. But in this work, the authors assume that feedback is easy and \"at regular intervals, the workers keep communicating to the PS, the number of chunks they have processed\". In this case, it would be better to coordinate the workers to send partial gradients from non-overlapping datasets, which gives ideal numerical stability as well. \n\n2. The overall presentation can be improved for readability. For example, currently, there is not a dedicated section to introduce the system formulation, and it is difficult for readers to find definitions for concepts such as $d$, which is introduced in the related work section. \n\n3. Algorithm 1 is not self-contained. In its current form, it would be better to revise it or describe it in conjunction with other detailed steps.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "_[Question 1 and second part of Weakness 1]_ - The reviewer's proposed solution works only in the case where we consider $\\ell=1$, i.e., in the case when we are not communication-efficient. In this situation, it is potentially possible to arrive at a protocol where each $g_{\\mathcal{D}_i}, i = 1, \\dots, N$ appears as part of an encoded gradient only once across the cluster. Therefore, the workers can generate partial sums of non-overlapping gradients so that the PS can calculate the required sum. We note that our algorithm also applies in this setting.\nAs discussed in our manuscript, in addition to leveraging worker feedback for \"computation-efficiency\", we also provide a solution that is \"communication-efficient\" and numerically stable. Communication-efficiency here means that the workers communicate vectors of length $d/\\ell$ (recall that $d$ is the number of parameters).  However, such a straightforward solution will not work in the communication-efficient case when $\\ell > 1$. Note that in this case simply communicating partial sums will not work. For instance, if $\\ell=2$, then each worker is only allowed to communicate an encoded gradient of length $d/2$. In the exact case, at least two different workers process each gradient; these workers are arbitrary. Thus, it is not at all straightforward to decide the partial sums in this case. In fact, the work of [21] addresses this issue (in the original gradient coding setting) using polynomial interpolation, which is unfortunately numerically unstable. \n\nOur protocol allows for the workers to independently operate and agree on the same encoding matrix and allows the PS to recover the sum of the gradients, while remaining numerically stable. This is our key contribution. We hope that this clarifies the reviewer's question about this issue.\n\n\n\n\n_[Question - 2]_ - In most problems of practical interest, the parameter vector, e.g., for a deep learning problem is of the order of several million whereas a typical cluster contains about a few hundred workers. \nFor the discussion below suppose that the parameter vector is of length 100 million and suppose that there are 1000 workers. Our protocol requires the workers to send the number of chunks they have processed at periodic intervals. This translates into a 1000-length integer vector where each component can be described in at most $\\log_2 N$ bits. For most reasonable values of $N$, this will fit in 16-bits. In an iteration, if this happens $\\xi$ times, then the additional overhead is at most $\\xi \\times 1000 \\times 16$ bits. When compared to the overhead of a 100-million floating point vector (32-bit or 64-bit). Thus, even if $\\xi \\approx 200$, the overhead is about 0.1\\%, i.e., it is negligible. We also emphasize that the gradient computations are not held up because of this communication, thus, its impact will be negligible. In addition, please note that our protocol allows the overall system to save a significant amount of computation, as discussed above. Ultimately, what matters is the overall job execution time, which is much smaller for us. \n\nIf indeed, $\\xi$ turns out to be very large, the PS can conclude that either there are too many failures or severe slowdowns and take other corrective action (which we do not consider); the original gradient coding protocol will also fail to complete the job here. \n\nPlease also see our overall response document that discusses some preliminary numerical results.\n\n\n\n_[First part of Weakness -1]_ - The reviewer is correct in stating that the original gradient coding model allows the PS to decode as long as enough number of workers send their encoded gradients. Crucially, however, this comes at a significant cost. Note that a slowdown or a failure is a somewhat rare event, happening perhaps at most 10\\% of the time in the cluster. This means that 90\\% of the time the cluster is fully operational. In these settings, it is quite wasteful for the cluster to process all its assigned gradients and then compute the encoded gradient. We have made this point in-depth in the \"Motivation\" section (pg. 2). Specifically, for the example from the original GC paper, it can be seen that under ideal operating conditions, the cluster has processed enough gradients such that the PS can compute the overall gradient. However, under the original GC protocol, the workers will only respond after they have computed their second assigned chunk. This can potentially double the overall computation time under regular operating conditions.\n\nThe fundamental motivation of our work is to attack the problem of stragglers within distributed learning while addressing this undesirable aforementioned overhead.  Our solution uses a small amount of feedback from the workers to the PS. Note that this is a very small amount of communication as compared to the transmission of the encoded gradient (which is a vector of length several million). Moreover, the system designer can decide how frequently the workers report the number of chunks they have processed.\n\nOur main contribution is our protocol that provably leverages the small amount of worker feedback to arrive at a gradient coding protocol that protects the system against stragglers while not incurring the overhead of the original GC protocol.\n\n_[Weakness-2]_ - We apologize for this and will definitely make sure to make appropriate changes if the paper is accepted. However, we do want to point out that in the Introduction Section (line 26 of manuscript, pg. 1), we specify the parameter vector as $\\mathbf{w} \\in \\mathbb{R}^d$, i.e., the definition of $d$ appears very early in the manuscript.\n\n_[Weakness-3]_ -  Algorithm 1 specifies how the workers determine their encoding coefficients. Owing to space limitations, we did not repeat the description of how the matrix $\\mathbf{B}$ is formed within the description of Algorithm 1. We are happy to answer more questions about it and also edit the description based on feedback from the reviewer.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lLQhsPz48L", "reviewer": "Reviewer_aGFU", "summary": "This paper provides a coded distributed computation solution when the parameter server needs to compute the gradient (exactly or approximately) over a very large dataset. The idea relies on distribution dataset into chunks and assigning chunks to different workers, such that each worker computes the gradient for only a subset of the chunks. The workers then send their computations to the server in a coded manner to reduce the communication load. In principle, redundant computations are introduced to compensate for slow straggling workers.", "questions": "- The authors claim that no previous work considered approximate gradient computations. This is not exactly correct, as the following work makes almost the same claim:\n\nE. Ozfatura, S. Ulukus and D. Gündüz, \"Coded Distributed Computing With Partial Recovery,\" in IEEE Transactions on Information Theory, vol. 68, no. 3, pp. 1945-1959, March 2022, doi: 10.1109/TIT.2021.3133791.\n\nPlease see Section V of this paper that applies the proposed ideas to gradient coding, which is called coded communication (since computation results are coded before being communicated to the server).\n\nThe authors should revise their claims in light of the above work, clearly explain how/why their scheme is superior to the one proposed here, and also provide numerical comparisons.", "limitations": "- As noted above, one of the main limitation is the lack of comparison with other existing schemes in the literature. Also, one would like to see the results of the algorithm implemented on a more realistic scenario.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The authors propose a new class of algorithms that benefits from additional communication between the server and the workers, where the worker tracks the chunks computed by the workers at each iteration, and informs all the workers about the state of others. The proposed protocol allows also partial computation of the gradients, which can be used to speed up optimisation steps at the expense of reduced accuracy, similarly to stochastic gradient descent. The authors provide numerical examples that illustrate the benefits of their proposed algorithm.", "weaknesses": "- One of the main weaknesses of the proposed algorithm is the additional communication overhead. The protocol requires communication from each worker to the server and from the server to each worker after each iteration. Even though these are packets of limited size, only containing information about the state of computation, not the computation results, they do still need to be communicated back and forth, and the algorithm relies on the correct reception of these packets by their recipients. In practice, this may cause significant load on the system particularly when the number of workers is large. \n\n- The proposed algorithm requires solving another optimization problem to find the right combining coefficients when the server requests the results from the workers. Each worker needs to solve a problem not only for its own coefficients, but also the other workers' problems to be able to track the coded solutions transmitted by them. This puts quite a bit of an extra computation load (probably much less then what is being computed for the gradient computation, but still an additional computation step). \n\n- Overall the presentation of the algorithm could be a bit more clear. It was difficult to follow the description. I believe it would be better to provide the illustrative example before presenting the details of the algorithm, and walk the reader through the steps of the proposed algorithm and highlight the benefits. \n\n- Some relevant literature is not considered.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "_[Weakness-1]_ - The reviewer is correct in stating that our algorithm needs more communication. However, we would like to clarify certain points here. Most work in the gradient coding including the original protocol and ours assumes a setting where communication is not noisy. This is easily justified when considering clusters within the cloud (for instance).\n\nWithin one iteration, the workers periodically communicate to the PS how many chunks they have processed. The additional communication from the PS to the workers happens only once, when the PS sends the \"encode-and-transmit\" signal. \nIn most problems of practical interest, the parameter vector, e.g., for a deep learning problem is of the order of several million whereas a typical cluster contains about a few hundred workers. \nFor the discussion below suppose that the parameter vector is of length 100 million and suppose that there are 1000 workers. Our protocol requires the workers to send the number of chunks they have processed at periodic intervals. This translates into a 1000-length integer vector where each component can be described in at most $\\log_2 N$ bits. For most reasonable values of $N$, this will fit in 16-bits. In an iteration, if this happens $\\xi$ times, then the additional overhead is at most $\\xi \\times 1000 \\times 16$ bits. When compared to the overhead of a 100-million floating point vector (32-bit or 64-bit). Thus, even if $\\xi \\approx 200$, the overhead is about 0.1 \\%, i.e., it is negligible. We also emphasize that the gradient computations are not held up because of this communication, thus, its impact will be negligible. In addition, we emphasize that our protocol allows the overall system to save a significant amount of computation as discussed above. Ultimately, what matters is the overall job execution time which is much smaller for us. \n\nPlease also see our overall response document that discusses some preliminary numerical results.\n\n_[Weakness-2]_ - As discussed on pg.5 (Complexity analysis) of our manuscript, the complexity of the least-squares step is $O(\\Delta^2 \\ell)$ which is around $O(\\ell^3)$. Moreover, worker $W_i$ will solve at most $\\ell \\delta_i$ such least-squares problems ($\\delta_i$ is the number of chunks assigned to $W_i$). Recall that a communication-efficiency factor of $\\ell$ means that the workers communicate vectors of length $d/\\ell$. Note that $d$ is of the order of 100 million or so, whereas a typical number for $\\ell$ may be in the set {2,3,4}. This is because prior results demonstrate that for exact gradient recovery we need $\\ell$ copies of each gradient to be processed across the cluster. Likewise, $\\delta_i$ is also a small number. Thus, it can be observed that the least-squares complexity is truly negligible as compared to even calculating the gradient on one chunk. \n\nWe also emphasize (see Remark 1 in the manuscript) that $W_j$ only works with a submatrix of $\\mathbf{B}$ denoted $\\tilde{\\mathbf{B}}_j$ which is much smaller than $\\mathbf{B}$.\n\n_[Weakness-3]_ - We thank the reviewer for pointing this out. We will definitely address this point if the paper were to be accepted.\n\n_[Question - 1]_ - We thank the reviewer for pointing out this work. We would like to point out that our statement on page 3 (Main Contributions) states that - \" there are hardly any schemes for communication-efficient approximate gradient coding\". The method in the cited reference works only for the case of $\\ell=1$, i.e., it is not communication-efficient. Moreover, it considers the transmission of multiple encoded gradients from the workers to the PS within the same iteration. Thus, it falls within the class of so-called \"multi-message communication (MMC) schemes\". This is a huge overhead as the parameter length is of the order of hundreds of millions. Thus, it will be significantly more communication-intensive than our proposed scheme.\n\nTo address the reviewer's comment, we implemented the scheme of Ozfatura et al. 2022 that is described in Section V of their paper. Fig. 1 of the global PDF document contains a comparison of our partial GC scheme (with $\\ell=1$) with their CCPR scheme. We simulated scenarios where $\\alpha=1$ and $\\alpha=5$ nodes were failed. The rest of the simulation settings are described in Section 4 of our manuscript. We can clearly, see the MSE of our scheme is much lower than their scheme. When $\\alpha = 1$ at $T=4$ seconds, our scheme has MSE $\\approx 0$ whereas their MSE is around $10^{-2}$. Moreover, the CCPR scheme needs to transmit around 42 encoded gradients as against our scheme which only needs 19. It is clear that our scheme is quite superior to their scheme.\n\nWe would like to emphasize that we have discussed these multi-message communication schemes in lines 73-76 of the manuscript (pg. 2, Related Work). However, we missed this reference, which we will definitely include in our discussion. \n\n\nOnce again, we would like to emphasize that the key contribution of our work is in designing a protocol that takes advantage of a small amount of additional communication for huge job execution time reductions. \n\n_[Limitation-1]_ - As pointed out above, there are algorithms that communicate multiple encoded gradients from the workers to the PS in a single iteration. Such algorithms are referred to MMC schemes and will have a much higher communication overhead than our scheme. However, we agree with the reviewer and will definitely address this point in more detail if the manuscript is accepted.\n\nRegarding actual implementation on the cloud platform, please see our overall response that contains some preliminary numerical results that demonstrate that the overhead of communicating the vector of counts is negligible.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7AAJM0G698", "reviewer": "Reviewer_Wfvp", "summary": "In distributed learning, workers in large scale clusters may be slower than expected promised or are prone to failure. Gradient coding tries to address this by introducing redundancy within the assignment of chunks (of data) to workers. There, ideas from coding theory are used to recover the full gradient. \n\nExisting work is either not efficient or rejects \"failed\" workers, leading to suboptimal performance. In this work, the authors present a new gradient coding protocol, leveraging the work performed by partial stragglers. The approach offers redundancy in assignment of chunks, leading to worker calculating linear combination of the gradients of the chunks. Further, the workers know the assignment matrix and ordering. \n\nThe authors claim that the Algorithm is efficient in terms of compute and communication and numerically stable. Specifically, they claim that the algorithm is around 2x faster in the original setting and further, in the approximate gradient reconstruction setting, MSE is several orders of magnitude better.", "questions": "- The redundancy leads to some overhead. What if one would not do this and redistribute data again that was not used in the previous iteration? \n- How does your work compare performance wise with simple baselines, like the PS distributes the chunks of data to different workers and if some don't report back, their chunks get redistributed again? How do the methods compare regarding memory, compute and communication?\n- I am surprised that the failure rate of nodes is taken into account when analyzing the algorithm. Experiments with varying failure rates and varying $\\ell$ would be good to compare different approaches. Specifically, under which regime is this Algorithm better than related work? What failure rates does one need to assume for this algorithm to be better? \n- The authors mention that variable spot instance pricing is an application. Can the authors provide a back of the envelope calculation how much more compute one would need compared to a standard setting and high the difference in spot prices would need to be in order for the method to be economically viable? \n- Just a clarification: The vector $\\psi$ does not only have the counts of how many data chunks a worker processed but which data chunks each worker did, yes? \n- It is unclear to me how data chunks are treated that where processed by more than $\\ell$ workers as this would then result in a $B^{(j)}$ that has more than $\\ell$ columns. \n- How would the protocol handle a case where a worker during or after the gradients get encoded becomes unresponsive?", "limitations": "While the authors provide a limitations section, cover potential limitations seen by me (see Questions and Weaknesses).", "rating": 3, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The proposed GC idea seems to be novel, particularly the distributed gradient encoding. \n- The math, as far as i checked is correct. \n- The example in Section 2.2 was helpful and improved readability. \n- Efficient and robust training in a distributed environment is becoming more and more important topic.", "weaknesses": "- The writing was not easy to follow. The example was helpful though. \n- To me, the biggest weakness of the work is its limited comparison to baselines. It is unclear to me, how the proposed algorithm compares computationally with a simple baseline, where workers share gradients for data chunks with the PS and if a data sample does not get processed, the PS sends it to a different worker. \n- It is unclear in which regime the approach offers benefits: The error rates of workers do not seem to be taken into account. This is strange to me, as an error rate of 0 would render the approach certainly not optimal. \n- Various aspects of the work remain unclear (see Questions). \n\nMinor:\n- Lines 46 and following: $nnz(v)$ is commonly typesettes (as a function) as $\\text{nnz}(v)$. Similarly for later occurances.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "_[Weakness-1]_ -  We thank the reviewer for pointing this out. We are happy to act on suggestions from the reviewer about this issue. \n\n_[Weakness-2]_ _and_ _[Questions 1 \\& 2]_ - You are considering a situation where the PS dynamically adjusts the chunk assignment based on the status of the cluster. This will come a significant coordination cost for the PS. Moreover, there will be delays owing to the PS having to transmit specific chunks to different workers based on the straggler pattern. This differs significantly from the original vision of a PS + workers model where the PS essentially plays the role of a coordinator. Your proposed model is a very different one that is outside the scope of what we and others in the broad area of gradient coding protocols have considered.\n\n_[Weakness-3]_ - If the failure rate is zero, i.e., we are operating under ideal conditions, then our scheme will be optimal, i.e., the PS will be able to compute the gradient as soon as the cluster has enough information to support it. To see this in the case when $\\ell = 1$ consider Fig. 1 of the manuscript that we used as motivation to argue that the original gradient coding protocol is inefficient. In the ideal setting, the PS will send the encode-and-transmit message as soon as it receives the vector $\\psi = [1 ~1 ~1]$ and the workers will send their gradients. In clear contrast, the original gradient coding protocol will wait for each worker to process both its chunks, thereby doubling the iteration time compared to our scheme. This is the key contribution of our work.\n\n_[Question-3]_ - As we have discussed extensively in the paper, our scheme allows the PS to decode as soon as $\\ell$ copies of each chunk have been processed in the cluster (for the exact case). As soon as this happens, the PS sends the encode-and-transmit vector, following which the workers determine their encoding vectors and then transmit the encoded gradients. This small amount of feedback from the workers to the PS ensures that the scheme is very computation-efficient, i.e., the gradient can be computed as soon as enough copies of each chunk have been processed. Thus, our scheme is **guaranteed** to be better than any of the prior schemes that do not work with the feedback. This statement is true regardless of the considered failure rate. \n\n The second part of the question has to do with experiments corresponding different values of $\\ell$. This is a valid point and more experimentation needs to take place to compare the overall job execution times for different values of $\\ell$, i.e., exploring the time for communication vs. the time for computation space. However, we emphasize that our main contribution is the design of the protocol that works for any value of $\\ell$ and has provable performance guarantees that are backed up by numerical experiments.\n\n_[Question-4]_ - We provided spot instances as an example where failures are known to happen and highlighted the fact that these are used in many cases as they are offered at around 90\\% discount in many cases. However, the type of calculation requested by the reviewer is beyond the scope of our work and not its main focus.\n\n_[Question-5]_ - In line 110-113 (pg. 3) of the manuscript, we have pointed out that the workers know the assignment matrix and the ordering of the chunks within the workers. This is shared at the beginning of the protocol and does not change afterward. Following this, in the actual protocol, $\\psi$ only contains the counts.\n\n_[Question-6]_ - This is not correct. The number of columns in $\\mathbf{B}^{(j)}$ is always $\\ell$ regardless of how many workers process the $j$-th chunk. Instead, there will be more variables within $\\mathbf{B}^{(j)}$ that need to be solved for. For instance, eq. (8) of the manuscript and the surrounding discussion discuss an example where $\\ell=2$ and $\\mathcal{D}_1$ is processed by 3 workers.  In our analysis in Section 2.1 (pg. 5) we discuss that if $\\Delta > \\ell$ workers process the $j$-th chunk then we have an under-determined least-squares problem, where we will work with the minimum $\\ell_2$-norm solution. It is well-known that this solution is unique, so that the workers can independently agree on it.\n\n_[Question-7]_ - We are assuming that the worker has not yet transmitted the encoded gradient. In this case it will be treated as a failure, e.g., $W_3$ in Fig. 1b of the manuscript which is discussed in Sec. 2.2 (Illustrative Example).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their insightful comments. We have provided exhaustive bulleted responses to each question and weakness that has been pointed out by the reviewers. In some cases, essentially the same comment appears as a weakness and a question. In this case, we have provided a joint response. This global response also contains a PDF document with two sets of figures that form part of our response.

The reviewers as a whole have raised the following important issues about our manuscript. We provide a concise response to each of them here and direct the reviewers to the individual responses for more details.

**The communication overhead of our scheme (ryxi, TB09, aGFU)**

In our response to TB09 and aGFU, we consider a specific example (typical of deep learning) where the parameter is of length 100 million and the cluster has 1000 workers. A simple calculation shows that the communication overhead of our scheme is essentially negligible when compared to the time taken to convey the encoded gradients.

Furthermore, we implemented a simple baseline scheme with a PS and _m=30_ workers within AWS with t2.medium instances. We used the MNIST dataset with a CNN model with 1,199,882 parameters. The dataset is divided into _N=m_ chunks and the workers are given disjoint chunks. However, in our system, we also had each worker transmit an integer when it finished processing its assigned chunk. In the global PDF, Fig. 2, we have plotted the average amount of time it takes for computing the gradient, transmitting the gradient and also transmitting the integer from the workers to the PS. As can be observed, the time to communicate the integer is about 3-4 orders of magnitude lower than the time to communicate the gradient. Thus, even if this communication is repeated 10 - 50 times, the overall communication time will change only by a tiny negligible amount. Furthermore, for models with hundreds of millions of parameters, this additional communication will be even smaller.

We acknowledge that a full simulation, that compares different protocols on a larger dataset with a larger model, would make the point more forcefully. However, we hope that this serves to convince the reviewers that both our theoretical arguments and the numerical experiments indicate that the communication overhead of our scheme is negligible.

**The benefits of encoding the gradients in our protocol (TBo9).**

In addition to leveraging worker feedback for "computation-efficiency", we also provide a solution that is "communication-efficient" and numerically stable. Communication-efficiency means that the workers communicate vectors of length $d/\ell$ (recall that $d$ is the number of parameters). Reviewer TBo9 correctly identifies that with coordination amongst the workers, it may be possible to arrive at a protocol where the workers send partial sums of non-overlapping gradients that can be summed by the PS to obtain the required gradient. However, such an approach will only work when $\ell=1$. In the communication-efficient case, when $\ell \geq 2$ it is no longer straightforward to assign responsibilities to the workers such that the PS can decode the gradient only from partial sums. In particular, the work of [21] addresses this issue using polynomial interpolation under the original gradient coding model. 

We hope this convinces the reviewers about the need for our communication-efficient algorithm that allows for the workers to independently arrive at the same overall encoding matrix and allows the PS to recover the required gradient. 

**Comparisons with specific existing protocols (aGFU).**

We thank the reviewer aGFU for pointing out the reference by Ozfatura et al. 2022. We point out that their scheme is a so-called multi-message scheme which only works with $\ell=1$. This means that within an iteration, each worker send multiple encoded gradients to the PS. Thus in general, their scheme will be much more communication-intensive. To address this comment, we performed comparisons of our approach with their  paper (Section V, scheme specified in Fig. 4 and 5 of  Ozfatura et al. 2022). 

Fig. 1 in the global PDF document shows the corresponding MSE curves and curves quantifying the number of encoded gradients sent by their scheme and ours.  One can see, e.g., when there are $\alpha =5$ failures at $T=6$ seconds, our scheme has MSE almost zero, while the CCPR scheme has an MSE of about $10^{-2}$. Moreover, the CCPR scheme requires about 37 encoded gradients to be transmitted from the workers to the PS while our scheme only needs 15. Our scheme is thus superior in both respects.

**The computational overhead of solving least-squares problems at the workers (aGFU).**

We emphasize that each least-squares problem is of order $O(\ell^3)$ and the $i$-th worker solves $\ell \delta_i$ of them ($\delta_i$ is the number of chunks assigned to the $i$-th worker). As $\ell$ and $\delta_i$ are small integers, the complexity of the least-squares step is negligible.

**Questions about failure rates under which our protocol does better as compared to previous schemes (WVfvp).**

Our scheme allows the PS to decode as soon as enough copies of each chunk have been processed in the cluster (for the exact case). As soon as this happens, the PS sends the encode-and-transmit vector, following which the workers determine their encoding vectors and then transmit the encoded gradients. Thus, our scheme is guaranteed to be better than any of the prior schemes that do not work with feedback. This will be true regardless of the considered failure rate.

Meta-review: This paper studies the problem of gradient coding in distributed learning with stragglers. This paper presents a novel setting of partial stragglers. The paper proposes a novel algorithm where redundant computation is introduced to compensate for slow straggling worker nodes. One limitation is that the proposed method requires more communication but on the other hands allows better performance in the partial struggling scenario. Still, this may be a reasonable tradeoff for some applications.

All reviewers pointed out that the paper is not very well written, so I would encourage the authors to incorporate the reviewer feedback and polish the manuscript presentation.

The authors provided extensive rebuttal answers that addressed most of the reviewer concerns. 

One of the reviewers provided a low score (3) which lowers the average but did I think that their concerns were valid and they did not respond to the rebuttal. 

Overall I recommend that this paper is accepted since it proposes a novel algorithm for an interesting and natural setting.
Decision: Accept (poster)