Coded Computing for Resilient Distributed Computing: A Learning-Theoretic Framework

Summary

This paper focuses on coded computing for machine learning and derives loss-minimizing encoding and decoding functions.

Strengths

Please see the “Questions” section.

Weaknesses

Please see the “Questions” section.

Questions

My review is as follows: Major: The biggest thing that confused me when reading the paper was the use case for this kind of method. As far as I understand, this method is specifically designed for inference. Inference of computer vision models such as the ones used in the experiments of this paper (VGG, VIT) is actually very fast in practice. Even mobile phones can run inference on these models within a few tens or hundreds of milliseconds. What application would require to run many inferences for these models in parallel in a timely manner? I understand that the results are interesting from a theoretical point of view. It’s nice that encoding and decoding functions can be derived theoretically. But from a practical perspective, I cannot think of a scenario where one would need to make their inference straggler-resilient because it is typically already very low latency. (Furthermore, if an even lower latency is needed, then quantization is usually the direction to explore.) Please let me know if I’m missing something here. Perhaps, straggler resilient computing makes more sense for large-scale computing (e.g. large-model training) where you have a large-scale computation that is distributed onto a compute cluster. Minor: Some of the related work on coded computing has the property that if a given number of nodes return their solution, the exact output can be recovered and if not, an approximate solution can be generated. As far as I understand, the proposed method cannot recover the exact result even if all nodes return their result successfully. Please correct me if I’m wrong about this point. I wonder if this method could be modified to have the exact recovery property.

Rating

4

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

Yes.

Summary

The authors consider the problem of improving the reliability of distributed computing architectures by encoding the input data before it is processed by worker machines such that a good approximation of the desired output can be reconstructed using only a subset of the workers’ outputs. They utilize learning theory to determine a regularized objective function for the decoder as well as a loss function for the overall system, and provide solutions for the encoder and decoder which optimize their derived upper bounds on the loss function. The objective function is based on kernel ridge regression, which leads to a second-order smoothing spline solution for the decoder. Both the noiseless and the noisy cases are considered, and the proposed method is compared with the existing approach of Berrut coded computing in terms of its convergence rate in the noiseless setting and its empirical performance. To evaluate the empirical performance, distributed inference is performed for deep learning models of varying sizes and tasks with varying sizes for the output vector. The experimental results show that LETCC consistently achieves a lower estimation error on the model outputs.

Strengths

# Originality The main contribution which differentiates the LeTCC method from prior works like BACC appears to be the introduction of regularization which causes the optimal solution to be based on smoothing splines rather than interpolation. Existing papers which have considered optimizing cost functions only focus on learning how to generate parity data points. Overall, this paper brings a novel method to the table and adequately cites related works. # Quality Although I lack experience with some of the mathematical tools used, to my knowledge there is nothing incorrect about the technical results. The experimental methodology seems to allow for a fair comparison between LeTCC and BACC for the use case of image classification with a deep learning model. In terms of reconstruction accuracy, the experimental results validate that LeTCC is superior to BACC, in some cases by a significant margin. # Clarity The main content of the paper is laid out clearly with some small typos but no major issues. # Significance The method for coded computing introduced in this paper represents an advancement in the level of accuracy that can be achieved when the function applied by the worker nodes is a complex deep learning model. The authors show that this advancement can be achieved by adapting the encoder and decoder to the function through the tuning of the regularization weight, which is an interesting idea.

Weaknesses

# Originality This paper distinguishes itself sufficiently from existing works, so I see no issues in terms of originality. # Quality LeTCC is proven to have a reconstruction error that scales better than BACC in terms of the number of worker nodes, but its scaling in terms of the number of stragglers is not directly compared. Based on Theorem 9 in the BACC paper, it appears that the max error along a single dimensions scales as $S^2$. The mean-squared error (MSE) for LeTCC scales as $S^4$, but since the max norm is upper bounded by the Euclidean norm it is unclear how to compare these results. It would be nice to compare the theoretical dependence on the number of stragglers, especially since the experimental results are mixed (in two cases the difference in MSE shrinks as $S$ increases, and in the other case the MSE grows as $S$ increases). # Clarity The authors should explicitly state how many trials were averaged over to produce the plots in figure 3 to help readers interpret and/or reproduce the results. I identified the following typos in the paper: - Line 502: There is a “loc” subscript missing - Line 49: The sentence starting on this line is grammatically incorrect, I presume that the second comma is supposed to be replaced with the word “is” - Figure 3: The title of the top-left plot seems to have the values of N and K reversed # Significance Without more details on the hyperparameter optimization process and the relative computational complexity of fitting the encoder and decoder functions as compared to those of BACC, it is hard to say whether LeTCC is more practically advantageous to use than BACC. It could be that the overhead introduced by hyperparameter tuning outweighs the benefit from reduced reconstruction error in some cases. It would have been helpful to see how tolerant LeTCC is to changes in the smoothing parameters, i.e. how much variation can be allowed while still outperforming BACC. One can also see from Figure 3 that a large difference in the mean-squared error does not consistently translate to a large difference in relative accuracy (at least when deep models are used), which makes it less likely that LeTCC’s performance benefits would be worth the additional overhead. As it currently stands, these issues reduce the practical value of the contribution made by this paper.

Questions

According to Theorem 4, the mean-square error of LeTCC has a much worse scaling in terms of the number of stragglers in the noiseless setting than in the noisy setting. Does this originate from a sacrifice made to improve the scaling with respect to the number of worker nodes, or is there some other cause?

Rating

7

Confidence

2

Soundness

3

Presentation

4

Contribution

2

Limitations

The authors are upfront about the limited scope of their work. However, as mentioned in the weaknesses section, the extra overhead introduced by the need for hyperparameter tuning is something that I would have liked to have seen addressed in the paper. As mentioned in the weaknesses section, the comparison of error convergence rates with BACC is also limited.

Summary

This work proposes a learning theory-based novel framework for coded computing with a focus on distributed machine learning applications. The proposed method sends mixtures of input samples to the worker nodes that compute the desired results on the mixtures. An encoder and a decoder functions are fitted at the master node using input samples and the result from workers, respectively. Finally, the decoder function can be used to estimate the output of computing function for the input samples. It is shown that the loss function (divergence of the estimated output with the true output of computing functions) is upper bounded by the generalization error of the decoder regression and training error of the encoder regression under some conditions. Experimental evaluations are provided to show the efficacy of the proposed method over the state-of-the-art baseline.

Strengths

1. The proposed method leverages learning theory for coded computing which seems novel and interesting. 2. Rigorous theoretical analysis is provided including convergence rate derivation and recoverability analysis.

Weaknesses

1. The experimental section does not look comprehensive enough for the following reasons: (a) Only one baseline is considered. (b) Authors acknowledge in Section 3 that the computational efficiency of encoder and decoders is a crucial factor. Yet, this was not reported in the numerical section. 2. The computing functions (which are generally pre-trained neural networks) are evaluated on (probably) mixtures of input samples at the worker nodes. Those neural networks were trained on the data distribution. However, the mixture of input samples might not fall on the support of data distribution. Although for images, this does not seem to be an issue, there could be unexpected behavior in general.

Questions

1. Could the authors provide comparision with additional baselines? 2. Could the authors report the computational resources needed for fitting and evaluating the encoder and decoder? 3. Could the authors provide a discussion for the weaknesses number 2 explained above? Also, does this framework work (or can it be modified to work) for computing functions that take discrete inputs?

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

2

Limitations

Yes, but it is spread out throughout the manuscript. A separate limitation section/paragraph would be helpful for the readers.

Summary

The paper deals with coded distributed computing. I need to note that it is very popular research area now with a vast number of papers. But the authors are right when mention that the majority of papers utilizes standard algebraic codes (such as Reed-Solomon codes). The main problem of such approach is that these codes are designed over finite fields, which is not the case for machine learning tasks. The improvements utilize real or complex valued codes (e.g. Reed-Solomon codes over real or complex fields) but they face with the problems of accuracy (Vandermonde matrices have bad condition numbers). Moreover such approaches work only for some particular functions, e.g. polynomial ones. In this paper the authors propose a framework, which outperforms the Berrut approximate coded computing (BACC), which is the state-of-the-art coded computing scheme for general computing.

Strengths

The main strong point are as follows: - new framework foundation for coded computing, new loss function and its upper bound by decomposition - theoretical analysis and guarantees. Under some assumptions the authors find the optimum encoding and decoding functions and characterize the convergence rate for the expected loss in both noise-free and noisy computations. - Numerical analysis, that shows the new framework to outperforms the Berrut approximate coded computing (BACC), which is the state-of-the-art coded computing scheme for general computing.

Weaknesses

I list the main weaknesses below: - «We develop a new foundation for coded computing, based on the theory of learning, rather than the theory of coding». I would not be so categorical. Coding is a method when you add and the utilize the redundancy to deal with errors and erasures. The main advantage of your approach is that you are not using standard finite field codes. - How the optimal (under some assumptions) encoder and decoder functions in section 4 are related to the functions utilized for numerical experiments (DNNs)? Is it possible to analyse the performance under optimal encoder and decoder and compare it to the results from Section 5? - You made the comparison to BACC, which is a framework for general computing. Could you please make a comparison for some particular (e.g. polynomial) problems? I just wonder if proposed general approach is competitive with e.g. Lagrange computing and what you should pay for universality. So my claim is that more scenarios and computing problems should be checked to understand the limitations and applicability of your method. - How flexible is your approach if the system parameters change (the number of worker nodes or the number of stragglers). - Figure 3 seems to suffer from the lack of statistics (you need more experiments). - You mentioned Byzantine case. It is known to be a problem for the codes over the real field (in case of finite field the approaches are well-developed). It would be beneficial to briefly explain how you plan to deal with this problem.

Questions

See weaknesses

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Limitations are well described.

References in the General Response to Reviewers

[1] Jahani-Nezhad, T., et al. "Berrut approximated coded computing: Straggler resistance beyond polynomial computing." IEEE PAMI 2022. [2] Yu, Q., et al. "Lagrange coded computing: Optimal design for resiliency, security, and privacy." PMLR 2019. [3] Yu, Q., et al. "Polynomial codes: an optimal design for high-dimensional coded matrix multiplication." NeurIPS 2017. [4] Gautschi, W., et al. "Lower bounds for the condition number of Vandermonde matrices."" Numerische Mathematik 1987. [5] Eilers, P.H., et al. "Flexible smoothing with B-splines and penalties." Statistical science 1996. [6] De Boor, Carl. "Calculation of the smoothing spline with weighted roughness measure." Mathematical Models and Methods in Applied Sciences 11.01 (2001): 33-41. [7] Hu, C.L., et al. "Complete spline smoothing." Numerische Mathematik 1986.