Coded Computing for Resilient Distributed Computing: A Learning-Theoretic Framework
Authors: Parsa Moradi
Behrooz Tahmasebi
Mohammad Ali Maddah-Ali
Venue: NeurIPS 2024 poster (2024)
Keywords: Coded Computing
Distributed Computing
Non-Parametric Regression
Smoothing Spline
Kernel Ridge Regression
Primary area: safety_in_machine_learning
TL;DR: We propose a new framework for coded computing, based on learning theory, to handle general computation and we provide theoretical justification for its benefits as well as experimental evaluations. It strictly outperforms the state of the art.

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.

Coded Computing for Resilient Distributed Computing: A Learning-Theoretic Framework
Parsa Moradi University of Minnesota moradi @umn edu
Behrooz Tahmasebi
Mohammad Ali Maddah-Ali University of Minnesota maddah@umn. edu
MIT CSAIL bettmit.ee
Abstract
Coded computing has emerged promising framework for tackling significant challenges in large-scale distributed computing, including the presence of slow, faulty, compromised servers. In this approach, each worker node processes combination of the data, rather than the raw data itself. The final result then is de- coded from the collective outputs of the worker nodes. However, there is signifi- cant gap between current coded computing approaches and the broader landscape general distributed computing, particularly when comes machine learning workloads. To bridge this gap, we propose a novel foundation for coded comput- ing, integrating the principles of learning theory, and developing framework that seamlessly adapts with machine learning applications. In this framework, the ob- jective is find the encoder and decoder functions that minimize the loss function, defined as the mean squared error between the estimated and true values. Facili- tating the search for the optimum decoding and functions, function can be upper-bounded by the summation of two terms: the generaliza- tion error of the decoding function and the training error 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 the estimation decays with the rate of O(5 and O(S"/ -/s) in noiseless and noisy computation settings, respectively. where N is the number of worker nodes with at most 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 accuracy and rate of convergence.
show that the loss
Introduction
The theory of coded computing has been developed to improve the reliability and security of large- scale 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 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, crucial aspect of distributed computing systems [3-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 (linear) combination of the data, known as coded data. This redundancy in the coded data enables the
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 (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 compu- tation 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 -eed-Sooomon 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 foundation that is inconsistent with the computational require- ments of machine learning. Developing code that preserves its specific construction while com- posing with computation is extremely challenging, leading to significant restrictions. Firstly, current methods mainly restricted to specific computation functions, such as polynomials and matrix multiplication [3, 11, 13, 16, 17J. Secondly, rooted in algebraic error correction codes, existing approaches are tailored for finite field computations, leading to numerical instability when dealing with val-valued data [18, 19]. Furthermore, these methods are unsuitable for approximate, fixed- point, or Moating-poine computing, where exact computation is neither possible 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, 13J. 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 com- puting scheme into 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-25], and leveraging approximation computing techniques to reduce the recovery threshold and increase recovery flexibility [26-29]. However, these attempts fail to bridge the existing gap between coded computing and general dis- tributed computing systems. The root cause of these issues lies in the fact that they are grounded in coding theory, based on foundation that is not compatible with the requirements of large-scale machine learning. Therefore, this paper aims to address the following 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.
Objective:
In this paper, we establish a learning-theoretic theoretic foundation for coded computing, applicable to general computations. We adopt 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 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-arr and the numerical evaluations support the theoretical derivations (see Figure 1(b)).

---

3
LuNel5 architecture [5 30)
B
3
Encoder
Decoder
3
logg | Ml
5
5
5
2
2
:ACC:scpe -2
Lercc:
2
5.0
logiN)
Figure ((a): Coded Computing: Each worker node Figure ((b): The log-log plot of the expected error processes combination of data (coded data). The de- versus the number of workers (N) for the proposed coder recovers final results, even in presence of framework (LeTCC) and the state-of-the tfe-the-att BACC [29]. missing outputs from some worker nodes.
LeTCC framework not only achieves a lower estimation error hut 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 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 second- order Sobolev functions, decoding functions and characterize the convergence rate for the expected loss in both noise-free and noisy computation regimes (Section 4).
the theory of RKHSs to find the optimum encoding and
We have extensively evaluated the proposed scheme across different data points and puting functions including saate-of-the-are deep neural networks and demonstrated that our proposed framework considerably outperforms the satte-of-the-are in terms of recovery ac- curacy (Section 5).
2 Preliminaries and Problem Definition
2.1 Notations
Throughout this paper, uppercase and lowercase bold letters denote matrices and vectors, respec- tively. Coded vectors and matrices are indicated by a ~ sign, as in x, Å. The set {1, (1. n) is denoted as [n] and symbol [S] denotes the cardinality of the set S. Finally, represent first, second and k-th order derivative of function f as f', f and (k),, respectively.
2.2 Problem Setting
Consider master node and set of N workers. The master node is tasked with computing { K
using cluster of N worker nodes, given a set of K data points {x X E T Here, Rdd - R represents an arbitrary function, which could be simple one-dimensional function complex deep neural network, and K, d. m are integers. A naive approach would be to assign the computation of fxxx) to one worker node & E [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 coded data points to each worker node using an encoder function. Each coded data point is combination of raw data points. Subsequently, each

---

Worker Nodes
X1
f(x1)
f(-)
f(X2)
X2
f()
f(x1)
X1
f-))
f(x2)
X2
Encoder
Decoder
uenc (Bn) = Xn
Xn
f(Xn)
udec (ax) = f(xx)
f(
f(xx)
XK
f-))
f(XN)
N
f(-)
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 's goal is to approximately recover fxxx) R f(x;) 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, {/
Proposed Framework: LeTCC
Here, we propose a novel straggler-resistaml Learning- Leaming-Theeortic Coded Computing (LeTCC) frame- work for general distributed computing. As depicted in Figure 2, our framework comprises two encoding and decoding layers, with computing layer sandwiched between them. The framework operates according to the following steps:
(1) Encoding Layer:
The master node fits an encoder regression function Men: : B Rd at points {(O,, k for fixed, distinct, and ordered values ai < 022 < ... < E IR. Then, it computes the encoder function uene(.) on another set fixed, distinct, and ordered values (8,, J.N where 31 B3 <
AN I, with & E [K] and E [N]. Subsequently, the master node sends the coded data points &,, = Ugno (8..) Rd to worker n for n E [N]. Note that each coded data point X,, a combination of all initial points
{xx [x+) R==
(2) Computing Layer: Each worker node n E [N] computes f(x.) ((uenc(5n) on its assigned input and sends the result back to the master node.
(3) Decoding Layer: The master node receives the results f(x+) from the non-straggler worker nodes in the set F. Next, it fits decoder regression function Udee IR - R
at points (3,, f(x.)) = (Be, ((uen) (B.))) Finally, using the function uaee the master node computes f(xx) Usee (a4) Recall that (dc)(ax)) se ((u)nc((a))) R3 f(xx).
approximation of f(x;) for k [K].
As mentioned above, the master node selects and fixes the regression points, [K and (3,,) J. which remain constant throughout the entire process. The encoder and decoder functions are the only components subject 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, well the computation of these regression functions points [B.Joe. and ( If the master node's computation time is not substantially decreased compared to computing K by itself, then adopting this framework would not provide any benefits for the master node.

---

3.1 Objective
We view the whole scheme as unified predictive framework that provides an approximate es- timation of the values {f(x))) We denote the estimator function of the LeTCC scheme as fa. Maee FI))), where = [ai..... ,xx' 3 == 3xl"" and F == fi...... }|j
represents the set of non-straggler worker nodes.
Let us define a random variable FS.N distributed over the set of all subsets workers with maximum stragglers, (F F C [M] [F] > N - S). Also, suppose each worker node [N]
computes the function f, (x) = f(x) + en. where 6n. n E [N] are independent zero-mean noise
vectors with covariance I
This enables us to define the following loss function, which evaluates the framework's performance:
R(P)=
E F.FNN
Σ
((xx)
((xx) ((xx))
E
[uac f(xx)113 (I)
K
FS.N
K
k=1
where f(x) Pa Menzy Udecs Fx) simplify the notation, |1-112 represents the f2-norm, and (c1,...; CNl l"l". Our objective is to find (.) and u.ec(.) that minimize the objective func- tion (1), which is very challenging, given that f()) composition of u.ec(.) and usee (.) and the computation in the middle. Here, we take an important step to decompose these two, to gain deeper understanding of interactions. Adding and subtracting f(uene and utilizing inequality of arithmetic and geometric means (AM-GM), one can obtain an upper bound for (1):
R(f)= FN.NN
(Msec (axeee()))))))))))))))))))))(( + (f(Uenc (ax)) )
K
K
2
E C.FNFS.N
Udde (aw) - (Uenc (22))
+
(f(onn 1 f(xx)l1 (2)
K
K
1=
(F)
Pe (P)
The 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.
(f) The expected generalization error of the decoder regression: Recall that the master node fits a decoder regression function, U.se.)), (-), at a set of points denoted as ((unc
Lase represents the f2-norm of the decoder regression function's
error on distinct set of points (ax J which are different from its training data { Consequently, this term provides unbiased estimate of the decoder's generalization error. Given that the decoder regression function develops estimate f(Ulenc-)), the generaliza- tion error the decoder regression is inherently tied to the properties of (.)enc())). This, in turn, is influenced by characteristics of both the f(-) and U.ne()) functions, making the Lase (f) a complex interplay of these two functions.
Leme (f) A proxy to the training error of the encoder regression: Remember that the encoder regression is fitted at points {(ax, X Consequently, the training error is calculated as 1
J Ek= [[xx)c(ax)) - Xx 122- Therefore, Lene represents the encoder training enror magnified by the effect of computing function f(-). Specifically, if f()) is Lipschitz, then Lene (f) can upper bounded by:
K
2q
K
((Uu))((())) f(xx)11
Uene (ax) - x
(3)
K
K
Rm
Main Results
In this section, we examine the proposed framework from theoretical standpoint. We provide comprehensive explanation of the design process for the decoder and encoder functions and subse- quently analyze the convergence rate. For simplicity, we present the results for one-dimensional
5

---

function f IR - R. These results are generalizable to the case where f : - I as discussed in Appendix F.
Suppose the regression points, {ax 1k=1; {Bn) are confined to the interval Ω = (-1,1) and
Wenee Maee E 7L2 (St; R), where 712 (S2; IR) is the reproducing kernel Hilbert space (RKHS) of second- Sn (f (8)) dt
order Sobolev functions on the interval 12 induced with the norm [I
f(-1)² + f')=1) 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.
Decoder Design: Since Ldec in the decomposition (2) characterizes the generalization error of the decoder function, propose regularized objective function for the decoder:
argmin WE (Q:R)
Σ NEF
(u (B.) (Wene (Bo))) Xa J. (u"(t)) dt.
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 S2. Equation (4) represents a Kernel Ridge Regression problem (KRR). It can be shown that the solution of (4) has the following form [31, 32]:
do d1t Σ Co Bt..)
(5)
where do, d1 IR ou(:.-) ) is the kernel function of Hb (S2; R) (see Definition 2 and (44) in Ap- pendix A.1), and с = [ei....,c. F E B Substituting (5) into the main objective (4), the coefficient vectors and d == (do, d1]"' can be efficiently computed by optimizing quadratic equa- tion [33]. This solution known as the second-order smoothing spline function. The theoretical properties of smoothing splines reviewed in Appendix A.2.
Let us define the following variables, which represent the maximum and minimum distances be- tween consecutive data points in the decoder layer, [B, 1
A max WE (O)U(N)
(B²+1 B,), A min min {pu+1 pn). nE(N-1)
(6)
with 3n := 1 and BN+1 := 1. The following theorems provide crucial insights for designing the encoder function well as deriving the convergence rates.
Theorem (Upper bound for noiseless computation, an = =0). Consider the LeTCC framework with K. N worker nodes and at most S stragglers with da < N-1 Assume {ork k=1 are arbitrary and
distinct points in Ω = (-1,1) and there is constant B such that Aan continuous function, then:
< B. ff)) is q-Lisschitz
Anan
(S (S+1) N
20²
R()) <i
1I(ff Uene) "
+
Wenee (ax)) - Fkk
K
where C1 is constant.
The proof of Theorem and the detailed expression for C1 can be found in Appendix B.1. Theorem (Upper bound for noisy computation). Consider the LeTCC framework with N worker nodes and at most S stragglers and (N- Xa- & do for constant dn E. Assume each worker node computes fa(x) f(x) fn with E[(r)] = O and [B(2]] & og Assume (ax } K
k= are arbitrary
and distinct points in Ω = (-1,1) and suppose there is constant B such that Ann < B. Assume f()) is q-Lipschitz continuous function. Then,
Ann
0. (C2 (g(C)))) PP((S) II Uhnne) (I(
29 K
K
R(} <
"
(Wenc ((ts) xxx)
N N- -S)
k=1
(8)

---

if
C2 -()o) ps(S) ||(S (eene) )2)
1
(22()))))))
< SW--5)-
(9)
(N -
-N-5) 5)
where C2 is constant, C(Ao) O(A)) is an increasing function of Xu, and pa(S) is degree-4 polynomial in S with positive constant coefficients.
The proof and expressions for C2 and C(Ao) are provided in Appendix B.2.
The upper bounds established in Theorems 1, 2 hold for all Mene H2 RR) However, they do not directly lead to a design for (-). To address this, we present the following theorem which bounds the || o Wene (0:3)) enabling us to construct M-ne(-) without compromising the convergence rate.
Encoder Design:
Theorem 3. Consider a LeTCC scheme. Assume computing function f6) is q-Lipschitz continuous and | (Q:R) v. Then:
24 K
R(f) & Σ
(uen)(aa) xx6)² 2 de 2e.3(( (I ((
(10)
IR+ R_ where is depending on for some monotonically increasing function (N,S, 0o, q: v).
The proof can be found in Appendix B.3. By applying the representer theorem [34], duce that the optimal encoder (.), which minimizes the right-hand side of (10) takes the form (-ne(-) Σx= 21.0(0 -), where E RK and é is the kernel function of H22 (52: R), as discussed in Appendix A.2 and in (46). However, due 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.
de-
Proposition 1. In the noiseless case, there exists M R that depends only fax 1km and 1 { such that:
(i) If 11 ((RR) & M, then:
R(F) & R(uenc),
(1I)
where R(u) is defined as follows:
2q²
Σ (u(as) xx)² + d (m1 + m2M) (M u((()) dt).
K
R(u)
(12)
K
and my, my are constants.
(ii) If u (-) is the minimizer of (12), then ||u" |1² & M.
See Appendix B.4 for the proof. Proposition I states that, under mild assumptions there exists smoothing spline that minimizes the upper bound given in (12) without changing in convergence rate.
Using Theorems 2, and 3, derive the convergence rate of the proposed scheme as stated in the following theorem.
Convergence Rate:
Theorem 4 (Convergence rate). For LeTCC scheme with N worker nodes and a maximum of S stragglers, R()) & O (SEN-=) for the noisy computation, and R()) O (S3N-33 for the noiseless setting.
Refer Appendix B.5 for the proof. Notably, the convergence rate yields from Theorem 4 surpasses the sate-of-the-ar Berrut coded computing approach upper bound [29] (Figure 1), both with respect to S and N (see Appendix C.I for detailed comparison).
7

---

Table I: Comparison of the proposed framework (LeTCC) and the state-of-the-an (BACC) in terms of the Root Mean Squared Error (RMSE) and the Relative Accuracy (RelAcc).
LENETS
REPVGG
VIT (20,8.
(N, K, (FF)
(100, 20, 60)
(60, 20, 20)
Method
RMSE
RELACC
RMSE
RELACC
RMSE
RELACC
BACC
2.55:1 0.43
0.921 0.04
2.441 0.38
0.831 0.05
0.681 0.13
0.90+ 0.07
LETCC
2.18 0.51
0.94+ 0.04
2.04 0.42
0.87+ 0.05
0.62+ 0.11
0.94 0.06
5
Experimental Results
In this section, we extensively evaluate the proposed scheme across various scenarios. Our assess- ments involve examining multiple deep neural networks computing functions and exploring the impact of different numbers stragglers on the scheme's 's efficiency. The experiments are run using PyTorch [35] in single GPU machine. We evaluate the performance of the LeTCC scheme in three different model architectures:
Shallow model: We choose LeNet5 [36] architecture as known shallow network with approximately 6 x 10 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 10 [38] dataset. We use the recently introduced RepVGG [39] network with around 26 million parameters which was trained on CIFAR-10'.
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. consider the Vision Transformer (ViT) [40] computer vision for our prediction model, with more than 80 million parameters (in the base version). The network trained and fine-tuned the ImageNet- 1K dataset [41]
of the state-of-the-ar base neural networks in
We use the output of the last softmax layer of each model as the output. Hyper-parameterr
The entire encoding and decoding process is the same for different functions, as we adhere to a non par-maraectric approach. The sole hyper-paramedt parameters involved are the two smooth- ing parameters (Denc; Adee) which determined using cross-validation and greed search over differ- ent values 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 comput- ing [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 compu- tation in Appendix D.
Interpolation Points: We choose Chebyshev points of the first and second kind, {as) =
COS
(2k-1)m
2K
and [B,) = cos
(n-1)m for fair comparison with [29].
N-1
Evaluation Metrics:
We employ evaluation metrics assess the performance of the pro- posed framework: Relative Accuracy (RelAcc) and Root Mean Squared Error (RMSE). RelAcc defined as the ratio of the base model's prediction accuracy the accuracy of the estimated model on the initial data points. RMSE, on the other hand, is our main loss defined in (I) 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,
Ex ( - f(xx)]l2 for data distribution X.
'The pre-trained weights can he found here.
We use the official PyTorch pre-trained ViT network from here.
8

---

archtecture. (M.K) (20.111.1)
RepVGG
LeNer5
BACC LeTCC
BACC
LeTce
15-
Staggins
VIT architecture (W.K)-BD
RepVGG trchitecture. K) 180 450
Lettet5 archieecture (V, K) KiK) (100,
300
180
BACC
50
LOTCC
LeTCE
LaTCE
Number
Nanber Staggers
Namber Strageer
Figure 3: Performance comparison of LeTCC and BACC with 95% confidence interval across diverse range of stragglers for different models in a low-redundancy regime (smaller x)
Performance Evaluation: Table presents both RMSE and RelAce 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 archi- tectures, 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 config- urations, 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 illustrate the perfor- mance 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 K is rela- tively small-indicating system design without excessive redundancy, which is practical-the proposed scheme demonstrates even greater improvements in both metrics.
The calculation and inference of smoothing spline coefficients can be performed linearly the number of regression points by leveraging B-spline basis functions [43-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.
Computational Complexity:
Sensitivity Analysis: We additionally investigate the sensitivity of the proposed schemee perfor- mance 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 and Figure 6, the optimal smoothing parameters and the scheme's 's performance ex- hibit low sensitivity to the number of stragglers (or worker nodes) and to the smoothing parameters, respectively.
Coded Points: We also compare the coded points ( sent to the workers in LeTCC and BACC schemes. The results, shown Figure 7, demonstrate BACC coded samples exhibit high- frequency noise which causes the scheme to approximate the original prediction worse than LeToC.

---

arentecuree K0
RepVSG architecture.
LeMer5 arch (V,
BACC LeTCC
BACC
BACI
Lerce
Lerce
Sesggier
VIT vrviecaare, K) (20,0)
RepVGG techitecture. K) M1-1i0 180, 20)
Lettet5 architcctrre (V. (2.8) 200
-10
BACC
LoTCC
LeTCC
Sumber
Nanber Stagger
Narder
Figure 4: Performance comparison of LeTCC and BACC with 95% confidence interval across diverse range of stragglers for different models in a high-redundancy regime (larger x)
6
Related Work
Coded computing was initially introduced to tackle the challenges of distributed computation, par- ticularly 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-50J. where each task is assigned 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 s input data [3, 13. 26, 29, 51-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, 12, 13, 17, 52, 56-58). Recently, there have been attempts to gener- alize coded computing for general computations [4, 5, 29, 59]. Towards extending the application of coding computing to machine learning computation, Kosaian al. [59] suggest training a neural network to predict coded outputs from coded data points. However, the scheme of Kosaian al. [59] requires a complex training process and tolerates only one straggler. In another work, Jahani- Nezhad and Maddah-Ali [29] proposes BACC, model-agnostic and numerically stable framework for general computations. They successfully employed BACC to train neural networks on a cluster of workers, while tolerating larger number of stragglers. Building on the BACC framework, Soleymani et al. [42] introduced ApproxIFER scheme, as a straggler resistance and Byzantine-robut prediction serving system. However, the scheme of BACC uses reasonable rational interpolation (Berrut in- terpolation [60]), off the shelf, for encoding and decoding, without considering any end-to-end cost function optimize. In contrast, theoretically formalize 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, con- trasting with existing works that rely on coding theory and use metrics like minimum distance and recovery threshold for design. This shift foundations removes barriers to using coded computing for machine learning applications, allows 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, fu- ture work will extend our proposed scheme to achieve Byzantine robustness and privacy, offering promising avenues for further research.
10

---

8 Acknowledgments
This material based upon work supported by the National Science Foundation under Grant CIF- 2348638. Behrooz Tahmasebi is supported by NSF Award CCF-2112666 (TILOS Al Institute) and NSF Award 2134108.
References
[1] Jeffrey Dean and Luiz André Barroso. The tail at scale. Communications of the ACM, 56(2): 74-80, 2013.
[2] Vipul Gupta, Shusen Wang, Thomas Courtade, and Kannan Ramchandran. Oversketch: Ap- proximate matrix multiplication for the cloud. In 2018 IEEE International Conference on Big Data (Big Data), pages 298-304. IEEE, 2018.
[3] Qian Yu, Songze Li, Netanel Raviv, Seyed Mohammadreza Mousavi Kalan, Mahdi Soltanolkotabi, and Salman A Avestimehr. Lagrange coded computing: Optimal design for resiliency, security, and privacy. In The 22nd International Conference on Artificial Intelli- gence and Statistics, pages 1215-1225, PMLR, 2019.
[4] Jinhyun So, Basak Guler, and Amir Salman Avestimehr. scalable approach for privacy- preserving collaborative machine learning. In Advances in Neural Information Processing Systems, volume 33, pages 8054-8066 8066, 2020.
[5] Jinhyun So, Başak Güler, and Amir Salman Avestimehr. CodedPrivateML: A fast and privacy- preserving framework for distributed machine learning. IEEE Journal on Selected Areas in Information Theory, 2(1):441-45, 2021.
[6] Zhuqing Jia and Syed Ali Jafar. On the capacity of secure distributed batch matrix multiplica- tion. IEEE Transactions on Information Theory, 67(1 ((11)))742-74377 2021.
[7] Malihe Aliasgari, Osvaldo Simeone, and Jörg Kliewer. Private and secure distributed matrix multiplication with flexible communication load. IEEE Transactions on Information Forensics and Security, 2020.
[8] Minchul Kim and Jungwoo Lee. Private secure coded computation. In 2019 IEEE International Symposium Information Theory (ISIT), pages 1097-1101. IEEE, 2019.
[9] Wei-Ting Chang and Ravi Tandon. On the upload versus download cost for secure and private matrix multiplication. In 2019 IEEE Information Theory Workshop (ITW), pages 1-5, IEEE, 2019.
[10] Wei-Ting Chang and Ravi Tandon. On the capacity of secure distributed matrix multiplication. In 2018 IEEE Global Communications Conference (GLOBECOM), pages 1-6, 2018.
[11] Qian Yu, Mohammad Ali Maddah-Ali, and Salman Avestimehr. Straggler mitigation in distributed matrix multiplication: Fundamental limits and optimal coding. IEEE Transactions on Information Theory, 66(3):1920-1933 2020.
[12) Rafael G.I. DOliveira, Salim El Rouayheb, and David Karpuk. GASP codes for secure dis- tributed matrix multiplication. IEEE Transactions on Information Theory, 66(7):4038 40500 2020.
[13] Qian Yu, Mohammad Maddah-Ali, and Salman Avestimehr. Polynomial codes: an optimal design for high-dimensional coded matrix multiplication. Advances in Neural Information Processing Systems, 30, 2017.
[14] Irving S Reed and Gustave Solomon. Polynomial codes over certain finite fields. Journal of the society for industrial and applied mathematics, 8(2):300-304, 1960.
[15] Venkatesan Guruswami, Atri Rudra, and Madhu Sudan. Essential Coding Theory. Draft Available, 2022.

---

[16] K. Lee, M. Lam, R. Pedarsani, D. Papailiopoulos, and K. Ramchandran. Speeding up dis- tributed machine learning using codes. IEEE Transactions on Information Theory, 64(3):1514- 1529, 2018.
[17] K. Lee, C. Suh, and K. Ramchandran. High-dimensional coded matrix multiplication. In Pro- ceedings of IEEE International Symposium on Information Theory (ISIT), pages 2418-2422 2017.
[18] Walter Gautschi and Gabriele Inglese. Lower bounds for the condition number of vandermonde matrices. Numerische Mathematik, 52(3):241-255 1987.
[19] Gene Golub and Charles F. Van Loan, Matrix computations. JHU press, 2013.
[20] Jinhyun So, Basak Guler, and Salman Avestimehr. A scalable approach for privacy-preserving collaborative machine learning, Advances in Neural Information Processing Systems, 33:8054- 8066, 2020.
[21] Adarsh M. Subramaniam, Anoosheh Heidarzadeh, and Krishna R. Narayanan. Random Khatri-Rao- Ahatru-Rao--roduct codes for numerically-stan -table distributed matrix multiplication. CoRR, abs/1907.0 abs/1997,0 2019.
[22] Aditya Ramamoorthy and Tang. Numerically stable coded matrix computations via circulant and rotation matrix embeddings. IEEE Transactions Information Theory, 68(4):2684-270) 2703, 2022.
[23] Anindya Bijoy Das, Aditya Ramamoorthy, and Namrata Vaswani. Efficient and robust dis- tributed matrix computations via convolutional coding. IEEE Transactions on Information Theory, 67(9):6266-228) 6282, 2021.
[24] Mahdi Soleymani, Hessam Mahdavifar, and Amir Salman Avestimehr. Analog Lagrange coded computing. IEEE Journal on Selected Areas in Information Theory, 2(1):283-295, 2021.
[25] Mohammad Fahim and Viveck R Cadambe. Numerically stable polynomially coded comput- ing. IEEE Transactions on Information Theory, 67(5):2758-27855 2021.
[26] Tayyeheh Jahani-Nezhad and Mohammad Ali Maddah-Ali. CodedSketch: A coding scheme for distributed computation of approximated matrix multiplication. IEEE Transactions on Information Theory, 67155:488544 2021.
[27] Vipul Gupta, Shusen Wang, Thomas Courtade, and Kannan Ramchandran. OverSketch: Ap- proximate matrix multiplication for the cloud. In 2018 IEFE International Conference Big Data (Big Data), pages 298-304, 2018
[28] Vipul Gupta, Swanand Kadhe, Thomas Courtade, Michael W. Mahoney, and Kannan Ram- chandran. Oversketched Newton: Fast convex optimization for serverless systems. In 2020 IEEE International Conference on Big Data (Big Data), pages 288-297, 2020.
[29] Tayyebeh Jahani-Nezhad and Mohammad Ali Maddah-Ali, Berrut approximated coded com- puting: Straggler resistance beyond polynomial computing. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):1111122, 2022.
[30] George Kimeldorf and Grace Wahba. Some results on tchebycheffian spline functions. Journal of mathematical analysis and applications, 33(1):82-95, 1971.
[31] Jean Duchon. Splines minimizing rotation-invarian semi-norms in sobolev spaces. In Con- structive Theory of Functions of Several Variables: Proceedings of a Conference Held at Ober- wolfach April 25-May 1, 1976, pages 85-100. Springer, 1977.
[32] Grace Wahba. Spline models for observational data. SIAM, 1990.
[33] Grace Wahba. Smoothing noisy data with spline functions. Numerische mathematik, 24(5): 383-393, 1975.
[34] Bernhard Schölkopf, Ralf Herbrich, and Alex Smola. generalized representer theorem. In International conference computational learning theory, pages 416-426. Springer, 2001.
12

---

[35] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
[36] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 (6(11))227-2233 2324, 1998.
[37] Yann LeCun, Corinna Cortes, Chris Burges, et al. MNIST handwritten digit database, 2010.
[38] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images.
2009.
[39] Xiaohan Ding, Xiangyu Zhang, Ningning Ma, Jungong Han, Guiguang Ding, and Jian Sun. Repvgg: Making vgg-style convnets great again. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 13733-13742 2021.
[40] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. 1929, 2020.
[41] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248-255. Icce, 2009.
[42] Mahdi Soleymani, Ramy Ali, Hessam Mahdavifar, and Salman Avestimehr. ApproxIFER: A model-agnostic approach to resilient and robust prediction serving systems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 8342-8350, 2022.
[43] Paul HC Eilers and Brian D Marx. Flexible smoothing with b-splines and penalties. Statistical science, 11(2):89-121, 1996.
[44] Carl De Boor. Calculation of the smoothing spline with weighted roughness measure. Mathe- matical Models and Methods in Applied Sciences, 11(01):33 41, 2001.
[45] Chiu Li Hu and Larry L Schumaker. Complete spline smoothing. Numerische Mathematik, 49:
1-10, 1986.
[46] Matei Zaharia, Andy Konwinski, Anthony D Joseph, Randy H Katz, and Ion Stoica. Improving mapreduce performance in heterogeneous environments. In Osdi, volume 8, page 7, 2008
[47] Lalith Suresh, Marco Canini, Stefan Schmid, and Anja Feldmann. C3: Cutting tail latency in cloud data stores via adaptive replica selection. In /2th USENIX Symposium on Networked Systems Design and Implementation (NSDI 15), pages 513-527, 2015.
[48] Nihar B Shah, Kangwook Lee, and Kannan Ramchandran. When do redundant requests reduce latency? IEEF Transactions on Communications, 64(2):715-722, 2015.
[49] Kristen Gardner, Samuel Zbarsky, Sherwin Doroudi, Mor Harchol-Balter, and Esa Hyytia. Re- ducing latency via redundant requests: Exact analysis. ACM SIGMETRICS Performance Eval- uation Review, 43(1):347-3600 2015.
[50] Manmohan Chaubey and Erik Saule. Replicated data placement for uncertain scheduling. In 2015 IEEE International Parallel and Distributed Processing Symposium Workshop, pages 464-472. IEEE, 2015.
[51] Songze Li, Seyed Mohammadreza Mousavi Kalan, Amir Salman Avestimehr, and Mahdi Soltanolkotabi. Near-optimal straggler mitigation for distributed gradient methods. In 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pages 857-866 IEEE, 2018.
[52] Anindya B Das, Aditya Ramamoorthy, and Namrata Vaswani. Random convolutional coding for robust and straggler resilient distributed matrix computation. arXiv preprint 1xXiv:1907.08064,1
2019. 2019.
13

---

[53] Aditya Ramamoorthy, Anindya Bijoy Das, and Li Tang. Straggler computation via coding theory: Removing bottleneck in large-scale data processing. IEEE Signal Processing Magazine, 37(3):136-145, 2020.
Stragaler-resistant resistant distributed matrix
[54] Can Karakus, Yifan Sun, Suhas Diggavi, and Wotao Yin. Straggler mitigation in distributed optimization through data encoding. Advances in Neural Information Processing Systems, 30, 2017.
[55] R. Tandon, Q. Lei, A. G. Dimakis, and N. Karampatziakis. Gradient coding: glers in distributed learning. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 3368-3377 Sydney, Australia, August 2017.
Avoiding strag-
[56] Aditya Ramamoorthy and Li Tang. Numerically stable coded matrix computations via circulant and rotation matrix embeddings. IEEE Transactions on Information Theory, 68(4))2684-2700 2021.
[57] Qian Yu, Mohammad Ali Maddah-Ali, and Amir Salman Avestimehr. Straggler mitigation in distributed matrix multiplication: Fundamental limits and optimal coding. IEEE Transactions on Information Theory, 66(3):1920-1933 2020.
[58] Mohammad Fahim and Viveck R. Cadambe. Numerically stable polynomially coded comput- ing. IEEE Transactions Information Theory, 67(5):2758 2785, 2021.
[59] Jack Kosaian, KV Rashmi, and Shivaram Venkataraman. Parity models: A general framework for coding-based resilience in ml inference. arXiv preprint arXiv: /905000800 2019.
[60] J-P Berrut. Rational functions for guaranteed and experimentally well-conditioned global in- terpolation. Computers Mathematics with Applications, 15(1):1-16, 1988.
[61] Giovanni Leoni. A first course in Sobolev spaces, volume 181. American Mathematical Society, 2024.
[62] Robert A Adams and John JF Fournier. Sobolev spaces. Elsevier, 2003.
[63] Alain Berlinet and Christine Thomas-Agnan. Reproducing kernel Hilbert spaces in probability and statistics. Springer Science & Business Media, 2011.
[64] David L Ragozin. Error bounds for derivative estimates based on spline smoothing of exact or noisy data. Journal of approximation theory, 37(4):335-355 1983.
[65] Florencio I Utreras. Convergence rates for multivariate smoothing spline functions. Journal of approximation theory, 52(1):1-27, 1988.
[66] Heinrich W Guggenheimer, Alan S Edelman, and Charles R Johnson. A simple estimate of the condition number a linear system. The College Mathematics Journal, 26(1):2-5, 1995.
14

---

A Preliminaries
A.1 Sobolev spaces and Sobolev norms
Let Ω be an open interval IR and M be a positive integer. We denote by TP (2; (R) the class of all measurable functions IR + RM that satisfy:
J. (t) dt < co, Vj [M],
(13)
where g(-) = (') .M O-11. The space L (2; can be endowed with the following norm,
known as the L" norm:
( =
Σ 2
(14)
for 1 & p < oo, and
I ((R.M)) = max sup [g)(t)
(15)
jE[M] LEf
for oc. Additionally, function : R-M is in The (R) if it lies in IP(V; (R for all compact subsets C S2.
Definition 1 (Sobolev Space). The Sobolev space WmP (2; R) is the space all functions
g E L" (2; R) such that all weak derivatives of order denoted by g(), belong to L (Ω; (M:
for E [m]. This space is endowed with the norm:
=>b 0 LO(DERM))
11lll (00.1mm..(9:BRM)) = (191112 +
(16)
for 1 & <p= <xpoa co, and
g0(0) (=( }
|| for (0 == max (1811==(0183))
max :E|m)
(17)
Similarly, Whe (S; M) is defined as the space of all functions g E Liee (Ω; (2) with all weak
derivatives of order i belonging to Th (D) for E [m-] (QQ:Rr) and [| [m defined similar (16) and (19) respectively, using L (S;; IR) instead of LP IR).
Definition (Sobolev Space with compact support): Denoted by W (S2: RM) collection of
functions g defined on interval Ω = (a, b) such that g(a) = O'g'(a) 0.... (m...,.(mm-1(( 0 and
|m) (2(3)) < cc. This space can be endowed with the following norm:
119l = (m))
(18)
for < < oo, and
|19|l (1))) = | (M.RM)
(19)
for p
The next theorem provides an upper bound for norm of functions in the Sobolev space, which plays crucial role in the proof of the main theorems of the paper.
Theorem 5 (Theorem 7.34, [61]). Let Ω C R be open interval and let g WLl R).
Assume < p. p. r.rre & so and r > q. Then:
Il I - [IllI + + 119 (.
(20)
for every 0 < <<<c
15

---

Note that L (St) in Theorem 5 is the length of the interval Q.
((
Corollary 1. Suppose
Whl (2; and Q S R. be an open interval. If ll ((( <
(S2).
then:
llg 10ll < 2 ||ا|| L llg (=(0)))))
(21)
Substituting p.q 2 and in Theorem 5 and optimizing over l, one can derive the optimum value of E, denoted by e" as
Proof.
| (((0))))))
(22)
1 (((RR)))))
11 (x3(a)))))) || (
Since
< (12), the optimum value is in the valid interval mentioned Theorem
Corollary (Corollary 7.36, [61]). 1/p and r 2 and let E WT. lg (=a) = mi g). Then
(a, b), let S p.q.r r S oo be such that 1/r z loc (St R with g' E L" (9; Let to E [a, be such that
llg (2o) (T.Ra))) Allgll 11g (1lllll(0))RM))
(23)
where a = 0 ifr q and 1 1/p 1/r 0 and otherwise
1/p 1/r
= 1 1/p + 1/q
Corollary 3. Theorem and Covollary 2 hold true when f W2.2 (1;
Proof. We prove the above corollary by showing that w2.2 (2; 12
S w1.1 (1;:1-M)) S
Who (2: Rd). Using Sauchy-Schwarte inequality, one can show:
12 / (1,(0)) dt
| [
Σ (t(( & 1=1
Σ
1=1
M
(J 12(0))2 dt
$ (2) 00,
< (c)
Σ
(24)
)=1
where (a) follows from the bounded length of Ω and
W2.2 (2; Similarly:
II 1 = Σ // (1( <
Σ
M
12 dt
J. (1,00) at
3=1
Ø=1
(C)))) $
Σ ( |500 dt
M
(m) co.
(25)
J=1
Equations (24) and (25) prove that 2.. (2; R) S WT.1 (2;
Now, suppose f
w1.1 (S;; R²). For every closed subset [c, df Ω we have:
M Σ
1 (11100)a))
(D())a di
<
80,
(26)
j=1
(t)(t)
Σ
(
(b) (5) dt
& oc,
(27)
where (a) is due to [c, df c and (b) because of f E w1.1 R*). Therefore, f
who (2; Rd).
16

---

Equivalent norms. There have been various norms defined on Sobolev spaces in the literature that are equivalent (16) (see [62], [63, Ch. 7], and [32, Sec. 10.2]). Note that two norms II- .Il-Ilw, are equivalent there exist positive constants 7/, ?/2 such that 7/1 llgllw, & llllww, 7/2 |1g llsllwa" The equivalent norm in which we are interested is the one introduced [30]. Let = (a. b) I.. We define W (S2; 1) as the Sobolev space endowed with the following norm:
Σ 9) (l()))))
1 (02.2))))
(5(a)
+
(28)
The following lemma derives the equivalence constants (h,, 72) for the norms I1laaa and (
Lemma 1. Let 1 = (a, b) be an arbitrary open interval in IR. Then for every g E w2.2 (2;
< [2(b a) max 1, (b a)} (2 max 1, (b a)}² + 1] |
(29)
max [1, (b a)}² + +1) |19 |1
&
(30)
(b a)
Proof. By expanding around the point and utilizing the integral remainder form of Taylor's expansion, for every x E (a, we have:
g(x) g(o)= f [[ d()))
(31)
Therefore:
x(x)²= + (())))))) +20(a) S d())
20(a)² +2 [[00000
(b)
< 29(0)² 2(x a) S( (tt
& 2g(a)² + 2(b - a) [ g((1) dt,
(32)
where (a) follows from the 2g(a) fed g'(t) di < g(a)2 + (Se g() (b) is based on Cauchy- Schwartz inequality, and (c) is due to x < b. Following the same steps as (32), we have:
g((x)² < 2g) ( 2(b a) dt
(33)
Integrating both sides of (33) we have:
S 2'()) < / (a
dy 2(b 2 (f"00008 at) dy
2(b - (a) + +2 - a)2 I (t)
< 2(b a) max 1, (b a)} s(a)² + g'aa² + $f d'(1 a
2(b a) max(1, 1, (b a)} |1 -1
(34)
17

---

where (a) is based on adding the positive term (b- (b-a) a) g(a)² to the right-hand side. Based on the (32) and (34) we have:
[ (()) dx & 2 g(a) da + 2(b 2() (f. d'(0 at dx
2(b a).((a)² + +2(4 a)? g(1)2
(8)
< 2(h a) a(a)² + 4(b - a)² 3. ga())² + 4(b - a)* S( g'()P
< 4 a) max max [1, (b-aa))) (b-a)*} |19| (a:))
(35)
where (a) follows by integrating both sides of (32) and (b) is due to (33). Using (35) and (34) and the fact that La g" dt & | we have:
f 9 (²()) + S. g'tt S: g(t)² dt
lg I (O.R)
< 2 - a) max (b a)} (2 max 1, (6 - a}}² + 1) +1]
l1g a (36)
For the other side, using the same steps as (32), we have:
g(a)² - 9(x)² ( d((t) 2g(a). [- g'(t)dt
(
< 2g(2)² + 2 2(. d(())
2
(6)
< 2g(x)² + 2(x - a) S g(())2
(9
< 2g(x)² + 2(b a) [ dt)
(37)
where (a) is because of -2((a) lee g g(()) di < g(a)² + ( g'(l) di) 2 (b) follows from Cauchy- Schwartz inequality, and (c) is due to x & b. Integrating both sides of (37), we have
(b - aa.).. g()) = { g(a)² do <
g(x)² de + 2(b 10--0 a) 1" (f0000 di dx
0(1)² di + 2(b -(b-bboop aa) S d'
2
2 max (b (b-a)} a)}² (f alts dt + [ ('0(00 de + ['d'tt] dt
(t))))
2 (b - })}² || 1 [)))))))
(38)
where (a) follows by change of variable from x to t and (b) follows by adding the positive term 2 maxx(1, (b a)}² f (t))) to the right side. Thus, (38) directly results in
2
g(a)² < (b (b-a) a)
max (b-a)) a}}² || I (
(39)
Following same steps as (38) and (39) results in
g')2²² 2 < (b a)
max(1, (b-,,))))) a)}² || (
(40)
Considering the fact that 1 (t)) dt & I1 we can complete the proof:
||al| o(a)² + 2a)2 + L (t))) dt
(b (b-a) max (1, (b - a)} + +1) -1
4
(41)
18

---

Corollary 4. Based on Lemma 1, for Ω = (-1, have
11ll ((2,)) < || [19l & 73 1191ll (2)))))))
(42)
Corollary 4 directly follows from Lemma by substituting (a, b) = (-1,1).
Corollary 5. The result of Lemma I remains valid for multi-dimensional cases, where 9 R - R.M, for some M >
Corollary directly follows from applying Lemma each component of the function g(-) and using the definition vector-valued function norm:
M Σ
M
Illl
(
Σ
g000)
Proposition 2. (161, Section 7.21, [63, Theorem 1211/321) For any open interval Q S IR and m, M.N,
7tth (2; RM = Wmm. (2;
H. (0; := wmm (2; M)
H6" (2; (0,RM) W (9;
(43)
are Reproducing Kernel Hilbert Spaces (RKHSs).
The full expression of the kernel function of 7 (S2; R) and HTh (S2; R) and other equivalent norms of Sobolev spaces can be found in [63, Section 4]. For 7. (S2; R). the kernel function as follows:
13
(t (t- mmm-1 1 (s x) m-
R(t, 8)
=
Σ
+
dx.
(44)
j!2
52
(m 1)!2
==
where (.)+ positive part funetion.
A.2 Smoothing Splines
Consider the data model yı = f(4) + for = 1,.... n, where 4 f (a, C R. B(e]] = 0.
and E[c?] & ag- Assuming f E mm. (S2; R), the solution the following optimization problem is referred to as the smoothing spline:
- -2)) + 2 / (p)))(t)) dt,
S Sx =
argmin Σ (t.tt)
(45)
(
where l. Vnl. Based on Proposition 2, TM (2; = Wm, (S); R) with the norm
|l (1))8))2((2:3)))) is RKHS for some kernel function (.,,)). Therefore for any Wm. (Ω) R).
we have:
v(t) (u(-), fmm (0:)))))))
(46)
can be shown that s),,s) (t, s) + (t, s) where (t, is kernel function of Hp (Ω: R) and R. (t, s) is a null space of H (S:; R) which is the space of all polynomials with degree less than m.
The solution of (45) has the following form [31,
772
(-) = Σ d.ci()) + Σ c2,(),
(47)
1=1
19

---

where v3(.) (-,t)) for j E [n], and {(:())== are the basis functions of the space of polynomi- als of degree at most m 1. Substituting u² into (45) and optimizing over [c1,.... Gz 7 and
[d....., ......,. dn d we obtain the following result [32]:
S Sx,mmlyl(y) = Q Q XT) Q²yy
(48)
where
Qux(x+m)
Taxm
Enxn }
O 0mxm
0mxn
I (mttm)((utm)
Onx1
Enxn
Túj = (ti)),
Dij = (ti,t))
(49)
Equation (48) states that the smoothing spline fitted on the data points y is linear operator:
S SA, (z) == Axz,
(50)
for IR", where Ax:=
= Q (QTQ + A - Q It can be shown that the u" (-) is natural spline
[32, 33). Thus, if =- is basis function for an m-th order natural spline (such as truncated power or B-spline basis functions), we have:
w (t) Σ E,b,(t),
(51)
E= (N'N + XD) -1 N
(52)
where N. b,(tt), b,y (t) dt for i,j [ni] and E Ki..... E.1T.
To characterize the estimation error of the smoothing spline, If Sx.mm (y)l, we need to define two variables analogous those in (6), which quantify the minimum and maximum consecutive
distance of the regression points (4:)-21
Amax
max (1i+1 41 Amin (0(0)-((1)
min (le+1 - 44.
(53)
vE(n-1]
where boundary points are defined as (to, fn+1) = (a, The following theorem offers an upper bound for the j-th derivative of the smoothing spline estimator error function in the absence of noise (0g- = 0).
Theorem 6. (164, Theorem 4. 10]) Consider data model = (t,)) with (4.] belong to Ω = [a, for E [n]. Let
= P2(m
max
n.
+ D(m) (Amax)
2m
(54)
Amin
b b-aa
where Pa(.) 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 qpm.2 (S; there exist function H (m,,) such that:
(J - (x)m(y)) (((
< <H(mj)) (1+ (1-(00)) (b a)2m (
))
(m-=))
m
LP(RR)
(55)
Note that (f SX., ( = f m. (y). the presence of noise, where do > 0, we can exploit the linearity of the smoothing spline operator and the mutual independence of the noise terms to conclude that:
Es [IISS SA (y)) (y)))l
E.e [[ICS SA [y] (((((+)))))) +))l ))
= =II( - S -
+ E. [IK]] - - Sammly/(
(56)
where - (S(4), [(t.)]. The first term in (56) can be upper bounded using Theorem 6. The following theorem establishes upper bound for the second term when Ams is bounded:
A
20

---

Theorem 7. (165, Section 5]) Consider data model yi f(tt)) where Blc]] = 0 and Elc,] & o
for i [n]. Assume there exist a constant B > O such that Aam
& B. Then for each j E
Bun
{0, 1, .....,.............. m) there exist constant X and function Q(m, du) such that:
Ee ||Ke (Ammm(y((t)) L2(0)R)
Q(m, (.2) og -2
(57)
n
for X & do and nd amm 3 1.
Note that based on [65], Qm. Ao) w(m, j)A3" ().,)))
B Proof of Theorems
Recall from (2) that R()) & (en (f)+ + Loce (f), where
2
Lfco(f) FNFFN
(uscolaxs) - f (Meac (Menc((x)))) 22))))
(58)
K
K
2
Lene (f)
Σ A=1
(Weec (ax)) - [(xx)))
(59)
K
We begin by deriving a general intermediate bound for Laee and Lene which will be key component in the proofs of Theorems 2 and 1. The subsequent subsections will then provide the remaining details to complete the proofs of both theorems.
Lemma 2. Let f E be q-Lipschitz continuous function Then:
2q K
Lene
(Wen (crx) xxx)
(60)
Proof. Using Lipschitz property, we have:
Lene
Σ
(a)) - f(xx1))
K
2
([(( [xxx)
K
2
(q [ (at) 1)²
K
24
K
(Meno (uene(ax:) - 22
(61)
K
k=1
As previously mentioned, Lase represents the expected generalization error the decoder function. To leverage the results from Theorems and 7 we must establish that the composition of f with the encoder Wene belongs to Sobolev space W2. (2; R).
Lemma 3. Let f + R. be q- Lipishhiitz continuous function with || & v and Q C IR be an open interval. If Uene E 2//22 (St; IR) then f Uenc E 2/222 (S; IR).
Proof. Let us define fo(t) = f(t - f(0.. Thus fo(0) = 0 and fo is L-Lisschit. Using Lipschitz property
(M (t)) - (o) < 9² Mene (t)² fo (Mgn (+)) =lf
(62)
21

---

Integrating both sides of (62):
(fo o Vene (t)) & <p / (emc dt < oc,
(63)
where (a) follows by Vene E W2. R2; Given that fo is g-Lipschitz, its derivative is bounded in the - (S2; R.)-ormm i.e.
<g. q. Thus
S 2 ((fo then (t)))) dt (fo(Menc(t)) (t)))² Meno(t)² dt < 9², / Venecty dt (b) co.
(64)
where (a) follows by chain rule and (b) follows by Meen E w2.2 (1:; R). For the second derivative have:
J. (fo(uenc(t)) dt @
[umne (t) (ueen(t)) + (()ne()2 56 Menc (t))] dt
22
(b)
(t) + w'me (t)*] [oue (t)) + fö (weno (t)) dt
(0)
+ v22 ( (V)no()) (t)] dt
(a²
(6) (Iuma (t)112200))))) + (t)e)
(g² 12)
(1 + (Iluenct))) + |I (t)1l2 )*)
(9² + 1²)
(65)
where (a) follows from the chain rule, (b) is derived using the Cauchy-Schwartz Schwartz inequality, (c) is due
to |1 2 (0:2) < v, (d) follows from Theorem with r = 4, = Q = 2, 1, and (e) is result of Mene E 22.2 R). Equations (63), (64), and (63) demonstrate that fo Uene E 22.2 (52; RR. Note that Q is bounded, and every constant function belongs 2/2.2 (92; IR). Thus, we can conclude that fo Uenn (1) + (0) = f Menc (t))(() E 2222.2 (S; R).
Let us define the function (tt)= == Udoc(t) f( (uene (t)). Based on Lemma 3, and given that Uder and a Uene belong the Sobolev space 8//2,2 (S2; R), it follows that w2.2 (1;; IR). The subsequent lemmas establish upper bounds for || y- (2):)) and [[ (p:a) leveraging properties of functions
in Sobolev spaces.
Lemma 4. 1fΩ = (-a, a), then:
[(l|)a(():)) & || ( VaB+ +2² || ( V2a
(66)
Proof. Assume Ixo 12: h (xr) = 0. Therefore, [b(x)] = S hl(x)) dx for [wo, a). Thus
[x(x)] - 1 h' hx(x) dx
[ [1'(z)) dr & (f"
111dds dr
$ ( [1(xx)) dz $ (67)
where (a) and (b) are followed by the triangle and Cauchy-Schward inequalities respectively. Inte- grating the square of both sides over the interval [roo, a) yields:
f (2))) do & ("
([ dx dz & (n (2 (2-=0)
2o) dz S [1((x))2 dx,
(a 1--ma xo)- -xo)-
20
(68)
where (a) follows by vi < a. On the other side, we have the following for every x E xo]:
[Mxx] | (((x) dx <
280 [M(xa) dr <
(1,0) 12 de
$1 [N())) dr
1/2
(69)
22

---

Therefore, we have similar inequality:
[h(x))? dx & 1 (oo - 2)) dx / (x)) dr.
(70)
Using (68) and (70) completes the proof:
[ = / 20 [n(x)) dx + f |1(x))/ dx
|| 11(1)))00))
(
3g
(x0 -x) I) dx + f
(a- -
zo) dr
2
a
a² - x
|| |1
3o (rD aa)
+
30 (a xo)
(71)
2
2
= =1 =114')2
(n) + d²) < 11h' [16'l12((2)))
2a².
(72)
Thus, if zo exists, the proof is complete. In the next step, we prove the existence of no E S such that h (zo) = 0. Recall that h(t) = Udde (t) - f (Mene (f)) and (+)) is the solution of (4). Assume there no such Zp. Since h E w/22 (St; IR), then h(-) is continuous. Therefore, if there exist f,,42 E S such that h(t1) < 0 and l((2) > O. then the intermediate value theorem states that there exists To E (41,42) (2) such that (xxa)) = O. Thus, h()) > 0 or h(t) < 0 for all E S. Without loss of generality, assume the first case where h(t) > 0 for all E Q2 It means that us (t) (t))eett) for all t E Q2 Let us define
8 = argmin Ustec - (Menc(())
BEF
Let Udee (t) = Udeec (t) Udee (8*). Note that Ja (1/ (t)) dt Sa (u/bec (t)) dt. Therefore,
Mudec (Bx) - / (Venc (Bo)))²=
[Tstec (Bo) + Useec (ltee(8 - (Menc (Bo))))
PEF
VEF
Σ vEFF
[Tuec (Bo) - f (Mene (Bo)))? + +IF1 Useec (B*)²
20acc(3"))
[ (Bt)) ((
vEF
[Udec (Bu) I (Menc (Bo))1²
(73)
where (a) follows from (f)) > 0 and udec(B.) ((uen((B.)) for all E F. This leads to contradiction since implies that Ude: not the solution of the (4). Therefore, our initial assumption must be wrong. Thus, there exists zn E Ω such that h(x0)) 0.
Lemma 5. Let Ω = (-1,1). For h(tt) = Mdde (t) {(eene(t) we have:
| (0. < 211 || |1 0o,
(74)
and
|| ( & 11lll + 11 60.
(75)
Proof. Using Lemma 4 one can conclude
|| (((.R)
< 22.
(76)
| (P(0:))
Since h E W/.2 (Ω; IR) we can apply Corollary 1 and Theorem 5 with = and p,g = 2 to
complete the proof of (74). Furthermore, using Theorem with = oo and p. g = 2 and completes the proof of (75).
23

---

Building upon Lemma 5 and starting from (58), we can derive an upper bound for Lase:
2
Ldee [doc(Usde) (sdce)
B
Uddc ( f (ax)))
K
K
BrFF [
K
k=1
2
E [1
k=1
(c)
2E,
|| (11(111)00))
( 2 [11112((02R)
[ [1
1
(77)
where (a) follows from the definition of htt). (b) is due to the fact that h((t) & ( for t e Ω (c) follows by applying Lemma 5, and (d) is result of applying the Cauchy-Schwaan inequality.
B.1 Proof of Theorem
Proof. As previously mentioned, (-) is second-order smoothing spline fitted the data points , f(un ().)))..., ( i f (Vene (B: }}) }. where F := { Bir,................ Pipzi } represents the set of non-straggler worker nodes, and Wene = { (Mene (Bi, )), ..... (Meac (1/1z))) ))} is the corre- sponding set of computation results from these non-straggler workers. By the definition given in (50), (x.121)(-)) denotes the smoothing spline operator for the decoder layer. Hence, we have the following:
Ex [[10[221000 Ex [[] Mene
(78)
where f = those in (6):
f (3,121))3 }) Let us define the following variables analogous to SE(O,...151)
AF
max {Big-1 3ig
AF min
min (Bigr - -Be, SE(1....(5")
(79)
Since there at most S stragglers among the worker nodes, have AE < SS+ + 1) Amax and Additionally, because Amin & 2. there exists constant J such <
AZ
(S + 1)
Ame Aun
<
A
that Amax < & and consequently, A
J(S+1)
J(S+1) N- Otherwise, this would contradict the
N
condition Ama < B. Ann
Applying Theorem 6 with Ω = (-1, 1), m 2, we have
Ey [10122000))]
Ho (f Mene M
(2))
Es [L],
(80)
(2(())))))
and
Ex | 2 [)))
$ Hi ||s Mene )(0) (2(()R)
EF
1 + 4
(81)
16'
where
L. p2
(N- S)
da + D(2)
(A
and Ho, Hi H2, 0), (2, 1) defined
A
in Theorem 6. Thus, we have:
F
(N - -S)A F
da + D. (A |
E, [.] < Rs
P2
max
max
A min
(4)
A
F
J(S 1)
Es
P2
A
F
Aa + D. EE
AA
(82)
min
(b)
F
J(S + 1)
(S + 1)* N4
E,F
max
Aa + DJ
(83)
min
24

---

where D := (2) and (a) and (b) follow from Substituting in (91),(92), and (92), we have:
<
J(S+1) N-3
and
A <
J(S+1) N
respectively,
max
Ex |11 < Ho (f (heme) )
2
F max
J(S
Ad + DJ (S + 1)a
(2(0))
Ex
Pe
A J
4
N4
(84)
Ex [ < Hi ||s )
(2(00
EF
p2
A F
max
J
U(S+1)
4
Ad + DJ (S + 1)4
N4
EF
p2
A
A m
J(S+1)
A DJ
(S+1)* N
1 1
16
(85)
Therefore, derive upper bound for (77) based on the above inequalities. This upper bound holds for any λa- Since Àa & N-1 and
A
< (S 1)B, we have:
J(S
(S 1)4
DJ DJ (S 1)*
Ex
P2
F min
4
DJ
N4
< Pa (S+1))
N4
(S + 1)
(86)
N
where P3 is a degree-3 polynomial in (S + 1) with positive constant coefficients, and D is the sum of the coefficients of 23 and DJ Therefore, we have:
$) 1
[1 r(S,N)
Lax & (f Usno) (2)
(Ho ((),)()
H1 H1,
(2(
16
H म r(S,N) (1+ r(S,N)
= =I Mene (2)
(87)
L2(()))
16
where r(S,N) N) = D (9+1)" = 2 max(1, we have:
No. Note that, since S+1 N then 1 r(S.N) 16
< 2 max(1, D). Defining
Liss < 11
M Menc) ) (1(0)))
H H n -(S,N)
(88)
Defining := H3 Hi and applying Lemma 2, completes the proof.
B.2 Proof of Theorem 2
Using the decomposition (56) we have:
E [[A]] (11(2(0)) Ex [||s Men: 1A. 21211
EE,F [llf o Mene -A..1112 2 [
(89)
where f = (f( (Venc (Bi }}} and e == (Ci)...,,G(p)) Same as (79) we define
the following variables:
max
max [E(
{Bry1s - 3 Ar
min S (E(1...[[F1111 (B - -B,
(90)
Again we have A max of the bounded condition that we have. Therefore,
< (S+1) Amax and
A A
< (S+1)
Aus Ani
& (S+1)B, where (a) is because
A A
is bounded. Additionally, since Amia < N
25

---

then Amn & B implies that both Amax = ())) Thus, there exists constant J such that Aaa < N- Anio
Therefore, we have A & Amax (S +) < J(S+1)
((++))
Applying Theorems 6 and 7 with N-S
? = (-1, m = 2, we have:
Bes |1A1 [1100)]
< Ho .Holl(f ) ) (2(2)))
By [L] +
Qoog N S %x
(91)
and
Be [11()(22000)
< H1 (f (ooee) (2) 2 Es (1+
L
)
+ Qioâ
N S xx=
(92)
(2(02)))
16
where
L p2
(N (N-S)A Xa (12) (A Ho, Hi
H(2 0) H2, 1),
and
Amo
(o(An))Q1(Ab)) == Q22,0, 1,2,1, as defined in Theorems 6 and 7. Since
A
(S + B)B, we have:
mi
Ez[L] Ey (2 (N-S))4 S)
Aa + D. (A
(
J(S+1)
Ay DJ (S 1)
(2(S
4
(N ---))* S)
= PS(S 11 Aa DJ
(93)
(N (N- 5)
where := (22) + 1) - P2 (B(S 1)), pa + 1) == (5 J(S+1) a degree three
1
polynomial of (5 + 1), and (a) follows from the A & J(S+1) N-S
Substituting in (91), we have:
E.FF [1NN12(00.R]]
& Ho (f a uene)
2
Pa(S + 1) Ass DJ (5+
+ Lo(An)o N S Ad
(2(0.R)
(N 55
(a)
< Ho [] Memo
(2)
Au (pa(S + 1) + DJ + 1)t) + 2o(Ao)
N W-S X1
(2((R))
h Ho (f o uenc) (2)
2
Aa pa(S + 1) + 2o(2o N - \ 1/4
(94)
(:;())
where (a) follows from the fact that 1 - S) < 1, as assumed in Theorem 7 and (b) is by definition Ps + 1) := PS + 1) + (S + 1)* is a degree four polynomial of (S + 1). An analogous upper bound can be derived for E.,= [1 as
< Hr (f Menc) 12) 180)|1 (
(1 (1+ Au Pa(S+ + +111
EeFF | [1
-x pa 1)}
16
(20)00
+ N N-S S
X-
( S Hi (s o Mene) Mene 12)
pr ps + 1)
1 do Pa 1) 2
16
(An)
-
+ N S S
@ [ o Unm) )22)
(2(3)))) n. { p4(S + 1)
Q1 x
(95)
N
where (a) follows from the definition Aa
< An. (b) is derived from the definition n = By applying the upper bound for Lase from (77) and incorporating the
H1 (1 + A0 p((S+1) 1
16
26

---

results from (94) and (95), we can deduce the following:
(a)
(|(E o Menc )eno) )
M Qo(AD)o
Ldce <
- N0
L2(BRR)
(||Cf Uene
)22
(1(S) + Qi(A0)0n
Ad
(2(()))
-
< 2n
(|(C Mene) )
(2)
(2(0))) Mmax (S) + Q (Mo)
Ad
N S
2x ||(f Uonne )(2)
(((()))) Mmnx (S) + Qma (20)
(96)
N - S
where (a) follows by the definitions (o(S) == Hg (s + 1) and μ1 (S) == 8j (s(S + 1) and (b)
is due to Qu(Ao), (Ao) Qmax (Ao) max (o())))) Q1 (Ao)) and (D( f1 (8) Σ Mmax (S)
max max( (Mo(S), Mi (5)}. Therefore, we can conclude that:
Leec < 22 (mmx((S) -11 )ene) 12(02:))
+ Xy
(97)
N
Based on the definition of Umax (S) we have:
(1 11 1 P4( 7
Jmmax (S) = max Ho Pa(S), H1
(1
Pa(S)
16
(SP
Hmux: ps()) max p4(5),
16
< Hmax ((())) (1 (1+p4(5)
max {16, }o}
16
-max (54(S) max {4, Ao
(98)
where Hmax == max Ho, H1} and (a() = (=()) ( (Itp((8)) (mentioned in Theorem 7), we have:
Based on definition of Quax (Nn)
Q (An) max m wos wi Ao + w1
< Wmax A Wmax.
')
Wmax
21 max Da=
(99)
Wmax
where Wmax = max(woo: w1} and Tmaxx = max ( (W, w1
Therefore we have:
Wm. max
Ag
tines Wine
Loso & 2x Hmax (S( max (4, Ao3 ||(5 Meno )201 (2(D)R)
+ Ax
N
(100)
Since (97) holds for all da, by minimizing the right-hand side of (97) with respect Aa obtain:
3H (S(S) (N - S) - ||(s o Uene) )20 -
max {4, do}
Aj
(101)
4wmax
max
By substituting the expression for Aj into (97), have:
3
Ldsc < (3 /3H $ (N==))
max {4, Aoo
|f Uene) (2)
(N-
420maxx
max
Minax
(102)
27

---

Thus, defining C2
3Hf
C(Ao)
max (4.2))
and using previously driven upper bound
max
for Lene in Lemma 2 completes the proof.
B.3 Proof of Theorem
The upper bounds presented in Theorems 1 and 2 depend on ||(S ) 1> with exponents
of _ and respectively. By applying the chain rule, can demonstrate that:
[ [f(uea(tt)) dt ( 9
/ [u)ne()) (Uene(t) + (een(t)) f (Meno (t)) dt
12
(b)
$
(1)) + (t)") ( (U))2c())2 + f" (ueecc(t)) de
12
(
S. [1) + (t)*) dt
$
(a² v²)
(q² 12)
[I (1) (((.)))))))) + +1
(
< (q² + v²)
I (t)] + (
+ II (t)ll (f))12)(00)))
< (g² + 12)
1 (t) (1) + (1)l222 + I| (1) (172)))))))))
< (12 (2) [1
+ 4 |
(9² + v²) 73 Uene [
+4 x 73 Mene (222)
(b) (q² + x²) 2 (1
(g² + x²) + (Iuenoe 1222
(103)
where (a) follows from the chain rule, (b) derived using the Cauchy-Schward inequality, (c) due to ( & v, (d) follows from Theorem 5 with r 4, = 2, 1, (e) follows from AM-GM inequality, (f) is result of adding positive terms || | ((;;)) and || (
to the first term and || Meme (l to the second term in the parenthesis, (g) is result of applying Corollary 4, (h) by defining (t) == 73t + 4 732 and is because of Proposition 2. Combining (103) with Theorems and we have
K
R(F)
2
(uen((as) - 2 + de 36 (Iluneel ((4
(104)
A=1
for the noiseless setting and
29 K
K (Wene (Menc(Ox) xx)2 + No. (I 11 (0:30
R()) &
(105)
for the noisy setting, where the parameters and Ae are as follows:
x C1 (S + 1)3
(q² +22
(106)
N3.
N 2C())) #
o
(S)+ (9² 12)
(107)
N
Note that since (t) and (t) = : are monotonically increasing in R+, its composition mono- tonically increasing as well. Moreover, de and X share the same exponent of N as in Theorems and 2, respectively. Consequently, the provided upper bound does not compromise the convergence rate.
28

---

B.4 Proof of Proposition
For part (i), we know that for < M, we have:
(t) 73t
7 t73 x 73*t) & t(73 +4x 73 M) t(m + m2M), (108)
where my == 73, m2 = 73 Therefore, if Mene ( < M, then:
Mnn ) Σ (m² m2 M)
Menc (((())))
(mi + M)
(ennc (-1) + W'ac (-1) +
|m( )
(M+ M + ( [t)c dt
(m1 + m2
(109)
where (a) because of Mene 12 (2:3) < M. Thus, we have:
242
K
R(A)- <
xxx)² + de | ((
K
k=1
24
(ueno(ax) - =xx) de (m² m2M) (MI
M - / wC
K
R (Uenn))
(110)
For part (ii), let Meme (t) be natural spline used as the encoder function fitted to the data points (lak ]k)]/== Then, have:
Xe(m: + m221) (M + / (w)))(t) dt) < R(u*)
R(uen)) (b) de(m= + m2 M + / | (t)) limme((t) dt
(111)
where (a) follows from the optimality of u² (-), and (b) follows from Mene (an)((x)) = for ls E [K]. Therefore, So (((c)) dt & Sa [eee (1) dt.
Since n w-)+) smoothing spline, has the representation in natural spline space (as mentioned in (51)):
K+4
"² (1(
Σ
Eabx(1),
(112)
where, (bx()) is basis functions of second order natural splines. Therefore, using Cauchy- Schwartz inequality, we have:
K
K+4
Iu (t) <
Σ
E²
Σ
(b(())))
(113)
k=1
A=
and
K+4
K+4
(u (1)()) &
Σ
2
Σ 1E(O))
(114)
A=1
k=
Both (113) and (114) hold for all t Ω. Thus:
(()))(-1))²= < ||u" 1 ( < ||E12
|h 1 (0,3)
(115)
(u')(-1))² < 11(""))1 (=2R)))) < ||E||
| (0:R)
(116)
29

---

where & := [E1, EK+Il" (NTN + xa) N with Ny bi(ay), Di Sa (t)b (t) dt for i E [K + 4] as defined in (51), and x := ((1,...,xxk)) Noted that (11b/ (((R) ) k= and {llba (110|lli=(00;)))) (1:3) J== +4 depend only on {au)
K+4
$
Lemma 6. f = (NTN) -1 N then |1E122 < k())
[
2 |
[ K
E
where
R(D) is condition number of tb
Proof. By defining Ñ := N and rearranging the expression for &. we obtain:
E= (N + Aσ) N x = Φ-112 x [
T
NΦ 1/2]
+ +x1)
No 1/00
x
= [N + A1) N
(117)
Define z = [TN)
N Thus, N = N'Ñz. Thus, by applying the
inequality, have:
N N (NTN
= =
N NZ < <|(N AT) NT
-|
2
(118)
Let Ñ UDV be the singular value decomposition of N. Therefore, have:
N'N+AI -1
NTN
VVD2VT + AT) VD&V"/ ||
2
T (D² + AI) -1 V VD2V*
V- (D² + XI) ''V*/1 ||,
(D² AI) D2
X?
2
diag
X + X
X +
1,
(119)
where (a) because V is unitary matrix and A.,..., Ax are eigenvalues of N. Continuing from (117), we obtain:
11/2 2 = (NNN- NTÑ
< |z/2
(120)
Let us define Xo = NN NT.. Thus, we have:
z (NTN) -1 NT. x
(o (0-1/2N' No 1/2)
T -1/2Nxxx
1// (N N
11/2x0-
(121)
Therefore, we can bound the |E = VETTEE T
| = 1000 1/2g
|||
< ||zl|| = |
(122)
30

---

Since is symmetric, by Rayleigh-Rite Ritz theorem we know that:
<' E'E
|
min
Amax
(123)
|6
where A A are minimum and maximum eigenvalues of 4, and (a) is due to the fact that since is kernel matrix of RKHS space and (bx(-))k= are basis functions, it is positive definite. Thus, we have:
E
x
max
| = <<()) |
(124)
min
min
Ain
Applying the bound for condition number introduce in [66], we can complete the proof:
K+1
2
|
< det
(125)
+b
K +
where ||-1| is the Frobenius norm.
Using Lemma 6, (115), and (116) have:
K
K+4
|u" (((2))) &
||
|
Σ
16 (1223)
Mone (1) dt
1.0 (SUR)
k=1
1
|
Σ
| 7 (0,3)
+
K44
16 1,30 (2,3)
det
K +
+
Uene
(1)1?
(126)
where (a) follows by applying Lemma 6. Setting M equal to the right-hand side of Equation (126) completes the proof.
B.5 Proof of Theorem 4
Consider natural spline (ene(() as the encoder function fitted on the data points {ag, xx)] Let M (t) denote the optimal encoder minimizing the upper bound in (10). Then, we have:
2q K
< R(f)
(unn xxx)² + de 9( M 11 (a:))
(n)
2q
2
K
(an) - xx)² + do I( Mone (
(b)
(( Mome स2 (1:
(127)
where (a) follows from the optimality of uine()) and (b) due to the fact that Wene (anc(a))) (a4) Tke since Mene (-) is a natural spline. Note that o [| l( is independent N and S, and depends only ar and I& for 1e [K]. Additionally, based on the Theorem 3 and (106), de N and
A N- B) for the noiseless and noisy cases, respectively. Thus, the upper bound provided (10) converges at most at the rate of O 33) for the noiseless case and O(S N -8) for the noisy case.
C Comparison with Berrut Coded Computing
C.1
Convergence rate
The 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 follows:
(S + 1)T
[[aaac(() - f Meme (t)
< 2(1 + Rin
|If u (f)ll,
(128)
10 (0:R)
2N
31

---

if - s is odd, and
(S + 1)x²
[faacc() fo Menne (t) (w:R)) < + R) Rin
(Ilf (()
2N
llf w'enc (t) (103)))
(129)
if N is even, where R (s+1)(++3)r* Since ||-1l (():)) is upper bounded by |l (1:))=(()))) we can directly derive a convergence rate for the squared 1,2 (S2; IR. -norm of the error as increeses:
[eacc(() - Menn (t) ((;)) < ((2) (Eaco(t) - uena 1 (0:R)
< <O(S"N~>) (130)
Compared to our results, the upper bound for LeTCC provided in Theorem 1, O(S is less sensitive to the number of stragglers and converges faster with increasing N. Note that, since the (1)))))():)) is upper bounded by (0):))) the statement above does not guarantee faster conver-
gence of the proposed scheme compared to Berrut approach.
should be noted that [29] does not analyze the noisy setting.
C.2 Computational complexity
From the experimental view, we compare the whole encoding and decoding time (on a single CPU machine) for LeTCC and BACC frameworks, shown in the following table:
Table 2: Average and std of end-to-end processing time of LeTCC and BACC for different architectures
BACC
LETCC
LENET5, (N, K) (100, 20)
0.013s 0.002
0.007a + 0.001
REPVGG, (N, K) (60, 20)
1.62s + 0.18
1.59s 0.14
VIT. (NV, K) (20, 8) 1.60s 1 0.28
1.74s - 0.29
As shown in Table 2, the end-to-end processing time of the proposed framework is par with BACC.
D Comparison with Lagrange Coded Computing
Although the only existing coded computing scheme for general functions is Berrut coded com- puting [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:
D.1 Accuracy of function approximation
LCC is applicable only to polynomial computing functions [3]. Additionally, to enable recovery, the number of servers required must be at least (K - 1) x deg(f) S + worker nodes [3, 29]; otherwise, the master node cannot recover any results. Moreover, LCC designed for computation over finite fields and encounters serious instability when computing over real numbers, particularly /) is around 25 or higher [18,20 29].
when (K- - 1) x dfg
We compare the proposed framework with LCC in Figure 5. Note that if < (K=1)xdeg(/++$+++
LCC cannot operate effectively. To adapt LCC for such cases, we approximate results by fitting 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 low-degree polynomial and a small number of data points (deg(f) and K = 5). In contrast, Figures 5c and 5d show performance for a higher-degree polynomial and a larger dataset (deg(ʃ) = 15 and K 10). As shown in Figures 5a and 5b, LCC achieves exact results for 5 < 7. However, at larger values of S, well as larger polynomial degree (as in Figures Sc and 5c), the proposed approach, without any parameter tuning, outperforms LCC in terms of both computational stability (lower variance) and recovery accuracy.
32

---

Myrrrmal Ohggns 5 OL -120
Adverral segrus 20-200000
Lervec
4200
preppin
(a)
(b)
(d)
Figure 5: Average performance of LeTCC and Lagrange Coded Computing, with a 95% confidence interval. Plots (a) and (d) show the overall performance, while the zoomed-in subplots (b) and (c)
highlight the performance for smaller range of stragglers.
D.2 Computational complexity
Encoding and decoding complexities in LCC are O(N logg (K) log (og(K))) d) and O((V S) log ((N log - S)) log log((NV - .S) m)) respectively, where and m are input and output dimensions of the computing function f(-), respectively [3]. In contrast, as mentioned before, for smoothing splines, the encoding and decoding process, which involves evaluation on new points and calculating the fitted coefficients, have the computational complexity of O(K.d) (.dd) and
Consequently, the computational complexity of the proposed scheme is less than LCC.
E
Sensitivity Analysis
E.1 Sensitivity to number of stragglers
The smoothing parameters for each model show low sensitivity to the number of stragglers (or worker nodes). To find the optimal smoothing parameter, N values. The following table presents the optimal smoothing parameters for selected numbers of stragglers for LeNet5 with K) (100, 60) and RepVGG with (N, K) (60, 20), respectively. As shown in Table 3, the optimal values of Ae and Aa exhibit low sensitivity to the number of stragglers.
cross-validation across different
g
Table 3: Optimal smoothing parameters for different number of stragglers for LeNet and RepVGG architectures.
LENETS
REPVGG
(N, K)
(100, 60)
(60, 20)
S
X
X
x
X
0
10
13
10 6
10 6
10
5
13
10 6
10 6
10-4
10
13
10 5
10-4
15
13
1
10-5
10-4
20
10
10 6
10
10-4
25
10
10
10
10
30
10
10
10
10
35
10
10-4
10-5
10-3
E.2 Sensitivity to smoothing parameters
To assess the performance of the proposed scheme with respect to the smoothing parameters, vary each parameter individually around its optimal point while holding the other parameter fixed their optimal value. We then record the average percentage increase in RMSE relative to the RMSE at the
33

---

optimal point. Figure presents these results for LeNet with (N, KNKKS) = (100, 60, 20) (Figures 6a and 6b) and for RepVGG with (N,K, K) (60, 20, 35) (Figures and 6d).
A = =00-
A m
A. m
0.08
00:00 2002
02 182
0.00
0.30
005
0.52
0.00
-8
-12
Iag.
log.lA.1
(a)
(b)
Au A5 10
AamAl 10-
-
0.33
201 2ee0----
1Po 1982
6122
1000
0.30
0.35
0.0
2
0.00
(c)
(d)
Figure 6: Sensitivity of LeTCC performance with respect to (og) and logio(Ae). The yellow line represents the performance when the variable smoothing parameter set to zero.
As shown in Figure 6, the presence of more stragglers increases the sensitivity of LeTOC with respect to its smoothing parameter. However, even in high-straggler regime, the RMSE increases by only around 3% when the smoothing parameter deviates from its optimal value by a scale of 10.
F High-dimensional computing function
Let us consider more general cases where f [f1,-.., Sm] is vector-valued function, where each component function fj R IR. is Lipsshhti continuous. Based on (2), have:
2
R(F)
[as)(ax)) f(ueno (ax)))
|| [f f(xx)11.
FNF
K
k=1
2
m
j=1 g
(Mdtec, (Oxx) [5 (ak)))
Uene (ark) -x
K
K
k=
m7
2
(Weee,, (ax) f3 (Mene (ax))))))))
+
2 m
1
2
Menc (een((r)))) 22
Fe,N
K
K
1=1
Let us define the following objective for the decoder function:
Ujec
argmin
Σ
I|u (Bo) (uenc (1o)))12
+
Σ Au /
(u)(t))² dt.
(131)
(E
NEF
34

---

The solution to (131), denoted as doe is vector-valued function, where each component Udee, (-) smoothing spline function fitted to the data points {SS,, ʃj (Nene (3r))) oEF As a result, By defining q -ー= of and scaling up all upper bounds for Cas by factor of m, all previous results and theorems seamlessly extend to high-dimensional computing functions.
G Coded data points
Figures and 7c display coded samples generated by BACC and LeTCC, respectively, derived from the same initial data points depicted in Figure 7a. These samples are presented for the MNIST dataset with parameters (N, K) = (70, 30). From the figures, it is apparent (Specifically in paired ones that are shown with the same color) that while both schemes' coded samples are a weighted combination of multiple initial samples, BACC's coded samples exhibit high-frequency noise. This observation suggests that LeTCC regression functions produce more refined coded samples without any disruptive noise.
7
0
3
6
&
9
/
/ 6
9
8
9
5
O
77
4
9
0 9
2
0 9
0
4
6
(a) Initial inputs
7
7
9
9
9
q
9
6
&
4
4
2
q
0
9
9
9
9
9
9
9
(b) BACC coded samples
(c) LeTCC coded samples
Figure 7: Comparison of coded samples between BACC and LeTCC frameworks. Figure 7a represents the initial data points {x for K 30. Figures 7b and 7c display N 70 coded samples {x, N from BACC and LeTCC, respectively. Samples with clear differences are highlighted with the same color.
35

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We detailed our contributions clearly in the abstract and the introduction sections of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We provided all the details regarding the assumptions, conditions, and lim- itations 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 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 au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, a facial recognition algorithm may perform poorly when image resolution is low 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 fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
36

---

Answer: [Yes]
Justification: Our paper includes theoretical results in Section 4. In our theorems, we clearly mentioned all the required assumptions, and complete (and correct) proof of them is available in appendices (e.g., see Appendix B). Please see Section 3 for a full definition of the problem and introduction to the notations used in the paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proof' provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data provided not)?
Answer: [Yes]
Justification: We completely explained our proposed framework in Section 3 and we also provided details regarding our empirical evaluations in Section in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture the contribution it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
fully might suffice,
specific model and empirical evaluation,
While NeurIPS does not require releasing code, the conference does require sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in
37

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: We provided references to all the open datasets that we used in the paper. Regarding the code, are happy share later if required.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips) cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so No an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ /nips. htc///bblc/gguueeeeeeeeeeeeeeeee /et////ouuueiiionnniiiio
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
We provided full experimental details in the paper (see Section 5).
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined other appropri- ate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification: The details are provided in Section 5.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
38

---

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 enror bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report 2-sigma error bar than state that they have 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 еπτог rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
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 type of compute workers CPU or GPU, internal cluster, 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 the paper (e.g., preliminary or failed experiments that didn't t make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https http:://////....//eeeee cc weabllic/Ehhiscuddelllooeee
Answer: [Yes]
Justification:
We followed the NeurIPS code ethics in our paper.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations 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 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.
39

---

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), faireess considerations (e.g.. deployment of technologies that could make decisions that unfairly impact spe- cific 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 mitiga- tion strategies (e-g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
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 high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines restrictions to access the model or implementing safery 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
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 dataset.
The authors should state which version of the asset used and, possible, include URI.
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.
40

---

If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswith wwwwehhced....o www.coo///aa//c condsatsesss has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve these.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection. cura- tion, or other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper deseribe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve these.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. you obtained IRB approval, you should clearly state this in the paper.
41

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
42


Reviews:
[{"review_id": "thr2r3N9Lv", "reviewer": "Reviewer_Uhit", "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.", "questions": "See weaknesses", "limitations": "Limitations are well described.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main strong point are as follows:\n- new framework foundation for coded computing, new loss function and its upper bound by decomposition\n- 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.\n- 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:\n- «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.\n- 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?\n- 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.\n- How flexible is your approach if the system parameters change (the number of worker nodes or the number of stragglers).\n- Figure 3 seems to suffer from the lack of statistics (you need more experiments).\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our gratitude to the reviewer for their valuable comments and feedback. In the above, we have offered a general response to the reviewers, addressing some of their common concerns. Here, we provide additional responses to the remaining questions raised.\n\n> «We develop a new foundation for coded computing, based on the theory of learning\nrather 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.\n\n**Answer:** We appreciate the reviewer’s valuable feedback. We would like to clarify our first contribution. As we mentioned in the objective box (line 70):\n> The main objective of this paper is to develop a new foundation for coded\ncomputing, **not solely based on coding theory, but also grounded in learning theory**\n\nas well as abstract (lines 8 and 9):\n> we propose a novel foundation for coded computing, **integrating the principles of learning theory**, and developing a new framework that seamlessly adapts with machine learning applications.\n\nTherefore, what we mean by \"based on the learning theory\" is basically integrating a learning theoretic mindset, on top of coding theory, into the whole framework, including (i) considering the whole system as an end-to-end system, (ii) defining its corresponding loss function and (iii) deriving optimum encoder and decoder function using theories from kernel regression. It does not mean that we are not using coding and learning theoretical approaches instead. Conventional coded computing did not consider the whole system view and was solely based on algebraic coding theory, originally developed for communication theory, which makes them not well generalizable to machine learning applications.\n\nWe agree that this sentence in Line 86 could cause misunderstanding, and we will change it accordingly.\n\n> 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 analyze the performance under optimal encoder and decoder and compare it to the results from Section 5?\n\n**Answer:** In fact, we do use the optimal encoder and decoder functions in the numerical experiments. We proved in Corollary 4 (lines 236-240) that the optimal encoder function is the smoothing spline function, just like the decoder function. As a result, we use smoothing spline functions for our experiments in both encoder and decoder with smoothing parameters $\\lambda_{enc}$ and $\\lambda_{dec}$ respectively. For more clarification, we will mention this fact directly in our experimental setup section (Section 5).\n\n> 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.\n\n**Answer:** We have provided further comparisons with Lagrange Coded Computing in the general rebuttal, as well as in Figure 3 of the attached PDF.\n\n> How flexible is your approach if the system parameters change (the number of worker nodes or the number of stragglers).\n\n**Answer:** We have included a discussion on the sensitivity of the framework's hyper-parameters ($\\lambda_{enc}$ and $\\lambda_{dec}$) to the number of stragglers in the general rebuttal.\n\n> Figure 3 seems to suffer from the lack of statistics (you need more experiments).\n\n**Answer:** We have included a detailed description of our experiments and added confidence intervals to the plots. Please refer to the general rebuttal and Figures 1 and 2 in the attached PDF for a comprehensive discussion.\n\n> You mentioned the Byzantine case. It is known to be a problem for the codes over the real field (in the case of the finite field, the approaches are well-developed). It would be beneficial to briefly explain how you plan to deal with this problem.\n\n**Answer:** We appreciate the reviewer's insightful comment. While analyzing the scheme in the presence of Byzantine faults is beyond the scope of this paper, which primarily focuses on straggler resiliency, we acknowledge the importance of this aspect. Similar to [1], which enhances Berrut coded computing with Byzantine robustness using the Berlekamp-Welch (BW) decoding algorithm for Reed-Solomon codes [2], we plan to explore the same approach to incorporate Byzantine robustness into our framework. Still, it needs significant work to design an effective error correction algorithm and develop a theoretical guarantee tailored to our framework.\n\n\n[1] Soleymani, M., et al. \"ApproxIFER: A model-agnostic approach to resilient and robust prediction serving systems.\" AAAI 2022.\n[2] Blahut, R.E., \"Algebraic codes on lines, planes, and curves: an engineering approach.\" Cambridge University Press 2008.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eTwqO9V9qV", "reviewer": "Reviewer_JpiK", "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.", "questions": "1. Could the authors provide comparision with additional baselines?\n2. Could the authors report the computational resources needed for fitting and evaluating the encoder and decoder?\n3. 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": "Yes, but it is spread out throughout the manuscript. A separate limitation section/paragraph would be helpful for the readers.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The proposed method leverages learning theory for coded computing which seems novel and interesting.\n2. 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:\n   (a) Only one baseline is considered.  \n   (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.\n\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our gratitude to the reviewer for their valuable comments and feedback. In the above, we have offered a general response to the reviewers, addressing some of their common concerns. Here, we provide additional responses to the remaining questions raised.\n\n> The experimental section does not look comprehensive enough for the following reasons: (a) Only one baseline is considered.\n(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. \n\n>>Could the authors provide comparison with additional baselines?\n\n>>Could the authors report the computational resources needed for fitting and evaluating the encoder and decoder?\n\n\n**Answer:** We thank the reviewer for their constructive comment. Although there is only one baseline for general computing approximation, we compared our proposed scheme with Lagrange Coded Computing for polynomial computation. Additionally, we have analyzed the computational complexity of our scheme and compared it with BACC and Lagrange. Please refer to our general response for a detailed discussion.\n\n> 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.\n    \n>>Also, does this framework work (or can it be modified to work) for computing functions that take discrete inputs?\n    \n\n**Answer:** We appreciate the reviewer's thoughtful and detailed comment. Firstly, as established in Theorems 1-3, our results are predicated on the assumption of computing function smoothness, which is guaranteed by bounding the maximum norm of its first and second derivatives. Consequently, our framework ensures high recovery accuracy only when the computing function exhibits smoothness. If this smoothness assumption is not met, our framework cannot guarantee accurate recovery.\n\nSecondly, based on the results of Theorems 1-3 and Corollary 2, we have shown that the optimal encoder is the smoothing spline. It is shown that the smoothing spline operator is asymptotically equivalent to a kernel regression estimator with a Silverman kernel, whose local bandwidth is $\\lambda^{\\frac{1}{4}}q(t)^{\\frac{-1}{4}}$, where $\\lambda$ is the smoothing parameter and $q(t)$ is the probability density function of the input data points [1]. This leads to the key observation:\n\n\n* In the smoothing spline, the bandwidth (i.e., the number of data points effectively contributing to the input data of a worker node) and their corresponding weights depend on the input data distribution as well as the smoothing parameter. This property makes our approach more generalizable to various data distributions. If the data distribution is such that a linear combination of input data points may be inappropriate, we can control the number of points involved in the linear combination and their weights by choosing the right smoothing parameter. This ensures that the output of the linear combination remains reasonably close to the data distribution on which the model was trained.\n\nIn contrast, the Berrut approach has a fixed, bounded bandwidth due to the $\\frac{1}{z-\\alpha}$ factor in the numerator of the data points coefficient\n$$u_{enc}(z)=\\sum_{i=0}^{K-1} \\frac{\\frac{(-1)^i}{\\left(z-\\alpha_i\\right)}}{\\sum_{j=0}^{K-1} \\frac{(-1)^j}{\\left(z-\\alpha_j\\right)}} \\mathbf{x}_i$$\nTherefore, the problem that the reviewer mentioned will affect BACC more. This observation suggests another perspective on why the proposed solution outperforms BACC. \n\n\nFinally, in the case of discreet input, if the model exhibits \"smoothness\" (i.e., it accepts continuous input and has bounded first and second derivatives, ensuring that small changes in the input result in minimal output changes), our proposed scheme will be effective.\n\n[1] Silverman, B.W. \"Spline smoothing: the equivalent variable kernel method.\" The Annals of Statistics, 1984\n\n> Limitations: Yes, but it is spread out throughout the manuscript. A separate limitation section/paragraph would be helpful for the readers.\n\n**Answer:** We thank reviewer for the helpful comment. We will add a dedicated section to the  limitations of our work in next version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iNNAUsqqcK", "reviewer": "Reviewer_SdcZ", "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.", "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": "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.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "# Originality\nThe 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.\n# Quality\nAlthough 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.\n# Clarity\nThe main content of the paper is laid out clearly with some small typos but no major issues.\n# Significance\nThe 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\nThis paper distinguishes itself sufficiently from existing works, so I see no issues in terms of originality.\n# Quality\nLeTCC 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). \n# Clarity\nThe 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.\n\nI identified the following typos in the paper:\n- Line 502: There is a “loc” subscript missing\n- 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”\n- Figure 3: The title of the top-left plot seems to have the values of N and K reversed\n\n# Significance\nWithout 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our gratitude to the reviewer for their valuable comments and feedback. In the above, we have offered a general response to the reviewers, addressing some of their common concerns. Here, we provide additional responses to the remaining questions raised.\n\n> 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).\n\n\n**Answer:**  We thank the reviewer for the detailed question. Note that our proposed solution achieves a factor of $S^4$ for the **squared** $\\ell_2$ norm of the error, compared to the factor of $S^2$  for the $\\ell_\\infty$ norm of error (equivalently $S^4$ factor for  **squared** $\\ell_\\infty$ norm) in the BACC paper. Thus, if we compare these two schemes since $\\ell_2$ norm is upper bounded by $\\ell_{\\infty}$ norm, both of them have the factor of $S^4$ for the upper bound of the $\\ell_2$ norm of the error. Therefore, we cannot conclude that BACC performs better than LeTCC in terms of the scale of the error as a function of $S$.\n\n> 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.\n\n**Answer:** We have provided information on the statistical properties of our experiments, including confidence intervals, in the general rebuttal and Figures 1 and 2 of the attached PDF. For a comprehensive overview of our experimental results and statistics, please see the general rebuttal and the attached file.\n\n\n>I identified the following typos in the paper:\n\n>> - Line 502: There is a “loc” subscript missing \n\n>>- 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”\n\n>> - Figure 3: The title of the top-left plot seems to have the values of N and K reversed\n\n\n\n**Answer:** Thank you for pointing out the typos in our paper. We appreciate your attention to detail and have corrected them.\n\n> 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.\n\n**Answer:** Please refer to the general rebuttal and attached PDF for comprehensive information on the experiments, including smoothing parameter sensitivity, experimental statistics, and a comparison of the computational complexity of the proposed model.\n\n> 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?\n\n**Answer:** Based on Theorem 4, the error convergence rates of noiseless and noisy settings are $\\mathcal{O}(S\\cdot(\\frac{S}{N})^3)$ and $\\mathcal{O}(S\\cdot(\\frac{S}{N})^\\frac{3}{5})$, respectively. We note that, for $S<N$, $S\\cdot(\\frac{S}{N})^3 < S\\cdot(\\frac{S}{N})^\\frac{3}{5}$ and thus, as we expect, the upper bound on the error of the noiseless cases scales better compare to that of noisy ones. It is important to note that considering the variation of these bounds as a function of $S$ without considering the effect of $N$ may lead to a misleading conclusion \n\n>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.\n\n**Answer:** We thank the reviewer for pointing out the limitations of out work. We have already addressed some of them in the general rebuttal and we will include them as a separate section in the revised paper. Also we decided to add a full section to the revised version of the paper to discuss the limitations in a more structured way in the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "csJTHWSgbk", "reviewer": "Reviewer_a2Af", "summary": "This paper focuses on coded computing for machine learning and derives loss-minimizing encoding and decoding functions.", "questions": "My review is as follows:\n\nMajor: \n\nThe 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? \n\nI 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.\n\nMinor: \n\nSome 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": "Yes.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Please see the “Questions” section.", "weaknesses": "Please see the “Questions” section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our gratitude to the reviewer for their valuable comments and feedback. In the above, we have offered a general response to the reviewers, addressing some of their common concerns. Here, we provide additional responses to the remaining questions raised.\n\n> Major:\n>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?\n> 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.\n\n**Answer:** We appreciate the reviewer’s valuable feedback. We would like to answer this as follows:\n\n1. Machine Learning as a Service (MLaS) is a new paradigm where resource-constrained clients outsource their computationally expensive tasks to powerful clouds such as Amazon, Microsoft, and Google [1]. Consequently, prediction serving systems in these powerful clouds host complex machine learning models and respond to a vast number of inference queries worldwide with low latency [1]. However, the limited number of worker nodes, the large volume of inference queries, and the ever-increasing complexity of models make this task even more challenging. In this context, addressing the straggler issue and making the entire system straggler-resistant is crucial. As shown in [2], stragglers are inevitable even in simple tasks like matrix multiplication. Therefore, straggler resiliency is a vital feature of any prediction serving system. \n\n2. Inference is just one example of the proposed framework's applications. As mentioned in the paper, the framework is designed for general computing functions. Notably, inference is a crucial task, as it has been used as a benchmark in other works, such as [1]. \nBy utilizing the gradient of a model's loss with respect to its parameters as the computing function, $f(x) =\\nabla L(x; \\theta)$, where $L$ is the loss of a large pre-trained neural network like large language models, the proposed framework can be applied to fine-tuning large neural networks as well. We consider this case as a potential direction for our future work.\n\n[1] Soleymani, M., et al. \"ApproxIFER: A model-agnostic approach to resilient and robust prediction serving systems.\" AAAI 2022.\n\n[2] Gupta, V., et al. \"Oversketch: Approximate matrix multiplication for the cloud.\" Big Data 2018.\n\n> Minor:\nSome 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.\n\n**Answer:**  We appreciate the reviewer’s valuable feedback. To the best of our knowledge, for **general computation**, there is no solution that has the property of exact recovery for a small number of stragglers and approximate results for a larger straggler. On the other hand, for specific structured computations such as polynomial computation, Lagrange coded computing [1] can give us exact output if $(K-1)\\cdot \\operatorname{deg}(f) + S < N$. However, the decoding algorithm of Lagrange coded computing does not work for the cases where the above condition does not hold. If we use a heuristic solution in which we fit a lower degree polynomial to the existing solution, the approximation is not acceptable (see Figure 3 in the attachment). \n\nAdditionally, if the function that we want to compute belongs to the space of functions generated through smoothing spline basis (refer to Equation (5) in the paper), then exact recovery is also feasible in our proposed scheme with appropriate hyper-parameters and appropriate condition on the number of stragglers. \n\n[1] Yu, Q., et al. \"Lagrange coded computing: Optimal design for resiliency, security, and privacy.\" PMLR 2019.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
#  General Response to Reviewers

We appreciate the reviewers' constructive feedback. Here, we provide a general response to their common questions.

**Experiments.** In our revised version, we present a more comprehensive evaluation by incorporating the statistical properties of our experiments. Specifically, for each number of stragglers $S$, we evaluate LeTCC and BACC using the same input data points $\mathbf{x}_1, \dots, \mathbf{x}_k$ and repeat the experiment $20$ times with different sets of randomly chosen input data. We then plot the average result with a 95% confidence interval, providing a clearer picture of the performance and variability of each method. Figures 1 and 2 in the attached PDF display the average performance at a 95% confidence interval. Figure 1 shows a visible performance gain in both the RelAcc and MSE when $\frac{N}{K}$ is small (this is the practically important case, where the system is not over-designed with highly coded redundant computing). On the other hand, when the system is over-designed with a smaller $\frac{N}{K}$ ratio, then LeTCC shows a minor improvement compared to BACC, specifically in the relative accuracy.

We will include the new experiments (the ones depicted in Figure 1 of the attached PDF) in our next version.

**Sensitivity Analysis.** The smoothing parameters for each model exhibit low sensitivity to the number of stragglers (or worker nodes). To determine the optimal smoothing parameter, we employ cross-validation for different values $\frac{S}{N}$. The following tables display the optimal smoothing parameters for some numbers of stragglers for LeNet5 with $(N, K) = (100, 60)$ and RepVGG with $(N, K) = (60, 20)$, respectively. We will include this discussion in the revised version of the paper. As we can see, the optimum values of $\lambda^*_{enc}$ and $\lambda^*_{dec}$ are not sensitive to the number of stragglers.


|#Stragglers|$\lambda^*_{enc}$|$\lambda^*_{dec}$|
|-|-|-
|0|$10^{-13}$|$10^{-6}$
|5|$10^{-13}$|$10^{-6}$
|10|$10^{-13}$|$10^{-6}$
|15|$10^{-13}$|$10^{-6}$
|20|$10^{-13}$|$10^{-6}$
|25|$10^{-8}$|$10^{-5}$
|30|$10^{-8}$|$10^{-4}$
|35|$10^{-8}$|$10^{-4}$

|#Stragglers|$\lambda^*_{enc}$|$\lambda^*_{dec}$
|-|-|-
|0|$10^{-6}$|$10^{-4}$|
|5|$10^{-6}$|$10^{-4}$|
|10|$10^{-5}$|$10^{-4}$|
|15|$10^{-5}$|$10^{-4}$|
|20|$10^{-5}$|$10^{-4}$|
|25|$10^{-5}$|$10^{-4}$|
|30|$10^{-5}$|$10^{-3}$|
|35|$10^{-5}$|$10^{-3}$|

**Other Baselines.** Note that the **only** existing coded computing scheme for general functions is Berrut coded computing [1], which we have compared with our proposed scheme. Other schemes handle specific computations like polynomial functions [2] and matrix multiplication [3].

As suggested by the reviewers, we compare our proposed scheme with Lagrange coded computing [2], designed for polynomial computations:

* **Accuracy of function approximation**: Lagrange coded computing is only applicable to polynomial computing functions [2]. Also, the number of servers required to recover must be at least $(K-1)\times \text{deg}(f)+S+1$ worker nodes [1, 2]; otherwise, the master node cannot recover anything. Finally, the Lagrange coded computing is designed for computation over finite fields, and it faces serious instability problems in computation over real numbers when $(K-1)\times \text{deg}(f)$ is around $10$ or more [1, 4]. 
We compare the proposed framework (LeTCC), and the Lagrange coded computing in Figure 3 in the attached document. Recall that if $N < (K-1)\times \text{deg}(f)+S+1$, Lagrange coded computing does not work. Still, to push the application of Lagrange coded computing to those cases, we can fit a lower degree polynomial to the existing workers' results to get approximate results. We run LeTCC and Lagrange coded computing for the same set of input data and fixed polynomial function 20 times and plot the average performance with a 95% confidence interval in Figures 3a, 3b and 3c, 3d. Figures 3a and 3b show performances of Lagrange and LeTCC for the case where the degree of the polynomial and the number of data points are small ($\text{deg}(f)=3$ and $K=5$), while Figures 3c and 3d show the performance for larger polynomial degree and number of data points($deg(f)=15$ and $K=10$). As shown in Figure 3a, 3b, Lagrange gives us the exact result for $S\le7$. However, for larger values of $S$ and also in Figures 3c and 3d, the proposed approach, without any parameter tuning, outperforms Lagrange coded computing both in terms of computational stability (low variance) and the accuracy of recovery.

* The **computational complexity** of encoding and decoding in Lagrange Coded Computing are $\mathcal{O}(K\cdot \log^2(K) \cdot \log\log (K)\cdot d)$ and $\mathcal{O}((N-S)\cdot \log^2((N-S)) \cdot \log\log ((N-S))\cdot m)$, respectively, where $d$ and $m$ are input and output dimensions of the computing function $f(\cdot)$, respectively [2]. In contrast, for Smoothing Splines, the encoding and decoding process, which involves the evaluation of new points and calculating the fitted coefficients, have the computational complexity of $\mathcal{O}(K.d)$ and $\mathcal{O}((N-s).m)$, respectively, leveraging the B-Spline basis functions [5-7]. Consequently, the computational complexity of the proposed scheme is less than Lagrange Coded Computing.
Note that based on the BACC paper [1], the computational complexity of the Berrut method for encoding and decoding is the same as LeTCC. 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:

||BACC|LeTCC
|-|-|-
|LeNet5, $(N,K)=(100, 20)$| $0.013s \pm 0.002$|$0.007s \pm 0.001$
|RepVGG, $(N,K)=(60, 20)$| $1.62s \pm 0.18$|$1.59s \pm 0.14$
|ViT, $(N,K)=(20, 8)$|$1.60s \pm 0.28$|$1.74s \pm 0.29$

We will include the above discussion in the revised version of the paper.

Meta-review: 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.
Decision: Accept (poster)