# Variants on Block Design Based Gradient Codes for Adversarial Stragglers

Animesh Sakorikar and Lele Wang  University of British Columbia
5500 Main Mall, Vancouver, BC V6T1Z4, Canada
Emails<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Gradient coding is a coding theoretic framework to provide robustness against
slow or unresponsive machines, known as stragglers, in distributed machine
learning applications. Recently, Kadhe et al. proposed a gradient code based
on a combinatorial design, called balanced incomplete block design (BIBD),
which is shown to outperform many existing gradient codes in worst-case
adversarial straggling scenarios [1]. However, parameters for which such BIBD
constructions exist are very limited [2]. In this paper, we aim to overcome
such limitations and construct gradient codes which exist for a wide range of
parameters while retaining the superior performance of BIBD gradient codes.
Two such constructions are proposed, one based on a probabilistic construction
that relax the stringent BIBD gradient code constraints, and the other based
on taking the Kronecker product of existing gradient codes. Theoretical error
bounds for worst-case adversarial straggling scenarios are derived.
Simulations show that the proposed constructions can outperform existing
gradient codes with similar redundancy per data piece.

##  I Introduction

Due to recent increases in size of available training data, a variety of
machine learning tasks are distributed across multiple computing nodes to
speed up the learning process. However, the theoretical speedup from
distributing computations and parallelization may not be achieved in practise
due to slow or unresponsive computing nodes, known as _stragglers_. Stragglers
can significantly impact the accuracy and efficiency of the computation [3, 4,
5]. Therefore, mitigating stragglers is one of the major challenges in the
design of distributed machine learning systems.

Basic approaches to mitigate stragglers include ignoring stragglers, detecting
and avoiding stragglers [5], or replicating tasks across workers [3], [6].
Recently, several coding theoretic based schemes were proposed to allow more
efficient use of redundant computations in mitigating stragglers [7, 8, 9,
10].

_Gradient coding_ is one of the coding theoretic schemes, proposed by [4], to
mitigate stragglers. In a gradient coding scheme, a central processor
partitions the uncoded training data into pieces and distributes them among
multiple computing nodes, called workers. Each worker computes a linear
combination of the gradients on its assigned training data pieces. The central
processor aggregates the returned linear combinations to obtain the gradient
sum. The goal is to design the set of linear combinations such that the
gradient sum can be recovered _exactly_ when any $s$ set of linear
combinations are lost. Several gradient codes under the _exact recovery_
criterion are proposed in [4, 11, 12].

While exact recovery is a natural criterion that extends from traditional
coding theory, it has some limitations for distributed learning applications.
Firstly, the computational loads for exact recovery are proportional to the
number of stragglers [4], and therefore an accurate estimate of the number of
stragglers is needed to minimize unnecessary computation. Moreover, in many
learning algorithms, such as stochastic gradient decent, an approximation of
the actual gradient sum is sufficient [13]. For these reasons, it is common to
consider gradient codes that _approximately_ recover the gradient sum such
that the squared $2$-norm of the difference between the actual gradient sum
and its approximation is minimized, referred to as _squared error_ [13]. A
variety of approximate gradient code constructions are proposed in [14, 13,
15, 1, 16, 17, 18, 7, 19].

In approximate gradient coding, common assumptions on the straggling scenarios
include (1) random straggling, where stragglers are assumed to follow some
stochastic assumptions, and (2) worst-case straggling with no stochastic
assumptions, where any $s$ subset of workers can be straggled. In this paper,
we consider the squared error in the worst-case straggling scenario, referred
to as _worst-case squared error_ , because it may be difficult to estimate the
statistical model of stragglers in real time for some applications, such as
massive-scale elastic and serverless systems [1].

Under this performance criterion, we discuss two existing gradient codes:
fractional repetition codes (FRCs) [4] and balanced incomplete block design
(BIBD) gradient codes [1]. An FRC is constructed by partitioning workers and
gradients into equal subsets, such that each worker in a partition is assigned
every gradient in the same gradient partition. FRCs are easy to construct and
exist for a wide range of distributed system parameters, but perform poorly in
worst-case straggling scenarios [14]. BIBD gradient codes are constructed from
combinatorial block designs, and are robust in worst-case straggling
scenarios. However, the set of system parameters for which a BIBD gradient
code is known to exist is very limited [2].

This motivates us to ask the following question: _Is it possible to construct
gradient codes that exist for a wide range of system parameters while
retaining the superior worst-case performance produced by BIBD gradient
codes?_ We answer this affirmatively by providing two new constructions. In
the first construction (Section III), we propose a probabilistic gradient code
that relaxes the stringent BIBD gradient code constraints. Unlike the BIBD
gradient codes, which require constant computation load on each worker and
constant number of shared gradients between any pair of workers, in our
construction, we only require these constraints to be satisfied on average. We
show that the expected worst-case squared error of our construction is lower
than that of the BIBD gradient code with the same design parameters. In the
second construction (Section IV), we propose new gradient codes by taking the
Kronecker product of existing gradient codes. Upper bounds on the normalized
worst-case squared error are derived for three types of constructions: the
Kronecker products of (1) an FRC with an FRC, (2) an FRC with a BIBD, and (3)
a BIBD with a BIBD. Simulations show that the Kronecker product of two BIBDs
can have superior worst-case performance than other constructions with a
similar redundancy per data piece, including a single BIBD, a single FRC, and
the Kronecker product of an FRC and a BIBD.

Figure 1: Comparison of Kronecker Product codes with FRCs and BIBDs.

##  II Problem Formulation

We use bold capital script $\bm{G}$ for random matrices, capital script $G$
for deterministic matrices, and bold script $\bm{f}$ for vectors. Let $I_{n}$
be the $n\times n$ identity matrix and $J_{k\times n}$ be the $k\times n$ all-
one matrix. Let $\bm{1}_{k}$ denote the $k\times 1$ all-one column vector and
$\bm{0}_{k}$ denote the $k\times 1$ all-zero column vector.

###  II-A Distributed Learning

In many machine learning algorithms, the goal is to find a model
$\bm{\theta}_{\mathrm{min}}$ that minimizes some loss function $L$ over a
training data set. Specifically, given training data
$\mathcal{D}=\\{(x_{i},y_{i})\\}_{i=1}^{k}$, the aim is to compute

$\bm{\theta}_{\mathrm{min}}=\arg\min_{\bm{\theta}\in\mathbbm{R}^{p}}\frac{1}{k}\sum_{i=1}^{k}L(\bm{\theta},x_{i},y_{i}).$
(1)

Gradient descent (GD) is an iterative algorithm that estimates the optimal
model $\bm{\theta}_{\mathrm{min}}$. Starting with some initial guess
$\bm{\theta}^{(0)}$, the model $\bm{\theta}^{(t)}$ at iteration $t$ is updated
as

$\bm{\theta}^{(t+1)}=\bm{\theta}^{(t)}+\frac{\alpha}{k}\sum_{i=1}^{k}\nabla
L(\bm{\theta}^{(t)},x_{i},y_{i}),$ (2)

where $\nabla L(\bm{\theta}^{(t)},x_{i},y_{i})$ is the gradient of loss
function $L$, and $\alpha$ is the learning rate.

When the training data size $k$ is large, the gradient sum computation in (2)
is a computational bottleneck. To avoid this computational bottleneck, we can
distribute the gradient computations over multiple workers, known as
distributed learning, or distributed gradient descent. In each iteration of
distributed GD, a central processor transmits the current model to each worker
in the distributed system. Each worker computes some subset of the $k$
gradients, and return the sum to the central processor. The central processor
computes the gradient sum from the returned results, and updates the model as
done in (2). Henceforth we will focus on a single iteration of distributed GD.

###  II-B Gradient Coding

Consider a distributed learning (or distributed GD) setting with $n$ workers
$\mathcal{W}$ and $k$ data $\mathcal{D}=\\{(x_{i},y_{i})\\}_{i=1}^{k}$. The
goal of gradient coding is to introduce redundancy in gradient computations so
that the distributed system is robust against stragglers [4].

A gradient code (GC) can be characterized by a $k\times n$ binary encoding
matrix $G$. Row $i\in[k]:=\\{1,2,\dotsc,k\\}$ of $G$ corresponds to data piece
$d_{i}$, and column $j\in[n]$ corresponds to worker $j$, where $G_{ij}=1$ if
worker $j$ computes the gradient of $d_{i}$, and $G_{ij}=0$ otherwise. The
worker load is the number of gradient computations assigned to a worker, and
data redundancy is the number of workers computing the gradient of a data
piece. When each worker has the same worker load $l$, and each data piece has
redundancy $r$, $G$ is called an $(n,k,l,r)$-GC.

The goal is to compute the gradient sum in (2). Since we consider only one
iteration of distributed GD, we omit the dependence on time $t$. Then the goal
is to compute

$\sum_{i=1}^{k}\nabla L(x_{i},y_{i})=\bm{f}\bm{1}_{k},$

where $\bm{f}=(\nabla L(x_{1},y_{1}),\dotsc,\nabla L(x_{k},y_{k}))$. Let $s$
be the number of straggling workers, $\mathcal{U}\subset\mathcal{W}$ be the
set of non-straggling workers, $G_{\mathcal{U}}$ be the sub-matrix of $G$ with
columns indexed by $\mathcal{U}$. Then, the central processor receives
$\bm{f}G_{\mathcal{U}}$ from the workers in $\mathcal{U}$. The goal is to
recover $\bm{f}\bm{1}_{k}$ from $\bm{f}G_{\mathcal{U}}$ for any $\mathcal{U}$
such that $|\mathcal{U}|=n-s$. Notice that $\bm{f}G_{\mathcal{U}}$ is a
$1\times(n-s)$ vector. Each entry of $\bm{f}G_{\mathcal{U}}$ is a result
(partial gradient sum) returned by a non-straggling worker in $\mathcal{U}$.
To approximate the gradient sum, we take a linear combination of returned
results

$\bm{f}G_{\mathcal{U}}\bm{v},$

where $\bm{v}\in\mathbbm{R}^{n-s}$ is called the decoding vector. Then the
difference between the gradient sum approximation
$\bm{f}G_{\mathcal{U}}\bm{v}$ and the target computation $\bm{f}\bm{1}_{k}$ is

$\bm{f}G_{\mathcal{U}}\bm{v}-\bm{f}\bm{1}_{k}=\bm{f}(G_{\mathcal{U}}\bm{v}-\bm{1}_{k}).$
(3)

Note that (3) depends on $\bm{f}$, which we do not know a priori. Thus we
focus on minimizing the squared 2-norm of
$(G_{\mathcal{U}}\bm{v}~{}-~{}\bm{1}_{k})$. We can now define the optimal
decoding vector as

$\bm{v}_{\mathrm{opt}}(G,\mathcal{U}):=\arg\min_{\bm{v}\in\mathbbm{R}^{n-s}}\|G_{\mathcal{U}}\bm{v}-\bm{1}_{k}\|_{2}^{2}.$

Then the normalized worst-case squared error when $s$ workers are straggled is
defined as

$\operatorname*{err}(G,s)=\frac{1}{k}\max_{\begin{subarray}{c}\mathcal{U}\subset\mathcal{W}\\\
|\mathcal{U}|=n-s\end{subarray}}\|G_{\mathcal{U}}\bm{v}_{\mathrm{opt}}(G,\mathcal{U})-\bm{1}_{k}\|_{2}^{2}.$
(4)

This normalization allows us to compare between gradient codes with different
number of gradients to compute. Note that to make an objective comparison, one
should choose gradient codes with the same fractional redundancy $r/n$, since
each data-piece is redundantly assigned to the same fraction of total workers
in each gradient code being compared. We then compare the normalized worst-
case squared errors as a function of the fraction of straggling workers.

###  II-C Existing constructions

In [4], the authors show that an $(n,k,l,r)$-GC can exactly recover all $k$
gradients for any set of $s$ stragglers if

$l\geq\frac{k(s+1)}{n}.$ (5)

In the following, we focus on two constructions relating to the technical
sections of our paper. In [4], a gradient code construction called FRC is
provided. An FRC with $n$ workers, $k$ data pieces, worker load $l$, and
redundancy $r$ is called an $(n,k,l,r)$-FRC. The encoding matrix
$G^{\mathrm{F}}$ is given by

$G^{\mathrm{F}}=\begin{bmatrix}J_{l\times r}&0_{l\times r}&\dotsc&0_{l\times
r}\\\ 0_{l\times r}&J_{l\times r}&\dotsc&0_{l\times r}\\\
\vdots&\vdots&\ddots&\vdots\\\ 0_{l\times r}&0_{l\times r}&\dotsc&J_{l\times
r}\end{bmatrix},$

where $0_{l\times r}$ is the $l\times r$ all-zero matrix. An $(n,k,l,r)$-FRC
can exactly recover all gradients if condition (5) is satisfied. FRCs can also
be used to approximately recover the gradient sum. The normalized worst-case
squared error of an $(n,k,l,r)$-FRC $G^{\mathrm{F}}$ with $s$ stragglers is
[14, Section 4.1]

$\operatorname*{err}(G^{\mathrm{F}},s)=\frac{l}{k}\left\lfloor\frac{s}{r}\right\rfloor.$
(6)

For completeness, we include a proof of (6) error in Appendix A.

Gradient codes can also be constructed from combinatorial balanced incomplete
block designs (BIBD) as proposed in [1]. A combinatorial design is a pair
$(\mathcal{X},\mathcal{A})$, where
$\mathcal{X}=\\{x_{1},x_{2},\dotsc,x_{k}\\}$ is a set of elements called
points, and $\mathcal{A}=\\{A_{1},A_{2},\dotsc,A_{n}\\}$ is a collection of
subsets of $\mathcal{X}$, called blocks. A design $(\mathcal{X},\mathcal{A})$
is called a $(n,k,l,r,\lambda)$-BIBD if there are $k$ points in $\mathcal{X}$,
$n$ blocks in $\mathcal{A}$, each of size $l$, where every point is contained
in $r$ blocks, and any pair of distinct points is contained in exactly
$\lambda$ blocks. We can represent a BIBD by an $k\times n$ incidence matrix
$M$, where $M_{i,j}=1$ iff $x_{i}\in A_{j}$ and $0$ otherwise. A BIBD is
called _symmetric_ if its incidence matrix satisfies $M=M^{T}$. For any
$(n,k,l,r,\lambda)$-BIBD with incidence matrix $M$, its dual-design is defined
as the design with incidence matrix $M^{T}$.

A key observation in [1] is that one can design a gradient code from a BIBD
(with incidence matrix $M$) by setting the encoding matrix of the gradient
code $G^{\mathrm{B}}=M$. Clearly the gradient code $G^{\mathrm{B}}$ is an
$(n,k,l,r)$ gradient code. Moreover, if $G^{\mathrm{B}}$ is designed from a
symmetric or dual BIBD, then every pair of distinct workers of
$G^{\mathrm{B}}$ share exactly $\lambda$ gradients to compute. This introduces
redundancy and provides robustness against stragglers. Throughout this paper,
we only consider BIBD gradient codes constructed from symmetric BIBDs and
dual-designs of BIBDs. We call these codes $(n,k,l,r,\lambda)$-BIBDs, or
$(n,k,l,\lambda)$-BIBDs when the parameter $r$ is not relevant. For
convenience, the number of shared gradient computations between any pair of
workers $\lambda$ is known as the number of intersections.

BIBDs provide superior performance against worst-case stragglers: the optimal
decoding vector and normalized worst-case squared error of a BIBD depends only
on the number of stragglers, and not on the specific straggling scenario.
Specifically, an $(n,k,l,\lambda)$-BIBD $G^{\mathrm{B}}$ with $s$ stragglers
has a constant optimal decoding vector, and the normalized worst-case squared
error of $G^{\mathrm{B}}$ with $s$ stragglers is given by [1, Theorem 1]

$\operatorname*{err}(G^{\mathrm{B}},s)=1-\frac{l^{2}(n-s)}{kl+k\lambda(n-s-1)}.$
(7)

For the same set of parameters $(n,k,l,r)$, an $(n,k,l,r)$-BIBD promises
better worst-case straggling performance than an $(n,k,l,r)$-FRC when it
exists. However, the set of parameters $(n,k,l,\lambda)$ for which a BIBD is
known to exist is very limited [2]. This motivates us to propose a new
gradient code that exists for a wide range of parameters, while retaining the
superior performance of BIBD.

##  III Probabilistic BIBD Gradient Codes

In this section, we propose a new gradient code, referred to as _probabilistic
BIBD_ gradient codes. We generate the random encoding matrix
$\bm{G}^{\mathrm{PB}}$ such that _on average_ the desired BIBD properties
(such as worker load $l$ and $\lambda$ shared computations between any two
workers) are satisfied. The construction of probabilistic BIBD gradient codes
is provided in Section III-A, and we show that probabilistic BIBD gradient
codes have smaller average error than that of combinatorial BIBDs in Section
III-B.

###  III-A Existence and Construction

We define a joint distribution $p(x^{n})$ on the $n$ entries of the first row
in the encoding matrix $\bm{G}^{\mathrm{PB}}$ and generate all $k$ rows in the
encoding matrix i.i.d. according to $p(x^{n})$. We discuss the constraints
$p(x^{n})$ should satisfy to ensure the desired BIBD properties.

  1. 1.

In order for each column $j\in[n]$ of $\bm{G}^{\mathrm{PB}}$ to have $l$ ones
on average, the marginal distribution on the entry in column $j$, denoted by
$X_{j}$, must satisfy

$\mathbbm{P}(X_{j}=1)=\sum_{\begin{subarray}{c}x^{n}\in\\{0,1\\}^{n}\\\
x_{j}=1\end{subarray}}p(x^{n})=\frac{l}{k}.$ (8)

  2. 2.

In order for each pair of columns $1\leq i<j\leq n$ to have $\lambda$
intersections on average, the distribution on the entries in columns $i$ and
$j$ must satisfy

$\mathbbm{P}(X_{i}=X_{j}=1)=\sum_{\begin{subarray}{c}x^{n}\in\\{0,1\\}^{n}\\\
x_{i}=x_{j}=1\end{subarray}}p(x^{n})=\frac{\lambda}{k}.$ (9)

  3. 3.

Since $p(x^{n})$ is a probability distribution, it must satisfy

$\displaystyle\sum_{x^{n}\in\\{0,1\\}^{n}}p(x^{n})$ $\displaystyle=1,$ (10)
$\displaystyle p(x^{n})$ $\displaystyle\geq 0\text{ for all
}x^{n}\in\\{0,1\\}^{n}.$ (11)

Now the problem of finding $p(x^{n})$ reduces to finding a non-negative
solution to the linear system $A\bm{p}=\bm{b}$. We arrange the linear system
so that equation (10) corresponds to first row of $A$, equations (8)
correspond to the next $n$ rows, followed by $\binom{n}{2}$ rows from
equations (9). Observe that $A$ is an $\left(1+n+\binom{n}{2}\right)\times
2^{n}$ binary matrix, whose entries are the coefficients of $p(x^{n})$ in
equations (8), (9), and (10). The entry in row $i\in[2^{n}]$ of $\bm{p}$ is
$p(x^{n})$, where $x^{n}$ is the binary expansion of $i-1$. Lastly, $\bm{b}$
is a column vector with $\left(1+n+\binom{n}{2}\right)$ entries, where the
first entry is $1$, the next $n$ entries are $l/k$, and the remaining entries
are $\lambda/k$. The system for size $n=3$ is shown below:

$\displaystyle\begin{bmatrix}1&1&1&1&1&1&1&1\\\ 0&1&0&1&0&1&0&1\\\
0&0&1&1&0&0&1&1\\\ 0&0&0&0&1&1&1&1\\\ 0&0&0&1&0&0&0&1\\\ 0&0&0&0&0&1&0&1\\\
0&0&0&0&0&0&1&1\\\ \end{bmatrix}\begin{bmatrix}p(000)\\\ p(001)\\\ p(010)\\\
p(011)\\\ p(100)\\\ p(101)\\\ p(110)\\\ p(111)\\\
\end{bmatrix}=\begin{bmatrix}1\\\ l/k\\\ l/k\\\ l/k\\\ \lambda/k\\\
\lambda/k\\\ \lambda/k\\\ \end{bmatrix}.$ (12)

The main theorem of this section provides the parameters $n,k,l$ and $\lambda$
for which a non-negative solution $p(x^{n})$ to the system $A\bm{p}=\bm{b}$
exists.

######  Theorem 1.

For all $n\geq l\geq\lambda$, a solution exists for the linear system
$A\bm{p}=\bm{b}$ defined by equations (8), (9), and (10). Additionally, if
$l\geq\lambda$, $2\lambda\geq l$, and $k\geq 3l-2\lambda$, a non-negative
solution exists for $A\bm{p}=\bm{b}$.

A key observation in establishing Theorem 1 is that matrix $A$ turns out to be
the same as the generator matrix of a Reed-Muller (RM) code of order 2 and
block length $2^{n}$, which are defined as follows [20, p. 373].

######  Definition 1.

The binary Reed-Muller code of order $2$ and block length $2^{n}$ is the set
of all vectors $f(v_{1},\dotsc,v_{n})$, where $f$ is a boolean function which
is a polynomial of degree at most $2$, and $(v_{1},\dotsc,v_{n})$ is any
length $n$ binary vector.

One can verify that the matrix in equation (12) constitutes a basis for the
Reed-Muller code of order $2$ and length $2^{3}$, and therefore is a generator
matrix for this code. In general, this equivalence is true for any $n$.

######  Lemma 1.

The matrix $A$ defined by constraints (8), (9), and (10) is a generator matrix
of the Reed-Muller code of order $2$ and length $n$.

###### Proof:

A solution to the system of equations $A\bm{p}=\bm{b}$ exists if and only if
the rank of the augmented coefficient matrix $\hat{A}=[A|\bm{b}]$ is equal to
the rank of $A$. It is known that generator matrices for Reed-Muller codes
have full rank, thus from Lemma 1 we have
$\operatorname{rank}(A)=1+n+\binom{n}{2}$, and
$\operatorname{rank}(\hat{A})\geq\operatorname{rank}(A)=1+n+\binom{n}{2}$.
Since $\hat{A}$ is a $\left(1+n+\binom{n}{2}\right)\times\left(2^{n}+1\right)$
matrix, $\operatorname{rank}(\hat{A})\leq 1+n+\binom{n}{2}$. Thus
$\operatorname{rank}(\hat{A})=\operatorname{rank}(A)$, and a solution to the
system exists for all $n\geq l\geq\lambda$.

To show a non-negative solution exists, consider a solution of the form
$\bm{p}=(\alpha,\beta,\dotsc,\beta,\gamma)$, where $p(0^{n})=\alpha$,
$p(1^{n})=\gamma$, and $p(x^{n})=\beta$ for all
$x^{n}\not\in\\{0^{n},1^{n}\\}$. Then equations (10), (8) and (9) become:

$\displaystyle\alpha+\beta(2^{n}-2)+\gamma$ $\displaystyle=1,$ (13)
$\displaystyle\beta(2^{n-1}-1)+\gamma$ $\displaystyle=\frac{l}{k},$ (14)
$\displaystyle\beta(2^{n-2}-1)+\gamma$ $\displaystyle=\frac{\lambda}{k}.$ (15)

Solving equations (13), (14), and (15) for $\alpha,\beta$ and $\gamma$, we get

$\displaystyle\beta$ $\displaystyle=\frac{l-\lambda}{k(2^{n-2})},$
$\displaystyle\gamma$
$\displaystyle=\frac{1}{k}\left[2\lambda-l+\frac{l-\lambda}{2^{n-2}}\right],$
$\displaystyle\alpha$
$\displaystyle=1+\frac{2\lambda-3l}{k}+\frac{l-\lambda}{k(2^{n-2})}.$

For a positive solution $\bm{p}$ to the system, we require $\alpha,\beta$ and
$\gamma$ to be non-negative. One can check they are indeed non-negative when
$l\geq\lambda$, $2\lambda\geq l$, and $k\geq 3l-2\lambda$. ∎

Theorem 1 shows that probabilistic BIBD gradient codes exist for a wider range
of system parameters than that of BIBD gradient codes.

###  III-B Error of Probabilistic Gradient Codes

In this section, we analyze the normalized worst-case squared error
performance of probabilistic BIBD gradient codes. Let $n,k,l$ and $\lambda$
satisfy the conditions in Theorem 1, and $\bm{G}^{\mathrm{PB}}$ be an $n$
worker and $k$ gradients to compute probabilistic BIBD gradient code, with
worker load $l$ and intersections $\lambda$ in expectation. Then
$\bm{G}^{\mathrm{PB}}$ is called an $(n,k,l,\lambda)$ probabilistic BIBD .
Since $\bm{G}^{\mathrm{PB}}$ is a randomly generated matrix, the performance
depends on the specific realization $\bm{G}^{\mathrm{PB}}$. Thus we redefine
the normalized worst-case squared error in (4) for an $(n,k,l,\lambda)$
probabilistic BIBD with $s$ stragglers as

$\operatorname*{err}(\bm{G}^{\mathrm{PB}},s)=\frac{1}{k}\max_{\begin{subarray}{c}\mathcal{U}\subset\mathcal{W}\\\
|\mathcal{U}|=n-s\end{subarray}}\mathbbm{E}\left[\|\bm{G}^{\mathrm{PB}}_{\mathcal{U}}\bm{v}_{\mathrm{opt}}(\bm{G}^{\mathrm{PB}},\mathcal{U})-\bm{1}_{k}\|_{2}^{2}\right].$

The following theorem characterizes the error of an $(n,k,l,\lambda)$
probabilistic BIBD with $s$ stragglers.

######  Theorem 2.

Let $n\geq l\geq\lambda$, $2\lambda\geq l$, and $k\geq 3l-2\lambda$. For a
probabilistic $(n,k,l,\lambda)$-BIBD gradient code $\bm{G}^{\mathrm{PB}}$
generated from the probability distribution specified in Section III-A, we
have

$\operatorname*{err}(\bm{G}^{\mathrm{PB}},s)\leq
1-\frac{l^{2}(n-s)}{kl+k\lambda(n-s-1)},$

where $s$ is the number of stragglers.

Theorem 2 shows that probabilistic BIBD gradient codes have lower normalized
worst-case squared errors than BIBD gradient codes on average. Thus, we can
construct probabilistic BIBD gradient codes to retain the superior performance
of BIBD gradient codes even if a BIBD gradient code does not exist for the
desired system parameters.

To prove Theorem 2, we first state the following result from [1], which gives
the optimal decoding vector and normalized worst-case squared error of a BIBD
with $s$ stragglers.

######  Lemma 2.

[Theorem 1 in [1]] For a non-random $(n,k,l,\lambda)$-BIBD gradient code
$G^{\mathrm{B}}$ with $s$ stragglers, the optimal decoding vector is

$\bm{v}_{\mathrm{opt}}(G^{\mathrm{B}},s)=\left(\frac{l}{l+\lambda(n-s-1)}\right)\bm{1}_{n-s},$

and the worst-case squared error is

$\max_{\begin{subarray}{c}\mathcal{U}\subset[n]\\\
|\mathcal{U}|=n-s\end{subarray}}\|G^{\mathrm{B}}_{\mathcal{U}}\bm{v}_{\mathrm{opt}}(G^{\mathrm{B}},\mathcal{U})-\bm{1}_{k}\|_{2}^{2}=k-\frac{l^{2}(n-s)}{l+\lambda(n-s-1)}.$
(16)

Then dividing both sides of the worst-case squared error in equation (16) by
$k$, we obtain the BIBD error expression in (7).

To prove Theorem 2, we bound the normalized worst-case squared error of a
$(n,k,l,\lambda)$ probabilistic BIBD gradient code by decoding with the
optimal decoding vector of an $(n,k,l,\lambda)$-BIBD provided in Lemma 2.

###### Proof:

Since $\bm{G}^{\mathrm{PB}}$ is a random matrix with probability distribution
specified in Section III-A, the expected number of ones in each column of is
$l$, and the expected number of intersections between any two columns is
$\lambda$. Then for any set of $n-s$ non-straggling worker indices
$\mathcal{U}$

$\displaystyle\mathbbm{E}[(\bm{G}^{\mathrm{PB}}_{\mathcal{U}})^{T}\bm{1}_{k}]$
$\displaystyle=l\bm{1}_{n-s},$ (17)
$\displaystyle\mathbbm{E}[(\bm{G}^{\mathrm{PB}}_{\mathcal{U}})^{T}(\bm{G}^{\mathrm{PB}}_{\mathcal{U}})]$
$\displaystyle=(l-\lambda)I_{n-s}+\lambda J_{(n-s)\times(n-s)}.$ (18)

Define the constant decoding vector

$\tilde{\bm{v}}=\left(\frac{l}{l+\lambda(n-s-1)}\right)\bm{1}_{n-s}.$

Then

$\displaystyle\phantom{=}\operatorname*{err}(\bm{G}^{\mathrm{PB}},s)$
$\displaystyle=\frac{1}{k}\max_{\begin{subarray}{c}\mathcal{U}\subset[n]\\\
|\mathcal{U}|=n-s\end{subarray}}\mathbbm{E}[\|\bm{G}^{\mathrm{PB}}_{\mathcal{U}}\bm{v}_{\mathrm{opt}}(\bm{G}^{\mathrm{PB}},\mathcal{U})-\bm{1}_{k}\|_{2}^{2}]$
$\displaystyle=\frac{1}{k}\max_{\begin{subarray}{c}\mathcal{U}\subset[n]\\\
|\mathcal{U}|=n-s\end{subarray}}\left[\sum_{g}\mathbbm{P}(\bm{G}^{\mathrm{PB}}=g)\|g_{\mathcal{U}}\bm{v}_{\mathrm{opt}}(g,\mathcal{U})-\bm{1}_{k}\|_{2}^{2}\right]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\frac{1}{k}\max_{\begin{subarray}{c}\mathcal{U}\subset[n]\\\
|\mathcal{U}|=n-s\end{subarray}}\left[\sum_{g}\mathbbm{P}(\bm{G}^{\mathrm{PB}}=g)\|g_{\mathcal{U}}\tilde{\bm{v}}-\bm{1}_{k}\|_{2}^{2}\right]$
$\displaystyle=\frac{1}{k}\max_{\begin{subarray}{c}\mathcal{U}\subset[n]\\\
|\mathcal{U}|=n-s\end{subarray}}\mathbbm{E}\left[\|\bm{G}^{\mathrm{PB}}_{\mathcal{U}}\tilde{\bm{v}}-\bm{1}_{k}\|_{2}^{2}\right]$
$\displaystyle=\frac{1}{k}\max_{\begin{subarray}{c}\mathcal{U}\subset[n]\\\
|\mathcal{U}|=n-s\end{subarray}}\mathbbm{E}\left[(\bm{G}^{\mathrm{PB}}_{\mathcal{U}}\tilde{\bm{v}}-\bm{1}_{k})^{T}(\bm{G}^{\mathrm{PB}}_{\mathcal{U}}\tilde{\bm{v}}-\bm{1}_{k})\right]$
$\displaystyle=\frac{1}{k}\max_{\begin{subarray}{c}\mathcal{U}\subset[n]\\\
|\mathcal{U}|=n-s\end{subarray}}\mathbbm{E}\Big{[}\bm{1}_{k}^{T}\bm{1}_{k}-2\tilde{\bm{v}}^{T}(\bm{G}^{\mathrm{PB}}_{\mathcal{U}})^{T}\bm{1}_{k}$
$\displaystyle\hskip
130.0002pt+\tilde{\bm{v}}^{T}(\bm{G}^{\mathrm{PB}}_{\mathcal{U}})^{T}G^{\mathrm{PB}}_{\mathcal{U}}\tilde{\bm{v}}^{T}\Big{]}$
$\displaystyle=\frac{1}{k}\max_{\begin{subarray}{c}\mathcal{U}\subset[n]\\\
|\mathcal{U}|=n-s\end{subarray}}\bigg{(}\mathbbm{E}\left[\bm{1}_{k}^{T}\bm{1}_{k}\right]-2\tilde{\bm{v}}^{T}\mathbbm{E}\left[(\bm{G}^{\mathrm{PB}}_{\mathcal{U}})^{T}\bm{1}_{k}\right]$
$\displaystyle\hskip
130.0002pt+\tilde{\bm{v}}^{T}\mathbbm{E}\left[(\bm{G}^{\mathrm{PB}}_{\mathcal{U}})^{T}\bm{G}^{\mathrm{PB}}_{\mathcal{U}}\right]\tilde{\bm{v}}\bigg{)}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\frac{1}{k}\max_{\begin{subarray}{c}\mathcal{U}\subset[n]\\\
|\mathcal{U}|=n-s\end{subarray}}\left(k-2l\tilde{\bm{v}}^{T}\bm{1}_{n-s}+\tilde{\bm{v}}^{T}((l-\lambda)I_{n-s}+\lambda
J_{n-s})\tilde{\bm{v}}\right)$
$\displaystyle=1-\frac{l^{2}(n-s)}{kl+k\lambda(n-s-1)},$

where $(a)$ follows because $\tilde{\bm{v}}$ is a constant decoding vector
that may not be optimal, and $(b)$ follows from equations (17) and (18). ∎

##  IV Kronecker Product Gradient Codes

In the previous section, we constructed probabilistic gradient codes that
satisfy the desired BIBD properties on average. We now switch to a different
construction, referred to as _product gradient codes_ , which are constructed
by taking the Kronecker product of matrices of existing gradient codes. We
first define the Kronecker product.

######  Definition 2.

If $A$ is a $k_{1}\times n_{1}$ matrix, and $B$ is a $k_{2}\times n_{2}$
matrix, then the Kronecker product $A\otimes B$ is a $k_{1}k_{2}\times
n_{1}n_{2}$ matrix given by

$A\otimes B:=\begin{bmatrix}A_{1,1}B&\cdots&A_{1,n_{1}}B\\\
\vdots&\ddots&\cdots\\\ A_{k_{1},1}B&\cdots&A_{k_{1},n_{1}}B\\\
\end{bmatrix}.$

We establish the normalized worst-case squared error performance for Kronecker
products of two FRCs, an FRC with a BIBD, and two BIBDs in Theorems 3, 4, and
5 respectively. For convenience, we extend the domain of FRC error expression
in (6) to the set of real numbers. For an $(n,k,l,r)$-FRC $G^{\mathrm{F}}$ and
any real number $0\leq s\leq n$, let

$\operatorname*{err}(G^{\mathrm{F}},s)=\frac{l}{k}\left\lfloor\frac{s}{r}\right\rfloor.$

######  Theorem 3.

Let $G^{\mathrm{F}_{i}}$ be an $(n_{i},k_{i},l_{i},r_{i})$-FRC for $i=1,2$.
Then for any $s\in[n_{1}n_{2}]$,

$\displaystyle\operatorname*{err}(G^{\mathrm{F}_{1}}\otimes
G^{\mathrm{F}_{2}},s)$
$\displaystyle=\frac{l_{1}}{k_{1}}\operatorname*{err}\left(G^{\mathrm{F}_{2}},\frac{s}{r_{1}}\right)$
$\displaystyle=\frac{l_{2}}{k_{2}}\operatorname*{err}\left(G^{\mathrm{F}_{1}},\frac{s}{r_{2}}\right).$

######  Theorem 4.

Let $G^{\mathrm{F}}$ be an $(n_{1},k_{1},l_{1},r_{1})$-FRC and
$G^{\mathrm{B}}$ be an $(n_{2},k_{2},l_{2},r_{2},\lambda_{2})$-BIBD GC. Then
the error of $G^{\mathrm{F}}\otimes G^{\mathrm{B}}$ with $s$ stragglers is
bounded as

$\operatorname*{err}(G^{\mathrm{F}}\otimes
G^{\mathrm{B}},s)\leq\operatorname*{err}\left(G^{\mathrm{F}},\frac{s}{n_{2}}\right)+\frac{l_{1}}{k_{1}}\operatorname*{err}\left(G^{\mathrm{B}},b\right),$

where
$b=\left\lfloor\tfrac{1}{r_{1}}\left(s-\left\lfloor\tfrac{s}{r_{1}n_{2}}\right\rfloor
r_{1}n_{2}\right)\right\rfloor$. In addition, for any
$G^{\mathrm{F}},G^{\mathrm{B}}$, and any $s$,

$\operatorname*{err}(G^{\mathrm{F}}\otimes
G^{\mathrm{B}},s)=\operatorname*{err}(G^{\mathrm{B}}\otimes
G^{\mathrm{F}},s).$

######  Theorem 5.

Let $G^{\mathrm{B_{i}}}$ be an $(n_{i},k_{i},l_{i},r_{i},\lambda_{i})$-BIBD
for $i=1,2$. The error of $G^{\mathrm{B_{1}}}\otimes G^{\mathrm{B_{2}}}$ with
any $s\in[n_{1}n_{2}]$ stragglers is bounded as

$\operatorname*{err}(G^{\mathrm{B_{1}}}\otimes G^{\mathrm{B_{2}}},s)\leq
1-\frac{(l_{1}l_{2})^{2}(n_{1}n_{2}-s)}{k_{1}k_{2}\left(d+\lambda_{1}\lambda_{2}(n_{1}n_{2}-s)\right)},$

where

$d=(l_{1}-\lambda_{1})(l_{2}-\lambda_{2})+n_{2}(l_{1}\lambda_{2}-\lambda_{1}\lambda_{2})+n_{1}(\lambda_{1}l_{2}-\lambda_{1}\lambda_{2}).$

We first find the error of Kronecker product of FRCs.

###### Proof:

Notice that $G^{\mathrm{F_{1}}}\otimes G^{\mathrm{F_{2}}}$ is an
$(n_{1}n_{2},k_{1}k_{2},l_{1}l_{2},r_{1}r_{2})$-FRC. Then the result follows
from the error of an FRC. ∎

We now establish Theorem 4. In order to prove Theorem 4, we need Lemmas 3–6.
In Lemmas 3 and 4, an $(n,k,l,r)$ gradient code with exactly $\lambda$
intersections between any pair of workers is considered. We define it as an
$(n,k,l,r,\lambda)$-GC. Notice that an $(n,k,l,r,\lambda)$-GC is not
necessarily a BIBD gradient code, since it may not satisfy the BIBD gradient
code constraint

$r(l-1)=\lambda(k-1).$

However, such a code has the same optimal decoding vector and error expression
as a BIBD with the same parameters $(n,k,l,\lambda)$.

######  Lemma 3.

Let $G$ be an $(n,k,l,r,\lambda)$-GC, where $l>\lambda$. Then for any set of
$s\in[n]$ stragglers $\mathcal{U}$, the optimal decoding vector is given by

$v_{\mathrm{opt}}(G,\mathcal{U})=\left(\frac{l}{l+\lambda(n-s-1)}\right)\bm{1}_{n-s},$

and the squared error is

$\left\|G_{\mathcal{U}}v_{\mathrm{opt}}(G,\mathcal{U})-1_{k}\right\|_{2}^{2}=k-\frac{l^{2}(n-s)}{l+\lambda(n-s-1)}.$

The proof follows essentially from the proof of Theorem 1 in [1], and is
included in Appendix B for completeness.

######  Lemma 4.

Let $G^{\mathrm{B}}$ be an $(n_{1},k_{1},l_{1},\lambda_{1})$-BIBD gradient
code $G^{\mathrm{B}}$, and $G=G^{\mathrm{B}}\otimes\bm{1}_{k_{2}}$ for some
positive integer $k_{2}$. Then for any integer $0\leq s\leq n_{1}$, for any
$\mathcal{U}$ such that $|\mathcal{U}|=n-s$,

$\left\|(G^{\mathrm{B}}\otimes\bm{1}_{k_{2}})_{\mathcal{U}}\bm{v}_{\mathrm{opt}}(G,\mathcal{U})-\bm{1}_{k_{1}k_{2}}\right\|_{2}^{2}=k_{1}k_{2}\operatorname*{err}(G^{\mathrm{B}},s).$

Equivalently, the normalized worst-case squared errors satisfy

$\operatorname*{err}(G^{\mathrm{B}}\otimes\bm{1}_{k_{2}},s)=\operatorname*{err}(\bm{1}_{k_{2}}\otimes
G^{\mathrm{B}},s)=\operatorname*{err}(G^{\mathrm{B}},s).$

The proof of Lemma 4 is deferred to Appendix C. A key observation in
establishing Theorem 4 is that the squared error of a block diagonal gradient
code is the sum of squared errors from each block. The following lemma makes
this observation precise. The proof is provided in Appendix D.

######  Lemma 5.

Let $G$ be a block-diagonal gradient code given by

$G=\begin{bmatrix}G^{(1)}&0_{l\times r}&\dotsc&0_{l\times r}\\\ 0_{l\times
r}&G^{(2)}&\dotsc&0_{l\times r}\\\ \vdots&\vdots&\ddots&\vdots\\\ 0_{l\times
r}&0_{l\times r}&\dotsc&G^{(\tau)}\end{bmatrix},$

where $\tau\in\mathbbm{N}$, and each block $G^{(m)}$ is a gradient code with
$n$ workers and $k$ gradients to compute for each $m\in[\tau]$. Let
$\bm{v}:=(\bm{v}_{1},\bm{v}_{2},\dotsc,\bm{v}_{\tau})$, where $\bm{v}_{m}$ is
a decoding vector for each $m\in[\tau]$. Then for any set of non-stragglers
$\mathcal{U}$

$\|G_{\mathcal{U}}\bm{v}-\bm{1}_{k\tau}\|_{2}^{2}=\sum_{m=1}^{\tau}\|G^{(m)}_{\mathcal{U}_{m}}\bm{v}_{m}-\bm{1}_{k}\|_{2}^{2}$

where

$\mathcal{U}_{m}=\mathcal{U}\cap\\{(m-1)n+1,(m-1)n+2,\dotsc,mn\\}$

is the set of non-stragglers of $G^{(m)}$.

Another important observation in establishing Theorem 4 is that the error
function of a BIBD is a convex sequence. The proof is deferred to Appendix E.

######  Lemma 6.

Let $G^{\mathrm{B}}$ be an $(n,k,l,\lambda)$-BIBD GC. Then
$\\{\operatorname*{err}(G^{\mathrm{B}},s)\\}_{s=0}^{n}$ is a convex sequence,
i.e.,

$2\operatorname*{err}(G^{\mathrm{B}},s)\leq\operatorname*{err}(G^{\mathrm{B}},s-1)+\operatorname*{err}(G^{\mathrm{B}},s+1)$

for all $s\in[n-1]$.

We are ready to prove Theorem 4.

###### Proof:

For convenience, let $G:=G^{\mathrm{F}}\otimes G^{\mathrm{B}}$. Recall that
for any $s$ stragglers and $\tilde{s}=n_{1}n_{2}-s$ non-stragglers,

$\operatorname*{err}(G,s)=\frac{1}{k_{1}k_{2}}\max_{\mathcal{U}:|\mathcal{U}|=\tilde{s}}\min_{\bm{v}}\|G_{\mathcal{U}}\bm{v}-\bm{1}_{k_{1}k_{2}}\|_{2}^{2}.$

We simplify the squared error
$\|G_{\mathcal{U}}\bm{v}-\bm{1}_{k_{1}k_{2}}\|_{2}^{2}$ for any set
$\tilde{s}$ non-stragglers $\mathcal{U}$ by decomposing $G$ into blocks and
sub-blocks. Then, we fix the decoding vector $\bm{v}$, and find the worst-case
set of stragglers to determine $\operatorname*{err}(G,s)$.

By construction, $G$ is a block-diagonal matrix given by

$G=\begin{bmatrix}J_{l_{1}\times r_{1}}\otimes
G^{\mathrm{B}}&{\bm{0}}&\dotsc&{\bm{0}}\\\ \bm{0}&J_{l_{1}\times r_{1}}\otimes
G^{\mathrm{B}}&\dotsc&\bm{0}\\\ \vdots&\vdots&\ddots&\vdots\\\
\bm{0}&\bm{0}&\dotsc&J_{l_{1}\times r_{1}}\otimes
G^{\mathrm{B}}\end{bmatrix},$

where each zero block $\bm{0}$ is the $l_{1}k_{2}\times r_{1}n_{2}$ all-zero
matrix. For each block $m\in[k_{1}/l_{1}]$, let
$\mathcal{U}_{m}=\mathcal{U}\cap\\{(m-1)n_{2}r_{1}+1,(m-1)n_{2}r_{1}+1,\dotsc,mn_{2}r_{1}\\}$
be the set of non-stragglers in block $m$. Denote
$\tilde{s}_{m}=\left|\mathcal{U}_{m}\right|$ as the number of non-stragglers
and $s_{m}=n_{1}r_{2}-\tilde{s}_{m}$ as the number of straggling workers in
block $m$.

Now, represent each decoding vector in the following form

$\bm{v}=(\bm{v}_{1}^{T},\bm{v}_{2}^{T},\dotsc,\bm{v}_{k_{1}/l_{1}}^{T})^{T},$

where $\bm{v}_{m}$ is a length $\tilde{s}_{m}$ vector for each block $m$.
Then, the squared error can be expressed, by Lemma 5, as

$\|G_{\mathcal{U}}\bm{v}-\bm{1}_{k_{1}k_{2}}\|_{2}^{2}=\sum_{m=1}^{k_{1}/l_{1}}\big{\|}\left(J_{l_{1}\times
r_{1}}\otimes
G^{\mathrm{B}}\right)_{\mathcal{U}_{m}}\bm{v}_{m}-\bm{1}_{l_{1}k_{2}}\big{\|}_{2}^{2}.$

We now further decompose each block $m$ into $r_{1}$ sub-blocks to analyze the
squared error. Observe that each block of $G$ is given by

$J_{l_{1}\times r_{1}}\otimes
G^{\mathrm{B}}=\begin{bmatrix}\bm{1}_{l_{1}}\otimes
G^{\mathrm{B}}&\bm{1}_{l_{1}}\otimes
G^{\mathrm{B}}&\dotsc&\bm{1}_{l_{1}}\otimes G^{\mathrm{B}}\\\ \end{bmatrix},$

and consists of $r_{1}$ copies of $\bm{1}_{l_{1}}\otimes G^{\mathrm{B}}$,
which we denote as sub-blocks. Each sub-block $j\in[r_{1}]$ of block
$m\in[k_{1}/l_{1}]$ has workers

$\mathcal{B}_{m_{j}}=(m-1)n_{2}r_{1}+\\{(j-1)n_{2}+1,(j-1)n_{2}+2,\dotsc,jn_{2}\\},$

where for any set $A$ and $\alpha\in\mathbbm{R}$, $\alpha+A:=\\{\alpha+a:a\in
A\\}$. Let

$\mathcal{U}_{m_{j}}=\mathcal{U}\bigcap\mathcal{B}_{m_{j}}$

be the set of non-stragglers of sub-block $j$ of block $m$. Denote

$\tilde{s}_{m_{j}}=|\mathcal{U}_{m_{j}}|$

as the number of non-stragglers and $s_{m_{j}}=n_{2}-\tilde{s}_{m_{j}}$ as the
number of stragglers of sub-block $j$ of block $m$. Let

$j^{\prime}(m)=\arg\min_{j\in[r_{1}]}s_{m_{j}}$

be the sub-block in block $m\in[k_{1}/l_{1}]$ with the minimum number of
stragglers. Consider the decoding vector

$\displaystyle\bm{v}_{m}$
$\displaystyle=(\bm{0}_{\tilde{s}_{m_{1}}},\dotsc,\bm{0}_{\tilde{s}_{m_{j^{\prime}(m)-1}}},$
$\displaystyle\hskip 30.00005pt\bm{v}_{\mathrm{opt}}(\bm{1}_{l_{1}}\otimes
G^{\mathrm{B}},\mathcal{U}_{m_{j^{\prime}(m)}}),\bm{0}_{\tilde{s}_{m_{j^{\prime}(m)+1}}},\dotsc,\bm{0}_{\tilde{s}_{m_{r_{1}}}}).$
(19)

Since all $r_{1}$ sub-blocks in any block $m\in[k_{1}/l_{1}]$ compute the same
set of gradients, this decoding vector can be interpreted as estimating the
gradients of block $m$ using only the results returned from the sub-block with
the least number of stragglers. Then

$\displaystyle\hskip
12.50002pt\|G_{\mathcal{U}}\bm{v}-\bm{1}_{k_{1}k_{2}}\|_{2}^{2}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{m=1}^{k_{1}/l_{1}}\|(J_{l_{1}\times
r_{1}}\otimes
G^{\mathrm{B}})_{\mathcal{U}_{m}}\bm{v}_{m}-\bm{1}_{l_{1}k_{2}}\|_{2}^{2}$
$\displaystyle=\sum_{m=1}^{k_{1}/l_{1}}\|(\bm{1}_{l_{1}}\otimes
G^{\mathrm{B}})_{\mathcal{U}_{m_{j^{\prime}(m)}}}\bm{v}_{\mathrm{opt}}\left(\bm{1}_{l_{1}}\otimes
G^{\mathrm{B}},\mathcal{U}_{m_{j^{\prime}(m)}}\right)-\bm{1}_{l_{1}k_{2}}\|_{2}^{2}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\sum_{m=1}^{k_{1}/l_{1}}l_{1}k_{2}\operatorname*{err}\left(G^{\mathrm{B}},s_{m_{j^{\prime}(m)}}\right),$

where $(a)$ follows since the choice of decoding vector $\bm{v}_{m}$ in (19)
may not be optimal, and $(b)$ follows from Lemma 4 since each sub-block
$j\in[r_{1}]$ of each block $m\in[k_{1}/l_{1}]$ is an
$(n_{2},k_{2}l_{1},l_{1}l_{2},r_{2},\lambda_{2}l_{1})$-GC.

Now the worst-case squared error can be bounded as

$\displaystyle\hskip
15.00002pt\max_{\mathcal{U}:|\mathcal{U}|=\tilde{s}}\min_{\bm{v}}\|G_{\mathcal{U}}\bm{v}-\bm{1}_{k_{1}k_{2}}\|_{2}^{2}$
$\displaystyle\leq\max_{\mathcal{U}:|\mathcal{U}_{m_{j}}|=\tilde{s}_{m_{j}}}\sum_{m=1}^{k_{1}/l_{1}}l_{1}k_{2}\operatorname*{err}\left(G^{\mathrm{B}},s_{m_{j^{\prime}(m)}}\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\max_{\mathcal{U}:|\mathcal{U}_{m}|=\tilde{s}_{m}}\sum_{m=1}^{k_{1}/l_{1}}l_{1}k_{2}\operatorname*{err}\left(G^{\mathrm{B}},\left\lfloor\frac{s_{m}}{r_{1}}\right\rfloor\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\sum_{m=1}^{c}l_{1}k_{2}\operatorname*{err}\left(G^{\mathrm{B}},\left\lfloor\frac{s_{m}}{r_{1}}\right\rfloor\right)+l_{1}k_{2}\operatorname*{err}\left(G^{\mathrm{B}},\left\lfloor\frac{s_{c+1}}{r_{1}}\right\rfloor\right)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\left\lfloor\frac{s}{n_{2}r_{1}}\right\rfloor
l_{1}k_{2}+l_{1}k_{2}\operatorname*{err}(G^{\mathrm{B}},b).$

Here $(a)$ follows since $s_{m_{j^{\prime}(m)}}\leq\lfloor s_{m}/r_{1}\rfloor$
for any block $m$, thus
$\operatorname*{err}(G^{\mathrm{B}},s_{m_{j^{\prime}(m)}})$ is maximized when
$s_{m_{1}}=s_{m_{2}}=\dotsc=s_{m_{r_{1}}}=\lfloor s_{m}/r_{1}\rfloor$. Above,
$(b)$ follows since the error expression of $G^{\mathrm{B}}$ is a convex
sequence in $s$ as shown in Lemma 6, therefore

$\sum_{m=1}^{k_{1}/l_{1}}l_{1}k_{2}\operatorname*{err}\left(G^{\mathrm{B}},\left\lfloor\frac{s_{m}}{r_{1}}\right\rfloor\right)$

is maximized when all workers in

$c:=\left\lfloor\frac{s}{n_{2}r_{1}}\right\rfloor$

blocks are straggled, i.e., $s_{1}=s_{2}=\dotsc=s_{c}=r_{1}n_{2}$, and the
remaining stragglers are placed in block $c+1$. Lastly, $(c)$ follows by
observing that the first $c$ blocks each have $r_{1}n_{2}$ stragglers and
$\operatorname*{err}(G^{\mathrm{B}},\lfloor(r_{1}n_{2})/r_{1}\rfloor)=1$.
Dividing by $k_{1}k_{2}$ gives the desired result.

Observe that for any $s\in[n_{1}n_{2}]$ stragglers,

$\operatorname*{err}(G^{\mathrm{F}}\otimes
G^{\mathrm{B}},s)=\operatorname*{err}(G^{\mathrm{B}}\otimes G^{\mathrm{F}},s)$

since $G^{\mathrm{F}}\otimes G^{\mathrm{B}}$ and $G^{\mathrm{B}}\otimes
G^{\mathrm{F}}$ are permutation equivalent. Then, we can repeat the analysis
of $G^{\mathrm{B}}\otimes G^{\mathrm{F}}$ above, with a decoding vector and
worst-case set of stragglers that are permutation equivalent to our choice of
decoding vector and corresponding worst-case set of stragglers for
$G^{\mathrm{F}}\otimes G^{\mathrm{B}}$. ∎

We now establish Theorem 5 that upper bounds the normalized worst-case squared
error of the Kronecker product of two BIBDs. We need the following technical
lemma (see Appendix F for the proof).

######  Lemma 7.

Let $G^{\mathrm{B_{i}}}$ be an $(n_{i},k_{i},l_{i},r_{i},\lambda_{i})$-BIBD
for $i=1,2$, and $G=G^{\mathrm{B_{1}}}\otimes G^{\mathrm{B_{2}}}$. Then for
any set of $\tilde{s}$ non-stragglers $\mathcal{U}\subset[n_{1}n_{2}]$

$\bm{1}_{\tilde{s}}^{T}G_{\mathcal{U}}^{T}G_{\mathcal{U}}\bm{1}_{\tilde{s}}\leq\tilde{s}d+\lambda_{1}\lambda_{2}\tilde{s}^{2},$

where

$d=(l_{1}-\lambda_{1})(l_{2}-\lambda_{2})+n_{2}(l_{1}\lambda_{2}-\lambda_{1}\lambda_{2})+n_{1}(\lambda_{1}l_{2}-\lambda_{1}\lambda_{2}).$

Notice that the Kronecker product of two BIBD gradient codes is not
necessarily another BIBD gradient code. As a result, a constant decoding
vector may not be optimal. However, even the sub-optimal constant decoding
vectors provide reasonable error performance in simulations. In the following,
we establish Theorem 5 by upper bounding the error using the error
corresponding to a constant decoding vector.

###### Proof:

For convenience we write $G:=G^{\mathrm{B_{1}}}\otimes G^{\mathrm{B_{2}}}$.
Consider a constant decoding vector $\bm{v}$ given by

$\bm{v}_{a}=a\bm{1}_{\tilde{s}},$

where $a\in\mathbbm{R}$ will be specified later, and $\tilde{s}:=n_{1}n_{2}-s$
is the number of non-straggling workers. Then

$\displaystyle\hskip 15.00002pt\operatorname*{err}(G,s)$
$\displaystyle=\frac{1}{k_{1}k_{2}}\max_{\mathcal{U}:|\mathcal{U}|=\tilde{s}}\min_{\bm{v}}\|G_{\mathcal{U}}\bm{v}-\bm{1}_{k_{1}k_{2}}\|_{2}^{2}$
$\displaystyle\leq\frac{1}{k_{1}k_{2}}\max_{\mathcal{U}:|\mathcal{U}|=\tilde{s}}\min_{a}\|G_{\mathcal{U}}\bm{v}_{a}-\bm{1}_{k_{1}k_{2}}\|_{2}^{2}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\frac{1}{k_{1}k_{2}}\max_{\mathcal{U}:|\mathcal{U}|=\tilde{s}}\min_{a}\left(k_{1}k_{2}-2\bm{v}_{a}^{T}G_{\mathcal{U}}^{T}\bm{1}_{k_{1}k_{2}}+\bm{v}_{a}^{T}G_{\mathcal{U}}^{T}G_{\mathcal{U}}\bm{v}_{a}\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{1}{k_{1}k_{2}}\max_{\mathcal{U}:|\mathcal{U}|=\tilde{s}}\min_{a}\Big{(}k_{1}k_{2}-2al_{1}l_{2}\tilde{s}+a^{2}\left(\tilde{s}d+\lambda_{1}\lambda_{2}\tilde{s}^{2}\right)\Big{)}$
$\displaystyle=\frac{1}{k_{1}k_{2}}\min_{a}\Big{(}k_{1}k_{2}-2al_{1}l_{2}\tilde{s}+a^{2}\left(\tilde{s}d+\lambda_{1}\lambda_{2}\tilde{s}^{2}\right)\Big{)}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}1-\frac{(l_{1}l_{2})^{2}(\tilde{s})}{k_{1}k_{2}(d+\lambda_{1}\lambda_{2}\tilde{s})}.$

Firstly, $(a)$ follows since for any set of $\tilde{s}$ non-stragglers
$\mathcal{U}$, we have

$\displaystyle\left\|G_{\mathcal{U}}\bm{v}_{a}-\bm{1}_{k_{1}k_{2}}\right\|_{2}^{2}$
$\displaystyle=$
$\displaystyle\left(G_{\mathcal{U}}\bm{v}_{a}-\bm{1}_{k_{1}k_{2}}\right)^{T}\left(G_{\mathcal{U}}\bm{v}_{a}-\bm{1}_{k_{1}k_{2}}\right)$
$\displaystyle=$ $\displaystyle
k_{1}k_{2}-2\bm{v}_{a}^{T}G_{\mathcal{U}}^{T}\bm{1}_{k_{1}k_{2}}+\bm{v}_{a}^{T}G_{\mathcal{U}}^{T}G_{\mathcal{U}}\bm{v}_{a}.$

Secondly, $(b)$ follows since by construction, each column of
$G_{\mathcal{U}}$ has exactly $l_{1}l_{2}$ ones, thus

$\displaystyle 2\bm{v}_{a}^{T}G_{\mathcal{U}}^{T}\bm{1}_{k_{1}k_{2}}$
$\displaystyle=2a\bm{1}_{\tilde{s}}^{T}G_{\mathcal{U}}^{T}\bm{1}_{k_{1}k_{2}}$
$\displaystyle=2al_{1}l_{2}\bm{1}_{\tilde{s}}^{T}\bm{1}_{\tilde{s}}$
$\displaystyle=2al_{1}l_{2}\tilde{s}.$

Moreover, from Lemma 7, we have

$\displaystyle\bm{v}_{a}^{T}G_{\mathcal{U}}^{T}G_{\mathcal{U}}\bm{v}_{a}$
$\displaystyle=a^{2}\bm{1}_{\tilde{s}}^{T}G_{\mathcal{U}}^{T}G_{\mathcal{U}}\bm{1}_{\tilde{s}}$
$\displaystyle\leq
a^{2}\left(\tilde{s}d+\lambda_{1}\lambda_{2}\tilde{s}^{2}\right).$

Lastly, $(c)$ follows by observing that $l_{1}\geq\lambda_{1}$,
$l_{2}\geq\lambda_{2}$, and $\tilde{s}\geq 0$, thus we are minimizing over a
convex quadratic function in $a$, where the minimzing constant $a^{*}$ is
given by

$a^{*}=\frac{l_{1}l_{2}}{d+\tilde{s}\lambda_{1}\lambda_{2}}=\frac{l_{1}l_{2}}{d+(n_{1}n_{2}-s)\lambda_{1}\lambda_{2}}.$

∎

##  V Conclusion

In this work, we provided two approximate gradient code constructions. We show
that our first construction, called probabilistic BIBD gradient codes, exist
for a wider range of system parameters than BIBD gradient codes, and have
lower average error than BIBD gradient codes. Our second construction, called
product gradient codes, allow us to construct new gradient codes from existing
gradient codes in a scalable manner. We derive upper bounds on the normalized
worst-case squared errors of various product gradient codes. The simulation in
Fig. 1 shows that the Kronecker product of BIBDs has lower error than a BIBD
gradient code with similar redundancy per data piece.

##  Appendix A FRC Error

######  Lemma 8.

If $G^{\mathrm{F}}$ is an $(n,k,l,r)$-FRC, then the error under $s$ stragglers
is

$\operatorname*{err}(G^{\mathrm{F}},s)=\frac{l}{k}\left\lfloor\frac{s}{r}\right\rfloor.$

for any $s\in[n_{1}]$.

###### Proof:

Since $G^{\mathrm{F}}$ is an FRC, its corresponding bipartite graph consists
of $\frac{n}{r}$ disjoint sub-graphs, which we will call “blocks”. Each block
has $r$ workers and $l$ gradients to be computed. From algorithm 1 in [4], the
optimal decoding vector recovers all gradients in a block if there is at least
one non straggler in the block. Thus only gradients in blocks where all $r$
workers are stragglers cannot be recovered. With $s$ stragglers, at most
$\left\lfloor\frac{s}{r}\right\rfloor$ blocks can be fully straggled, so at
most $l\left\lfloor\frac{s}{r}\right\rfloor$ gradients cannot be recovered.
Then

$\displaystyle\operatorname*{err}(G^{\mathrm{F}},s)$
$\displaystyle=\max_{\begin{subarray}{c}\mathcal{U}\subset[n]\\\
|\mathcal{U}|=n-s\end{subarray}}\frac{\|G^{\mathrm{F}}_{\mathcal{U}}\bm{v}_{\mathrm{opt}}(G^{\mathrm{F}},\mathcal{U})-\bm{1}_{k}\|_{2}^{2}}{k}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\frac{\left\|\bm{1}_{l\left\lfloor\frac{s}{r}\right\rfloor}\right\|_{2}^{2}}{k}$
$\displaystyle=\frac{l}{k}\left\lfloor\frac{s}{r}\right\rfloor.$

where $(a)$ follows from the fact that at most
$l\left\lfloor\frac{s}{r}\right\rfloor$ gradients cannot be recovered when
there are $s$ stragglers. ∎

##  Appendix B Proof of Lemma 3

The proof follows essentially from the proof of Theorem 1 in [1], and is
included here for completeness.

We first obtain the optimal decoding vector of $G$ for any set of
$\tilde{s}:=n-s$ non-stragglers $\mathcal{U}$. Recall

$\bm{v}_{\mathrm{opt}}(G,\mathcal{U}):=\arg\min_{\bm{v}\in\mathbbm{R}^{n-s}}\|G_{\mathcal{U}}\bm{v}-\bm{1}_{k}\|_{2}^{2}.$

An optimal solution to the above optimization problem is given by
$\bm{v}_{\mathrm{opt}}(G,\mathcal{U})=G_{\mathcal{U}}^{\dagger}\bm{1}_{k}$,
where $G_{\mathcal{U}}^{\dagger}$ is the Moore-Penrose inverse of
$G_{\mathcal{U}}$. It is known that
$G_{\mathcal{U}}^{\dagger}=(G_{\mathcal{U}}^{T}G_{\mathcal{U}})^{-1}G_{\mathcal{U}}^{T}$
when $G_{\mathcal{U}}^{T}G_{\mathcal{U}}$ is invertible. Observe that

$G_{\mathcal{U}}^{T}G_{\mathcal{U}}=(l-\lambda)I_{\tilde{s}}+\lambda
J_{\tilde{s}\times\tilde{s}}$ (20)

since each column of $G_{\mathcal{U}}$ has $l$ ones, and any pair of columns
of $G_{\mathcal{U}}$ has $\lambda$ intersections. Since $l>\lambda$ by
assumption, $G_{\mathcal{U}}^{T}G_{\mathcal{U}}$ is invertible. Thus

$\bm{v}_{\mathrm{opt}}(G,\mathcal{U})=(G_{\mathcal{U}}^{T}G_{\mathcal{U}})^{-1}G_{\mathcal{U}}^{T}\bm{1}_{k}.$

We have

$\displaystyle(G_{\mathcal{U}}^{T}G_{\mathcal{U}})^{-1}$
$\displaystyle=\Big{(}(l-\lambda)I_{\tilde{s}}+\lambda
J_{\tilde{s}\times\tilde{s}}\Big{)}^{-1}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\frac{1}{l-\lambda}I_{\tilde{s}}+\frac{1}{1+\operatorname*{tr}\left(\frac{\lambda}{l-\lambda}J_{\tilde{s}}\right)}\frac{\lambda}{(l-\lambda)^{2}}J_{\tilde{s}}$
$\displaystyle=\frac{1}{l-\lambda}\left(I_{\tilde{s}}+\frac{\lambda}{l+\lambda(\tilde{s}-1)}J_{\tilde{s}}\right),$
(21)

where $(a)$ follows from the matrix inversion lemma [21]. Thus the optimal
decoding vector is given by

$\displaystyle\bm{v}_{\mathrm{opt}}(G,\mathcal{U})$
$\displaystyle=(G_{\mathcal{U}}^{T}G_{\mathcal{U}})^{-1}G_{\mathcal{U}}^{T}\bm{1}_{k}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}(G_{\mathcal{U}}^{T}G_{\mathcal{U}})^{-1}l\bm{1}_{\tilde{s}}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\frac{l}{l+\lambda(\tilde{s}-1)}\bm{1}_{\tilde{s}},$
(22)

where $(a)$ follows since each column of $G_{\mathcal{U}}$ has $l$ ones, and
$(b)$ follows from equation (21).

We now find the normalized worst-case squared error of $G$ with $s$
stragglers. Observe that

$\displaystyle\hskip
15.00002pt\|G_{\mathcal{U}}\bm{v}_{\mathrm{opt}}(G,\mathcal{U})-\bm{1}_{k}\|_{2}^{2}$
$\displaystyle=\left(G_{\mathcal{U}}\bm{v}_{\mathrm{opt}}(G,\mathcal{U})-\bm{1}_{k}\right)^{T}\left(G_{\mathcal{U}}\bm{v}_{\mathrm{opt}}(G,\mathcal{U})-\bm{1}_{k}\right)$
$\displaystyle=\Big{(}\bm{1}_{k}^{T}\bm{1}_{k}-2\bm{v}_{\mathrm{opt}}^{T}(G,\mathcal{U})G_{\mathcal{U}}^{T}\bm{1}_{k}$
$\displaystyle\hskip
60.00009pt+\bm{v}_{\mathrm{opt}}^{T}(G,\mathcal{U})G_{\mathcal{U}}^{T}G_{\mathcal{U}}\bm{v}_{\mathrm{opt}}(G,\mathcal{U})\Big{)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\Big{(}k-2l\bm{v}_{\mathrm{opt}}^{T}\bm{1}_{\tilde{s}}$
$\displaystyle\hskip
60.00009pt+\bm{v}_{\mathrm{opt}}^{T}(G,\mathcal{U})\big{(}(l-\lambda)I_{\tilde{s}}+\lambda
J_{\tilde{s}\times\tilde{s}}\big{)}\bm{v}_{\mathrm{opt}}(G,\mathcal{U})\Big{)}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\left(k-\frac{2l^{2}\tilde{s}}{l+\lambda(\tilde{s}-1)}+\frac{l^{2}\left((l-\lambda)\tilde{s}+(\lambda)\tilde{s}^{2}\right)}{(l+\lambda(\tilde{s}-1))^{2}}\right)$
$\displaystyle=k-\frac{l^{2}\tilde{s}}{l+\lambda(\tilde{s}-1)}.$

where $(a)$ follows since each column of $G_{\mathcal{U}}$ has $l$ ones, and
from equation (20). Above, $(b)$ follows from equation (22).

##  Appendix C Proof of Lemma 4

Notice that $G^{\mathrm{B}}\otimes\bm{1}_{k_{2}}$ is an
$(n_{1},k_{1}k_{2},l_{1}k_{2},r_{1},\lambda_{1}k_{2})$-GC, thus by Lemma 3

$\displaystyle\hskip
10.00002pt\left\|(G^{\mathrm{B}}\otimes\bm{1}_{k_{2}})_{\mathcal{U}}v_{\mathrm{opt}}(G,\mathcal{U})-\bm{1}_{k_{1}k_{2}}\right\|_{2}^{2}$
$\displaystyle=k_{1}k_{2}-\frac{(l_{1}k_{2})^{2}(n_{1}-s)}{l_{1}k_{2}+\lambda_{1}k_{2}(n_{1}-s-1)}$
$\displaystyle=k_{1}k_{2}\left(1-\frac{l_{1}^{2}(n_{1}-s)}{l_{1}k_{1}+\lambda_{1}k_{1}(n_{1}-s-1)}\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}k_{1}k_{2}\operatorname*{err}(G^{B},s),$

where $(a)$ follows from equation (7). Observe that $\bm{1}_{k_{2}}\otimes
G^{\mathrm{B}}$ is also an
$(n_{1},k_{1}k_{2},l_{1}k_{2},r_{1},\lambda_{1}k_{2})$-GC, thus

$\displaystyle\hskip 15.00002pt\left\|(\bm{1}_{k_{2}}\otimes
G^{\mathrm{B}})_{\mathcal{U}}v_{\mathrm{opt}}(G,\mathcal{U})-\bm{1}_{k_{1}k_{2}}\right\|_{2}^{2}$
$\displaystyle=\left\|G_{\mathcal{U}}v_{\mathrm{opt}}(G,\mathcal{U})-\bm{1}_{k_{1}k_{2}}\right\|_{2}^{2}.$

Dividing by $k_{1}k_{2}$ gives the desired equality.

##  Appendix D Proof of Lemma 5

The workers and gradients of $G^{(j)}$ and $G^{(j^{\prime})}$ are disjoint if
$j\neq j^{\prime}$ for any $1\leq j,j^{\prime}\leq n\tau$. Then

$\displaystyle\|G_{\mathcal{U}}\bm{v}-\bm{1}_{k\tau}\|_{2}^{2}$
$\displaystyle=\sum_{i=1}^{k\tau}\left((G_{\mathcal{U}}\bm{v})_{i}-1\right)^{2}$
$\displaystyle=\sum_{j=1}^{\tau}\sum_{i=1}^{k}\left((G^{(j)}_{\mathcal{U}_{j}}\bm{v}_{j})_{i}-1\right)^{2}$
$\displaystyle=\sum_{j=1}^{\tau}\|G^{(j)}_{\mathcal{U}_{j}}\bm{v}_{j}-\bm{1}_{k}\|_{2}^{2}.$

##  Appendix E Proof of Lemma 6

We first show that if a function $f:\mathbbm{R}\to\mathbbm{R}$ is convex, then
$\\{f(m)\\}_{m=0}^{\infty}$ is a convex sequence. If $f$ is convex, then for
all $t\in[0,1]$ and any $x_{1},x_{2}\in\mathbbm{R}$

$f(tx_{1}+(1-t)x_{2})\leq tf(x_{1})+(1-t)f(x_{2}).$

Set $t=\frac{1}{2}$, and let $x_{1}=m-1$ and $x_{2}=m+1$ for any
$m\in\mathbbm{N}$. Then the above expression becomes

$f(m)\leq\frac{f(m-1)+f(m+1)}{2},$

thus $\\{f(m)\\}_{m=0}^{\infty}$ is a convex sequence. It remains to show that
the BIBD error expression is a convex function. Let $f:[0,n]\to\mathbbm{R}$ be
the function given by

$f(x)=1-\frac{l^{2}(n-x)}{kl+k\lambda(n-x-1)}$

for any $x\in[0,n]$, and notice that
$\\{\operatorname*{err}(G^{\mathrm{B}},s)\\}_{s=0}^{n}=\\{f(s)\\}_{s=0}^{n}$.
Since

$\frac{\partial^{2}f}{\partial
x^{2}}=\frac{2l^{2}\lambda(\lambda-l)}{k(\lambda(x-n-1)+1)}$

is non-negative for any $x\in[0,n]$, $f$ is a convex function, and
$\\{\operatorname*{err}(G^{\mathrm{B}},s)\\}_{s=0}^{n}$ is a convex sequence.

##  Appendix F Proof of Lemma 7

We write

$G_{\mathcal{U}}=\begin{bmatrix}|&|&\dotsc&|\\\
\bm{w}_{1}&\bm{w}_{2}&\dotsc&\bm{w}_{\tilde{s}}\\\ |&|&\dotsc&|\end{bmatrix},$

where $\bm{w}_{1},\bm{w}_{2},\dotsc,\bm{w}_{\tilde{s}}$ are column vectors of
size $k_{1}k_{2}$. Then

$(G_{\mathcal{U}}^{T}G_{\mathcal{U}})_{i,j}=\bm{w}_{i}^{T}\bm{w}_{j}$

is the number of intersections between non-straggling workers
$i,j\in\mathcal{U}$. To determine the number of intersections between workers
$i$ and $j$, we partition the $[n_{1}n_{2}]$ workers of $G$ into “blocks” and
“classes”. Let block $m\in[n_{1}]$ refer to the set of $n_{2}$ workers

$\mathcal{B}_{m}:=\\{(m-1)n_{2}+1,(m-1)n_{2}+2,\dotsc,mn_{2}\\}.$

Similarly, class $m^{\prime}\in[n_{1}]$ refers to the set of $n_{1}$ workers

$\mathcal{C}_{m^{\prime}}:=\\{m^{\prime},m^{\prime}+n_{2},m^{\prime}+2n_{2},\dotsc,m^{\prime}+{n_{1}-1}n_{2}\\}.$

Let $i_{\mathrm{b}}$ and $j_{\mathrm{b}}$ be the block that $i$ and $j$ are
from respectively i.e. $i\in\mathcal{B}_{i_{\mathrm{b}}}$ and
$j\in\mathcal{B}_{j_{\mathrm{b}}}$. Similarly , we denote by $i_{\mathrm{c}}$
and $j_{\mathrm{c}}$ the classes that workers $i$ and $j$ are in. By
construction of $G$, notice that

$\bm{w}_{i}^{T}\bm{w}_{j}=\begin{cases}l_{1}l_{2}&i=j,\\\
l_{1}\lambda_{2}&i\neq j,i_{\mathrm{b}}=j_{\mathrm{b}},\\\
\lambda_{1}l_{2}&i\neq j,i_{\mathrm{c}}=j_{\mathrm{c}},\\\
\lambda_{1}\lambda_{2}&\text{otherwise.}\end{cases}$

Let
$\tilde{s}_{i_{\mathrm{b}}}=\left|\mathcal{U}\cap\mathcal{B}_{i_{\mathrm{b}}}\right|$
be the number of non-straggling workers in block $i_{\mathrm{b}}$, and
$\tilde{z}_{i_{\mathrm{c}}}=\left|\mathcal{U}\cap\mathcal{C}_{i_{\mathrm{c}}}\right|$
be the number of non-straggling workers in class $i_{\mathrm{c}}$. Then

$\displaystyle\hskip
15.00002pt1_{\tilde{s}}^{T}G_{\mathcal{U}}^{T}G_{\mathcal{U}}\bm{1}_{\tilde{s}}$
$\displaystyle=\sum_{i\in\mathcal{U}}\sum_{j\in\mathcal{U}}\bm{w}_{i}^{T}\bm{w}_{j}$
$\displaystyle=\sum_{i\in\mathcal{U}}\Big{(}l_{1}l_{2}+(\tilde{s}_{i_{\mathrm{b}}}-1)l_{1}\lambda_{2}+(\tilde{z}_{i_{\mathrm{c}}}-1)(\lambda_{1}l_{2})$
$\displaystyle\hskip
50.00008pt+(\tilde{s}-\tilde{s}_{i_{\mathrm{b}}}-\tilde{z}_{i_{\mathrm{c}}}+1)\lambda_{1}\lambda_{2}\Big{)}$
$\displaystyle=(l_{1}-\lambda_{1})(l_{2}-\lambda_{2})\tilde{s}+\lambda_{1}\lambda_{2}\tilde{s}^{2}$
$\displaystyle\hskip
30.00005pt+(l_{1}\lambda_{2}-\lambda_{1}\lambda_{2})\sum_{i\in\mathcal{U}}\tilde{s}_{i_{\mathrm{b}}}+(l_{2}\lambda_{1}-\lambda_{1}\lambda_{2})\sum_{i\in\mathcal{U}}\tilde{z}_{i_{\mathrm{c}}}.$

Now observe that

$\displaystyle\sum_{i\in\mathcal{U}}\tilde{s}_{i_{\mathrm{b}}}$
$\displaystyle=\sum_{m=1}^{n_{1}}\sum_{i\in\mathcal{U}\cap\mathcal{B}_{m}}\tilde{s}_{i_{\mathrm{b}}}$
$\displaystyle=\sum_{m=1}^{n_{1}}\sum_{i\in\mathcal{U}\cap\mathcal{B}_{m}}\tilde{s}_{m}$
$\displaystyle=\sum_{m=1}^{n_{1}}\tilde{s}_{m}^{2}.$

Notice that $0\leq\tilde{s}_{m}\leq n_{2}$ for each $m\in[n_{1}]$, and
$\sum_{m=1}^{n_{1}}\tilde{s}_{m}=\tilde{s}$. Therefore

$\sum_{i\in\mathcal{U}}\tilde{s}_{i_{\mathrm{b}}}=\sum_{m=1}^{n_{1}}\tilde{s}_{m}^{2}\leq\sum_{m=1}^{n_{1}}\tilde{s}_{m}n_{2}=n_{2}\tilde{s}.$

Similarly, we have

$\displaystyle\sum_{i\in\mathcal{U}}\tilde{z}_{i_{\mathrm{c}}}$
$\displaystyle=\sum_{m^{\prime}=1}^{n_{2}}\sum_{i\in\mathcal{U}\cap\mathcal{C}_{m^{\prime}}}\tilde{z}_{i_{\mathrm{c}}}$
$\displaystyle=\sum_{m^{\prime}=1}^{n_{2}}\sum_{i\in\mathcal{U}\cap\mathcal{C}_{m^{\prime}}}\tilde{z}_{m^{\prime}}$
$\displaystyle=\sum_{m^{\prime}=1}^{n_{2}}\tilde{z}_{m^{\prime}}^{2}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{m^{\prime}=1}^{n_{2}}\tilde{z}_{m^{\prime}}n_{1}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}n_{1}\tilde{s}.$

where $(a)$ follows since $0\leq\tilde{z}_{m^{\prime}}\leq n_{1}$ for any
$m^{\prime}\in[n_{2}]$, and $(b)$ follows since
$\tilde{z}_{1}+\tilde{z}_{2}+\dotsc+\tilde{z}_{n_{2}}=\tilde{s}$. Therefore,
we have

$\bm{1}_{\tilde{s}}^{T}G_{\mathcal{U}}^{T}G_{\mathcal{U}}\bm{1}_{\tilde{s}}\leq\tilde{s}d+\lambda_{1}\lambda_{2}\tilde{s}^{2}.$

## Acknowledgment

The authors would like to thank Ziqiao Lin, who participated as a summer
intern student in the initial stage of this work. This work was supported in
part by the NSERC Discovery Launch Supplement DGECR-2019-00447, in part by the
NSERC Discovery Grant RGPIN-2019-05448, and in part by the NSERC Collaborative
Research and Development Grant CRDPJ 543676-19.

## References

  * [1] S. Kadhe, O. O. Koyluoglu, and K. Ramchandran, “Gradient coding based on block designs for mitigating adversarial stragglers,” in _Proc. IEEE Int. Symp. Inf. Theory_ , 2019, pp. 2813–2817.
  * [2] C. J. Colbourn and J. H. Dinitz, _Handbook of Combinatorial Designs, Second Edition (Discrete Mathematics and Its Applications)_. Chapman & Hall/CRC, 2006.
  * [3] J. Chen, X. Pan, R. Monga, S. Bengio, and R. Jozefowicz, “Revisiting distributed synchronous SGD,” 2017. [Online]. Available: https://arxiv.org/abs/1604.00981
  * [4] R. Tandon, Q. Lei, A. G. Dimakis, and N. Karampatziakis, “Gradient coding: Avoiding stragglers in distributed learning,” in _Proceedings of the 34th International Conference on Machine Learning_ , D. Precup and Y. W. Teh, Eds., vol. 70, 06–11 Aug 2017, pp. 3368–3376.
  * [5] N. J. Yadwadkar, B. Hariharan, J. E. Gonzalez, and R. Katz, “Multi-task learning for straggler avoiding predictive job scheduling,” _Journal of Machine Learning Research_ , vol. 17, no. 106, pp. 1–37, 2016.
  * [6] D. Wang, G. Joshi, and G. Wornell, “Using straggler replication to reduce latency in large-scale parallel computing,” _SIGMETRICS Perform. Eval. Rev._ , vol. 43, no. 3, p. 7–11, Nov. 2015.
  * [7] M. F. Aktas, P. Peng, and E. Soljanin, “Effective straggler mitigation: Which clones should attack and when?” _SIGMETRICS Perform. Eval. Rev._ , vol. 45, no. 2, p. 12–14, Oct. 2017.
  * [8] K. Lee, M. Lam, R. Pedarsani, D. Papailiopoulos, and K. Ramchandran, “Speeding up distributed machine learning using codes,” _IEEE Trans. Inf. Theory_ , vol. 64, no. 3, pp. 1514–1529, 2018.
  * [9] S. Li, S. M. Mousavi Kalan, A. S. Avestimehr, and M. Soltanolkotabi, “Near-optimal straggler mitigation for distributed gradient methods,” in _IEEE International Parallel and Distributed Processing Symposium Workshops_ , 2018, pp. 857–866.
  * [10] Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “Straggler mitigation in distributed matrix multiplication: Fundamental limits and optimal coding,” _IEEE Trans. Inf. Theory_ , vol. 66, no. 3, pp. 1920–1933, 2020.
  * [11] W. Halbawi, N. Azizan, F. Salehi, and B. Hassibi, “Improving distributed gradient descent using reed-solomon codes,” in _Proc. IEEE Int. Symp. Inf. Theory_ , 2018, pp. 2027–2031.
  * [12] A. Reisizadeh, S. Prakash, R. Pedarsani, and A. S. Avestimehr, “Tree gradient coding,” in _Proc. IEEE Int. Symp. Inf. Theory_ , 2019, pp. 2808–2812.
  * [13] N. Raviv, R. Tandon, A. Dimakis, and I. Tamo, “Gradient coding from cyclic MDS codes and expander graphs,” in _Proceedings of the 35th International Conference on Machine Learning_ , J. Dy and A. Krause, Eds., vol. 80, 10–15 Jul 2018, pp. 4305–4313.
  * [14] Z. B. Charles, D. S. Papailiopoulos, and J. S. Ellenberg, “Approximate gradient coding via sparse random graphs,” 2017. [Online]. Available: http://arxiv.org/abs/1711.06771
  * [15] Z. Charles and D. Papailiopoulos, “Gradient coding via the stochastic block model,” 2018. [Online]. Available: https://arxiv.org/abs/1805.10378
  * [16] H. Wang, Z. Charles, and D. Papailiopoulos, “Erasurehead: Distributed gradient descent without delays using approximate gradient coding,” 2019. [Online]. Available: https://arxiv.org/abs/1901.09671
  * [17] S. Wang, J. Liu, and N. Shroff, “Fundamental limits of approximate gradient coding,” _Proc. ACM Meas. Anal. Comput. Syst._ , vol. 3, no. 3, Dec. 2019\.
  * [18] M. Glasgow and M. Wootters, “Approximate gradient coding with optimal decoding,” 2020. [Online]. Available: https://arxiv.org/abs/2006.09638
  * [19] S. Sarmasarkar, V. Lalitha, and N. Karamchandani, “On gradient coding with partial recovery,” 2021. [Online]. Available: https://arxiv.org/abs/2102.10163
  * [20] F. MacWilliams and N. Sloane, _The Theory of Error-Correcting Codes_ , ser. North-Holland Mathematical Library. Elsevier, 1977, vol. 16.
  * [21] K. S. Miller, “On the inverse of the sum of matrices,” _Mathematics Magazine_ , vol. 54, no. 2, pp. 67–72, 1981. [Online]. Available: http://www.jstor.org/stable/2690437