Approximate Gradient Coding via Sparse Random Graphs

Introduction

Deploying algorithms on distributed systems has become the de facto choice for scaling-out machine learning on large data sets. Distributed algorithms generally achieve substantial runtime speedups compared to single node algorithms. Unfortunately, these speedup gains often fall short of the theoretically optimal speedup when scaling beyond a few tens of compute nodes . This commonly observed behavior is referred to as the speedup saturation phenomenon. One of the causes of speedup saturation is the presence of stragglers. These are compute nodes whose runtime is substantially higher than the average runtime among all nodes.

Several methods for mitigating the effect of stragglers have been recently proposed. These approaches include replicating jobs across redundant nodes and dropping stragglers in the case that the underlying computation is robust to errors . Moreover, redundant compute nodes can help improve the performance of distributed model training algorithms, as demonstrated in .

Recently, tools from coding theory have gained traction in an effort to mitigate stragglers. Lee et al. proposed the use of techniques from coding theory to compensate for stragglers and communication bottlenecks in machine learning settings, especially for the computation of linear functions. Li et al. proposed using coding theory to reduce inter-server communication in the shuffling phase of MapReduce . Then, propose another coding-theoretic algorithm for speeding up distributed matrix multiplication in heterogeneous clusters. The use of codes for distributed matrix multiplication and linear operations on functions was also studied in , which analyzes the trade-off between the flexibility and sparsity of the code.

In , the authors propose gradient coding, a technique to exactly recover the sum of gradients from a subset of compute nodes. The authors show that $k$ gradients can be recovered from any $k-s$ compute nodes, as long as each node computes $s+1$ gradients. In other words, the algorithm is robust to $s$ stragglers. Gradient coding is particularly relevant to synchronous distributed learning algorithms that involve computing sums of gradients, such as mini-batch stochastic gradient descent and full-batch gradient descent. While some of the gradient code constructions in are randomized, the authors in use deterministic codes based on expander graphs to achieve similar results.

Most of the above results focus on exact reconstruction of a sum of functions. In many practical distributed settings, we may only require approximate reconstruction of the sum. For example, parallel model training in machine learning settings has been shown to be robust to noise . In some scenarios, noisy gradients may even improve the generalization performance of the trained model . By only approximately reconstructing the desired function, we hope to increase the speed and tolerance to stragglers of our distributed algorithm. In fact, expander graphs, particularly Ramanujan graphs, can be used for such approximate reconstruction . Unfortunately, expander graphs, especially Ramanujan graphs, can be expensive to compute in practice, especially for large numbers of compute nodes. Moreover, the desired parameters of the construction may be constrained according to underlying combinatorial rules.

In this work, we use sparse graphs to create gradient codes capable of efficiently and accurately computing approximate gradients in a distributed manner. More generally, these codes can be used to approximately compute any sum of functions in a distributed manner. We formally introduce the approximate recovery problem using a coding–theoretic interpretation, and present and analyze two decoding techniques for approximate reconstruction: an optimal decoding algorithm that has polynomial-time complexity, and a fast decoding method that has linear complexity in the sparsity of the input.

We focus on two different codes that are efficiently computable and require only a logarithmic number of tasks per compute node. The first is the Fractional Repetition Code (FRC) proposed in . We show that FRCs can achieve small or zero error with high probability, even if a constant fraction of compute nodes are stragglers. However, we show that FRCs are susceptible to adversarial stragglers, where an adversary can force a subset of the nodes to become stragglers. To get around this issue, we also present the Bernoulli Gradient Code (BGC) and the regularized Bernoulli Gradient Code (rBGC), whose constructions are based on sparse random graphs. We show that adversarial straggler selection in general codes is NP-hard, suggesting that these random codes may perform better then FRCs against polynomial-time adversaries. We give explicit bounds on the error of BGCs and rBGCs that show that their potential tolerance to adversaries comes at the expense of a worse average-case error than FRCs. We provide simulations that support our theoretical results. These simulations show that there is a trade-off between the decoding complexity of a gradient code and its average- and worst-case performance.

Setup

2 Problem Statement

In this work, we consider a distributed master-worker setup of $n$ compute nodes, each of which is assigned a maximum of $s$ tasks. The compute nodes can compute locally assigned tasks and they can send messages to the master node.

The goal of the master node is to compute the sum of $k$ functions

The above setup is relevant to distributed learning algorithms, where we often wish to find some model ${\bf x}$ by minimizing

Approximate Gradient Coding: There are three components of an approximate gradient coding scheme:

The function assignment per compute node.

The messages sent from a compute node to the master.

The decoding algorithm used by the master to recover an approximate sum of gradients.

After assigning tasks to each compute node, we let the compute nodes run local computations for some maximum amount of time. Afterwards, we may have compute nodes that either failed to compute some functions or are still running. These are the straggler nodes. During the approximate reconstruction of the sum, we assume that the master node only has access to the output of the $r$ non-straggler nodes out of the $n$ total compute nodes. We want to use their output to compute the best approximation possible to $f({\bf x})$ given in (2.1). We assume that we can only take linear combinations of the outputs of the non-straggler nodes.

More formally, the task assignments are represented by a function assignment matrix ${\bf G}$, a $k\times n$ matrix where the support of column $j$ indexes the functions assigned to compute node $j$. The entries of column $j$ correspond to the coefficients of the linear combination of these local functions that the compute node sends back to the master once the compute node has completed its local computations.

Let $\mathbf{A}$ denote the $k\times r$ submatrix of ${\bf G}$ corresponding to the $r$ non-straggler compute nodes. The minimum recovery error for a given subset matrix $\mathbf{A}$ is given by

To better analyze this error, we define the optimal decoding error of a matrix $\mathbf{A}$.

The optimal decoding error of a non-straggler matrix $\mathbf{A}$ is defined as

The optimal decoding error quantifies how close ${\bf 1}_{k}$ is to being in the span of the columns of $\mathbf{A}$. Taking ${\bf x}={\bf 0}_{r}$, we see that for any $\mathbf{A}$, $0\leq\operatorname{err}(\mathbf{A})\leq k$. It is worth noting that $\operatorname{err}(\mathbf{A})$ is the absolute error incurred in our approximation. The multiplicative error is $\operatorname{err}(\mathbf{A})/k$. Note that if $\operatorname{err}(\mathbf{A})$ is small, then the overall minimum recovery error is small relative to $\|{\bf f}\|_{2}^{2}$, since

For a given matrix $\mathbf{A}$, let $\mathbf{A}^{+}$ denote its pseudo-inverse. Properties of the pseudo-inverse imply

In general, we are interested in constructing function assignment matrices ${\bf G}$ such that submatrices $\mathbf{A}$ have small decoding error. Note that we can either consider the worst-case among all $\mathbf{A}$ or consider the setting where $\mathbf{A}$ is chosen uniformly at random. We will refer to these ${\bf G}$ matrices as approximate gradient codes.

Approximate gradient codes were constructed in using expander graphs. The authors show in particular that if ${\bf G}$ is the adjacency matrix of a Ramanujan graph, then the worst-case decoding error is relatively small. Unfortunately, such graphs may be expensive to compute in practice. To circumvent this issue, we use simplified random constructions.

Our main theorem shows that there is an efficiently computable code that has small or zero decoding error with high probability, even with a constant fraction of stragglers. We state an informal version of this theorem below. Theorem 8 below will provide a more general and formal statement, along with the proof.

We can assign $s=O(\log k)$ tasks to each compute node in such a way that with probability at least $1-\frac{1}{k}$, we can tolerate $\Theta(k)$ randomly chosen stragglers within a multiplicative error of $\epsilon$ where

In other words, for any $k$ and a constant fraction of stragglers $r$, there is a code with sparsity $\Theta(\log(k))$ that can exactly reconstruct the gradient with high probability. While this code achieves smaller error for most $\mathbf{A}$ than previously designed gradient codes, we show that this comes at the expense of the worst-case error, which can be $\Theta(k)$. Here, the worst-case is taken over all possible sets of nodes that become stragglers. Moreover, this worst-case be computed efficiently by an adversary. On the other hand, we show that in general, adversarial straggler selection is NP-hard. In order to counter polynomial-time adversaries, we give another approximate gradient code that utilizes randomness. We also bound the decoding error of this code. We show the following informal theorem.

We can randomly assign $O(\log k)$ tasks to each compute node in such a way that with probability at least $1-\frac{1}{k}$, we can tolerate $\delta k$ randomly chosen stragglers within a multiplicative error of $\epsilon$ where

Theorem 24 below gives a more general and formal statement, along with the proof. In comparison, work in derives worst-case bounds on $\operatorname{err}(\mathbf{A})$ when ${\bf G}$ is the adjacency matrix of an $s$-regular expander graph. Given such a ${\bf G}$, denotes its eigenvalues as $\lambda_{1}\geq\ldots\geq\lambda_{k}$. We will let $\lambda({\bf G}):=\max\{|\lambda_{2}|,|\lambda_{k}|\}$. Then the aforementioned work proves the following theorem.

Suppose ${\bf G}$ is a $\log(k)$-regular expander. Then we can tolerate any $\delta k$ stragglers within a multiplicative error of $\epsilon$ where

In particular, if ${\bf G}$ is a Ramanujan graph, then this becomes $\epsilon=O(\delta k/(1-\delta)s)$. This comes at the expense of having a more computationally difficult construction, as expander graphs, especially Ramanujan graphs, can be difficult to compute.

Decoding: We would like to note that the performance of a gradient code depends in part on the decoding algorithm, i.e., how we use the output from the non-stragglers to approximate the desired output. In our setting, we want to use the received non-straggler matrix $\mathbf{A}$ to approximate ${\bf 1}_{k}$. We give two possible methods below. We will refer to these as decoding methods because of the parallels to coding theory.

For the one-step decoding error, we will generally consider $\rho=\frac{k}{rs}$. If ${\bf G}$ has $s$ entries in each column and row, then we would expect $\mathbf{A}$ to have roughly $\frac{rs}{k}$ entries in each row. If this holds exactly, then setting $\rho=\frac{k}{rs}$ will allow us to exactly reconstruct the gradient.

A decoding method analogous to the one-step decoding method was previously used in . Note that the one-step decoding method is more efficient to compute than the optimal decoding, especially when $\mathbf{A}$ is ill-conditioned or $k$ is large. Moreover, we can apply the one-step decoding method even if we do not have direct access to $\mathbf{A}$ but can compute matrix-vector product $\mathbf{A}{\bf x}$. The one-step decoding method allows us to avoid putting the entire matrix $\mathbf{A}$ in to memory of the master compute node in settings where this is not possible.

It is straightforward to see that if ${\bf v}$ is the optimal decoding vector of $\mathbf{A}$, then $\|{\bf v}-{\bf 1}_{k}\|_{2}^{2}=\operatorname{err}(\mathbf{A})$. On the other hand, if ${\bf v}$ is the one-step decoding vector of $\mathbf{A}$ then $\|{\bf v}-{\bf 1}_{k}\|_{2}^{2}\geq\operatorname{err}(\mathbf{A})$. We define the one-step decoding error of $\mathbf{A}$ as follows.

For a given $\rho>0$, the one-step error of $\mathbf{A}$ is defined by

Fractional Repetition Codes

We would like to devise a code that achieves small error with high probability in the setting that our stragglers are chosen randomly. In fact, this can be achieved by the fractional repetition code (FRC) used in . Note that only considers this code for exact reconstruction of the gradient over all subsets of stragglers. This code can still be used when we only want approximately reconstruct the sum of $k$ gradients with high probability.

This scheme works by replicating certain tasks between compute nodes. Suppose that we have $k$ tasks and $k$ compute nodes and we want each compute node to compute $s$ tasks. Without loss of generality, we suppose that $s$ divides $k$. The assignment matrix ${\bf G}_{\text{frac}}$ for this scheme is then defined by

We assume that the $k\times r$ matrix ${\bf A}_{\text{frac}}$ of non-stragglers has columns that are sampled uniformly without replacement from the $k$ columns of ${\bf G}_{\text{frac}}$. We first compute the expected one-step decoding error. Let ${\bf a}_{i}$ denote column $i$ of ${\bf A}_{\text{frac}}$.

Fix ${\bf a}_{i}$. Since ${\bf a}_{i}$ has $s$ non-zero entries that are all $1$, ${\bf a}_{i}^{T}{\bf a}_{i}=s$. Next, suppose $j\neq i$. By the construction of ${\bf G}_{\text{frac}}$, there are only $s-1$ columns of ${\bf G}_{\text{frac}}$ that are not orthogonal to ${\bf a}_{i}$. Note that ${\bf a}_{j}$ is a duplicate of ${\bf a}_{i}$ with probability $\frac{s-1}{k}$. If this holds, then ${\bf a}_{i}^{T}{\bf a}_{j}=s$, and it is 0 if this does not hold. Therefore, for $i\neq j$,

Setting $\rho=\frac{k}{rs}$ in the one-step decoding method, we have

Between step 1 and step 2 we used the fact that the columns of $\mathbf{A}_{\text{frac}}$ all have $s$ non-zero entries so ${\bf 1}_{k}^{T}\mathbf{A}_{\text{frac}}=s{\bf 1}_{r}$. Applying Lemma 4,

Next, we consider the optimal decoding error of $\mathbf{A}_{\text{frac}}$. Note that each column of $\mathbf{A}_{\text{frac}}$ must be equal to one of the following $k/s$ distinct vectors,

There are $s$ copies of each ${\bf v}_{i}$ in ${\bf G}_{\text{frac}}$ and $\mathbf{A}_{\text{frac}}$ has a set of columns given by sampling $r$ of these without replacement. It is straightforward to see that $\operatorname{err}(\mathbf{A}_{\text{frac}})=\alpha s$, where $\alpha$ is the number of $i$ such that ${\bf v}_{i}$ is not a column of $\mathbf{A}_{\text{frac}}$.

Let $Y_{1},\ldots,Y_{k/s}$ denote the random variables where $Y_{i}$ indicates whether ${\bf v}_{i}$ is not a column of $\mathbf{A}$. Note that we then have

Each $Y_{i}$ is 1 iff none of the $s$ columns in the $i$th block of ${\bf G}_{\text{frac}}$ are sampled as part of the $r$ non-stragglers. Therefore,

Combining (3.1) and (3.2), we get the following theorem.

We would now like high-probability bounds on $\operatorname{err}(\mathbf{A})$. By (3.1), this reduces to bounding how many of the $Y_{i}$ are non-zero. This can be done via standard techniques concerning with-replacement sampling.

Fix $T\subseteq\{1,2,\ldots,k/s\}$ such that $|T|=\alpha+1$. Then

Note that the probability that we have no more than $\alpha$ of the ${\bf v}_{i}$ missing from the columns of $\mathbf{A}$ is the probability that $\operatorname{err}(\mathbf{A}_{\text{frac}})\leq\alpha s$. Therefore,

While this exact expression is complicated, this result easily shows that if $s=\Omega(\log(k))$, then with probability at least $1-\frac{1}{k}$, $\operatorname{err}(\mathbf{A})$ is relatively small. Recall that the number of non-stragglers $r=(1-\delta)k$ for $\delta\in(0,1)$.

We wish to show that for $s\geq(1+\frac{1}{1+\alpha})\log(k)/(1-\delta)$, the right-hand side of this equation is at most $\frac{1}{k}$. Manipulating, this is equivalent to $s$ satisfying

Since $s\geq(1+\frac{1}{1+\alpha})\log(k)/(1-\delta)$, we have

Letting $\beta=(\alpha+2)\log(k)/r$, (3.4) implies that (3.3) holds if

Since this occurs for all $\beta\geq 0$, the desired result is shown.∎

Theorem 8 implies that with probability at least $1-\frac{1}{k}$, an FRC will have multiplicative error $\epsilon$ where

Therefore, this implies Theorem 1. While FRCs have demonstrably small optimal decoding error when the stragglers are selected randomly, we will later show that it does not perform well when the stragglers are selected adversarially. In order to improve our tolerance to adversarial stragglers, we will develop a coding scheme based on random graphs.

Adversarial Stragglers

While FRCs have small average-case error, their worst-case error is large. Even worse, it is computationally efficient to find these worst-case straggler sets. In fact, they can be found in linear time in the number of compute nodes. Recall that the assignment matrix ${\bf G}_{\text{frac}}$ for FRC is defined by

As previously noted, each column of $\mathbf{A}_{\text{frac}}$ has $k/s$ distinct possibilities,

Furthermore, the optimal decoding error increases by $s$ if and only if all of the columns in one of the $k/s$ blocks of ${\bf G}_{\text{frac}}$ are all stragglers. Therefore, if one were to select $k-r$ stragglers adversarially, they would pick all of the $s$ columns from one block, then all of the $s$ columns from another block, and continue until they had selected $k-r$ stragglers. This corresponds to picking $r$ non-stragglers corresponding to every column of $r/s$ of the blocks in ${\bf G}_{f}rac$. Here, we assume that $s$ divides $r$ for simplicity.

If ${\bf G}_{f}rac$ is given as in (4.1), then we can simply select the first $r$ columns of ${\bf G}_{\text{frac}}$ to be non-stragglers. If ${\bf G}_{\text{frac}}$ is permuted, then we can simply select all columns corresponding to $r/s$ blocks. There are therefore $(k-r)/s$ blocks missing from $\mathbf{A}$. Each contributes $s$ to the optimal decoding error. This implies that we have an overall error of $k-r$. The argument above shows that this is the worst-case error possible.

Note that the adversary can find this set in $O(k)$ operations if they have full-knowledge that an FRC scheme is being used with presentation as in (4.1). Even if they do not have this knowledge, an adversary can check for this coding scheme and find the worst-case straggler set in $O(k^{2})$ operations if they only have access to the matrix ${\bf G}_{\text{frac}}$. This implies the following theorem.

Suppose that we assign tasks using a Fractional Repetition Code. In the worst-case, the non-straggler matrix $\mathbf{A}$ will satisfy

Moreover, worst-case straggler sets can be found in quadratic time.

Suppose that $r=(1-\delta)k$ for some constant $\delta$. Then, the adversarial optimal decoding error is $\Theta(k)$. This is in stark contrast to Theorem 8, which shows that if the stragglers are selected randomly and $s=\Omega(\log k)$, then with high probability $\operatorname{err}(\mathbf{A})=O(\log k)$. Also note that since $\operatorname{err}_{1}(\mathbf{A})\geq\operatorname{err}(\mathbf{A})$, the adversarial one-step decoding error is $\Omega(k-r)$.

2 Adversarial Straggler Selection is NP-hard

In this section, we show that in general, adversarial straggler selection is NP-hard. This demonstrates that adversaries with polynomial-time computations may not be able to find a set of stragglers that maximizes the decoding error. In such cases, the average-case error may be a more useful indicator of how well a gradient code performs.

To show that general adversarial selection is NP-hard, we first define two problems.

The $k$-densest subgraph problem (D$k$S) asks, given a graph $(V,E)$, what $k$-vertex subgraph contains the most edges.

As shown in , this problem is NP-hard, even if we restrict to regular graphs. We now formally define the adversarial straggler problem.

Fix a constant $\rho>0$. The $r$-adversarial straggler problem ($r$-ASP) asks, given a square matrix ${\bf G}\in{}^{n\times n}$, which column-submatrix ${\bf A}$ maximizes

Note that this is the form that one-step decoding takes. We will show that for any $\rho\in(0,\frac{2}{3})$, this problem is NP-hard, even when we restrict to ${\bf G}\in\{0,1\}^{k\times k}$ with at most $s$ non-zero entries in each column.

For any $\rho\in(0,\frac{2}{3})$, the adversarial straggler problem is NP-hard. This holds even if we restrict to matrices ${\bf G}\in{}^{k\times k}$ with entries in $\{0,1\}$ and at most $s\geq 2$ non-zero entries per column.

In fact, the proof of our theorem also shows that if we instead consider all matrices ${\bf G}\in{}^{k\times n}$ where $k\geq n$, then $r$-ASP is NP-hard for any $\rho>0$.

We will give a reduction from D$k$S on $d$-regular graphs to $r$-ASP where ${\bf G}$ is boolean with at most $d$ non-zero entries per column.

Let $(V,E)$ be a $d$-regular graph on $n$ vertices. Note that $|E|=nd$. We want to solve D$k$S for $(V,E)$. Let ${\bf M}$ denote the adjacency matrix of $(V,E)$. Note that D$k$S is equivalent to

Let ${\bf B}$ denote the unsigned incidence matrix of $(V,E)$. That is, ${\bf B}$ is a $|E|\times|V|$ boolean matrix where the row corresponding to edge $e$ has a $1$ in column $v$ iff $e$ is incident to $v$. We will let ${\bf C}$ denote the $|E|\times|E|$ matrix given by adding $|E|-|V|=n(d-1)$ zero columns to ${\bf B}$. Note that ${\bf C}$ is a square $nd\times nd$ boolean matrix with at most $d$ non-zero entries in each column since $(V,E)$ is $d$-regular.

Let $r=k+(n-1)d$. Consider $r$-ASP on ${\bf C}$. This is equivalent to finding a vector ${\bf x}\in\{0,1\}^{|E|}$ with $\|{\bf x}\|_{0}=r$ that maximizes

Let ${\bf x}=\begin{pmatrix}{\bf y}\\ {\bf z}\end{pmatrix}$ where ${\bf y}\in\{0,1\}^{n},{\bf z}\in\{0,1\}^{n(d-1)}$. Note that ${\bf y}$ corresponds to which of the columns of ${\bf B}$ we select, while ${\bf z}$ corresponds to columns of ${\bf 0}$ we select. Recall that $\|{\bf y}\|_{0}+\|{\bf z}\|_{0}=r=t+n(d-1)$.

Note that ${\bf B}^{T}{\bf B}={\bf M}+{\bf I}d$. This implies

Therefore, $r$-ASP in this setting is equivalent to maximizing, over ${\bf y}\in\{0,1\}^{n},{\bf z}\in\{0,1\}^{n(d-1)}$ such that $\|{\bf y}\|_{0}+\|{\bf z}\|_{0}=r=k+n(d-1)$, the quantity

Note that if we fix a binary ${\bf y}$ such that $\|{\bf y}\|_{0}=a$, then

Therefore, maximizing this quantity corresponds to finding the $a$-densest subgraph of $(V,E)$. We now must show that when we maximize this over ${\bf y}$ and ${\bf z}$, then the solution will always have $\|{\bf y}\|_{0}=k$. Since $r=k+n(d-1)$, it suffices to show that ${\bf y}$ is as sparse as possible.

To show that this is the case, we will show that for $\rho\in(0,\frac{2}{3})$, increasing the sparsity of ${\bf y}$ by 1 will only decrease the objective function. Suppose that $\|{\bf y}\|_{0}=a$ and it has support $S$. Say that ${\bf y}^{\prime}$ satisfies $\|{\bf y}^{\prime}\|_{0}=a+1$ and it has support $S^{\prime}$ where $S\subseteq S^{\prime}$. Let $T,T^{\prime}$ denote the vertex subgraphs of $(V,E)$ corresponding to $S,S^{\prime}$, and let $e(S),e(S^{\prime})$ denote the number of edges in these subgraphs. Note that ${\bf y}^{T}{\bf M}{\bf y}=2e(S)$. We then have

Note that since $(V,E)$ is $d$-regular, $e(S^{\prime})\leq e(S)+d$. Therefore,

For $\rho\in(0,\frac{2}{3})$, this quantity is negative. Therefore, increasing the sparsity of ${\bf y}$ will decrease the objective function $f({\bf y})$. Therefore, the maximum of the $r$-ASP problem applied to ${\bf C}$ will have ${\bf y}$ as sparse as possible. Since $r=k+n(d-1)$ and $\|{\bf z}\|_{0}\leq n(d-1)$, this implies that the maximum occurs at $\|{\bf y}\|_{0}=k$. Let $S$ denote the support of ${\bf y}$. The objective function in (4.2) is then equal to

This is clearly maximized when $S$ is the set of vertices forming the densest $k$-subgraph.∎

Bernoulli Gradient Codes

In this section we will consider the case that ${\bf G}$ has entries that are Bernoulli random variables. For a given $s,k$, we will refer to the Bernoulli coding scheme as setting, for $i\in\{1,\ldots,k\},j\in\{1,\ldots,n\}$, ${\bf G}_{i,j}=\text{Bernoulli}(s/k)$. Intuitively, by injecting randomness in to the construction of ${\bf G}$, we improve our tolerance to adversarial stragglers. This comes as the cost of worse average-case error. While shows that if ${\bf G}$ is a Ramanujan graph then we have strong bounds on its adversarial decoding error, such graphs are notoriously tricky to compute. By using Bernoulli coding, we sacrifice a small amount of error in order to achieve a much simpler, efficiently computable coding scheme.

Suppose that the stragglers are selected uniformly at random. Then, the non-straggler submatrix $\mathbf{A}$ also has Bernoulli random entries. Note that the expected number of tasks assigned to each compute node is $s$. This construction will allow us to derive high-probability bounds on the decoding error for $s>\log(k)$. We will later show that we can enforce the desired sparsity $s$ of each column and maintain the same error. Moreover, enforcing this desired sparsity will let us extend these error bounds to the setting where $s<\log(k)$. In order to get a handle on the decoding error, we first develop a method to bound the optimal and one-step decoding errors.

Suppose we have a function assignment matrix ${\bf G}$ such that the sparsity of each column is exactly or approximately bounded by $s$. After performing the local computations on each compute node, we have access to a $k\times r$ submatrix $\mathbf{A}$ of the $r$ non-stragglers. We assume that $r=(1-\delta)k$ for some $\delta\geq 0$.

We would like to derive high probability bounds on $\operatorname{err}(\mathbf{A})$ in order to bound the optimal decoding error of $\mathbf{A}$, as in (2.3). Unfortunately, it is not straightforward to directly bound this error for a random matrix $\mathbf{A}$ since it involves the pseudo-inverse of $\mathbf{A}$. Instead, we will use an algorithmic approach to bound the optimal decoding error with high probability. The following lemma is adapted from .

Let ${\bf u}_{0}={\bf 1}_{k}$, and define

Moreover, for all $t$, $\|{\bf u}_{t}\|_{2}^{2}\geq\operatorname{err}(\mathbf{A})$.

We refer to the ${\bf u}_{t}$ as the algorithmic decoding error of $\mathbf{A}$. To prove Lemma 12, we will use the following lemma, adapted from .

If ${\bf u}$ is in the column span of $\mathbf{A}$ and $\nu\geq\|\mathbf{A}\|_{2}^{2}$ then

Fix some $t\geq 1$. We can decompose ${{\bf 1}_{k}}$ as ${\bf v}+{\bf w}$ where ${\bf v}$ is the orthogonal projection of ${\bf 1}_{k}$ on to the column span of $\mathbf{A}$ and ${\bf w}$ is in the nullspace of $\mathbf{A}^{T}$. Note that this implies that $({\bf I}-\mathbf{A}\mathbf{A}^{T}/\nu){\bf w}={\bf w}$. Therefore,

Since ${\bf v}$ is in the span of $\mathbf{A}$, $\left({\bf I}-\frac{\mathbf{A}\mathbf{A}^{T}}{\nu}\right)^{t}{\bf v}$ is also in the span of $\mathbf{A}$ and orthogonal to ${\bf w}$. By Lemma 13,

By construction, $\|{\bf w}\|_{2}^{2}=\min_{{\bf x}}\|\mathbf{A}{\bf x}-{\bf 1}_{k}\|_{2}^{2}$, completing the proof.∎

Note that the ${\bf u}_{t}$ are defined as the iterates of projected gradient descent. Consider the setting where $\nu=\|\mathbf{A}\|_{2}^{2}$. The matrix ${\bf P}=\mathbf{A}\mathbf{A}^{T}/\|\mathbf{A}\|_{2}^{2}$ is a projection operator (ie. ${\bf P}^{2}={\bf P}$), and it projects a vector on to the column-span of $\mathbf{A}$. By letting ${\bf u}_{t}={\bf u}_{t-1}-{\bf P}{\bf u}_{t-1}$, Lemma 12 one can show that this eventually converges to ${\bf u}_{0}-\mathbf{A}\mathbf{A}^{+}{\bf u}_{0}$. In other words, we eventually converge to the component of ${\bf u}_{0}$ that is orthogonal to the range of $\mathbf{A}$. Taking ${\bf u}_{0}={\bf 1}_{k}$, this eventually converges to $\operatorname{err}(\mathbf{A})$.

We can better understand ${\bf u}_{t}$ by taking a combinatorial view. Note that $\mathbf{A}$ encodes a bipartite graph with $k$ left vertices and $r$ right vertices, where $\mathbf{A}_{ij}$ is 1 iff there is an edge between vertex $i$ on the left and vertex $j$ on the right. Column $j$ of $\mathbf{A}$ corresponds to the incidence of the $j$th right vertex. In particular, the degree of vertex $j$ on the right equal the number of tasks computed by compute node $j$. We can compute $\|{\bf u}_{t}\|_{2}^{2}$ in terms of walks on this bipartite graph.

${\bf 1}_{k}^{T}(\mathbf{A}\mathbf{A}^{T})^{t}{\bf 1}_{k}$ equals the number of paths of length $2t$ from a left vertex to a right vertex.

Note that $(\mathbf{A}\mathbf{A}^{T})_{ij}$ is the number of paths of length 2 from the vertex $i$ to vertex $j$, where $i,j$ are both left vertices. More generally, $(\mathbf{A}\mathbf{A}^{T})^{t}_{ij}$ counts the weighted number of paths of length $2t$ from vertex $i$ to vertex $j$. Therefore, ${\bf 1}_{k}(\mathbf{A}\mathbf{A}^{T})^{t}{\bf 1}_{k}$ is the weighted number of paths of length $2t$ from a left vertex to a left vertex.∎

Let $a_{t}$ denote the weighted number of walks in the associated bipartite graph of $\mathbf{A}$ of length $2t$ starting and ending at a left vertex. Then

While ${\bf u}_{t}$ may be difficult to bound for sufficiently large $t$, we can handle ${\bf u}_{1}$ more directly. Moreover, as theory and simulations will show, even ${\bf u}_{1}$ will give us good bounds on $\operatorname{err}(\mathbf{A})$.

2 One-step Error of Bernoulli Gradient Codes

This approach is analogous to bounding ${\bf u}_{1}$, as the following lemma shows.

Recall that for a given $\nu$, ${\bf u}_{1}$ is given by

Suppose we have a random Erdős-Rényi graph $G(n,p)$ with adjacency matrix ${\bf B}$ where $np\geq\log(n)$. For any $\alpha\geq 1$ there exists a universal constant $C_{1}=C_{1}(\alpha)$ such that with probability at least $1-n^{-\alpha}$,

More generally, assume that ${\bf B}$ is a $n\times n$ adjacency matrix where ${\bf B}_{i,j}$ is Bernoulli with probability $p_{i,j}$. This is sometimes referred to as the inhomogeneous Erdős-Rényi model $G(n,(p_{i,j}))$. Let $p=\max_{i,j}p_{i,j}$. As discussed in , Lemma 18 extends to this setting using this definition of $p$ (see section 1.1). While this result applies directly to $n\times n$ adjacency matrices, we can easily extend this to $\mathbf{A}$. This will first require a basic lemma about the spectral norm of a structured block matrix.

Let ${\bf D}$ be a $n_{1}\times n_{2}$ matrix. Suppose that ${\bf C}$ is a $n\times n$ block matrix of the form

Standard properties of singular values imply that $\|{\bf D^{T}D}\|_{2}=\|{\bf DD^{T}}\|_{2}=\|{\bf D}\|_{2}^{2}$. Moreover,

Since the eigenvalues of a block diagonal matrix are given by the eigenvalues of all the blocks,

Let $\mathbf{A}$ be a $k\times r$ matrix where $k\geq r$ and $\mathbf{A}_{i,j}$ is Bernoulli with probability $s/k$. Then for all $\alpha\geq 1$, there exists a universal constant $C_{2}=C_{2}(\alpha)$ such that with probability at least $1-(k+r)^{-\alpha}$,

$\mathbf{A}$ encodes the structure of a bipartite graph with $k+r$ vertices. After relabeling, we can denote these vertices as $v_{1},\ldots,v_{k},v_{k+1},\ldots,v_{k+r}$ where the bipartite blocks are given by $\{v_{1},\ldots,v_{k}\},\{v_{k+1},\ldots,v_{k+r}\}$. The adjacency matrix ${\bf B}$ is therefore of the form

Note that ${\bf B}$ comes from an inhomogeneous Erdős-Rényi graph $G(k+r,(p_{i,j}))$ where $p_{i,j}$ is zero if $i$ and $j$ are both in $\{1,\ldots,k\}$ or $\{k+1,\ldots,k+r\}$, and $s/k$ otherwise. Therefore, $p=\max_{i,j}p_{i,j}=s/k$. By Lemma 18 (and the discussion following it), for all $\alpha>0$ there exists some universal constant $C_{1}=C_{1}(\alpha)$ such that with probability at least $1-(k+r)^{-\alpha}$,

This last equality holds by Lemma 19. Taking $C_{2}=\sqrt{2}C_{1}$ we conclude the proof.∎

Combining this with Lemma 16, we get the following theorem.

Suppose that $s\geq\log(n)$. Then for any $\alpha\geq 1$, there is a universal constant $C_{2}=C_{2}(\alpha)$ such that for $\rho=\frac{k}{rs}$, with probability at least $1-(k+r)^{-\alpha}$,

Empirically, the same bound holds for other methods of generating $\mathbf{G}$. If we choose the non-zero support of each column by selecting $s$ indices with or without replacement from $\{1,\ldots,k\}$, then we conjecture that the same theorem holds. Unfortunately, standard concentration inequalities are not enough to prove this result in such settings.

3 Regularized Bernoulli Gradient Codes

Both of these issues have the same cause: vertices whose degree is too large. Fortunately, this issue of enforcing concentration of sparse graphs has been studied and partially resolved in . They show that by appropriate regularization of graphs, we can improve their concentration in the sparse setting.

Let ${\bf B}$ be a random graph from the inhomogeneous Erdős-Rényi model $G(n,(p_{i,j}))$ and let $p=\max_{i,j}p_{i,j}$. For any $\alpha\geq 1$, the following holds with probability at least $1-n^{-\alpha}$. Take all vertices of ${\bf B}$ with degree larger than $2np$ and reduce the weights of the edges incident to those vertices in any way such that they have degree at most $np$. Let $\mathbf{B}^{\prime}$ denote the resulting graph. Then

Here $C_{3}$ is a universal constant. Note that this regularization can be performed analogously on $\mathbf{A}$. To form $\mathbf{A}^{\prime}$, we simply look at all columns with degree more than $2s$ and change entries in those columns from $1$ to until these columns have degree $s$. This satisfies the criterion in the above theorem. We can then use an almost identical version of the proof of Theorem 20 to prove the following theorem.

There is a universal constant $C_{4}=C_{4}(\alpha)$ such that for any $\alpha\geq 1$, $s\geq 1$, with probability at least $1-(k+r)^{-\alpha}$,

We can combine this with Lemma 16 to derive the following theorem concerning $\operatorname{err}(\mathbf{A}^{\prime})$. As before, this bound applies for both the one-step decoding and the optimal decoding.

For any $\alpha\geq 1,s\geq 1$, and letting $\rho=\frac{k}{rs}$, with probability at least $1-(k+r)^{-\alpha}$,

By regularizing in the above manner, we ensure that each compute node computes at most $2s$ tasks and that our error bound works for all $s$. Note that in practice, we cannot form $\mathbf{A}^{\prime}$ from $\mathbf{A}$ as we don’t know $\mathbf{A}$ a priori. Therefore we cannot tell the compute nodes to compute the functions corresponding to $\mathbf{A}^{\prime}$. Instead, we can regularize $\mathbf{G}$ in the same manner to obtain $\mathbf{G}^{\prime}$ in the following way such that we can apply Theorem 24 above. We refer to this code as the regularized Bernoulli Gradient Code, (rBGC).

The construction is simple. We initialize ${\bf G}$ with each entry Bernoulli$(s/k)$. For each column $j$ with more than $2s$ non-zero entries, we randomly set entries to 0 until it has $s$ non-zero entries. A detailed algorithm is provided below.

Note that the error incurred by an rBGC corresopnds to a multiplicative error $\epsilon$ where

Simulations

In this section we compare the empirical decoding error of Fractional Repetition Codes (FRCs) and Bernoulli Gradient Codes (BGC). Recall that we gave two decoding methods, one that corresponding to the optimal decoding error

and one corresponding to the one-step decoding error

We compare FRCs and BGCs to a coding scheme proposed in . There, Raviv et al. consider the scheme where ${\bf G}$ is the adjacency matrix of an $s$-regular expander graph with $k$ vertices. They show that for all $k\times r$ submatrices $\mathbf{A}$,

Here, $\lambda({\bf G})=\max\{|\lambda_{2}|,|\lambda_{k}|\}$, where the eigenvalues of ${\bf G}$ are given by

We would like to construct ${\bf G}$ to have $\lambda({\bf G})$ as small as possible. This is achieved by Ramanujan graphs. In practice, constructing expander graphs with small values of $\lambda$ is difficult. By taking a random $s$-regular graph, however, we can obtain can expander graph with high probability . As $k\to\infty$, $\lambda$ tends to the optimal value. In order to generate empirical data, we consider the setting where ${\bf G}$ is the adjacency matrix of a random $s$-regular graph.

Below, we plot the one-step and optimal decoding error $\operatorname{err}(\mathbf{A})$ and $\operatorname{err}_{1}(\mathbf{A})$ for these three schemes when $k=100$ and the fraction of stragglers $\delta$ varies. In order to normalize the error, we plot $\operatorname{err}(\mathbf{A})/k$ and $\operatorname{err}_{1}(\mathbf{A})/k$. We take $\rho=\frac{k}{rs}$ in the one-step decoding.

We see that under one-step decoding, FRCs and $s$-regular expanders perform extremely comparably. In this setting, BGCs seem to sacrifice some accuracy for simplicity. However, FRCs are also computationally simple and perform as well as taking $s$-regular expanders in the average case under one-step decoding. For optimal decoding, FRCs perform significantly better than $s$-regular expanders or BGCs, as the following plots show.

These plots show that if we instead consider optimal decoding, then FRCs greatly outperform the other two methods. In particular, FRCs can achieve zero optimal decoding error even with a non-trivial fraction of stragglers. If $s=10$, then we can achieve close to zero error even with half of the compute nodes being stragglers.

Finally, we compare the one-step and optimal decoding error for the BGCs, FRCs, and $s$-regular graphs. The results are plotted below.

2 Algorithmic Decoding Error of Bernoulli Gradient Codes

In this section we give empirical one-step error rates of BGCs for varying sizes of $r$ and sparsity $s$ of the matrix $\mathbf{A}$ . Recall that we defined the algorithmic decoding error of $\mathbf{A}$ by a sequence of vectors ${\bf u}_{t}$. Here, $\|{\bf u}_{1}\|_{2}^{2}$ corresponds to the one-step decoding error, while $\|{\bf u}_{t}\|_{2}^{2}$ converges to the optimal decoding error.

Let ${\bf G}$ be constructed via a BGC. We fix $k=100$ and take varying values of $\delta$ and $s$, letting $r=(1-\delta)k$. We then calculate the average value of $\|{\bf u}_{t}\|_{2}^{2}/k$ based on a Monte Carlo simulation for increasing values of $t$. We set $\rho=\|\mathbf{A}\|_{2}^{2}$. The results are below.

Conclusion and Open Problems

In this work, we formally described the approximate gradient coding problem and gave two different decoding methods for such codes. We analyzed two efficiently computable gradient codes, FRCs and BGCs, and gave explicit bounds for their decoding error. While FRCs exhibit extremely low average-case error, they are susceptible to adversaries, even polynomial-time adversaries. This is in contrast to our result that adversarial straggler selection is NP-hard. BGCs are constructed via sparse random graphs and are potentially less susceptible to polynomial-time adversaries.

While the problem of approximate gradient coding can be stated in relatively simple terms, our work shows that the problem is not simple. Bounding the error of gradient codes, even relatively straightforward codes such as BGCs, can be an arduous task. This is especially true in the context of optimal decoding error. Still, approximate gradient codes have exciting connections to coding theory, concentration of random graphs, expander graphs, and many other interesting combinatorial and algebraic objects. This work is intended to be a starting point towards understanding the approximate gradient coding problem. There are many remaining open problems, some directly continuing this work, others more tangentially related.

Tighter bounds on the optimal decoding error: For both BGCs and $s$-regular expander graphs, our empirical results show that there is a significant gap between the one-step and the optimal decoding error. So far, the only known results on the error of these codes concern their one-step decoding error. Better bounds on their optimal decoding error and, more generally, better methods for bounding the optimal decoding error would have great implications for the analysis and design of gradient codes. Unfortunately, such bounds are not straightforward. They require greater care and may require analysis of second- and higher-order moments or a better understanding of the pseudo-inverse of random matrices.

Algorithmic error and weighted walk counting: One potential method towards better bounds on the optimal decoding error comes from Lemma 12 above. As we show, one can bound the optimal decoding error by a weighted alternating sum involving the number of walks on a bipartite graph. Tight bounds on the number of walks in a random bipartite graph or deterministic constructions for bipartite graphs with more explicit fomrulas for the number of walks could lead to much better bounds on the error.

Approximate gradient coding capacity: Our work gives deterministic and randomized codes that achieve varying worst-case and average-case errors. In general, we know very little about how these error rates behave. One can ask: what is the information theoretic limit of an approximate gradient code, e.g., what is the optimal tradeoff between the recovery error, the probability of recovery, and the sparsity of the code?

Acknowledgements

The first author was supported in part by the National Science Foundation grant DMS-1502553.

References