# A Learning-Based Approach to Approximate Coded Computation

Navneet Agrawal1∗, Yuqin Qiu2∗, Matthias Frey1, Igor Bjelakovic3, Setareh
Maghsudi3,4,
Slawomir Stanczak1,3, and Jingge Zhu2
1 Technische Universität Berlin, Germany
2 Department of Electrical and Electronic Engineering, University of
Melbourne, Victoria, Australia
3 Fraunhofer Heinrich Hertz Institute, Berlin, Germany
4 Department of Computer Science, University of Tübingen, Germany

###### Abstract

Lagrange coded computation (LCC) is essential to solving problems about matrix
polynomials in a coded distributed fashion; nevertheless, it can only solve
the problems that are representable as matrix polynomials. In this paper, we
propose AICC, an AI-aided learning approach that is inspired by LCC but also
uses deep neural networks (DNNs). It is appropriate for coded computation of
more general functions. Numerical simulations demonstrate the suitability of
the proposed approach for the coded computation of different matrix functions
that are often utilized in digital signal processing.

††footnotetext:  $*$ These authors contributed equally to this work.
NA, MF, IB and SS acknowledge financial support by the Federal Ministry of
Education and Research of Germany in the program of ”Souverän. Digital.
Vernetzt.” Joint project 6G-RIC, project identification numbers: 16KISK020K
and 16KISK030. Furthermore, they were supported by BMBF under grant 01DR21009
and by the German Research Foundation (DFG) within their priority program SPP
1914 “Cyber-Physical Networking”. This work was also supported by the Berlin
University Alliance within the excellence strategy of the German federal and
state governments. JZ acknowledges the support by the Australian Research
Council under Project DE210101497 and the UoM-BUA Partnership scheme.

##  I Introduction

Coded Computation (CC) refers to a class of distributed computation schemes in
which an encoder injects redundancy into the input data before it is
distributed to the worker machines to perform the desired computation task.
This allows reconstruction of the full computation result with a decoding step
even if not all the workers have returned computation results. Therefore, CC
schemes can reduce latency and increase reliability in scenarios in which the
worker nodes are, e.g., subject to random failures or straggling [1].

The CC schemes with the recovery of the exact computation results are, for
instance, applicable to matrix-matrix multiplication [2, 3] and the
computation of matrix polynomials [4, 5]. Some papers have also proposed CC
schemes for these problems that can work with a significantly lower number of
worker results in the decoding step. This comes at the cost of recovering the
computation result only approximately with a certain prescribed accuracy [6,
7, 8]. Another line of research considers schemes that have a soft recovery
threshold in the sense that they do not need a minimum number of worker
results to obtain an estimate. Instead, they obtain estimates with increasing
accuracy as more and more of these results become available [9, 10, 11].
Approximate coded computation is relevant for many applications, including
those pertaining to approximate machine learning (ML) tasks using deep neural
network (DNN) models.

Many existing papers propose schemes specifically for the training stage of
DNNs that deal with erasures as well as with maliciously injected incorrect
computation results (seminal works include [12, 13]). References [14, 15, 16]
apply CC to the inference stage of ML computation tasks, and follow the
traditional CC paradigm that divides the scheme into the three stages of
encoding, computing, and decoding. These papers propose methods for “learning”
a suitable erasure code, wherein, one approach jointly trains an auto-encoder
for encoding and decoding operations, whereas, in another, the computation
corresponding to the encoded data is a specially trained neural network. In
both approaches, not only the system is constrained to a single erasure, but
the performance also degrades significantly with increasing number of inputs.

In this work, we aim to expand the class of functions compatible with the
approximate CC schemes to include non-polynomial functions other than, but not
excluding, the evaluations of the inference stage of neural networks. For
numerical evaluations, we focus on the approximate CC computations of the
following functions, which we believe to be of particular interest in the
context of wireless communications: computation of ($P_{1}$) the eigenvalues,
($P_{2}$) the dominant eigenvector corresponding to the largest absolute
eigenvalue, ($P_{3}$) the matrix exponential, and ($P_{4}$) matrix determinant
of a square matrix.

To the best of our knowledge, the CC schemes for these functions have not yet
been proposed in the state-of-the-art research. Our approach is substantially
inspired by the Lagrange Coded Computation (LCC) [4], but it extends the idea
by using neural networks to achieve the following improvements:

  * •

The class of computable functions are no longer limited to the matrix
polynomials.

  * •

The proposed scheme guarantees a recovery threshold, which is a design
parameter. In particular, its choice does not depend on the number of
computation inputs directly.

  * •

Approximate function computation allows for a judicious trade-off between the
accuracy and the computation time.

##  II Notation and Preliminaries

We consider a system consisting of a _master_ and $N$ _workers_. Given a
function $\mathit{f}:\mathcal{D}\to\mathcal{S}$, where
$\mathcal{D}\subset\mathbb{R}^{M\times M}$ and $\mathcal{S}$ is some finite
dimensional Euclidean space, the master is required to compute function values
at points gathered in the set
$\mathcal{X}\triangleq\\{\mathbf{X}_{1},\dots,\mathbf{X}_{K}\\}$, where
$\mathbf{X}_{k}\in\mathcal{D}$ for all $k=1,\dots,K$. For this purpose, the
master can distribute the computations to the workers.

In coded computation, the master node takes the input data $\mathcal{X}$ to
generate $N$ encoded data $\tilde{\mathbf{X}}_{i},i=1,\ldots,N$. The worker
$i$ performs computation on the encoded data $\tilde{\mathbf{X}}_{i}$ and
returns the result to the master. The coded computation scheme allows the
master to recover all desired function values $f(\mathbf{X}_{k})$,
$k=1,\ldots,K$ upon receiving the computation results from any subset of
$R\leq N$ workers. The smallest value of $R$ for which this is possible is
called the recovery threshold of the scheme. In this way, the CC schemes can
mitigate the impact of straggling or failing worker.

The LCC [4] scheme is a coded computation scheme for computing polynomial
functions $\mathit{f}$, say, of degree $d$. The functioning principle of the
LCC can be summarized as follows (see [4] for details): The data is encoded to
$N$ matries $\tilde{\mathbf{X}}_{i}$, $i=1,\ldots,N$, each of which amounts to
the evaluation of a Lagrange polynomial of degree $K-1$ at distinct scalars
$\alpha_{n}$. The worker $n\in\\{1,\dots,N\\}$ then computes the desired
polynomial $\mathit{f}$ on the encoded data $\tilde{\mathbf{X}}_{n}$. The
computation result $\mathit{f}(\tilde{\mathbf{X}}_{n})$ can be viewed as the
evaluation of a composite polynomial of degree $(K-1)d$, formed by the
Lagrange polynomial and the polynomial function $\mathit{f}$ at a point
$\alpha_{n}$. Hence, to recover this polynomial, the master only requires
$R=(K-1)d+1$ results from the workers. The desired function values can then be
obtained by evaluating the polynomial at suitable points. Although LCC is
optimal in terms of the recovery threshold, it suffers from two crucial
limitations: (i) the function $\mathit{f}$ is restricted to be a polynomial of
the input in LCC; and (ii) the recovery threshold $R$ of LCC grows
proportionally with the number of inputs $K$ and degree $d$ of the polynomial
$\mathit{f}$.

The core motivation for this work is to explore the possibility of extending
the idea of LCC to general functions, while ensuring a recovery threshold.
Roughly speaking, we replace both the encoding and the computation operations
in LCC by deep neural networks. Particularly, these operations are carefully
designed such that the computation results from workers are evaluations of a
certain polynomial (reminiscent of LCC or any polynomial-based CC scheme),
hence only polynomial interpolation is needed for the recovery. In the sequel,
we will discuss how our construction can overcome the limitations of LCC
mentioned above to some degree. However, we point out that we only aim to
recover the result approximately, whereas LCC and many other coded computation
schemes guarantees a perfect recovery (up to numerical stability issues in the
recovery phase).

##  III AI-aided Coded Computation Scheme

We propose an _AI-aided coded computation_ (AICC) scheme that utilizes a
learning-based approach for coded computation, applicable to a large class of
functions including non-polynomials. AICC employs a system design that
inherits the recovery-through-interpolation aspect of the LCC, but ensures a
fixed recovery threshold that does not directly depend on the number of inputs
or polynomial degree of the function. Note that although AICC can only provide
an approximate solution in general, in Section IV, we show that our design
achieves a sufficient level of accuracy. Since an approximate solution is good
enough in many practical applications, AICC is relevant in a wide range of
applications. In the following, we first describe the system architecture and
then the training procedure of the proposed scheme.

###  III-A System architecture and operation

. . .Enc.$E$$\mathbf{X}_{1}$$\mathbf{X}_{K}$$\alpha_{n}$Comp. $H$Pre-proc.. .
.$\mathbf{X}_{1}$$\mathbf{X}_{K}$$\tilde{\mathbf{X}}_{n}$$\tilde{\boldsymbol{y}}_{n}$
Figure 1: Encoding and computation operation for worker $n$.

The system includes three operations: _encoding_ , _computation_ , and
_decoding_. The master performs the encoding and the decoding operations while
the workers do the computations. In the following, we describe each of these
operations in detail. Figure 1 depicts the general structure of the encoding
and computation operations for one worker.

#### Encoding operation

Figure 2 shows the structure of the encoding function. Given an integer $G>0$,
the encoder
$\mathit{E}:(\mathcal{D})^{K}\times\mathbb{R}\to\mathbb{R}^{M\times M}$ is
given by

$\displaystyle\mathit{E}(\mathcal{X},\alpha)\triangleq\sum_{g=0}^{G}\mathbf{U}_{g}\
\alpha^{g}.$ (1)

The coefficients $\mathbf{U}_{g}\in\mathbb{R}^{M\times M}$, $g=0,\dots,G$, are
obtained via the functions $\Gamma_{g}:(\mathcal{D})^{K}\to\mathbb{R}^{M\times
M}$ such that $\mathbf{U}_{g}\triangleq\Gamma_{g}(\mathcal{X})$. The functions
$\Gamma_{g}$, $g=0,\dots,G$ are DNNs whose training procedure will be
discussed in Section III-B. Given the input set $\mathcal{X}$, the function
$\mathit{e}(\cdot)\triangleq\mathit{E}(\mathcal{X},\cdot)$ is a degree $G$
polynomial. Integer $G$ is a design parameter that, in contrast to the LCC,
does not directly depend on the number of input matrices $K$. Encoded matrices
are obtained for $N$ distinct scalars $\\{\alpha_{1},\dots,\alpha_{N}\\}$ as:

$\displaystyle(\forall
n\in\\{1,\dots,N\\})\qquad\tilde{\mathbf{X}}_{n}\triangleq\mathit{e}(\alpha_{n})\in\mathbb{R}^{M\times
M},$ (2)

where $\alpha_{n}\in\mathbb{R}$, for all $n=1,\dots,N$. Each encoded matrix is
then sent to one of the $N$ workers for computation.

#### Computation operation $\mathit{H}$

Figure 3 shows the structure of the computation function. Worker $n$ performs
the computation operation on the encoded matrix $\tilde{\mathbf{X}}_{n}$.
Given an integer $P>0$, the computation operation
$\mathit{H}:(\mathcal{D})^{K}\times\mathbb{R}^{M\times M}\to\mathbb{R}^{V}$
yields

$\displaystyle\mathit{H}(\mathcal{X},\tilde{\mathbf{X}})\triangleq\sum_{p=0}^{P}\mathbf{V}_{p}\
\text{Vec}(\tilde{\mathbf{X}}^{p}),$ (3)

where $\text{Vec}(\mathbf{X})$ vectorizes matrix $\mathbf{X}$ by stacking its
columns. The integer $V$ represents the number of coordinates in the range
space $\mathcal{S}$ of the desired function $\mathit{f}$. The coefficients
$\mathbf{V}_{p}\in\mathbb{R}^{V\times M^{2}}$, $p=0,\dots,P$, are obtained via
DNNs $\Lambda_{p}:(\mathcal{D})^{K}\to\mathbb{R}^{V\times M^{2}}$ as
$\mathbf{V}_{p}\triangleq\Lambda_{p}(\mathcal{X})$. Given coefficients
$\mathbf{V}_{p}$, we use
$h(\tilde{\mathbf{X}}_{n})\triangleq\mathit{H}(\mathcal{X},\tilde{\mathbf{X}}_{n})$
to denote the function that represents the computation operation. It takes
encoded data $\tilde{\mathbf{X}}_{n}$ as input and outputs the computation
result
$\tilde{\boldsymbol{y}}_{n}\triangleq\mathit{h}(\tilde{\mathbf{X}}_{n})$.
Notice that for a given dataset $\mathcal{X}$, the operation $\mathit{H}$ is
common to all the workers. Hence, the coefficients $\\{\mathbf{V}_{p}\\}$ can
be computed by the master, or by any one of the workers, and broadcasted to
all workers. The integer $P>0$ is a design parameter that does not directly
depend on the function $\mathit{f}$.

#### Decoding process

Given a scalar $\alpha\in\mathbb{R}$ and a corresponding encoded data vector
$\tilde{\mathbf{X}}$, worker output
$\tilde{\boldsymbol{y}}=h(\tilde{\mathbf{X}})=h(e(\alpha))$ can be viewed as a
polynomial evaluated at the point $\alpha$, since

$\displaystyle\mathit{h}(\mathit{e}(\alpha))=\sum_{p=0}^{P}\mathbf{V}_{p}\
\text{Vec}\left[\left(\sum_{g=0}^{G}\mathbf{U}_{g}\
\alpha^{g}\right)^{p}\right]=\sum_{l=0}^{GP}\boldsymbol{\gamma}_{l}\
\alpha^{l},$ (4)

where the last equality follows by taking scalars of the form $\alpha^{gp}$
out of the $\text{Vec}{\cdot}$ operation. Hence, the function
$\mathit{h}\circ\mathit{e}$ is a polynomial of degree
$GP\equiv\text{deg}(\mathit{e})\text{deg}(\mathit{h})$. In (4), the
coefficients $\boldsymbol{\gamma}_{l}$, $l=0,\dots,GP$, belong to
$\mathbb{R}^{V}$. Therefore, the number of data points required to recover
$\mathit{v}\triangleq\mathit{h}\circ\mathit{e}$ is $R=GP+1$. The recovery can
be performed, for example, using Lagrange interpolation. This integer $R$ is
the recovery threshold of the proposed AICC scheme.

To retrieve the final results, the master evaluates $\mathit{v}$ at scalars
$\beta_{1},\dots,\beta_{K}$, which are distinct real numbers that are chosen
in the training phase, and fixed for the given problem. This aspect is
different from LCC where these scalars can be chosen freely by the master at
the time of encoding. The final result of the decoding process is given by

$\displaystyle(\forall
k\in\\{1,\dots,K\\})\qquad\hat{\boldsymbol{f}}_{k}\triangleq\mathit{h}(\mathit{e}(\beta_{k}))\in\mathbb{R}^{V}.$
(5)

The master obtains the results
$\\{\hat{\boldsymbol{f}}_{1},\dots,\hat{\boldsymbol{f}}_{K}\\}$ as
approximations for
$\\{\mathit{f}(\mathbf{X}_{1}),\dots,\mathit{f}(\mathbf{X}_{K})\\}$. The
accuracy of this approximation, measured based on a cost function, is assured
by the training procedure described in the next section.

###  III-B Training

The encoding and decoding operations in the AICC scheme described in Section
III-A consist of DNNs
$\\{\Gamma_{0},\dots,\Gamma_{G},\Lambda_{0},\dots,\Lambda_{P}\\}$, each with
learnable parameters. These parameters are trained using a training dataset
such that the cost of approximating $\mathit{f}(\mathbf{X}_{k})$ with
$\hat{\boldsymbol{f}}_{k}$ is minimized for all $k\in\\{1,\dots,K\\}$ and all
input datasets. Distinct real-valued scalars $\beta_{k}$, $k=1,\dots,K$, are
chosen at the beginning. They remain fixed during the entire training and
operation phase. The choice of cost function depends on the application, but
it should be continuous and differentiable with respect to the learnable
parameters appearing in the DNN functions. However, one can select the
specific architecture of the DNNs and the training procedure freely. We
discuss these details in Section IV for various functions.

$\mathbf{X}_{1}$$\mathbf{X}_{2}$. . .$\mathbf{X}_{K}$$\Gamma_{0}$$\Gamma_{1}$.
.
.$\Gamma_{G}$$\times$$\times$$\alpha_{n}$$\alpha_{n}^{G}$$\mathbf{U}_{1}$$\mathbf{U}_{G}$$+$$\mathbf{U}_{0}$$\tilde{\mathbf{X}}_{n}$
Figure 2: Encoding Function at the master. $\mathbf{X}_{1}$$\mathbf{X}_{2}$. .
.$\mathbf{X}_{K}$$\Lambda_{0}$$\Lambda_{1}$. .
.$\Lambda_{P}$$\times$$\times$$\text{Vec}[\tilde{\mathbf{X}}_{n}]$$\text{Vec}[\tilde{\mathbf{X}}_{n}^{P}]$$\mathbf{V}_{1}$$\mathbf{V}_{P}$$+$$\mathbf{V}_{0}$$\tilde{\boldsymbol{y}}_{n}$
Figure 3: Computation Function of worker $n$.

Figures 2 and 3 respectively show the input-output structure of the encoding
and computation operations with corresponding DNNs. The training consists of
forward and backward passes over the system to update the parameters using the
stochastic gradient descent (SGD) algorithm. In each forward pass, given a
dataset $\mathcal{X}$ and a scalar $\beta_{k}$, the sequence of encoding,
computation, and decoding operations result in the output
$\hat{\boldsymbol{f}}_{k}=\mathit{h}(\mathit{e}(\beta_{k}))$. Then, in the
backward pass, the parameters are updated based on the gradients of the cost
w.r.t. the parameters, evaluated using the output $\hat{\boldsymbol{f}}_{k}$
and the target value
$\boldsymbol{f}_{k}\triangleq\text{Vec}(\mathit{f}(\mathbf{X}_{k}))$.

One instance of the training data consists of inputs
$\\{\mathbf{X}_{1},\dots,\mathbf{X}_{K}\\}$, distinct scalars
$\\{\beta_{1},\dots,\beta_{K}\\}$, and corresponding target labels
$\\{\boldsymbol{f}_{1},\dots,\boldsymbol{f}_{K}\\}$. The inputs
$\\{\mathbf{X}_{1},\dots,\mathbf{X}_{K}\\}$ corresponding to every training
instance are sampled i.i.d. from a given distribution which is representative
of the true distribution of inputs to the function $\mathit{f}$. One training
step consists of forward and backward pass over a _batch_ of data, and an
_epoch_ includes multiple batches. The SGD algorithm updates the weights after
every epoch, and the entire training runs for multiple epochs.

##  IV Simulations

In this section, we apply the proposed AICC scheme for coded computation of
four frequently-used matrix functions in digital signal processing
applications. In the following, we present details of those functions and
elaborate on the data generation process. We also discuss relevant
implementation issues highlighting unique aspects related to the design and
training of DNNs. Numerical results appear at the end, accompanied by a
discussion on the effect of various design parameters on the performance.

###  IV-A Applied problems

We consider the problems of computation of ($P_{1}$) the _eigenvalues_ ,
($P_{2}$) the _eigenvector corresponding to the largest absolute eigenvalue_ ,
($P_{3}$) the _matrix exponential_ , and ($P_{4}$) the _determinant_ of real-
valued square matrices. Each problem $P_{i}$, for $i=1,\dots,4$, is denoted by
the function $\mathit{f}^{(i)}:\mathcal{D}_{i}\to\mathcal{S}_{i}$,
respectively.

In the training phase, the scheme learns to solve a regression problem for
function approximation using a supervised learning approach. In this
framework, functions with an unbounded range are generally difficult to learn.
Thus, for the present simulations, we design the input distribution for each
problem to obtain a bounded range for the functions. Nevertheless, in
principle, the proposed scheme applies to any function with an arbitrary
domain and range for which a system with the structure described in Section
III is learnable to approximate the function with the desired accuracy.

For problem $P_{1}$, we generate an input sample as
$\mathbf{X}\triangleq\frac{1}{2}(\mathbf{A}+\mathbf{A}^{T})$, where
$\mathbf{A}$ is drawn uniformly from $[-1,1]^{M\times M}$. For problem
$P_{2}$, we similarly generate an input sample as
$\mathbf{X}\triangleq\frac{1}{2}(\mathbf{A}+\mathbf{A}^{T})$; however, here,
$\mathbf{A}$ is drawn uniformly from $[0,1]^{M\times M}$. We make the value of
$\mathit{f}^{(2)}$ unique by normalizing the output eigenvector to a vector of
unit norm and ensuring that the first nonzero component is positive. For
problem $P_{3}$, the input sample is generated as
$\mathbf{X}\triangleq\mathbf{A}/\lVert\mathbf{A}\rVert_{\mathrm{op}}$ with
$\mathbf{A}$ drawn uniformly from $[0,1]^{M\times M}$. In addition to keeping
the value of $\mathit{f}^{(3)}$ bounded, this ensures the numerical stability
of the algorithm used to compute the ground truth in training [17]. Here,
$\lVert\cdot\rVert_{\mathrm{op}}$ denotes the operator norm of matrices.

The matrix determinant in $P_{4}$ is bounded by generating diagonally-dominant
matrices. More precisely, we generate the input matrices as
$\mathbf{X}\triangleq\mathbf{I}-\mathbf{E}$, where $\mathbf{I}$ is the
identity matrix, and $\mathbf{E}$ has zeros on the diagonal and non-diagonal
elements sampled uniformly from $[-2.0/M,2.0/M]$ [18, 19]. The number of
coordinates in the range spaces $\mathcal{S}_{i}$, for $i=1,\dots,4$, are,
respectively, $M,M,M^{2}$ and $1$. For simulations, we compute the true values
of the functions by using the Python’s Numpy and Scipy libraries. For problems
$P_{1}$, $P_{3}$, and $P_{4}$, we use the cost function
$\mathit{C}(\hat{\boldsymbol{f}},\boldsymbol{f}):=\lVert\hat{\boldsymbol{f}}-\boldsymbol{f}\rVert$
for training, where
$\boldsymbol{f}\triangleq\text{Vec}(\mathit{f}(\mathbf{X}))$. We use
$\lVert\cdot\rVert$ to denote the Frobenius norm for matrices and vector norm
for vectors. For the eigenvector problem $P_{2}$, we add an additional term in
the cost function to influence the network in learning a vector of unit norm,
i.e.,
$\tilde{\mathit{C}}(\hat{\boldsymbol{f}},\boldsymbol{f}):=\mathit{C}(\hat{\boldsymbol{f}},\boldsymbol{f})+5\
(\lVert\hat{\boldsymbol{f}}\rVert-1.0)^{2}$.

###  IV-B Implementation details

Below we explicitly describe the DNN architecture and system design. For
simplicity, we implement the same system design and architecture for all
problems. Since the output dimension is different for each one, we choose the
free parameter $V$ (cf. (3)) to match the output dimension. The functions
$\\{\Gamma_{0},\dots,\Gamma_{G}\\}$ of the encoding polynomial $\mathit{e}$
are fully connected DNNs with $L=2$ hidden layers, each with $N=100$ nodes,
and the same non-linear activation. For the computation polynomial
$\mathit{h}$, the DNN $\Lambda_{0}$ has the same architecture as $\Gamma_{0}$,
and $\\{\Lambda_{1},\dots,\Lambda_{P}\\}$ are linear weight matrices. Note
that the master only needs to broadcast the coefficient
$\mathbf{V}_{0}=\Lambda_{0}(\mathcal{X})$ to the workers instead of the entire
input dataset $\mathcal{X}$, hence saving communication resources.

As described in Section III, we generate the training datasets randomly for
the given problem at every training iteration. This pervents overfitting of
the system to a specific dataset. A single step of training consists of a
batch of sets $\mathcal{X}$, each with $K$ i.i.d. matrices. Each training
epoch includes multiple batches. The scalar values
$\\{\beta_{1},\dots,\beta_{K}\\}$ are fixed to $\beta_{k}=k/K$, for
$k=1,\dots,K$. We implement the training using Tensorflow’s (version 2.8.0)
Keras module [20]. We employ the standard Adam optimizer from Keras, which
uses an exponentially decaying learning rate.

In the testing phase, we load the model with the learned weights of DNNs
corresponding to the training epoch with minimum loss. Besides, we generate
the test input data in the same way as for training, except that $R$ (recovery
threshold) scalars $\\{\alpha_{1},\dots,\alpha_{R}\\}$ are chosen as distinct,
but otherwise arbitrary real numbers. In simulations, we obtain these values
as $\alpha_{n}=n/(R+1)$. The master first generates the coefficients of the
encoder and computation polynomials (only $\mathbf{V}_{0}$) using the inputs
$\mathcal{X}$, and generates encoded matrices
$\\{\mathit{e}(\alpha_{r})\\}_{r=1}^{R}$. To imitate the erasure effect of the
channel, we only use the outputs of computation over these $R$ encoded
matrices (corresponding to the recovery threshold). In the final step, the
master interpolates the polynomial $\mathit{v}=\mathit{h}\circ\mathit{e}$
using $R$ worker results, and approximates the desired results as
$\hat{\boldsymbol{f}}_{k}\triangleq\mathit{v}(\beta_{k})\approx\boldsymbol{f}_{k}$
for $k=1,\dots,K$. Error in function approximation is evaluated in terms of
the normalized root mean square error (NRMSE), given by:

$\displaystyle\frac{\lVert\hat{\mathit{f}}_{k}-\mathit{f}(\mathbf{X}_{k})\rVert}{\lVert\mathit{f}(\mathbf{X}_{k})\rVert}.$
(6)

Simulations are performed on a _high performance computing_ (HPC) cluster with
nodes equipped with _graphical processing units_ (GPUs). A GPU, compared to a
_central processing unit_ (CPU), is more efficient in parallel processing of
large amount data due to its highly parallelized structure. Every HPC cluster
node is equipped with NVIDIA Tesla V100 SXM2 GPU with 32Gb RAM, and Intel
Xeon(R) Gold 6150 CPU @ 2.70 GHz with 512Gb RAM. The script used for
simulations is made available for reproducibility.111https://github.com/navya-
xx/AICC.git

###  IV-C Results

The errors in approximate coded computation of the problems
$P_{1},\dots,P_{4}$ are listed in Table I below. The results presented here
are evaluated on matrices of dimension $M=50$ with $K=3$ number of inputs in
each dataset and recovery threshold $R=5$. This shows the ability of the AICC
scheme to evaluate the functions $\mathit{f}^{(i)},i=1,\dots,4$, approximately
in a distributed manner through coded computation.

TABLE I: Function approximation error for AICC. Problem $\rightarrow$ | eigenvalue | eigvector | exponential | determinant
---|---|---|---|---
NMRSE (%) |  $4.64$% |  $5.81$% |  $7.85$% |  $1.50$%

Figure 4 shows the results for problems $P_{1}$ and $P_{2}$ in terms of
normalized root mean square error (NRMSE) for input matrices of dimensions $M$
varying from $50$ to $400$. The approximation error is low ($<5$%), and it is
interesting to observe that the error decreases with increasing dimensions
$M$, offering a reasonable accuracy for high dimensional problems. Note that,
with the present structure, the number of learnable parameters in the system
grows at least at $\mathcal{O}(KM^{2})$. While this increases the system’s
capability to learn high-dimensional problems with even higher accuracy, it
comes at the price of a longer and more complex training process.

In Figure 5, we compare the runtime of the proposed AICC scheme with standard
implementations in Python (called STD for brevity) of the problem $P_{1}$ for
exact computation of eigenvalues of a matrix. The input dataset consists of
128 batches of $K=3$ matrices, and runtime is averaged over 1000 runs. The
computation task corresponding to each scheme is performed on a single node in
the cluster. The runtime of STD is reported for both CPU and GPU based
implementations, using the Numpy function np.linalg.eigvalsh and the
Tensorflow function tf.linalg.eigvalsh, respectively. The AICC scheme runs all
master and worker computations on a single GPU, so that it is comparable to
the STD GPU computations in terms of computational resources used per unit of
time. As $M$ grows, the runtime of the STD scheme increase much faster than
that of AICC.

In Figure 6, we compare the performance of $P_{1}$ and $P_{4}$ with an
increasing number of inputs $K$, while keeping the recovery threshold of the
scheme constant at $R=5$ and the matrix dimension constant at $M=10$. Notice
that the approximation error does not increase too quickly with increasing
$K$. Therefore, for applications with a large number of input matrices needing
to be processed at a time, AICC enables approximate recovery with only a small
number of worker results.

In further experiments performed over matrix dimensions $M=10$ and $50$,
increasing the recovery threshold $R$ showed a slight downward trend in
approximation error for small $R$ as expected, but reaching an error floor
quickly. Further investigation is required in this regard, but one possible
explanation is that the learning saturates for the analyzed problems too soon
to show the expected trend.

50100150200250300350400$0$$0.01$$0.02$$0.03$$0.04$$0.05$Matrix dimension
$M$NRMSE$P_{1}$$P_{2}$ Figure 4:  Approximation error for problems $P_{1}$ and
$P_{4}$ for different matrix dimensions $M$.
50100150200250300350400$0$$0.5$$1$$1.5$$2$$2.5$$3$$3.5$$4$$4.5$$5$Matrix
dimension $M$Runtime in secondsAICCTensorflow (GPU)Numpy (CPU) Figure 5:
Comparison of runtime of AICC and standard implementations for computing
eigenvalues.
510152025303540$0$$0.02$$0.04$$0.06$$0.08$$0.1$$0.12$$0.14$$0.16$$0.18$$0.2$Number
of inputs $K$NRMSE$P_{1}$$P_{4}$ Figure 6: Varying number of inputs $K$ at
fixed recovery threshold $R=5$.

## References

  * [1] C. Li, H. Shen, and T. Huang, “Learning to diagnose stragglers in distributed computing,” in _2016 9th Workshop on Many-Task Computing on Clouds, Grids, and Supercomputers (MTAGS)_ , 2016, pp. 1–6.
  * [2] Q. Yu, M. Maddah-Ali, and S. Avestimehr, “Polynomial codes: an optimal design for high-dimensional coded matrix multiplication,” _Advances in Neural Information Processing Systems_ , vol. 30, 2017.
  * [3] S. Dutta, M. Fahim, F. Haddadpour, H. Jeong, V. Cadambe, and P. Grover, “On the optimal recovery threshold of coded matrix multiplication,” _IEEE Transactions on Information Theory_ , vol. 66, no. 1, pp. 278–301, 2019.
  * [4] Q. Yu, S. Li, N. Raviv, S. M. M. Kalan, M. Soltanolkotabi, and S. A. Avestimehr, “Lagrange coded computing: Optimal design for resiliency, security, and privacy,” in _The 22nd International Conference on Artificial Intelligence and Statistics_. PMLR, 2019, pp. 1215–1225.
  * [5] M. Soleymani, H. Mahdavifar, and A. S. Avestimehr, “Analog lagrange coded computing,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 2, no. 1, pp. 283–295, 2021.
  * [6] W.-T. Chang and R. Tandon, “Random sampling for distributed coded matrix multiplication,” in _ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2019, pp. 8187–8191.
  * [7] N. Charalambides, M. Pilanci, and A. O. Hero, “Approximate weighted cr coded matrix multiplication,” in _ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2021, pp. 5095–5099.
  * [8] T. Jahani-Nezhad and M. A. Maddah-Ali, “Codedsketch: A coding scheme for distributed computation of approximated matrix multiplication,” _IEEE Transactions on Information Theory_ , vol. 67, no. 6, pp. 4185–4196, 2021.
  * [9] V. Gupta, S. Wang, T. Courtade, and K. Ramchandran, “Oversketch: Approximate matrix multiplication for the cloud,” in _2018 IEEE International Conference on Big Data (Big Data)_. IEEE, 2018, pp. 298–304.
  * [10] S. Kiani and S. C. Draper, “Successive approximation coding for distributed matrix multiplication,” _arXiv preprint arXiv:2201.03486_ , 2022.
  * [11] H. Jeong, A. Devulapalli, V. R. Cadambe, and F. P. Calmon, “$\epsilon$-approximate coded matrix multiplication is nearly twice as efficient as exact multiplication,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 2, no. 3, pp. 845–854, 2021.
  * [12] L. Chen, H. Wang, Z. Charles, and D. Papailiopoulos, “Draco: Byzantine-resilient distributed training via redundant gradients,” in _International Conference on Machine Learning_. PMLR, 2018, pp. 903–912.
  * [13] M. M. Amiri and D. Gündüz, “Computation scheduling for distributed machine learning with straggling workers,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 24, pp. 6270–6284, 2019.
  * [14] J. Kosaian, K. Rashmi, and S. Venkataraman, “Learning a code: Machine learning for approximate non-linear coded computation,” _arXiv preprint arXiv:1806.01259_ , 2018.
  * [15] ——, “Parity models: erasure-coded resilience for prediction serving systems,” in _Proceedings of the 27th ACM Symposium on Operating Systems Principles_ , 2019, pp. 30–46.
  * [16] ——, “Learning-based coded computation,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 1, no. 1, pp. 227–236, 2020.
  * [17] A. H. Al-Mohy and N. J. Higham, “A new scaling and squaring algorithm for the matrix exponential,” _SIAM Journal on Matrix Analysis and Applications_ , vol. 31, no. 3, pp. 970–989, 2010.
  * [18] A. M. Ostrowski, _Sur l’approximation du determinant de Fredholm par les determinants des systèmes d’équations linéaires_. Almqvist & Wiksell, 1938.
  * [19] R. P. Brent, J. anne H. Osborn, and W. D. Smith, “Note on best possible bounds for determinants of matrices close to the identity matrix,” _Linear Algebra and its Applications_ , vol. 466, pp. 21–26, 2015.
  * [20] M. Abadi, A. Agarwal, P. Barham, E. Brevdo _et al._ , “TensorFlow: Large-scale machine learning on heterogeneous systems,” 2015, software available from tensorflow.org. [Online]. Available: https://www.tensorflow.org/