Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a new coded distributed gradient descent approach to mitigate the effect of stragglers in the distributed computation of gradients. The authors combine prior schemes on coded distributed gradient computation with repetition of unfinished tasks from straggling nodes across computation rounds with the assumption being that the overall computation can tolerate a finite amount of delay. Experiments on a distributed gradient descent task on AWS Lambda shows improvements over prior uncoded and coded approaches.
strength_and_weaknesses: Strengths:

1. The approach considers sequential computations and is designed based on the trends in straggling over time. The temporal aspect of straggling has not been considered by most prior coded distributed computing works and is arguably more practical in real scenarios (as also demonstrated by the experiments in this work).

2. The proposed approach is faster than baselines in real serverless computing settings (AWS Lambda) and reduces the computation load at workers which may be especially relevant for emerging frameworks like serverless computing where the individual instances do not have a lot of computing capacity.

Weakness:

1. The approach will improve over prior gradient coding works only when a finite amount of delay ($T>0$) can be tolerated. The authors consider a scenario where multiple neural networks are trained on the same dataset in their experiments where such a delay can be tolerated. However, it is unclear when this would happen in practice because typically gradient descent is a sequential operation with successive iterations of a single model being performed where such a delay would not be acceptable because the gradient from each round is needed for the next round. Please provide some examples/references to back this claim.

2. The proposed approach seems to strongly depend on the choice of hyperparameters ($B$, $W$, etc.). Indeed, the authors perform additional experiments to select the right hyperparameters. Given, the extra cost/latency of performing these added experiments, and the extra cost/latency of decoding the coded gradients, neither of which is included in the time measurements, it is unclear if the proposed schemes will give any net improvements over the uncoded scheme, especially since model training is a one-time operation where a small amount of straggling may actually not be a very significant issue. Therefore I would like to see either that the gain is significant after taking these factors into consideration or that incorrect/different choices of hyperparameters for the same setting do not lead to much differences in performance since that would imply that the extra experiments to choose the hyperparameters will not be needed.
clarity,_quality,_novelty_and_reproducibility: The paper is clear overall and the proposed scheme is novel within the context of coded distributed gradient descent. I have the following three comments/suggestions on the writing:

a. The audience, especially at ICLR, may not be familiar with the use of erasure codes for straggler mitigation in distributed computing. Therefore, I feel it would be better to provide some background on the general area of coded computing to make the paper more accessible at this venue.

b. Likewise it may be beneficial to provide some details on the Gilbert Elliot model and its deterministic counterpart to clarify why it is a suitable model for stragglers.

c. Please include a conclusion section.
summary_of_the_review: The paper introduces a new coded distributed gradient computation approach for mitigating stragglers in distributed gradient descent. While the approach improves over baselines if a finite delay in the computation can be tolerated, it is unclear where such delays would be acceptable in practice. Moreover, given the added cost/latency associated with choosing the hyperparameters for this approach the net gain over the uncoded approach is not yet clear.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper develops schemes to protect distributed gradient descent from stragglers building on previous work that induces redundancy in computation via error correcting codes. The authors specifically build on a technique called gradient coding that enables a master node to recover the sum of the gradients from $n$ distributed works, even if a certain prescribed number ($s$) nodes straggle (i.e., fail to provide their computation within a time-out). 

While gradient coding can protect each of the $\binom{n}{s}$ straggling patterns in every iteration, the authors here aim to be less conservative and aim to protect a subset of the straggling patterns that seem to occur more commonly in practice. They make two assumptions (1) there is some negative correlation in the straggling patterns - a node that  straggles in a given iteration is assumed to not straggle in $B$ iterations later, and (2) that the number of distinct stragglers in any given time-window is limited. For these assumptions, the authors develop new coding schemes that improve upon gradient coding in terms of the amount of redundancy required.
strength_and_weaknesses: Strengths:
+The redundancy of gradient coding can be quite a lot, and the recognition of structure among the set of stragglers in AWS lambda and reducing the overall redundancy is a positive contribution.   
+The developed coding schemes are novel and clever - even though they do build upon the idea of gradient coding.
+ The results are experimentally validated, and the experimental results are quite promising, and indicate the usefulness of carefully designed redundancy in AWS Lambda.

Weaknesses:
- The main use case for the developed technique is the application of training $M$ distinct models on the same data set. This seems to be a narrow - perhaps even contrived - use case as I see it. It is also inevitable that the developed technique cannot be applied to the most common use case of training a data set, due to the coding scheme incurring a delay in decoding (the sum of partial gradients at iteration $t$ is decoded at iteration $t+B$).

- In gradient coding, the load is $s+1$ times the load of the common case. Note that this is the same overhead as if the data sets were repeated $s$ times (which is much simpler!). The main benefit of gradient coding, as I understand it, is that it does not necessarily require $s+1$ to divide $n$, whereas replication would require this. In fact, notice that this replication scheme is also a candidate for the experimental results in Fig. 4, as $s=15,n=256$.

I would like the authors to clarify if the above property is also true for the developed coding schemes. If we allowed some additional divisibility criteria to be satisfied among the parameters, then do simpler schemes such as replication match the performance of the developed schemes?

- There is no statement/result on whether the developed schemes can be improved, or gap to optimality.



 
clarity,_quality,_novelty_and_reproducibility: In Example 3.3.1, the authors claim that "if the master did not receive $g_{2i}(t)$ in round $t$ and round $t+2, ...$.
However, as per my understanding of the model, this can never happen for that example. If $g_{2i}(t)$ does not return, it is because the node straggles in iteration $t$. If it straggles in iteration $t$, it then returns that answer in round $t+B = t+2$, and as per the coding scheme, $g_{2i}(t)$ is necessarily repeated in round $t+2$. Please correct this or add clarifying explanations.

Apart from the above detail, the system model and coding scheme (which is quite intricate) is presented quite clearly.  

--> A small clarification in the explanation of Fig. 14: For a given normalized load, are there 80 "dots" on the y axis corresponding to each job? If this is the case, the figure is the result of several hundreds of jobs? 
If not, then it is unclear what the dots represent.
summary_of_the_review: The paper advances the development of introducing coding based redundancy in training towards mitigating stragglers, and builds on a recent line of work that is of interest to the machine learning community. The recognition of spatial and temporal dependencies in stragglers, and the corresponding coding techniques are novel. However, the application of the techniques is limited to a relatively narrow use case of concurrent training of multiple models on the same data set.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper propose 2 extensions of gradient coding, by adding extra tolerance of stragglers and introducing asynchrony (staleness) to the updates. The theoretical analysis is provided for the computational load. The empirical results show that the proposed schemes are more efficient than the previous works. 
strength_and_weaknesses: Strength:
1. This paper propose 2 extensions of gradient coding, by adding extra tolerance of stragglers and introducing asynchrony (staleness) to the updates. The idea is natural and makes sense.
2. The theoretical analysis is provided for the computational load. 
3. The empirical results show that the proposed schemes are more efficient than the previous works. 

Weakness:
1. The experiment setup (CNN + MNIST) is too simple and small for distributed training. Such a simple task can be finished quickly on a single computer. To justify the efficiency of the proposed methods in practice, larger tasks such as resnet on cifar-100 or imagenet is highly recommended.
2. I recommend to show the sensitivity to the hyperparameters, i.e., how the curve of convergence (training loss) vs. time changes when using different B and W. It is important to show the readers how robust the proposed algorithms are, which will also be helpful for the new users when tuning these hyperparameters.
3. It seems that no convergence proof is provided. Although I think the convergence proof will be trivial since the proof can be reduced to the one for a simple asynchronous SGD algorithm, a convergence proof will make this work more thorough.
clarity,_quality,_novelty_and_reproducibility: This paper is well written with enough details provided for reproducing the experiments.
The proposed algorithms are novel.
summary_of_the_review: This paper propose 2 extensions of gradient coding, by adding extra tolerance of stragglers and introducing asynchrony (staleness) to the updates. The theoretical analysis is provided for the computational load. The empirical results show that the proposed schemes are more efficient than the previous works. I recommend to add experiments for the algorithms' sensitivity to the hyperparameters, and theoretical analysis for the convergence.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: Gradient Coding is a general approach distributed computation (of gradients) in the presence of straggling nodes. The paper introduces two new schemes for GC, where coding is not only done across compute nodes, but also across the time dimension, measured by compute rounds. The first scheme uses the original GC but with selective repetition of unfinished tasks. The second scheme, and main contribution, combines two classes of tasks, one that uses GC and the other that uses repetition. The two classes are multiplexed over workers and rounds in an adaptive manner.  An experimental evaluation is performed on AWS with 256 worker nodes, showing the performance of the new scheme. 
strength_and_weaknesses: Strength:
Using the temporal dimension in GC improves the normalized load per worker. The schemes cover various straggler models (e.g., bursty, arbitrary, fixed number per round). The experimental evaluation is performed in a real AWS environment, with a sizable number of nodes. 

Weaknesses:
The presentation is often hard to follow, due to the heavy and involved notation, although the high level ideas are relatively clear.
clarity,_quality,_novelty_and_reproducibility: The high level ideas and goals are clear, and explained well, but the notation and details are rather cumbersome.
summary_of_the_review: The paper proposes new CG schemes where that use the temporal dimension, and coding is done both across worker nodes and across compute rounds. As a result the normalized load per worker is reduced. Various design parameters are used to accommodate for different straggler models. The experimental evaluation is very good, and shows the performance of the new scheme.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: In this paper, the authors introduce two new techniques for distributed gradient computation in the presence of stragglers. The techniques combine Gradient Coding (GC) with selective repetition of tasks and adaptive multiplexing across workers and rounds. The theoretical analysis and experiments on an AWS Lambda cluster showed improved performance over the baseline GC scheme, leading to a 16% reduction in runtime.

The reviewers and myself identified several strengths, and only a few weaknesses about this work.

Strengths:
- Proposed algorithm is novel: Combines prior schemes on coded distributed gradient and provides new extensions
- Thorough experimental evaluation, in which proposed methods are faster than baselines in real serverless settings (e.g., AWS Lambda) 
- Reduces the computation load at workers 
- Theoretical analysis provided for computational load
- Well written with enough details for reproducing experiments
- The schemes cover various straggler models (e.g., bursty, arbitrary, fixed number per round)

Weaknesses:
- Unclear where finite delay in computation can be tolerated in practice
- The schemes depend strongly on several hyperparameters (B, W, etc.), and there's added cost in choosing them
- No convergence proof provided
- Presentation is often hard to follow due to the heavy and involved notation

The authors incorporated several of the reviewer's comments and made several revisions / additions to their paper to address concerns. These included a discussion on overheads due to decoding and parameter selection, additional experimental results, a discussion on applicability to various practical use cases and on sensitivity to hyperparameter selection error.

Overall, some concerns still remain, but this is a useful paper that will be of interest to a small subset of ML+Sys community within ICLR.
justification_for_why_not_higher_score: The paper although solid is quite limited in it's scope as it addresses a problem in the intersection of ICLR, ML, Sys, Coding theory communities. 
justification_for_why_not_lower_score: The paper presents a concrete set of advances both theoretical and practical in the area of codes for machine learning.
Decision: Accept: poster