Leveraging partial stragglers within gradient coding

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. Existing 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. The 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.

Strengths

- The proposed GC idea seems to be novel, particularly the distributed gradient encoding. - The math, as far as i checked is correct. - The example in Section 2.2 was helpful and improved readability. - 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. - 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. - 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. - Various aspects of the work remain unclear (see Questions). Minor: - Lines 46 and following: $nnz(v)$ is commonly typesettes (as a function) as $\text{nnz}(v)$. Similarly for later occurances.

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? - 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? - 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? - 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? - 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? - 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. - How would the protocol handle a case where a worker during or after the gradients get encoded becomes unresponsive?

Rating

3

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

While the authors provide a limitations section, cover potential limitations seen by me (see Questions and Weaknesses).

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.

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. - 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). - 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. - Some relevant literature is not considered.

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: E. 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. Please 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). The 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.

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

2

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.

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.

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. 2. 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. 3. 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.

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). 2. 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.

Rating

4

Confidence

4

Soundness

3

Presentation

2

Contribution

2

Limitations

See weakness and questions.

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. For 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.

Strengths

- The authors study a relevant problem of interest for the ML community. - The paper is well-structured and clearly explains the problem, the proposed solutions. It is easy to read and understand its main points. - 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. - 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. - 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. - 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.

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? - 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.

Rating

6

Confidence

3

Soundness

4

Presentation

3

Contribution

3

Limitations

The authors adequately addressed the limitations of their work.

Post Rebuttal

I thank the reviewers for addressing my concerns. After carefully reading the comments from the other reviewers and the authors' responses I have decided to keep my score.