Lightweight Projective Derivative Codes for Compressed Asynchronous Gradient Descent

Coded distributed computation has become common practice for performing gradient descent on large datasets to mitigate stragglers and other faults. This paper proposes a novel algorithm that encodes the partial derivatives themselves and furthermore optimizes the codes by performing lossy compression on the derivative codewords by maximizing the information contained in the codewords while minimizing the information between the codewords. The utility of this application of coding theory is a geometrical consequence of the observed fact in optimization research that noise is tolerable, sometimes even helpful, in gradient descent based learning algorithms since it helps avoid overfitting and local minima. This stands in contrast with much current conventional work on distributed coded computation which focuses on recovering all of the data from the workers. A second further contribution is that the low-weight nature of the coding scheme allows for asynchronous gradient updates since the code can be iteratively decoded; i.e., a worker's task can immediately be updated into the larger gradient. The directional derivative is always a linear function of the direction vectors; thus, our framework is robust since it can apply linear coding techniques to general machine learning frameworks such as deep neural networks.


Introduction
The majority of machine learning problems take the form: find a function h w0,...,w k in some family of hypothesis functions H that are parameterized over the w 0 , ..., w k which (1) where the D i are the datapoints, the x i are the input features, and the y i are the output features.
If the h w0,...,w k are smoothly parameterized by the w 0 , ..., w k , then this is usually accomplished by performing gradient descent on the summation of loss functions of the form l i (w) = l(h w (x (i) ), y (i) ) to compute i.e., find the w that best fits D. For example, one of the most common loss functions, l(f, y) = 1 2 ||f − y|| 2 , gives us the mean squared error and the ubiquitous method of least squares.
If the dataset D has many datapoints D i then the overall computation, or job, is distributed as tasks amongst workers, which model a distributed network of computing devices. This solution creates a new problem; stragglers and other faults can severely impact the performance and overall training time. An emerging technique is to use distributed coded computation to mitigate stragglers and other failures in the network. Many of the current algorithms only encode the data; this paper proposes further encoding the directional derivatives as well in such a way that allows for asynchronous gradient updates using low weight codes. Furthermore the number of weights usually grow quite large as well 1 , which necessitates a "2D" coding scheme which codes both the data and the derivatives.

Related Work
The two algorithms which we use to benchmark our algorithm are Gradient Coding  and K-Asynchronous Gradient Descent (Dutta et al., 2018b;; however, many of the design of our coding scheme is also influenced by the works in , (Yu et al., 2017), and (Dutta et al., 2020).

GRADIENT CODING
In the gradient coding Gradient Coding  scheme the main idea is to encode the derivatives with respects to the data partitions ∂ ∂Di from Eq. (1); since the loss function in Eq. (2) splits up into a sum of smaller loss functions, l i , in terms of the partitions, D i , linear codes can be efficiently applied to the gradients ∂ ∂Di . This work has gone on to spawn many works (Atallah & Rahnavard, 2018;Charles & Papailiopoulos, 2018;Ye & Abbe, 2018;Halbawi et al., 2018;Ozfatura et al., 2019b;Karakus et al., 2019;Ozfatura et al., 2019a;Horii et al., 2019;Raviv et al., 2020;Reisizadeh et al., 2019a;Maity et al., 2019;Bitar et al., 2019;Amiri & Gündüz, 2019;Reisizadeh et al., 2019b;Sasi et al., 2020;Wang et al., 2021;Ozfatura et al., 2020;Bitar et al., 2020;Zhang & Simeone, 2021); gradient coding is currently a vibrant topic of research. The main improvements of our coding scheme over the state of the art in Gradient Coding is that our code: can perform asynchronous coded updates, allows the backpropagation itself to be coded (which greatly reduces the communication complexity for high dimensional data), our code has 0 encoding and decoding overhead in terms of multiplications, and has an overall reduction in the redundancy of data/memory overhead.

ASYNCHRONOUS GRADIENT DESCENT
The main idea in Asynchronous Gradient Descent (Ferdinand et al., 2017;Dutta et al., 2018b;Ferdinand & Draper, 2018;Ferdinand et al., 2020;Dutta et al., 2021) is to simply perform a gradient update when whenever a specified number, k, workers have returned. The name "asynchronous" comes from the eponymous concept in distributed computing where communication rounds are not synchronized.

GENERAL CODED DISTRIBUTED FUNCTION COMPUTATION SCHEMES
The main idea in , (Yu et al., 2017), and (Dutta et al., 2020) is that one can distribute large matrix multiplications amongst workers and encode the smaller block matrix operations. The works initiated much research in distributed coded matrix multiplication (Dutta et al., 2020;Lee et al., 2017;Baharav et al., 2018;Dutta et al., 2018a;Wang et al., 2018;Soto et al., 2019;Dutta et al., 2019;Das & Ramamoorthy, 2019;Hong et al., 2021). Further work has been extended to include batch matrix multiplication as well (Yu et al., 2019;Jia & Jafar, 2020;Soto et al., 2022). The main drawback of these (multi-)linear methods is the non-linear activation functions; in particular, these methods can only encode the linear computations between the layers of a network. Another interesting approach is to attempt to encode the neural network itself (Kosaian et al., 2018;; however, this approach suffers from long training times dues to combinatorial explosion of different fault patterns is there are enough stragglers.

Contribution
The main contributions of this paper are to introduce a novel coding scheme for gradient descent that: allows for asynchronous gradient updates, maximizes the amount of information contained by random subsets of vectors, minimizes the weight of the code, compresses the gradient in a manner that scales well with the number of nodes, and achieves a lower a communication complexity and memory (storage) overhead with respect to the state of the art. Another improvement of our algorithm over the state of the art is to consider the correct information metric; all of the other coding schemes assume that the Hamming distance is the correct metric, which does not consider the natural (differential) geometry of the gradient. We will show that the correct distance is the one given by the real projective space 2 RP n . Furthermore, we will show that our coding scheme, i.e., our choice of coefficients, maximizes the amount of information returned by the workers and furthermore has zero decoding overhead (in terms of multiplications) since the master can just directly add and subtract the results returned by the workers without needing to decode the information.

Background
We quickly give some important definitions and background from coding theory, information theory, and geometry. In coded distributed computing an erasure code is a pair of functions C = (E, D) where the workers tasks are given by the encoding procedure θ 0 , ...,θ n−1 := E {θ 0 , ..., θ k } and a decoding procedure for some family of fault-tolerant subsets, F C , such that If F C consists of all the m-subsets (for some integer r) of θ 0 , ...,θ n−1 , then C can correct any r := n − m erasures or stragglers; furthermore, if r = n − k then the code is a maximum distance separable (MDS) code. If the encoder E is given by a generator matrix G C , i.e., if then C is called a linear code. The weight of a linear code is the maximum number of 0's in the rows of the matrix G C ; the importance of the weight metric stems from the fact that it measures the amount of work that the workers do since the rows of G C are the worker tasksθ i . Thus, in order to avoid confusion we will use t to denote the weight of the code as well as the number of tasks that each worker does; equivalently t is the number of data partitions on the workers. To further simplify notation we abuse notation and use C in place of G C and E C when the context is clear.
A potential point of confusion is that the θ need not be the weights w of the h w . This is because the derivative of loss function L also implicitly takes the data D i as an input; this is an important insight used in all gradient coding algorithms. One of the key insights of this paper is to allow the coded gradient to be linear combinations of both ∂ ∂Di and the ∂ ∂wi . An important notational convention is that we let the D i be partitions (or batches) of the data set instead of just datapoints as is common in the gradient coding literature; in particular, D 0 , ..., D t−1 denotes a partitioning of the dataset into t pieces.
The reason for the name "maximum distance separable code" is that an MDS maximizes the distances between the codewords E {θ 0 , ..., θ k } using the Hamming distance; in particular, maximum distance separable means that the code wordsθ ∈ C have achieve the maximum max C :code on Θ minθ ,θ ∈C d(θ,θ ) where d is the Hamming distance. There are two problems with this approach: the first is that MDS codes in this context require arbitrarily large amount of work, i.e., they have a large weight, and the second is that the classical discrete MDS codes are using the wrong metric. This paper proposes to use the metric given by the projective geometry 3 on the space of derivatives. Here we mean maximum distance separable with respect to the distance function d(θ, θ ) = min{arccos θ ,θ , arccos −θ,θ }.

General Overview of the Design Principles
Consider the case where there are two derivatives and we wish to create two parity tasks using only summation and subtraction in the encoding procedure. Such a code is given by the following generator matrix which adds fault tolerance to the job I = 1 0 0 1 with the parity tasks P = . This code has the serendipitous property of having negligible decoding complexity and negligible communication complexity! For example, if the master receives ∇ in the directionθ 3 = 1 √ 2 (θ 0 + θ 1 ), then the master can decrease both θ 0 and θ 1 by the value returned by W 2 , i.e.,θ 2 , if the master receives ∇ in the directionθ 2 = 1 √ 2 (θ 0 − θ 1 ), then the master can decrease θ 0 and increase θ 1 by the value returned by W 3 , i.e., θ 3 . The master need only perform 2 additions/subtractions, and more generally (see Eq. 4) if there are t "sub-tasks" the master only needs to perform t additions/subtractions. The multiplication by 1 √ 2 can be subsumed by the learning rate; thus, our code has zero multiplication overhead. Furthermore, this information can be communicated using only one float, since the master knows which direction/worker the derivative was computed from.

What is the Optimal Choice of Directions?
Looking at Fig. 1, we see that the code G is MDS in the sense that it maximizes the independence between the vectors. Equivalently 4 G minimizes the confusion between codewords or minimizes the mutual information between codewords; thereby maximizing the entropy or the information content. As we will soon see this has the effect of allowing lossy low-distortion compression for larger codes. A second contribution of this paper is to show how to preserve an approximate MDS property for larger codes which allows for this form of compression.
In what sense does C being MDS imply fault tolerance? The following example illustrates one kind of error which the code is immune to: Consider the case where two workers return the derivatives in the directionsθ = By inspecting the second diagram in Fig. 1, it is easy to see that lim →0θ → −θ, so that lim →0 arccos θ ,θ → π.We will also show that the Figure 1. The code C is MDS with respect to the the distance between the codewords. It is easy to see that −θi carries the same information asθi and it is therefore inefficient to include it since it is a form of replication coding. Likewise we should not include a vector that makes a small angle withθi for the same reason. The geometry of this problem is that of RP 1 , i.e., the real protective line. This is because the directionsθ and −θ are information theoretically equivalent. The second figure displays the relationship betweenθ andθ . Asθ becomes more linearly independent fromθ it begins to carry more novel information that cannot be inferred fromθ. At the "greenest" extremesθ andθ become statistically independent which is the maximum entropy configuration. Maximum entropy is equivalent (see Fn. 4) to maximum information about the θi.
error in the derivative can get bigger and bigger as → 0.

Motivating Example: Base Case of LWPD Codes
The last example did not allow us to show the more general lossy compression phenomenon that can occur for more general codes. Also we will soon prove that it is impossible to have MDS codes for large dimensions where the workers perform a small amount of work 5 . In a sense, k = 2 is a very special case. Therefore before showing the general compression phenomenon, let us show how to compress the derivative for k = 4. 1 2 ||h − y|| 2 , u input features x i , and space of hypothesis functions , H is the space of multinomial logistic regression functions (however, this procedure will work for any feed-forward deep neural network, see Fig. 2). Similarly to the previous design we can give the following directions to the workers however, this time we let ∂ ∂θ0 ="the derivative of the first half of the output nodes with respect to the first half of the dataset", ∂ ∂θ1 ="the derivative of the second half of the output nodes with respect to the first half of the dataset", ∂ ∂θ2 ="the derivative of the first half of the output nodes with respect to the second half of the dataset", and ∂ ∂θ3 ="the derivative of the second half of the output nodes with respect to the second half of the dataset". We can see that "lossy" part of the lossy compression is that the 4 workers don't necessarily return the gradient perfectly, but we will later prove that they return a pretty good approximation of it. However, we had a second further lossy compression step to our code; we give workers 5 and 6 the data partitions D 2 , D 3 and give workers 7 and 8 the data partitions D 1 , D 4 instead of giving these workers all of the partitions as the code in Eq. 3 suggests.

General Code Construction
We first show how to construct what we will denote as a [n, k, t]-projective derivative code, or [n, k, t]-code, for n = 2 m , k = 2 l and t = 2 p , i.e., n, k, t are all powers of 2, and then show how to use "cyclic" and "toroidal" permutations to construct the code for more general k, n; however, the t is always chosen to be a power of two for reasons that will soon become clear. The parameter n is the number of workers, k the number of derivatives/features, and t is the number of sub-tasks that each worker will perform; i.e., the number of derivatives per worker. Figure 2. The different ways to partition the backpropagation gradient. The first partition shows how to partition the gradient for a simple neural network with no hidden nodes. The two other partition corresponds to a more general deep-neural network with hidden nodes. The last partition shows how to apply the recursive step in Alg. 2.

The Characteristic Vectors
To construct the code we first construct the characteristic vectors from the following family of functions χ α : F p 2 −→ C, defined by the lambda expression where α, β ∈ F p 2 are defined as binary strings of length t and α, β is the dot product on α, β ∈ F p 2 , which is equivalent to taking the bit-wise AND 6 of α and β and then taking the XOR 7 of the result. In particular, α, β is defined as It is an elementary fact of representation theory that the vectors, √ 2 p χ α correspond to the irreducible representations of F p 2 in C and are therefore an orthogonal basis see Thm. 6 of (Serre, 2012) or Thm. 2.12 of (Fulton & Harris, 1991). One can also prove this fact by direct computation using discrete Fourier analysis see ch. 4 of (Tao & Vu, 2006). 6 AND is the logical conjunction, denoted by ∧, i.e., a ∧ b = 1 if a = b = 1 and a ∧ b = 0 otherwise. The bit-wise AND of two sequences α = α0...αp−1, β = β0...βp−1 is α ∧ β = (α0 ∧ β0)(α1 ∧ β1)...(αp−1 ∧ βp−1) 7 XOR is the exclusive or, denoted by ⊕, i.e., a ⊕ b = 1 if a = b and a ⊕ b = 0 if a = b.

Construction for Powers of Two
If we identify the binary strings α, β with the integers that they represent and let X (t) be the matrix defined coordinatewise by the equation where p = log(t) and χ α : F p 2 −→ C and let L (t) and R (t) be the matrices defined by the equation then we can define C (2k,k,t) , the generator for the [2k, k, t]code, as

Lightweight Projective Derivative Codes
where 8 s is the ratio of tasks to sub-tasks, θ (t) i is the sequence of sub-tasks θ it through θ (i+1)t−1 , andθ (t) i is similarly defined as a sequence of t consecutive workers. Equivalently if we define the "'rectangles" R (t) u,v as then we can define C (2k,k,t) coordinate -wise as It is straightforward to prove the following beautiful property Lemma 3.1. The matrices X (t) satisfy the following recursion relation Proof. This is a direct consequence of Thm. 10 in (Serre, 2012).
An alternative is the weaker statement 9 "X (2) is a Hadamard matrix and the tensor product of two Hadamard matrices is a Hadamard matrix" whose proof can be found in (Huffman & Pless, 2003).

DATA-&-GRADIENT-PARTITION FOR POWERS OF TWO
Similar to the example given in Sec. 2.2 we give the workersθ i the data partition given by Alg. 1. The

Algorithm 1 Data Partition Assignment
Input: data D, code parameters (n, k, t) Partition the data D into D 0 , .., D k−1 idea behind Alg. 1 is simple; we give the first worker 8 Equivalently, we can write these definitions as s = k t and θ (t) i = θitθit+1...θ (i+1)t−1 9 Although a weaker statement it suffices to to prove the claim of optimally,i.e., Thm. 4.5.
Data[θ 0 ] = D 0 , ..., D t−1 , and the second worker Data[θ 1 ] = D t , ..., D 2t−1 , and so on up to worker k, at which point we give the workers k, ..., n a cyclic shift of the previous assignment, e.g, worker k gets Data[θ k ] = D t 2 , ..., D t+ t 2 . The procedure for partitioning and encoding the gradients, Alg. 2, is slightly more involved; however, the main idea is illustrated in Fig. 2. The main intuition behind Alg. 2 is to

Algorithm 2 Gradient Partition Assignment
Input: network x, z 0 , ..., z m , y, code parameters (n, k, t) Set C := C (n,k,t) Partition y into t groups y (i) where y (0) = (y 0 , ..., y t−1 ); . . . ; Recursively call "Gradient Partition Assignment" on the network x, z 0 , ..., z m parameters (n, k, t) as in Fig. 2 to encode grad[θ i ] according to row i in C by repeatedly splitting the (non-zero-)row by t end for end if encode the gradient in the manner in which backpropagation occurs; this allows for the iterative decoding/gradient update at the master node, which in turn allows for asynchronous gradient updating.

Construction for General Parameters
Given some general (n, k, t) we construct the matrix C (n ,k ,t) , where n and k are the next nearest powers of 2 (repeating rows if necessary) and use a "2-D" permutation algorithm similar to (Fan et al., 2020) to distribute the sub-tasks in each round; however our algorithm uses more general (prime number) step-sizes chosen in each round and the permutations now occur in "higher dimensions 10 ." In particular; we now use a similar procedure to permute tasks amongst workers if n and k are not powers of 2. For example if we have n = 6 workers and k = 3 tasks we can add extra virtual tasks θ 3 = θ 0 , θ 4 = θ 1 , . . . , θ x = θ x%3 and perform the following toroidal permutations on C (5,3,2) so that at round r worker i performs task θ i+5r%n and similarly at round r we have t i = θ i+r%k .
More generally we find a displacement d equal to an (odd) prime number that is co-prime 11 to k and we let worker i performs task θ i+dr%n at round r and let t i = θ i+r%k at round r. This allows gives the following statistical uniformity lemma: Lemma 3.2. If the displacement, d, is equal to an (odd) prime number that is co-prime to k then the blue rectangle in (the general form of) Eq. 5 will visit every entry in the matrix with every possible pattern of X (t) and every cyclic permutation of the t i contained inside of the blue rectangle.
Proof. The leftmost point of the blue rectangle is equal to (i, i) + r(1, d) ≡ (i + r, i + dr) mod Z/n Z × Z/kZ. By the Chinese remainder theorem (see (Ireland & Rosen, 1982) or (Dummit & Foote, 2003)) (1, d) is a generator of mod Z/n Z × Z/kZ since d is coprime to 1, k, and n .

Theoretical Analysis
In this section we give a theoretical comparison of the algorithms, see Table 1, and we prove theorems regarding the existence and non-existence of codes with certain properties. The following theorem, i.e., Thm. 4.1, shows that Hammingdistance MDS coding schemes must have the workers do an arbitrarily large amount of work. We then later show that our codes are approximately MDS with respects to the projective geometry metric which maximize the amount of information sent back by the workers 12 while keeping the rectangle (see Eq. 5) is visited. 11 Although it is notoriously hard to find a prime divisor of number, it is surprisingly easy to find a prime non-divisor. This easy to see since one can just test divisibility by 2,3,5,... and since the product of the first primes less than 100 is approximately equal to 2 120 this will halt very quickly, i.e. it will halt in less than 25 steps for k < 2 120 since there are only 25 primes less than 100.
12 This is because large angles gives us large conditional entropy. amount of work done by the workers as low as possible; i.e., there are approximately projective-MDS that have weights t = 2, ..., n.
Theorem 4.1. If the parameters (n, k, t) satisfy t ≤ n − k then there is no Hamming-distance MDS (n, k)-code for the derivatives.
Proof. If A(C) i ="number of rows of weight i", then Theorem 7.4.1 in (Huffman & Pless, 2003) gives us that an MDS will have A(C) i = 0 for i ≤ n − k.
In particular; the proof of Thm. 4.1 can be strengthened to say that: Corollary 4.2. In an MDS (n, k)-coding scheme A(C) i = 0, for i ≤ n − k, where A(C) i = 0 is the weight distribution of a code.
The importance of Cor. 4.2 is made clear through the following interpretation: Corollary 4.3. In an MDS (n, k)-coding scheme all of the workers must do at least n − k amount of work.
However a simple observation of the construction given in Sec. 3.2 gives us that: Theorem 4.4. There exists (n, k, t)-LWPD codes for any t ≥ 2.
The next theorem proves that under the projective distance we have that our code achieves approximately maximal distance.
Theorem 4.5. The family (n, k, t)-code are approximately MDS (n, k)-code for the derivatives in the projectivedistance for n ≤ 2k.
Proof. By Lem. 3.2 it suffices to prove this for powers of two. The distance between any vectors is arccos 1 2 = π  vector; the distance is equal to the maximum π 2 for all other vectors.
The proof of Thm. 4.5 gives us that the distance between any two codewordsθ,θ is bounded above by d(C) = minθ ,θ∈C d(θ,θ) = π 3 and thus in term of percentages of the optimal π 2 we have π 2 − d(C) of the "theoretical" optimal distance; however there can be no code that achieves the "theoretical" optimal distance: Theorem 4.6. The percentage in Eq. 6 cannot be made 100%; i.e., there are no projective MDS codes for n > k which achieve distance π 2 .
Proof. If this statement was false there would be n + 1 linearly independent vectors in n-dimensional space, F n .
An interesting fact about the bound given by Thm. 4.5 is that is a constant independent of the dimension of the code and thus it scales well for larger and larger number of workers.

Experimental Results
The experiments were run on AWS Spot Instances; the workers are AWS EC2 c5a.large instances (compute optimized) and master is an AWS EC2 r3.large instance (Memory Optimized). The experimental procedure was written using Mpi4py (Dalcín et al., 2005;2008) in Python. We used a modification of the code in  written by the first author of  to implement Gradient Coding (GC) as well as the random data generation; the implementation only supported logistic regression and we generalized it to support multinomial logistic regression (i.e., more than one class). The software in  used a Gaussian mixture model of two distributions to create input features for the logistic model; we generalized it to allow for an arbitrary number of Gaussian distributions in the mixture to create a robust data set. To be as fair as possible in our comparison with K-Asynchronous Gradient descent (K-AC) (Dutta et al., 2018b) we made setup for K-AC nearly identical with the exception of the coding scheme; i.e., K-AC and LWPD used the exact same data partitions and same number of k workers in the k-asynchronous batches.
We ran experiments with 8 workers, 16 workers, and 32 workers (see Fig. 3). The testing error (i.e., the workers do not train on the test data) is plotted against the time. In all of the experiments we ran LWPD codes converged far faster; however, it often overfitted and sometimes the other algorithms would eventually get a lower test error. There are two possible explanations for this: either LWPD converges so much faster than the other algorithms that they never get a chance to overfit or the noise that initially helps LWPD find a very quick solution eventually causes it to stay some distance from the optimal solution. There is evidence for both of these possibilities because there are experiments were the other algorithms do not catch up to LWPD; see Sec. A for more results.
We have modified and re-ran our experiments to allow for deep neural networks (see Fig. 4). The new architecture had ReLU activations at the hidden nodes, Softmax at the output nodes, and cross entropy as the loss function. The experiments were run using Mpi4py on AWS Spot Instances with AWS EC2 c5a.large for the workers and AWS EC2 r3.large for the master. The original authors' implementation of Gradient Coding did not support deep neural networks and thus we simply compared with K-Asynchronous Gradient descent for these experiments. Both the updated and original experiments contained stragglers and highlighted the asynchronous nature of the algorithm, since we used Amazon Spot instances, which are the most unreliable but cost-efficient machines that Amazon AWS can offer.
In our experimental setup, all workers compute training loss individually. These plots should not be considered a centralized measure of model performance because the data set is decentralized. Thus, plotting training metrics does not make as much sense as, for example, visualizing the testing/validation set error or loss. Furthermore, we were guided by the intuition that the validation error is the more important measure, since it measures how well the algorithm or model can perform on data it has not seen.
The experimental data plots show test loss (y-axis) versus the time elapsed (x-axis). The test loss refers to the error on the validation set (which the model is not trained on) and thus overfitting occurs when the training loss continues to decrease, but the generalization error stops decreasing and eventually begins to grow. In our experiments, we observed that other methods reach similar convergence point much later in terms of number of iterations. One hypothesis is that our gradient coding approach offers faster training. A second possible explanation comes from the lossy compression of our algorithm. We trade off error for runtime. Our hypothesis is that the noise coming from the trade-off is beneficial in that it prevents us from being stuck in any potential saddle point.

Conclusion and Open Problems
We propose LWPD codes which allow for asynchronous gradient updates by maximizing the amount of information contained by random subsets of vectors and minimizing the weight of the code. Our code compresses the gradient in a manner that scales well with the number of nodes (and the dimension of the data) and achieves a lower a communication complexity and memory overhead with respect to the state of the art. Another improvement of our algorithm over the state of the art is our discovery of the correct information metric; all of the other coding schemes assume that the Hamming distance is the correct metric, which does not consider the natural (differential) geometry of the gradient. Furthermore, we showed that our code was very efficient since the master can just directly add and subtract the results returned by the workers without needing to decode the information. We proved many of the complexity guarantees theoretically and also provided much empirical evidence for the performance. For future work we would like to strengthen the theoretical results by proving stronger complexity bounds as well as further investigating the effect of noise (or lossy compression) on the performance; it seems that at first the lossy compression is a great help but eventually it causes over fitting.