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

Authors: parsa  moradi
mohammad ali maddah-ali
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 06:33:53

Abstract: Coded computing has emerged as a promising framework for tackling significant challenges in large-scale distributed computing, including the presence of slow, faulty, or compromised servers. In this approach, each worker node processes a combination of the data, rather than the raw data itself. The final result then is decoded from the collective outputs of the worker nodes.  However, there is a significant gap between current coded computing approaches and the broader landscape of general distributed computing, particularly when it comes to machine learning workloads. To bridge this gap, we propose a novel foundation for coded computing, integrating the principles of learning theory, and developing a framework that seamlessly adapts with machine learning applications. 
In this framework, the objective is to find the encoder and decoder functions that minimize the loss function, defined as the mean squared error between the estimated and true values. Facilitating the search for the optimum decoding and functions, we show that the loss function can be upper-bounded by the summation of two terms: the generalization error of the decoding function and the training error of the encoding function. 
Focusing on 
the second-order Sobolev space, we then derive the optimal encoder and decoder. We show that in the proposed solution, the mean squared error of the estimation decays with the rate of $\mathcal{O}(S^3 N^{-3})$ and $\mathcal{O}(S^{\frac{8}{5}}N^{\frac{-3}{5}})$ in noiseless and noisy computation settings, respectively, where $N$ is the number of worker nodes with at most $S$ slow servers (stragglers). Finally, we evaluate the proposed scheme on inference tasks for various machine learning models and demonstrate that the proposed framework outperforms the state-of-the-art in terms of accuracy and rate of convergence.

Main paper: 
 introduction: 
 The theory of coded computing has been developed to improve the reliability and security of largescale machine learning platforms, effectively tackling two major challenges: (1) the detrimental impact of slow workers (stragglers) on overall computation efficiency, and (2) the threat of faulty or malicious workers that can compromise data accuracy and integrity. These challenges have been well-documented in the literature, including the seminal work [1] from Google. For instance, [2] reported that in a sample set of 3000 matrix multiplication jobs on AWS Lambda, while the median job time was 40 seconds, approximately 5% of worker nodes took 100 seconds to respond, and two nodes took as long as 375 seconds. Furthermore, coded computing has also been instrumental in addressing privacy concerns, a crucial aspect of distributed computing systems [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] .The concept of coded computing has been motivated by the success of coding in communication over unreliable channels, where instead of transmitting raw data, the transmitter sends a (linear) combination of the data, known as coded data. This redundancy in the coded data enables the receiver to recover the raw data even in the presence of errors or missing values. Similarly, coded computing includes three layers [3, 11, 13] (see Figure 1(a) ):(1) The Encoding Layer in which a master node sends a (linear) combination of data, as coded data, to each worker node.(2) The Computing Layer, in which the worker nodes apply a predefined computation to their assigned coded data and send the results back to the master node.(3) The Decoding Layer, in which the master node recovers the final results from the computation results over coded data. In this layer, the decoder leverages the coded redundancy in the computation to recover the missing results of the stragglers and detect and correct the adversarial outputs.The existing coded computing has largely built upon algebraic coding theory, drawing inspiration from the renowned Reed-Solomon code construction in communication [14] , with proven straggler and Byzantine resiliency [15] . However, the coding in communication is designed for the exact recovery of the messages, built on a foundation that is inconsistent with the computational requirements of machine learning. Developing a code that preserves its specific construction while composing with computation is extremely challenging, leading to significant restrictions. Firstly, current methods are mainly restricted to specific computation functions, such as polynomials and matrix multiplication [3, 11, 13, 16, 17] . Secondly, rooted in algebraic error correction codes, existing approaches are tailored for finite field computations, leading to numerical instability when dealing with real-valued data [18, 19] . Furthermore, these methods are unsuitable for approximate, fixedpoint, or floating-point computing, where exact computation is neither possible nor necessary, such as in machine learning inference or training tasks. Finally, these schemes typically have a recovery threshold, which is the minimum number of samples required to recover results from coded outputs of worker nodes [3, 13] . If the number of workers falls below this threshold, the recovery process fails entirely.Several works have attempted to mitigate the aforementioned issues and transform the coded computing scheme into a more robust and adaptable one, applicable to a wide range of computation functions. These efforts include approximating non-polynomial functions with polynomial ones [5, 20] , refining the coding mechanism to enhance stability [21] [22] [23] [24] [25] , and leveraging approximation computing techniques to reduce the recovery threshold and increase recovery flexibility [26] [27] [28] [29] .However, these attempts fail to bridge the existing gap between coded computing and general distributed computing systems. The root cause of these issues lies in the fact that they are grounded in coding theory, based on a foundation that is not compatible with the requirements of large-scale machine learning. Therefore, this paper aims to address the following objective:Objective: The main objective of this paper is to develop a new foundation for coded computing, not solely based on coding theory, but also grounded in learning theory, that seamlessly integrates with machine learning applications, offering a more natural and effective solution for general computing.In this paper, we establish a learning-theoretic foundation for coded computing, applicable to general computations. We adopt an end-to-end system perspective, that integrates an end-to-end loss function, to find the optimum encoding and decoding functions, focusing on straggler resiliency. We show that the loss function is upper-bounded by the sum of two terms: one characterizing the generalization error of the decoder function and the other capturing the training error of the encoder function. Regularizing the decoder layer, we derive the optimal decoder in the Reproducing Kernel Hilbert space (RKHS) of second-order Sobolev functions. This provides an explicit solution for the optimum decoder function and allows us to characterize the resulting loss of the decoding layer. The decoder loss appears as a regularizing term in optimizing the encoding function and represents the norm in another RKHS. Thus, the optimum solution for the encoding function can be derived, too. We address two noise-free and noisy computation settings, for which we derive the optimal encoder and decoder and corresponding convergence rate. We prove that the proposed framework exhibits a faster convergence rate compared to the state-of-the-art and the numerical evaluations support the theoretical derivations (see Figure 1 (b)). LeTCC framework not only achieves a lower estimation error but also has a faster convergence rate.Contributions: The main contributions of this paper are:• We develop a new foundation for coded computing by integrating it with learning theory, rather than relying solely on coding theory. We define the loss function as the mean square error of the computation estimation, averaged over all possible sets of at most S stragglers (Section 3.1). To be able to find the best encoding and decoding functions, we bound the loss function with the summation of two terms, one characterizing the generalization error of the decoder function and the other capturing the training error of the encoder function (Section 3).• Assuming that the encoder and decoder functions reside in the Hilbert space of secondorder Sobolev functions, we use the theory of RKHSs to find the optimum encoding and decoding functions and characterize the convergence rate for the expected loss in both noise-free and noisy computation regimes (Section 4).• We have extensively evaluated the proposed scheme across different data points and computing functions including state-of-the-art deep neural networks and demonstrated that our proposed framework considerably outperforms the state-of-the-art in terms of recovery accuracy (Section 5). 
notations: 
 Throughout this paper, uppercase and lowercase bold letters denote matrices and vectors, respectively. Coded vectors and matrices are indicated by a ∼ sign, as in x, Ã. The set {1, 2, . . . , n} is denoted as [n] and symbol |S| denotes the cardinality of the set S. Finally, we represent first, second and k-th order derivative of function f as f ′ , f ′′ , and f (k) , respectively.Consider a master node and a set of N workers. The master node is tasked with computing {f (x k )} K k=1 using a cluster of N worker nodes, given a set of K data points{x k } K k=1 , x k ∈ R d .Here, f : R d → R m represents an arbitrary function, which could be a simple one-dimensional function or a complex deep neural network, and K, d, m are integers. A naive approach would be to assign the computation of f (x k ) to one worker node for k ∈ [K]. However, some worker nodes may act as stragglers, failing to complete their tasks within the required deadline. To mitigate this issue, the master node employs coding and sends N coded data points to each worker node using an encoder function. Each coded data point is a combination of raw data points. Subsequently, eachx 1 x 2 x K Encoder Decoder f(•) x1 Worker Nodes f(•) f(•) f(•) f(•) f(•) x2 xN f (x 1 ) f (x 2 ) f (x N ) f(x 1 ) f(x 2 ) f(x K ) u enc (β n ) = xn u dec (α k ) = f (x k ) xn f (x n ) Figure 2: LeTCC framework.worker applies the function f (•) to the received coded data and sends the result, coded results, back to the master node. The master node's goal is to approximately recover f (x k ) ≈ f (x k ) using a decoder function, even if some worker nodes appear to be stragglers. The redundancy in the coded data and corresponding coded results enables the master node to recover the desirable results, {f (x k )} K k=1 . 
proposed framework: letcc: 
 Here, we propose a novel straggler-resistant Learning-Theoretic Coded Computing (LeTCC) framework for general distributed computing. As depicted in Figure 2 , our framework comprises two encoding and decoding layers, with a computing layer sandwiched between them. The framework operates according to the following steps:(1) Encoding Layer: The master node fits an encoder regression function u enc : R → R d at points {(α k , x k )} K k=1 for fixed, distinct, and ordered valuesα 1 < α 2 < • • • < α K ∈ R.Then, it computes the encoder function u enc (•) on another set of fixed, distinct, and ordered values {β n } N n=1 whereβ 1 < β 2 < • • • < β N ∈ R, with k ∈ [K] and n ∈ [N ]. Subsequently, the master node sends the coded data points xn = u enc (β n ) ∈ R d to worker n for n ∈ [N ]. Note that each coded data point xn is a combination of all initial points {x k } K k=1 . (2) Computing Layer: Each worker node n ∈ [N ] computes f (x n ) = f (u enc (β n )) on itsassigned input and sends the result back to the master node.(3) Decoding Layer: The master node receives the results f (x v ) v∈F from the non-straggler worker nodes in the set F. Next, it fits a decoder regression functionu dec : R → R m at points (β v , f (x v )) v∈F = (β v , f (u enc (β v ))) v∈F . Finally, using the function u dec (•), the master node computes f (x k ) := u dec (α k ) as an approximation of f (x k ) for k ∈ [K]. Recall that u dec (α k ) ≈ f (u enc (α k )) ≈ f (x k ).As mentioned above, the master node selects and fixes the regression points, {α k } K k=1 and {β n } N n=1 , which remain constant throughout the entire process. The encoder and decoder functions are the only components subject to optimization.Note that the computational efficiency of the encoding and decoding layers is crucial. This includes the fitting process of the encoder and decoder regression functions, as well as the computation of these regression functions at points {β v } v∈F and {α k } K k=1 . If the master node's computation time is not substantially decreased compared to computing {f (x k )} K k=1 by itself, then adopting this framework would not provide any benefits for the master node.We view the whole scheme as a unified predictive framework that provides an approximate estimation of the values {f (x k )} This enables us to define the following loss function, which evaluates the framework's performance:EQUATION)where f (x) := fα,β [u enc , u dec , F](x) to simplify the notation, ∥•∥ 2 represents the ℓ 2 -norm, and ϵ = [ϵ 1 , . . . , ϵ N ] T . Our objective is to find u enc (.) and u dec (.) that minimize the objective function (1), which is very challenging, given that f (.) is a composition of u enc (.) and u dec (.) and the computation in the middle. Here, we take an important step to decompose these two, to gain a deeper understanding of interactions. Adding and subtracting f (u enc (α k )) and utilizing inequality of arithmetic and geometric means (AM-GM), one can obtain an upper bound for (1):EQUATIONThe right-hand side of (2) comprises two terms, which uncover an interesting interplay between the encoder and decoder regression functions. Let us elaborate on what each term corresponds to.• L dec ( f ) -The expected generalization error of the decoder regression: Recall that the master node fits a decoder regression function, u dec (•), at a set of points denoted as{(β v , f (u enc (β v )))} v∈F .L dec represents the ℓ 2 -norm of the decoder regression function's error on a distinct set of points {α k } K k=1 , which are different from its training data {β v } v∈F . Consequently, this term provides an unbiased estimate of the decoder's generalization error. Given that the decoder regression function develops to estimate f (u enc (•)), the generalization error of the decoder regression is inherently tied to the properties of f (u enc (•)). This, in turn, is influenced by characteristics of both the f (•) and u enc (•) functions, making the L dec ( f ) a complex interplay of these two functions.• L enc ( f ) -A proxy to the training error of the encoder regression: Remember that the encoder regression is fitted at points {(α k , x k )} K k=1 . Consequently, the training error is calculated as1 K K k=1 ∥u enc (α k ) -x k ∥ 2 2. Therefore, L enc represents the encoder training error magnified by the effect of computing function f (•). Specifically, if f (•) is q-Lipschitz, then L enc ( f ) can be upper bounded by:2 K K k=1 ∥f (u enc (α k )) -f (x k )∥ 2 2 ⩽ 2q 2 K K k=1 ∥u enc (α k ) -x k ∥ 2 2 .(3)Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?• 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. • It 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 a 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 of range (e.g. negative error 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 in the text. 
main results: 
 In this section, we examine the proposed framework from a theoretical standpoint. We provide a comprehensive explanation of the design process for the decoder and encoder functions and subsequently analyze the convergence rate. For simplicity, we present the results for a one-dimensional function f : R → R. These results are generalizable to the case where f : R → R m , as discussed in Appendix F.Suppose the regression points, {α k } K k=1 , {β n } N n=1 , are confined to the interval Ω := (-1, 1) and u enc , u dec ∈ H 2 (Ω; R), where H 2 (Ω; R) is the reproducing kernel Hilbert space (RKHS) of secondorder Sobolev functions on the interval Ω induced with the norm ∥f ∥ 2 2 which is an equivalent norm on Sobolev space introduced by [30] (see (28) in Appendix A.1). The definition and properties of Sobolev spaces, along with their reproducing kernels and norms, are reviewed in Appendix A.1.H 2 (Ω;R) := Ω (f ′′ (t)) 2 dt + f (-1) 2 + f ′ (-1)Decoder Design: Since L dec ( f ) in the decomposition (2) characterizes the generalization error of the decoder function, we propose a regularized objective function for the decoder:EQUATION)The first term in (4) corresponds to the mean squared error, while the second term characterizes the smoothness of the decoder function on the interval Ω. Equation ( 4) represents a Kernel Ridge Regression problem (KRR). It can be shown that the solution of (4) has the following form [31, 32] :EQUATIONwhere Definition 2 and (44) in Appendix A.1), and c = [c 1 , . . . , c |F | ] T ∈ R |F| . Substituting (5) into the main objective (4), the coefficient vector c can be efficiently computed by optimizing a quadratic equation [33] . This solution is known as the second-order smoothing spline function. The theoretical properties of smoothing splines are reviewed in Appendix A.2.d 0 , d 1 ∈ R, ϕ 0 (•, •) is the kernel function of H 2 0 (Ω; R) (seeLet us define the following variables, which represent the maximum and minimum distances between consecutive data points in the decoder layer, β n N n=1 :EQUATION)with β 0 := -1 and β N +1 := 1. The following theorems provide crucial insights for designing the encoder function as well as deriving the convergence rates. Theorem 1 (Upper bound for noiseless computation, σ 0 = 0). Consider the LeTCC framework with N worker nodes and at most S stragglers. Assume {α k } K k=1 are arbitrary and distinct points in Ω = (-1, 1) and there exist a constant J that ∆ max ⩽ J N . If f (•) is a q-Lipschitz continuous function, then:EQUATION)where C 1 is a constant.The proof of Theorem 1 and the detailed expression for C 1 can be found in Appendix B.1. Theorem 2 (Upper bound for noisy computation). Consider the LeTCC framework with N worker nodes and at most S stragglers and1 (N -S) 4 ⩽ λ d ⩽ λ 0 for λ 0 ∈ R. Assume each worker node computes f n (x) = f (x) + ϵ n with E[ϵ n ] = 0 and E[ϵ 2 n ] ⩽ σ 2 0 . Assume {α k } K k=1are arbitrary and distinct points in Ω = (-1, 1) and suppose there is constantEQUATIONwhereC 2 is a constant, C(λ 0 ) = O(λ 1 20 ) is an increasing function of λ 0 , and p 4 (S) is a degree-4 polynomial in S with positive constant coefficients.The proof and expressions for C 2 and C(λ 0 ) are provided in Appendix B.2.Encoder Design: The upper bounds established in Theorems 1, 2 hold for all u enc ∈ H 2 (Ω; R). However, they do not directly lead to a design for u enc (•). To address this, we present the following theorem which bounds the ∥f • u enc ∥ 2 L 2 (Ω;R) , enabling us to construct u enc (•) without compromising the convergence rate. Theorem 3. Consider a LeTCC scheme. Assume computing function f (•) is q-Lipschitz continuous and ∥f ′′ ∥ L ∞ (Ω;R) ⩽ ν. Then:EQUATION)for some monotonically increasing function ψ : R + → R + , where λ e is depending on (N, S, σ 0 , q, ν).The proof can be found in Appendix B.3. By applying the representer theorem [34] , we can deduce that the optimal encoder u enc (•), which minimizes the right-hand side of (10) takes the formu enc (•) = K k=1 z k ϕ(α k , •), where z ∈ R K , and ϕ is the kernel function of H 2 (Ω; R), as discussed in Appendix A.2 and in (46) . However, due to the non-linearity of g(•), calculating the values of the coefficients z is challenging. Nevertheless, we demonstrate that the coefficients can be efficiently derived under certain mild assumptions. Proposition 1. In the noiseless case, there exists M ∈ R that depends only on {α k } K k=1 and {x k } K k=1 , such that:EQUATIONwhere R(u) is defined as follows:EQUATION)and m 1 , m 2 are constants.(ii) If u * (•) is the minimizer of (12), then ∥u * ∥ 2 H 2 (Ω;R) ⩽ M .See Appendix B.4 for the proof. Proposition 1 states that, under mild assumptions there exists a smoothing spline that minimizes the upper bound given in (12) without changing in convergence rate.Convergence Rate: Using Theorems 1, 2, and 3, we can derive the convergence rate of the proposed scheme as stated in the following theorem. Theorem 4 (Convergence rate). For LeTCC scheme with N worker nodes and a maximum of S stragglers, R( f ) ⩽ O S Refer to Appendix B.5 for the proof. Notably, the convergence rate yields from Theorem 4 surpasses the state-of-the-art Berrut coded computing approach upper bound [29] (Figure 1 ), both with respect to S and N (see Appendix C.1 for detailed comparison). 
experimental results: 
 In this section, we extensively evaluate the proposed scheme across various scenarios. Our assessments involve examining multiple deep neural networks as computing functions and exploring the impact of different numbers of stragglers on the scheme's efficiency. The experiments are run using PyTorch [35] in a single GPU machine. We evaluate the performance of the LeTCC scheme in three different model architectures:• Shallow model: We choose LeNet5 [36] architecture as a known shallow network with approximately 6 × 10 4 parameters, trained on the MNIST [37] .• Deep model with low-dimensional output: In this scenario, we evaluate the proposed scheme when the function is a deep neural network trained on color images in CIFAR-10 [38] dataset. We use the recently introduced RepVGG [39] network with around 26 million parameters which was trained on CIFAR-101 .• Deep model with high-dimensional output: Finally, we demonstrate the performance of the LeTCC scheme in a scenario where the input and output of the computing function are high-dimensional, and the function is a relatively large neural network. We consider the Vision Transformer (ViT) [40] as one of the state-of-the-art base neural networks in computer vision for our prediction model, with more than 80 million parameters (in the base version). The network was trained and fine-tuned on the ImageNet-1K dataset [41] 2 .We use the output of the last softmax layer of each model as the output.Hyper-parameters: The entire encoding and decoding process is the same for different functions, as we adhere to a non-parametric approach. The sole hyper-parameters involved are the two smoothing parameters (λ enc , λ dec ) which are determined using cross-validation and greed search over different values of the smoothing parameters.Baseline: We compare LeTCC with the Berrut approximate coded computing (BACC) introduced by [29] as the state-of-the-art coded computing scheme for general computing. The BACC framework is used in [29] for training neural networks and in [42] for inference. Although Berrut coded computing [29] is the only existing coded computing scheme for general functions, we include a comparison of the proposed framework with the Lagrange coded computing scheme [3] for polynomial computation in Appendix D.Interpolation Points: We choose Chebyshev points of the first and second kind,{α i } K k=1 = cos (2k-1)π 2K and {β n } N n=1 = cos (n-1)π N -1, for fair comparison with [29] .Evaluation Metrics: We employ two evaluation metrics to assess the performance of the proposed framework: Relative Accuracy (RelAcc) and Root Mean Squared Error (RMSE). RelAcc is defined as the ratio of the base model's prediction accuracy to the accuracy of the estimated model on the initial data points. RMSE, on the other hand, is our main loss defined in (1) which measures the empirical average of the root mean square difference over multiple batches of and non-straggler set F, providing an unbiased estimation of expected mean square error,E x∼X ,F 1 K K k=1 ∥f (x k ) -f (x k )∥ 2 ,for data distribution X . Performance Evaluation: Table 1 presents both RMSE and RelAcc metrics side by side. The results demonstrate that LeTCC outperforms BACC across various architectures and configurations, with an average improvement of 15%, 17%, and 9% in RMSE for LeNet, RepVGG, and ViT architectures, respectively, and a 2%, 5%, and 4% enhancement in RelAcc. In a subsequent analysis, we evaluate the performance of LeTCC in comparison to BACC across a variety of straggler scenarios. For each number of stragglers, S, we randomly select S workers to act as stragglers. Both schemes are then run with the same input data points and straggler configurations, and the process is repeated 20 times. We record the average values of the RelAcc and RMSE metrics, along with their 95% confidence intervals. Figures 3 and 4 illustrate the performance of both schemes across three model architectures. As shown in both figures, the proposed scheme consistently outperforms BACC for nearly all straggler values. In Figure 3 , where N K is relatively small-indicating a system design without excessive redundancy, which is more practical-the proposed scheme demonstrates even greater improvements in both metrics.Computational Complexity: The calculation and inference of smoothing spline coefficients can be performed linearly in the number of regression points by leveraging B-spline basis functions [43] [44] [45] . Consequently, the encoding and decoding processes in LeTCC, which involve evaluating new points and calculating the fitted coefficients, have computational complexities of O(K • d) and O((N -S) • m), respectively, where d is the input dimension and m is the output dimension of the computing function f (•). This complexity is comparable to that of BACC, which has complexities of O(K) and O(N -S) for its encoding and decoding layers [29] . Table 2 in Appendix C.2 presents a comparison of the total end-to-end processing time statistics for the LeTCC and BACC schemes.Sensitivity Analysis: We additionally investigate the sensitivity of the proposed schemes performance to the value of the smoothing parameter, as well as the sensitivity of the optimal smoothing parameter to the number of stragglers (or workers). The results are presented in Appendix E. As shown in Table 3 and Figure 6 , the optimal smoothing parameters and the scheme's performance exhibit low sensitivity to the number of stragglers (or worker nodes) and to the smoothing parameters, respectively.Coded Points: We also compare the coded points {x n } N n=1 sent to the workers in LeTCC and BACC schemes. The results, shown in Figure 7 , demonstrate that BACC coded samples exhibit highfrequency noise which causes the scheme to approximate the original prediction worse than LeTCC. 
related work: 
 Coded computing was initially introduced to tackle the challenges of distributed computation, particularly the existence of stragglers or slow workers, and also faulty or adversarial nodes. Traditional approaches to deal with stragglers primarily rely on repetition [1, [46] [47] [48] [49] [50] , where each task is assigned to multiple workers either proactively or reactively. Recently, coded computing approaches have re- duced the overhead of repetition by leveraging coding theory and embedding redundancy in the worker's input data [3, 13, 26, 29, [51] [52] [53] [54] [55] . This technique, which mainly relies on theory of coding, has been developed for specific types of structured computations, such as polynomial computation and matrix multiplication [3, 7, 12, 13, 17, 52, [56] [57] [58] . Recently, there have been attempts to generalize coded computing for general computations [4, 5, 29, 59] . Towards extending the application of coding computing to machine learning computation, Kosaian et al. [59] suggest training a neural network to predict coded outputs from coded data points. However, the scheme of Kosaian et al.[59] requires a complex training process and tolerates only one straggler. In another work, Jahani-Nezhad and Maddah-Ali [29] proposes BACC, a model-agnostic and numerically stable framework for general computations. They successfully employed BACC to train neural networks on a cluster of workers, while tolerating a larger number of stragglers. Building on the BACC framework, Soleymani et al. [42] introduced ApproxIFER scheme, as a straggler resistance and Byzantine-robust prediction serving system. However, the scheme of BACC uses a reasonable rational interpolation (Berrut interpolation [60] ), off the shelf, for encoding and decoding, without considering any end-to-end cost function to optimize. In contrast, we theoretically formalize a new foundation of coded computing grounded in learning theory, which can be naturally used for machine learning applications. 
conclusions and future work: 
 In this paper, we developed a new foundation for coded computing based on learning theory, contrasting with existing works that rely on coding theory and use metrics like minimum distance and recovery threshold for design. This shift in foundations removes barriers to using coded computing for machine learning applications, allows us to design optimal encoding and decoding functions, and achieves convergence rates that outperform the state of the art. Moreover, the experimental evaluations validate the theoretical guarantees. While this work focuses on straggler mitigation, future work will extend our proposed scheme to achieve Byzantine robustness and privacy, offering promising avenues for further research. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [Yes] Justification: We provided all the details regarding our experiments in Section 5.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or 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 in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? Answer: [Yes] Justification: We followed the NeurIPS code of ethics in our paper. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: Our paper is focused on developing a new framework for coded distributed computing and should be categorized as foundational research. We believe this work has no direct societal impact that should be explained in the paper. Guidelines:• The answer NA means that there is no societal impact of the work performed.• 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 a 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This is not applicable to our work and this paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: This paper does not use 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a 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. 
 
 Appendix: Let Ω be an open interval in R and M be a positive integer. We denote by L p Ω; R M the class of all measurable functions g : R → R M that satisfy:EQUATIONwhere g(•) = [g 1 (•), . . . , g M (•)] T . The space L p Ω; R M can be endowed with the following norm, known as the L p norm:EQUATION)for 1 ⩽ p < ∞, andEQUATION)for p = ∞. Additionally, a function g :Ω → R M is in L p loc Ω; R M if it lies in L p (V ; R M ) for all compact subsets V ⊆ Ω.Definition 1 (Sobolev Space). The Sobolev space W m,p Ω; R M is the space of all functions g ∈ L p Ω; R M such that all weak derivatives of order i, denoted by g (i) , belong toL p Ω; R M for i ∈ [m]. This space is endowed with the norm:EQUATION)EQUATION)for p = ∞.Similarly, W m,p loc Ω; R M is defined as the space of all functions g ∈ L p loc Ω; R M with all weak derivatives of order i belonging toL p loc Ω; R M for i ∈ [m]. ∥g∥ W m,p loc (Ω;R M ) and ∥g∥ W m,∞ loc (Ω;R M )are defined similar to ( 16) and ( 19) respectively, using L p loc (Ω; R) instead of L p (Ω; R). Definition 2. (Sobolev Space with compact support): Denoted by W m,p 0 Ω; R M collection of functions g defined on interval Ω = (a, b) such that g(a) = 0, g ′ (a) = 0, . . . , g (m-1) (a) = 0 and g (m) L 2 (Ω;R) < ∞. This space can be endowed with the following norm:EQUATION)EQUATION)for p = ∞.The next theorem provides an upper bound for L p norm of functions in the Sobolev space, which plays a crucial role in the proof of the main theorems of the paper.Theorem 5 (Theorem 7.34, [61] ). Let Ω ⊆ R be an open interval and let g ∈ W 1,1 loc Ω; R M . Assume 1 ⩽ p, q, r ⩽ ∞ and r ⩾ q. Then:EQUATION)for every 0 < ℓ < L 1 (Ω).Note that L 1 (Ω) in Theorem 5 is the length of the interval Ω.EQUATION)Proof. Substituting p, q = 2 and r = ∞ in Theorem 5 and optimizing over ℓ, one can derive the optimum value of ℓ, denoted by ℓ * asEQUATION)Since∥g∥ L 2 (Ω;R M ) ∥g ′ ∥ L 2 (Ω;R M ) < L 1 (Ω), the optimum value is in the valid interval mentioned in Theorem 5.Corollary 2 (Corollary 7.36, [61] ).EQUATION)where α := 0 if r = q and 1 -1/p + 1/r = 0 and otherwiseα := 1 -1/p + 1/r 1 -1/p + 1/q . Corollary 3. Theorem 5 and Corollary 2 hold true when f ∈ W 2,2 Ω; R M .Proof. We prove the above corollary by showing thatW 2,2 Ω; R M ⊆ W 1,1 Ω; R M ⊆ W 1,1loc Ω; R M . Using Cauchy-Schwarz inequality, one can show:EQUATIONwhere (a) follows from the bounded length of Ω and f ∈ W 2,2 (Ω; R). Similarly:EQUATION)Equations ( 24) and (25) EQUATIONEQUATION)where (a) is due to[c, d] ⊂ Ω and (b) is because of f ∈ W 1,1 Ω; R M . Therefore, f ∈ W 1,1 loc Ω; R M .Equivalent norms. There have been various norms defined on Sobolev spaces in the literature that are equivalent to (16) (see [62] , [63, Ch. 7] , and [32, Sec. 10.2]). Note that two norms∥•∥ W1 , ∥•∥ W2 are equivalent if there exist positive constants η 1 , η 2 such that η 1 • ∥g∥ W2 ⩽ ∥g∥ W1 ⩽ η 2 • ∥g∥ W2 .The equivalent norm in which we are interested is the one introduced in [30] . Let Ω = (a, b) ⊂ R.We define W m,p Ω; R M as the Sobolev space endowed with the following norm:EQUATION)The following lemma derives the equivalence constants (η 1 , η 2 ) for the normsEQUATION)Proof. By expanding g around the point a and utilizing the integral remainder form of Taylor's expansion, for every x ∈ (a, b) we have:EQUATIONTherefore:EQUATIONwhere (a) follows from the 2g(a)• x a g ′ (t) dt ⩽ g(a) 2 + x a g ′ (t) dt 2 , (b) is based on Cauchy-Schwarz inequality, and (c) is due to x ⩽ b. Following the same steps as (32), we have:EQUATION)Integrating both sides of (33) we have:EQUATIONwhere (a) is based on adding the positive term (b -a) • g(a) 2 to the right-hand side. Based on the (32) and (34) we have:EQUATIONwhere (a) follows by integrating both sides of ( 32) and (b) is due to (33) . Using ( 35) and ( 34) and the fact thatb a g ′′ (t) 2 dt ⩽ ∥g∥ 2 W 2,2(Ω;R) , we have:EQUATION)For the other side, using the same steps as in (32) , we have:EQUATIONwhere (a) is because of -2g(a) • EQUATIONwhere (a) follows by a change of variable from x to t and (b) follows by adding the positive term 2 dt to the right side. Thus, (38) directly results in2 max{1, (b -a)} 2 • b a g ′′ (t)EQUATION)Following same steps as (38) and (39) results inEQUATION)Considering the fact that a g ′′ (t) 2 dt ⩽ ∥g∥ 2 W 2,2(Ω;R) , we can complete the proof:EQUATION)Corollary 4. Based on Lemma 1, for Ω = (-1, 1) we haveEQUATION)Corollary 4 directly follows from Lemma 1 by substituting (a, b) = (-1, 1).Corollary 5. The result of Lemma 1 remains valid for multi-dimensional cases, where g : R → R M , for some M > 1.Corollary 5 directly follows from applying Lemma 1 to each component of the function g(•) and using the definition of vector-valued function norm: [63, Theorem 121 ], [32] ) For any open interval Ω ⊆ R and m, M ∈ N,∥g∥ 2 W 2,2 (Ω;R M ) = M j=1 g (j) 2 W 2,2 (Ω;R) , ∥g∥ 2 W 2,2 (Ω;R M ) = M j=1 g (j) 2 W 2,2 (Ω;R) . Proposition 2. ([61, Section 7.2],EQUATION)are Reproducing Kernel Hilbert Spaces (RKHSs).The full expression of the kernel function of H m (Ω; R) and H m (Ω; R) and other equivalent norms of Sobolev spaces can be found in [63, Section 4] . For H m (Ω; R) the kernel function is as follows:EQUATION)where (•) + is positive part function.Consider the data model 2 (Ω; R), the solution to the following optimization problem is referred to as the smoothing spline:y i = f (t i ) + ϵ i for i = 1, . . . , n, where t i ∈ Ω = (a, b) ⊂ R, E[ϵ i ] = 0, and E[ϵ 2 i ] ⩽ σ 2 0 . Assuming f ∈ W m,EQUATION)where 2 (Ω; R), we have:y = [y 1 , . . . , y n ]. Based on Proposition 2, H m (Ω; R) := W m,2 (Ω; R) with the norm ∥•∥ W m,2 (Ω;R) is a RKHS for some kernel function ϕ(•, •). Therefore for any v ∈ W m,EQUATION)It can be shown that ϕ(t, s) = R P (t, s) + R 0 (t, s) where R 0 (t, s) is kernel function of H m 0 (Ω; R) and R P (t, s) is a null space of H m 0 (Ω; R) which is the space of all polynomials with degree less than m.The solution of (45) has the following form [31, 32] :EQUATIONwhere ν j (•) = R 0 (•, t j ) for j ∈ [n],EQUATIONwhereEQUATIONEquation (48) states that the smoothing spline fitted on the data points y is a linear operator:EQUATIONfor z ∈ R n , whereA λ := Q Q T Q + λΓ -1 Q T .It can be shown that the u * (•) is a natural spline [32, 33] . Thus, if {b i (•)} n i=1 is a basis function for an m-th order natural spline (such as truncated power or B-spline basis functions), we have:EQUATIONEQUATIONwhereN ij = b i (t j ), Φ ij = Ω b ′′ i (t)b ′′ j (t) dt for i, j ∈ [n],and ξ := [ξ 1 , . . . , ξ n ] T . To characterize the estimation error of the smoothing spline, |f -S λ,n,m (y)|, we need to define two variables analogous to those in (6) , which quantify the minimum and maximum consecutive distance of the regression points {t i } n i=1 :EQUATION)where boundary points are defined as (t 0 , t n+1 ) := (a, b). The following theorem offers an upper bound for the j-th derivative of the smoothing spline estimator error function in the absence of noise (σ 0 = 0). Theorem 6. ([64, Theorem 4.10]) Consider data modelEQUATION)where p d (•) is a degree d polynomial with positive weights and D(m) is a function of m. Then for each j ∈ {0, 1, . . . , m} and any f ∈ W m,2 (Ω; R), there exist a function H(m, j) such that:EQUATION)Note that (f -S λ,n,m (y)) (0) := f -S λ,n,m (y). In the presence of noise, where σ 0 > 0, we can exploit the linearity of the smoothing spline operator and the mutual independence of the noise terms to conclude that:EQUATION)where f = [f (t 1 ), . . . , f (t n )] T . The first term in (56) can be upper bounded using Theorem 6. The following theorem establishes an upper bound for the second term when ∆max ∆min is bounded:Theorem 7. ([65, Section 5]) Consider data model y i = f (t i )+ϵ i , where E[ϵ i ] = 0 and E[ϵ 2 i ] ⩽ σ 2 0 for i ∈ [n].Assume there exist a constant B > 0 such that ∆max ∆min ⩽ B. Then for each j ∈ {0, 1, . . . , m}, there exist a constant λ 0 > 0 and function Q(m, j, λ 0 ) such that:EQUATIONfor λ ⩽ λ 0 and nλ1 2m ⩾ 1.Note that based on [65] , Q(m, j, λ 0 ) = w(m, j)λ1 2m 0 + w(m, j).Recall from (2) that R( f ) ⩽ L enc ( f ) + L dec ( f ), whereEQUATION)EQUATION)We begin by deriving a general intermediate bound for L dec and L enc which will be a key component in the proofs of Theorems 2 and 1. The subsequent subsections will then provide remaining details to complete the proofs of both theorems. Lemma 2. Let f : R → R be a q-Lipschitz continuous function. Then:EQUATION)Proof. Using Lipschitz property, we have:EQUATION)As previously mentioned, L dec represents the expected generalization error of the decoder function.To leverage the results from Theorems 6 and 7 we must establish that the composition of f with the encoder u enc belongs to the Sobolev space W 2,2 (Ω; R). Lemma 3. Let f : R → R be a q-Lipschitz continuous function with∥f ′′ ∥ L ∞ (Ω;R) ⩽ ν and Ω ⊂ R be an open interval. If u enc ∈ W 2,2 (Ω; R) then f • u enc ∈ W 2,2 (Ω; R).Proof. Let us define f 0 (t) := f (t) -f (0). Thus f 0 (0) = 0 and f 0 is q-Lipschitz. Using Lipschitz propertyEQUATION)Integrating both sides of (62) :EQUATIONwhere (a) follows by u enc ∈ W 2,2 (Ω; R). Given that f 0 is q-Lipschitz, its derivative is bounded in theEQUATIONwhere (a) follows by chain rule and (b) follows by u enc ∈ W 2,2 (Ω; R). For the second derivative we have:EQUATIONwhere (a) follows from the chain rule, (b) is derived using the Cauchy-Schwarz inequality, (c) is due to ∥f ′′ 0 ∥ L ∞ (Ω;R) ⩽ ν, (d) follows from Theorem 5 with r = 4, p = q = 2, l = 1, and (e) is a result of u enc ∈ W 2,2 (Ω; R). Equations ( 63), (64) , and ( 63) demonstrate that f 0 • u enc ∈ W 2,2 (Ω; R). Note that Ω is bounded, and every constant function belongs to W 2,2 (Ω; R). Thus, we can conclude thatf 0 • u enc (t) + f (0) = f • u enc (t) ∈ W 2,2 (Ω; R).Let us define the function h(t) := u dec (t) -f (u enc (t)). Based on Lemma 3, and given that u dec and f • u enc belong to the Sobolev space W 2,2 (Ω; R), it follows that h ∈ W 2,2 (Ω; R). The subsequent lemmas establish upper bounds for ∥h∥ L ∞ (Ω;R) and ∥h ′ ∥ L ∞ (Ω;R) , leveraging properties of functions in Sobolev spaces. Lemma 4. If Ω = (-a, a), then:EQUATION)where (a) and (b) are followed by the triangle and Cauchy-Schwarz inequalities respectively. Integrating the square of both sides over the interval [x 0 , a) yields:EQUATION)where (a) follows by x 0 < a. On the other side, we have the following for every x ∈ (-a, x 0 ]:|h(x)| = x0 x h ′ (x) dx ⩽ x0 x |h ′ (x)| dx ⩽ x0 x 1 2 dx 1 2 • x0 x |h ′ (x)| 2 dx 1 2. (69) Therefore, we have a similar inequality:EQUATION)Using ( 68) and (70) completes the proof:EQUATION)Thus, if x 0 exists, the proof complete. In the next step, we prove the existence of x 0 ∈ Ω such that h (x 0 ) = 0. Recall that h(t) = u dec (t) -f (u enc (t)) and u dec (•) is the solution of (4). Assume there is no such x 0 . Since h ∈ W EQUATION)where (a) follows from u dec (β * ) > 0 and ūdec (β v ) > f (u enc (β v )) for all v ∈ F. This leads to a contradiction since it implies that u dec is not the solution of the (4). Therefore, our initial assumption must be wrong. Thus, there exists x 0 ∈ Ω such that h(x 0 ) = 0.Lemma 5. Let Ω = (-1, 1). For h(t) = u dec (t) -f (u enc (t)) we have:EQUATION)andEQUATION)Proof. Using Lemma 4 one can concludeEQUATION)Since h ∈ W 2,2 (Ω; R) we can apply Corollary 3 and Theorem 5 with r = ∞ and p, q = 2 to complete the proof of (74). Furthermore, using Theorem 5 with r = ∞ and p, q = 2 and ℓ = 1 completes the proof of (75).Building upon Lemma 5 and starting from (58), we can derive an upper bound for L dec :EQUATION)where (a) follows from the definition of h(t), (b) is due to the fact that h(t) ⩽ ∥h∥ L ∞ (Ω;R) for t ∈ Ω, (c) follows by applying Lemma 5, and (d) is a result of applying the Cauchy-Schwarz inequality.Proof. As previously mentioned, u dec (•) is a second-order smoothing spline fitted on the data points(β i1 , f (u enc (β i1 )), . . . , (β i |F | , f (u enc (β i |F | ))), where F := β i1 , . . . , β i |F | represents the set of non-straggler worker nodes, andf • u enc := f (u enc (β i1 )), . . . , f (u enc (β i |F | ))is the corresponding set of computation results from these non-straggler workers. By the definition given in (50) , S λd,|F|,2 (•) denotes the smoothing spline operator for the decoder layer. Hence, we have the following:EQUATION)where f = f (u enc (β i1 )), . . . , f (u enc (β i |F | )) . Let us define the following variables analogous to those in (6):EQUATION)Since there are at most S stragglers among worker nodes, ∆ F max ⩽ (S + 1) • ∆ max and∆ F max ∆ F min ⩽ (S + 1) • ∆max ∆min . Additionally because ∆ max = O( 1 N ), there exists a constant J such that ∆ max ⩽ J N and correspondingly ∆ F max ⩽ J(S+1) N ⩽ J(S+1) N -S . Applying Theorem 6 with Ω = (-1, 1), m = 2, we haveEQUATION)andEQUATION)whereL = p 2 ∆ F max ∆ F min • (N -S)∆ F max 4 λ d + D(2) • ∆ F max 4and H 0 , H 1 := H(2, 0), H(2, 1) as defined in Theorem 6. Thus, we have:EQUATIONEQUATION)where D := D( 2) and (a) and (b) follow from ∆ F max ⩽ J(S+1) N -S and ∆ F max ⩽ J(S+1) N respectively. Substituting in (90),(91), and (91), we have:EQUATION)E F ∥h ′ ∥ 2 L 2 (Ω;R) ⩽ H 1 (f • u enc ) (2) 2 L 2 (Ω;R) • E F p 2 ∆ F max ∆ F min • J(S + 1) 4 λ d + DJ 4 (S + 1) 4 N 4 1 2 •   1 + E F p 2 ∆ F max ∆ F min • J(S+1) 4 λ d + DJ 4 (S+1) 4 N 4 16   1 2.(85) Therefore, we can derive an upper bound for (77) based on the above inequalities. This upper bound holds for any λ d . To obtain an upper bound independent of λ d , we minimize the right-hand side of this bound with respect to λ d . Since all upper bounds in ( 85) and ( 84 EQUATIONEQUATION)where r(S, N ) := DJ 4 (S+1) 4 N 4 . Note that, since S + 1 ⩽ N then 1 + r(S,N ) 16 ⩽ 2 max(1, DJ 4 ). Defining η := 2 max(1, DJ 4 ), we have:EQUATION)Defining C := H 1 2 0 H 1 21 η 1 4 and applying Lemma 2, completes the proof.Using the decomposition (56) we have:EQUATION)wheref = f (u enc (β i1 )), . . . , f (u enc (β i |F | )) and ϵ = ϵ i1 , . . . , ϵ i |F | .Same as (79) we define the following variables:EQUATION)Again we have ∆ F max ⩽ (S + 1) • ∆ max and∆ F max ∆ F min ⩽ (S + 1) • ∆max ∆min (a)⩽ (S + 1)B, where (a) is because of the bounded condition that we have. Therefore,∆ F max ∆ F min is bounded. Additionally, since ∆ min ⩽ 2 N , then ∆max ∆min ⩽ B implies that both ∆ max = O( 1 N ).Thus, there exists a constant J such that ∆ max ⩽ J N . Therefore, we have∆ F max ⩽ ∆ max • (S + 1) ⩽ J(S+1) N ⩽ J(S+1) N -S .Applying Theorems 6 and 7 with Ω = (-1, 1), m = 2, we have:EQUATION)andEQUATION)whereL = p 2 ∆ F max ∆ F min • (N -S)∆ F max 4 λ d + D(2) • ∆ F max 4 , H 0 , H 1 := H(2, 0), H(2, 1), andQ 0 (λ 0 ), Q 1 (λ 0 ) := Q(2, 0, λ 0 ), Q(2, 1, λ 0 )as defined in Theorems 6 and 7. Since∆ F max ∆ F min ⩽(S + 1)B, we have:EQUATION)where D := D(2), p2 (S + 1) = p 2 (B(S + 1)), p 3 (S + 1) := p2 (S + 1)• J(S+1)4 is a degree three polynomial of (S + 1), and (a) follows from the ∆ F max ⩽ J(S+1) N -S . Substituting in (90), we have:EQUATIONwhere (a) follows from the fact that λ -1 d (N -S) -4 ⩽ 1, as assumed in Theorem 7 and (b) is by definition p 4 (S + 1) := p 3 (S + 1) + DJ 4 (S + 1) 4 is a degree four polynomial of (S + 1). An analogous upper bound can be derived forEQUATIONEQUATIONEQUATION)where (a) follows from the definition λ d ⩽ λ 0 , (b) is derived from the definition η :=H 1 1 + λ 0 p4(S+1) 16 1 2. By applying the upper bound for L dec from (77) and incorporating the results from ( 93) and (94), we can deduce the following:EQUATIONwhere (a) follows by the definitions µ 0 (S) := H 0 • p 4 (S + 1) and µ 1 (S) := η • p 4 (S + 1)1 2 , and (b) is due to Q 0 (λ 0 ), Q 1 (λ 0 ) ⩽ Q max (λ 0 ) := max{Q 0 (λ 0 ), Q 1 (λ 0 )}and µ 0 (S), µ 1 (S) ⩽ µ max (S) := max{µ 0 (S), µ 1 (S)}. Therefore, we can conclude that:EQUATION)Based on the definition of µ max (S) we have:EQUATIONEQUATIONEQUATIONEQUATION)where H max := max{H 0 , H 1 } and p 4 (S) := p 4 (S)1 2 • 1+p4(S) 16 1 2 . Based on definition of Q max (λ 0 )(mentioned in Theorem 7), we have:EQUATIONwhere w max := max{w 0 , w 1 } and wmax := max{ w0 , w1 }. Therefore we have:EQUATIONSince (96) holds for all λ d , by minimizing the right-hand side of (96) with respect to λ d , we obtain:EQUATIONBy substituting the expression for λ * d into (96), we have: L dec ⩽ 4 3H max 4w max 2 5 σ 0 N -S 3 5 • p 4 (S) 2 5 • (f • u enc ) (2) 4 5 L 2 (Ω;R)   max {4, λ 0 } 1 2 max λ 1 4 0 , wmax wmax   2 5 . (101) Thus, defining C 2 := 3Hmax 4wmax , C(λ 0 ) :=   max{4,λ0}The upper bounds presented in Theorems 1 and 2 depend on (f • u enc ) (2) 2 L 2 (Ω;R) , with exponents of 2 5 and 1, respectively. By applying the chain rule, we can demonstrate that: Combining (102) with Theorems 1 and 2 we haveEQUATIONEQUATIONfor the noiseless setting andEQUATION(104)for the noisy setting, where the parameters λ e and λ e are as follows:EQUATION)λ e = 2C(λ 0 ) 3 4 σ 2 0 N -S 3 5• p 4 (S)EQUATION)Note that since ψ(t) and γ(t) := tFor part (i), we know that for t ⩽ M , we have:EQUATIONwhereEQUATIONwhere (a) is because of ∥u enc ∥ 2 H 2 (Ω;R) ⩽ M . Thus, we have:EQUATIONFor part (ii), let u enc (t) be a natural spline used as the encoder function fitted to the data points{(α k , x k )} K k=1. Then, we have:EQUATIONwhere (a) follows from the optimality of u * (•), and (b) follows fromu enc (α k ) = x k for k ∈ [K]. Therefore, Ω |(u * ) ′′ (t)| 2 dt ⩽ Ω | u enc ′′ (t)| 2 dt.Since u * (•) is smoothing spline, it has the representation in natural spline space (as mentioned in (51)):EQUATIONwhere, {b k (•)} K k=1 is a basis functions of second order natural splines. Therefore, using Cauchy-Schwarz inequality, we have:EQUATION)andEQUATION)Both ( 112) and ( 113) hold for all t ∈ Ω. Thus:EQUATIONEQUATIONwhere (51) , andξ := [ξ 1 , . . . , ξ K ] T = N T N + λΦ -1 N T x with N ij = b i (α j ), Φ ij = Ω b ′′ i (t)b ′′ j (t) dt for i, j ∈ [K] as defined inx := [x 1 , . . . , x K ]. Noted that {∥b ′ k ∥ 2 L ∞ (Ω;R) } K k=1 and {∥b k ∥ 2 L ∞ (Ω;R) } K k=1 depend only on {α k } K k=1 . Lemma 6. If ξ := N T N -1 N T x, then ∥ξ∥ 2 2 ⩽ K •κ(Φ)• ξ 2 2 < 2K | det Φ| ∥Φ∥ 2 F K K 2 ξ 2 2, whereκ(Φ) is condition number of Φ.Proof. By defining N := NΦ -1 2 and rearranging the expression for ξ, we obtain:EQUATIONDefine z := N T N -1N T x. Thus, N T x = N T Nz. Thus, by applying the Cauchy-Schwarz inequality, we have:EQUATION)Let N = UDV T be the singular value decomposition of N. Therefore, we have:EQUATIONwhere (a) is because V is an unitary matrix and λ 1 , . . . , λ K are eigenvalues of N. Continuing from (116), we obtain:EQUATION)Let us define x 0 := N T N -1 N T x. Thus, we have:EQUATION)Therefore, we can bound the ∥ξ∥ Φ := ξ T Φξ:EQUATION)Since Φ is symmetric, by Rayleigh-Ritz theorem we know that:EQUATIONwhere λ Φ min , λ Φ max are minimum and maximum eigenvalues of Φ, and (a) is due to the fact that since Φ is kernel matrix of RKHS space and {b k (•)} K k=1 are basis functions, it is positive definite. Thus, we have:∥ξ∥ 2 2 ⩽ 1 λ Φ min ∥ξ∥ 2 Φ ⩽ K λ Φ min • ∥x 0 ∥ 2 Φ ⩽ Kλ Φ max λ Φ min ∥x 0 ∥ 2 2 = Kκ(Φ) ∥x 0 ∥ 2 2 .(123)Applying the bound for condition number introduce in [66] , we can complete the proof:EQUATION)where ∥•∥ F is the Frobenius norm.Using Lemma 6, (114) , and (115) we have:EQUATIONwhere (a) follows by applying Lemma 6. Setting M equal to the right-hand side of Equation ( 125) completes the proof.Consider a natural spline u enc (t) as the encoder function fitted on the data points {(α k , x k )} K k=1 . Let u * enc (t) denote the optimal encoder minimizing the upper bound in (10) . Then, we have:EQUATIONwhere (a) follows from the optimality of u * enc (t), and (b) is due to the fact that ) for the noiseless and noisy cases, respectively. Thus, the upper bound provided in (10) converges at most at the rate of O(S 3 N -3 ) for the noiseless case and O(S 8 5 N - 3 5 ) for the noisy case.u enc (α k ) = x k , since u enc (•) is a natural spline. Note that g ∥ u enc ∥ 2 H 2 (Ω;R) isThe upper bound of the infinity norm for the estimation provided in [29] for the coded computing scheme with N workers and maximum of S stragglers is as follows:EQUATIONif N -s is odd, andfBACC (t) -f • u enc (t) L ∞ (Ω;R) ⩽ 2(1 + R) sin (S + 1)π 2N ∥f • u ′′ enc (t)∥ L ∞ (Ω;R) + ∥f • u ′ enc (t)∥ L ∞ (Ω;R) , (128) if N -s is even, where R = (s+1)(s+3)π 2 4 . Since ∥•∥ L 2 (Ω;R) is upper bounded by ∥•∥ L ∞ (Ω;R), we can directly derive a convergence rate for the squared L 2 (Ω; R)-norm of the error as N increases:fBACC (t) -f • u enc (t) 2 L 2 (Ω;R) ⩽ L(Ω) • fBACC (t) -f • u enc (t) 2 L ∞ (Ω;R) ⩽ O(S 4 N -2 ). (129)Compared to our results, the upper bound for LeTCC provided in Theorem 1, O(S 3 N -3 ), is less sensitive to the number of stragglers and converges faster with increasing N . Note that, since the ∥•∥ L 2 (Ω;R) is upper bounded by ∥•∥ L ∞ (Ω;R) , the statement above does not guarantee faster convergence of the proposed scheme compared to Berrut approach.It should be noted that [29] does not analyze the noisy setting.From the experimental view, we compare the whole encoding and decoding time (on a single CPU machine) for LeTCC and BACC frameworks, as shown in the following table: As shown in Table 2 , the end-to-end processing time of the proposed framework is on par with BACC.Although the only existing coded computing scheme for general functions is Berrut coded computing [29] , with which we have compared our proposed scheme, other schemes are designed for specific computations, such as polynomial functions [3] and matrix multiplication [13] . To provide further comparison, we evaluate our proposed scheme against Lagrange coded computing (LCC) [3] , which is specifically designed for polynomial computations, as follows:LCC is applicable only to polynomial computing functions [3] . Additionally, to enable recovery, the number of servers required must be at least (K -1) × deg(f ) + S + 1 worker nodes [3, 29] ; otherwise, the master node cannot recover any results. Moreover, LCC is designed for computation over finite fields and encounters serious instability when computing over real numbers, particularly when (K -1) × deg(f ) is around 25 or higher [18, 29] .We compare the proposed framework with LCC in Figure 5 . Note that if N < (K-1)×deg(f )+S+1, LCC cannot operate effectively. To adapt LCC for such cases, we approximate results by fitting a lower-degree polynomial to the available workers' outputs. We run LeTCC and LCC on the same set of input data and a fixed polynomial function for 20 trials, plotting the average performance and corresponding 95% confidence intervals in Figure 5 . Figures 5a and 5b illustrate the performances of LCC and LeTCC for a low-degree polynomial and a small number of data points (deg(f ) = 3 and K = 5). In contrast, Figures 5c and 5d show performance for a higher-degree polynomial and a larger dataset (deg(f ) = 15 and K = 10). As shown in Figures 5a and 5b , LCC achieves exact results for S ≤ 7. However, at larger values of S, as well as larger polynomial degree (as in Figures 5c and 5d ), the proposed approach, without any parameter tuning, outperforms LCC in terms of both computational stability (lower variance) and recovery accuracy. Consequently, the computational complexity of the proposed scheme is less than LCC.The smoothing parameters for each model show low sensitivity to the number of stragglers (or worker nodes). To find the optimal smoothing parameter, we use cross-validation across different S N values. The following table presents the optimal smoothing parameters for selected numbers of stragglers for LeNet5 with (N, K) = (100, 60) and RepVGG with (N, K) = (60, 20), respectively. As shown in Table 3 , the optimal values of λ e and λ d exhibit low sensitivity to the number of stragglers. To assess the performance of the proposed scheme with respect to the smoothing parameters, we vary each parameter individually around its optimal point while holding the other parameter fixed at their optimal value. We then record the average percentage increase in RMSE relative to the RMSE at the optimal point. Figure 6 presents these results for LeNet with (N, K, S) = (100, 60, 20) (Figures 6a and 6b ) and for RepVGG with (N, K, S) = (60, 20, 35) (Figures 6c and 6d ). As shown in Figure 6 , the presence of more stragglers increases the sensitivity of LeTCC with respect to its smoothing parameter. However, even in a high-straggler regime, the RMSE increases by only around 3% when the smoothing parameter deviates from its optimal value by a scale of 10.Let us consider more general cases where f = [f 1 , . . . , f m ] is a vector-valued function, where each component function f j : R → R is q j -Lipschitz continuous. Based on (2), we have:R( f ) ⩽ E ϵ,F ∼F S,N 2 K K k=1 ∥u dec (α k ) -f (u enc (α k ))∥ 2 2 + 2 K K k=1 ∥f (u enc (α k )) -f (x k )∥ 2 2 . ⩽ E ϵ,F ∼F S,N   2 K K k=1 m j=1 u decj (α k ) -f j (u enc (α k )) 2 2   + 2 m j=1 q 2 j K K k=1 ∥u enc (α k ) -x k ∥ 2 2 = m j=1 E ϵ,F∼F S,N 2 K K k=1 u decj (α k ) -f j (u enc (α k )) 2 2 + 2 m j=1 q 2 j K K k=1 ∥u enc (α k ) -x k ∥ 2 2Let us define the following objective for the decoder function:EQUATION)The solution to (130), denoted as u ⋆ dec , is a vector-valued function, where each component u decj (•) is a smoothing spline function fitted to the data points {(β v , f j (u enc (β v )))} v∈F . As a result, By defining q = m j=1 q 2 j and scaling up all upper bounds for L dec by a factor of m, all previous results and theorems seamlessly extend to high-dimensional computing functions. Justification:We provided all the details regarding the assumptions, conditions, and limitations in the framework explanations (Section 3), theorems (Section 4), as well as the experiments section (Section 5) in the paper. Guidelines:• The answer NA means that the paper has no 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 a 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 on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 of 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.The pre-trained weights can be found here.We use the official PyTorch pre-trained ViT network from here.are monotonically increasing in R + , its composition is monotonically increasing as well. Moreover, λ e and λ e share the same exponent of N as in Theorems 1 and 2, respectively. Consequently, the provided upper bound does not compromise the convergence rate. 


Decision: This paper provides a new perspective on "coded computing" based on ML methods. The criticism seems to be directed at the viability of "coded computing" itself, rather than the paper. The implementation of the method is also questionable due to potentially excessive training time. The authors will do well to compare fast coded computing methods such as based on LDPC codes (Maity et al.), with their scheme.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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: questions: See weaknesses
limitations: limitations: Limitations are well described.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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?
limitations: limitations: Yes, but it is spread out throughout the manuscript. A separate limitation section/paragraph would be helpful for the readers.
paper_summary: paper_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.
strength_weakness: strength_weakness: # 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: 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?
limitations: 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.
paper_summary: paper_summary: This paper focuses on coded computing for machine learning and derives loss-minimizing encoding and decoding functions.
strength_weakness: strength_weakness: Please see the “Questions” section.
questions: 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.
limitations: limitations: Yes.

Comments: title: Any feedback on the rebuttal?
References in the General Response to Reviewers
comment: Thank you for you insightful comments and feedback. We will address the complete sensitivity analysis in the revised version.
Thank you for your valuable feedback. 

The importance of stragglers in distributed computing was raised in a seminal paper by Google [1]. The proposed framework introduces a straggler-resistant scheme for general computing, which is not limited to inference. For numerical evaluation, we chose machine learning inference as a benchmark, as it has been used in related papers such as [2].

[1] Dean, J., et. al, "The tail at scale." Communications of the ACM 2013

[2] Soleymani, M., et al, "ApproxIFER: A model-agnostic approach to resilient and robust prediction serving systems." AAAI 2022.
Thank you for your insightful comments.
Thank you for the rebuttal. I still think that if the stragglers were a big issue in inference serving, then the proposed method would be an interesting solution. However, I don't really see the straggling nodes to be a real issue in practice for inference serving. 

I agree with the authors' point that the model complexity keeps growing. We should keep in mind that the largest models are typically genAI models such as LLMs or image generation models (e.g. stable diffusion). LLMs generate tokens autoregressively and stable diffusion has an iterative denoising component.
Dear Reviewer a2Af,

As we approach the conclusion of the author-reviewer discussion phase, we wish to gently remind you that we remain available to address any additional questions or concerns you may have before finalizing your score.

Best regards,
The Authors
Thank you for your response. Most of my concerns have been addressed, although the nature of the sensitivity experiment which the authors conducted does not exactly explain how bad the performance drop will be if the value of the smoothing parameters is different from the optimal values by a given amount. I raise my score to 7.
Thank you for the additional experiments, discussion about the baselines and question 3. The authors have successfully addressed my comments. 
Therefore, I raise my score to 6.
[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.