Gradient Coding

Introduction

We propose a novel coding theoretic framework for mitigating stragglers in distributed learning. The central idea can be seen through the simple example of Figure 1: Consider synchronous Gradient Descent (GD) on three workers ($W_{1}$,$W_{2}$,$W_{3}$). The baseline vanilla system is shown in the left figure and operates as follows: The three workers have different partitions of the labeled data stored locally ($D_{1}$,$D_{2}$,$D_{3}$) and all share the current model. Worker 1 computes the gradient of the model on examples in partition $D_{1}$, denoted by $g_{1}$. Similarly, Workers 2 and 3 compute $g_{2}$ and $g_{3}$. The three gradient vectors are then communicated to a central node (called the master/aggregator) $A$ which computes the full gradient by summing these vectors $g_{1}+g_{2}+g_{3}$ and updates the model with a gradient step. The new model is then sent to the workers and the system moves to the next round (where the same examples or other labeled examples, say $D_{4}$,$D_{5}$,$D_{6}$, will be used in the same way).

The problem is that sometimes worker nodes can be stragglers (Li et al., 2014; Ho et al., 2013; Dean et al., 2012) i.e. delay significantly in computing and communicating gradient vectors to the master. This is especially pronounced for cheaper virtual machines in the cloud. For example on t2.micro machines on Amazon EC2, as can be seen in Figure 2: some machines can be $5\times$ slower in computing and communicating gradients compared to typical performance.

First, we discuss one way to resolve this problem if we replicate some data across machines by considering the placement in Fig.1 (b) but without coding. As can be seen, in Fig. 1 (b) each example is replicated two times using a specific placement policy. Each worker is assigned to compute two gradients on the two examples they have for this round. For example, $W_{1}$ will compute vectors $g_{1}$ and $g_{2}$. Now let’s assume that $W_{3}$ is the straggler. If we use control messages, $W_{1},W_{2}$ can notify the master $A$ that they are done. Subsequently, if feedback is used, the master can ask $W_{1}$ to send $g_{1}$ and $g_{2}$ and $W_{2}$ to send $g_{3}$. These feedback control messages can be much smaller than the actual gradient vectors but are still a system complication that can cause delays. However, feedback makes it possible for a centralized node to coordinate the workers, thereby avoiding stragglers. One can also reduce network communication further by simply asking $W_{1}$ to send the sum of two gradient vectors $g_{1}+g_{2}$ instead of sending both. The master can then create the global gradient on this batch by summing these two vectors. Unfortunately, which linear combination must be sent depends on who is the straggler: If $W_{2}$ was the straggler then $W_{1}$ should be sending $g_{2}$ and $W_{3}$ sending $g_{1}+g_{3}$ so that their sum is the global gradient $g_{1}+g_{2}+g_{3}$.

In this paper we show that feedback and coordination is not necessary: every worker can send a single linear combination of gradient vectors without knowing who the straggler will be. The main coding theoretic question we investigate is how to design these linear combinations so that any two (or any fixed number generally) contain the $g_{1}+g_{2}+g_{3}$ vector in their span. In our example, in Fig. 1(b), $W_{1}$ sends $\frac{1}{2}g_{1}+g_{2}$, $W_{2}$ sends $g_{2}-g_{3}$ and $W_{3}$ sends $\frac{1}{2}g_{1}+g_{3}$. The reader can verify that $A$ can obtain the vector $g_{1}+g_{2}+g_{3}$ from any two out of these three vectors. For instance, $g_{1}+g_{2}+g_{3}=2\left(\frac{1}{2}g_{1}+g_{2}\right)-\left(g_{2}-g_{3}\right)$. We call this idea gradient coding.

We consider this problem in the general setting of $n$ machines and any $s$ stragglers. We first establish a lower bound: to compute gradients on all the data in the presence of any $s$ stragglers, each partition must be replicated $s+1$ times across machines. We propose two placement and gradient coding schemes that match this optimal $s+1$ replication factor. We further consider a partial straggler setting, wherein we assume that a straggler can compute gradients at a fraction of the speed of others, and show how our scheme can be adapted to such scenarios. All proofs can be found in the appendix.

We also compare our scheme with the popular ignoring the stragglers approach (Chen et al., 2016): simply doing a gradient step when most workers are done. We see that while ignoring the stragglers is faster, this loses some data which can hurt the generalization error. This can be especially pronounced in supervised learning with unbalanced labels or heavily unbalanced features since a few examples may contain critical, previously unseen information.

In Figure 2, we show the average time required for 50 t2.micro Amazon EC2 instances to communicate gradients to a single master machine (a c3.8xlarge instance). We observe that a few worker machines incurred a communication delay of up to $5\times$ the typical behavior. Interestingly, throughout the timescale of our experiments (a few hours), the straggling behavior was consistent in the same machines.

We have also experimented extensively with other Amazon EC2 instances: Our finding is that cheaper instance types have significantly higher variability in performance. This is especially true for t2 type instance which on AWS are described as having Burstable Performance. Fortunately, these machines have very low cost.

The choices of the number and type of workers used in training big models ultimately depends on total cost and time needed until deployment. The main message of this paper is that going for very low-cost instances and using coding to mitigate stragglers, may be a sensible choice for some learning problems.

2 Related Work

The slow machine problem is the Achilles heel of many distributed learning systems that run in modern cloud environments. Recognizing that, some recent work has advocated asynchronous approaches (Li et al., 2014; Ho et al., 2013; Mitliagkas et al., 2016) to learning. While asynchronous updates are a valid way to avoid slow machines, they do give up many other desirable properties, including faster convergence rates, amenability to analysis, and ease of reproducibility and debugging.

Attacking the straggling problem in synchronous machine learning algorithms has surprisingly not received much attention in the literature. There do exist general systems solutions such as speculative execution Zaharia et al. (2008) but we believe that approaches tailored to machine learning can be vastly more efficient. In Chen et al. (2016) the authors use synchronous minibatch SGD and request a small number of additional worker machines so that they have an adequate minibatch size even when some machines are slow. However, this approach does not handle well machines that are consistently slow and the data on those machines might never participate in training. In Narayanamurthy et al. (2013) the authors describe an approach for dealing with failed machines by approximating the loss function in the failed partitions with a linear approximation at the last iterate before they failed. Since the linear approximation is only valid at a small neighborhood of the model parameters, this approach can only work if failed data partitions are restored fairly quickly.

The work of Lee et al. (2015) is the closest in spirit to our work, using coding theory and treating stragglers as erasures in the transmission of the computed results. However, we focus on codes for recovering the batch gradient of any loss function while Lee et al. (2015) and the more recent work of Dutta et al. (2016) describe techniques for mitigating stragglers in two different distributed applications: data shuffling and matrix multiplication. We also mention Li et al. (2016a), which investigates a generalized view of the coding ideas in Lee et al. (2015), showing that their solution is a single operating point in a general scheme of trading off latency of computation to the load of communication. Further closely related work has shown how coding can be used for distributed MapReduce, as well as a similar communication and computation tradeoff (Li et al., 2015, 2016b). All these prior works develop novel coding techniques, but do not code across gradient vectors in the way we are proposing in this paper.

Preliminaries

where $h_{R}$ is a gradient-based optimizer, which also depends on $R(\cdot)$. Several methods such as gradient descent, accelerated gradient, conditional gradient (Frank-Wolfe), proximal methods, LBFGS, and bundle methods fit in this framework. However, if the number of samples, $d$, is large, a computational bottleneck in the above update step is the computation of the gradient, $g$, whose computation can be distributed.

2 The General Setup

We can generalize the scheme in Figure 1(b) to $n$ workers and $k$ data partitions by setting up a system of linear equations:

Then, worker $W_{i}$ transmits $b_{i}\bar{g}$. Note that to transmit $b_{i}\bar{g}$, $W_{i}$ only needs to compute the partial gradients on the partitions in $\text{supp}(b_{i})$. Now, each row of $A$ is associated with a specific failure/straggler scenario, to which tolerance is desired. In particular, any row $a_{i}$, with support $\text{supp}(a_{i})$, corresponds to the scenario where the worker indices in $\text{supp}(a_{i})$ are alive/non-stragglers. Also, by the construction in Eq. (3), we have:

where $a_{i}(k)$ denotes the $k^{th}$ element of the row $a_{i}$. Thus, the entries of $a_{i}$ encode a linear combination which, when taken over the transmitted gradients of the alive/non-straggler workers, $\{b_{k}\bar{g}\}_{k\in\text{supp}(a_{i})}$, would yield the full gradient.

Going back to the example in Fig. 1(b), the corresponding $A$ and $B$ matrices under the above generalization are:

with $f=3,n=3,k=3$. It is easy to check that $AB=\mathbf{1}_{3\times 3}$. Also, since every row of $A$ here has exactly one zero, we say that this scheme is robust to any one straggler.

In general, we shall seek schemes, through the construction of $(A,B)$, which are robust to any $s$ stragglers.

The rest of this paper is organized as follows. In Section 3 we provide two schemes applicable to any number of workers $n$, under the assumption that stragglers can be arbitrarily slow to the extent of total failure. In Section 4, we relax this assumption to the case of worker slowdown (with known slowdown factor), instead of failure, and show how our constructions can be appended to be more effective. Finally, in Section 5 we present results of empirical tests using our proposed distribution schemes on Amazon EC2.

Full Stragglers

In this section, we consider schemes robust to any $s$ stragglers, given $n$ workers (with $s<n$). We assume that any straggler is (what we call) a full straggler i.e. it can be arbitrarily slow to the extent of complete failure. We show how to construct the matrices $A$ and $B$, with $AB=\mathbf{1}$, such that the scheme $(A,B)$ is robust to any $s$ full stragglers.

Consider any such scheme $(A,B)$. Since every row of $A$ represents a set of non-straggler workers, all possible sets over $[n]$ of size $(n-s)$ must be supports in the rows of $A$. Thus $f=\binom{n}{n-s}=\binom{n}{s}$ i.e. the total number of failure scenarios is the number of ways to choose $s$ stragglers out of $n$ workers. Now, since each row of $A$ represents a linear span over some rows of $B$, and since we require $AB=\mathbf{1}$, this leads us to the following condition on $B$:

Consider any scheme $(A,B)$ robust to any $s$ stragglers, given $n$ workers (with $s<n$). Then we require that for every subset $I\subseteq[n],\lvert I\rvert=n-s$:

where $\text{span}\{\cdot\}$ is the span of vectors.

The B-Span condition above ensures that the all $\mathbf{1}$s vector lies in the span of any $n-s$ rows of $B$. This is of course necessary. However, it is also sufficient. In particular, given a $B$ satisfying Condition 1, we can construct $A$ such that $AB=\mathbf{1}$, and $A$ has the support structure discussed above. The construction of $A$ is described in Algorithm 1 (in MATLAB syntax), and we have the following lemma.

Based on Lemma 1, to obtain a scheme $(A,B)$ robust to any $s$ stragglers, we only need to furnish a $B$ satisfying Condition 1. A trivial $B$ that works is $B=\mathbf{1}_{n\times k}$, the all ones matrix. However, this is wasteful since it implies that each worker gets all the partitions and computes the full gradient. Our goal is to construct $B$ satisfying Condition 1 while also being as sparse as possible in each row. In this regard, we have the following theorem, which gives a lower bound on the number of non-zeros in any row of $B$.

Consider any scheme $(A,B)$ robust to any $s$ stragglers, given $n$ workers (with $s<n$) and $k$ partitions. Then, if all rows of $B$ have the same number of non-zeros, we must have: $\left\lVert b_{i}\right\rVert_{0}\geq\frac{k}{n}(s+1)$ for any $i\in[n]$.

Theorem 1 implies that any scheme $(A,B)$ that assigns the same amount of data to all the workers must assign at least $\frac{s+1}{n}$ fraction of the data to each worker. Since this fraction is independent of $k$, for the remainder of this paper we shall assume that $k=n$ i.e. the number of partitions is the same as the number of workers. In this case, we want $B$ to be a square matrix satisfying Condition 1, with each row having at least $(s+1)$ non-zeros. In the sequel, we demonstrate two constructions for $B$ which satisfy Condition 1 and achieve the density lower bound.

In this section, we provide a construction for $B$ that works by replicating the task done by a subset of the workers. We note that this construction is only applicable when the number of workers, $n$, is a multiple of $(s+1)$, where $s$ is the number of stragglers we seek tolerance to. In this case, the construction is as follows:

We divide the $n$ workers into $(s+1)$ groups of size $(n/(s+1))$.

In each group, we divide all the data equally and disjointly, assigning $(s+1)$ partitions to each worker

All the groups are replicas of each other

When finished computing, every worker transmits the sum of its partial gradients

Thus, the first worker in the group gets the first $(s+1)$ partitions, the second worker gets the second $(s+1)$ partitions, and so on. Then, $B$ is simply $(s+1)$ replicated copies of $\overline{B}_{\text{block}}(n,s)$:

where for each $t\in\{1,\ldots,s+1\}$, $\overline{B}_{\text{block}}^{(t)}=\overline{B}_{\text{block}}(n,s)$.

It is easy to see that this construction can yield robustness to any $s$ stragglers. Since any particular partition of data is replicated over $(s+1)$ workers, any $s$ stragglers would leave at least one non-straggler worker to process it. We have the following theorem.

Consider $B_{frac}$ constructed as in Eq. (9), for a given number of workers $n$ and stragglers $s(<n)$. Then, $B_{frac}$ satisfies the B-Span condition (Condition 1). Consequently, the scheme $(A,B_{frac})$, with $A$ constructed using Algorithm 1, is robust to any $s$ stragglers.

The construction of $B_{frac}$ matches the density lower bound in Theorem 1 and, the above theorem shows that the scheme $(A,B_{frac})$, with $A$ constructed from Algorithm 1, is robust to $s$ stragglers.

2 Cyclic Repetition Scheme

In this section we provide an alternate construction for $B$ which also matches the lower bound in Theorem 1 and satisfies Condition 1. However, in contrast to construction in the previous section, this construction does not require $n$ to be divisible by $(s+1)$. Here, instead of assigning disjoint collections of partitions, we consider a cyclic assignment of $(s+1)$ partitions to the workers. We construct a $B=B_{cyc}$ with the following support structure:

where $\star$ indicates non-zero entries in $B_{cyc}$. So, the first row of $B_{cyc}$ has its first $(s+1)$ entries assigned as non-zero. As we move down the rows, the positions of the $(s+1)$ non-zero entries shift one step to the right, and cycle around until the last row.

Consider $B_{cyc}$ constructed using the randomized construction in Algorithm 2, for a given number of workers $n$ and stragglers $s(<n)$. Then, with probability $1$, $B_{cyc}$ satisfies the B-Span condition (Condition 1). Consequently, the scheme $(A,B_{cyc})$, with $A$ constructed using Algorithm 1, is robust to any $s$ stragglers.

Partial Stragglers

In this section, we revisit our earlier assumption of full stragglers. Under a full straggler assumption, Theorem 1 shows that any non-straggler worker must incur an $(s+1)$-factor overhead in computation, if we want to attain tolerance to any $s$ stragglers. This may be prohibitively huge in many situations. One way to mitigate this is by allowing at least some work to be done also by the straggling workers. Therefore, in this section, we consider a more plausible scenario of slow workers, but assume a known slowdown factor. We say that a straggler is an $\alpha$-partial straggler (with $\alpha>1$) if it is at most $\alpha$ slower than any non-straggler. This means that if a non-straggler completes a task in time $T$, an $\alpha$-partial straggler would require at most $\alpha T$ time to complete it. Now, we augment our previous schemes (in Section 3.1 and Section 3.2) to be robust to any $s$ stragglers, assuming that any straggler is an $\alpha$-partial straggler.

Note that our earlier constructions are still applicable: a scheme $(A,B)$, with $B=B_{frac}$ or $B=B_{cyc}$, would still provide robustness to $s$ partial stragglers. However, given that no machine is slower than a factor of $\alpha$, a more efficient scheme is possible by exploiting at least some computation on every machine. Our basic idea is to couple our earlier schemes with a naive distribution scheme, but on different parts of the data. We split the data into a naive component, and a coded component. The key is to do the split such that whenever an $\alpha$-partial straggler is done processing its naive partitions, a non-straggler would be done processing both its naive and coded partitions.

In general, for any $(n,s,\alpha)$, our two-stage scheme works as follows:

We split the data $\mathbf{D}$ into $n+n\frac{s+1}{\alpha-1}$ equal-sized partitions — of which $n$ partitions are coded components, and the rest are naive components

Each worker gets $\frac{s+1}{\alpha-1}$ naive partitions, distributed disjointly.

Each worker gets $(s+1)$ coded partitions, distributed according to an $(A,B)$ distribution scheme robust to $s$ stragglers (e.g. with $B=B_{frac}$ or $B=B_{cyc}$)

Any worker, $W_{i}$, first processes all its naive partitions and sends the sum of their gradients to the aggregator. It then processes its coded partitions, and sends a linear combination, as per the $(A,B)$ distribution scheme.

Note that each worker now has to send two partial gradients (instead of one, as in earlier schemes). However, a speedup gained in processing a smaller fraction of the data may mitigate this overhead in communication, since each non-straggler only has to process a $\frac{s+1}{n}\left(\frac{\alpha}{s+\alpha}\right)$ fraction of the data, as opposed to a $\frac{s+1}{n}$ fraction in full straggler schemes. Thus, when computation is the bottleneck, adopting a partial stragglers scheme may not hurt the overall efficiency. On the other hand, when communication is the bottleneck (and if a $2\times$ overhead is prohibitive), a full straggler scheme may be a better choice even with its (s+1)-factor overhead in computation for the non-straggler workers.

Fig. 4 illustrates our two-stage strategy for $n=3,s=1,\alpha=2$. We see that each non-straggler gets $4/9=0.44$ fraction of the data, instead of a $2/3=0.67$ fraction (for e.g. in Fig 1(b)).

Experiments

In this section, we present experimental results on Amazon EC2, comparing our proposed gradient coding schemes with baseline approaches. We compare our approaches against: $(1)$ the naive scheme, where the data is divided uniformly across all workers without replication and the aggregator waits for all workers to send their gradients, and $(2)$ the ignoring $s$ stragglers scheme where the data is divided as in the naive scheme, however the aggregator performs an update step after any $n-s$ workers have successfully sent their gradient.

We implemented all methods in python using MPI4py (Dalcin et al., 2011), an open source MPI implementation. Based on the method being considered, each worker loads a certain number of partitions of the data into memory before starting the iterations. In iteration $t$ the aggregator sends the latest model $\beta^{(t)}$ to all the workers (using Isend()). Each worker receives the model (using Irecv()) and starts a gradient computation. Once finished, it sends its gradient(s) back to the aggregator. When sufficiently many workers have returned with their gradients, the aggregator computes the overall gradient, performs a descent step, and moves on to the next iteration.

Our experiments were performed using two different worker instance types on Amazon EC2: m1.small and t2.micro — these are very small, very low-cost EC2 instances. We also observed that our system was often bottlenecked by the number of incoming connections i.e. all workers trying to talk to the master concurrently. For that reason, and to mitigate this additional overhead to some degree, we used a larger master instance of c3.8xlarge in our experiments.

We ran the various approaches to train logistic regression models, a well-understood convex problem that is widely used in practice. Moreover, Logistic regression models are often expanded by including interaction terms that are often one-hot encoded for categorical features. This can lead to 100’s of thousands of parameters (or more) in the trained models. To train the logistic regression models for using our proposed scheme (or the naive scheme), we used Nesterov’s Accelerated Gradient descent with a constant learning rate, where the constant was chosen optimally from a range. Note that other optimizers such as LBFGS would have also been applicable here since we obtain the full gradient in our schemes. For the ignoring s stragglers approach, we used gradient descent with a learning rate of $c_{1}/(t+c_{2})$ (which is typical for SGD), where $c_{1}$ and $c_{2}$ were also chosen optimally in a range. We did not use NAG here since it is unstable to noisy gradients. While we do not present any empirical results, we refer the reader to Devolder et al. (2014) for a theoretical and empirical analysis of the effect of noisy gradients in NAG. Thus another advantage of our schemes over ignoring s stragglers is that the latter cannot be combined with NAG because errors may quickly accumulate and eventually cause the method to diverge.

2 Results

In this experiment, we also artificially added delays to $s$ random workers in each iteration (using time.sleep()). Figure 5 presents the results of our experiments with $s=1$ and $s=2$ stragglers, on a cluster of $n=12$ m1.small machines. As expected, the baseline naive scheme that waits for the stragglers has poorer performance as the delay increases. The Cyclic and Fractional schemes were designed for one straggler in Figure 5(a) and for two stragglers in Figure 5(b). Therefore, we expect that these two schemes would not be influenced at all by the delay of the stragglers (up to some variance due to implementation overheads). The partial straggler schemes were designed for various $\alpha$. Recall that for partial straggler schemes, $\alpha$ denotes the slowdown factor.

Real Dataset: Next, we trained a logistic regression model on the Amazon Employee Access dataset from Kaggle https://www.kaggle.com/c/amazon-employee-access-challenge. We used $d=26200$ training samples, and a model dimension of $p=241915$ (after one-hot encoding with interaction terms). These experiments were run on $n=10,20,30$ t2.micro instances on Amazon EC2.

In Figure 7 we show the Generalization AUC of our method (FracRep and CycRep) versus ignoring $s$ stragglers (IgnoreStragg). As can be seen, Gradient coding achieved significantly better generalization error. We emphasize that the results in figures 6 and 7 do not use any artificial straggling, only the natural delays introduced by the EC2 cluster.

How is this stark difference possible? When stragglers were ignored we were, at best, receiving a stochastic gradient (when random machines are straggling in each iteration). As alluded to earlier, in this case the best we could do as an optimization algorithm is to run gradient descent as it is robust to noise. When using gradient coding however, we could retrieve the full gradient which gave us access to faster optimization algorithms. In Figure 7 we used Nesterov’s Accelerated Gradient (NAG).

Another advantage of using full gradients is that we can guarantee that we are training on the same distribution as the one the training set was drawn from. This is not true for the approach that ignores stragglers. If a particular machine is more likely to be a straggler, samples on that machine will likely be underrepresented in the final model, unless particular countermeasures are deployed. There may even be inherent reasons why a particular sample will systematically be excluded when we ignore stragglers. For example, in structured models such as linear-chain CRFs, the computation of the gradient is proportional to the length of the sequence. Therefore, extraordinarily long examples can be ignored very frequently.

Conclusion

In this paper, we have experimented with various gradient coding ideas on Amazon EC2 instances. This is a complex trade-off space between model sizes, number of samples, worker configurations, and number of workers. Our proposed schemes create computation overheads while keeping communication the same.

The benefit of this additional computation is fault-tolerance: we are able to recover full gradients, even if $s$ machines do not deliver their assigned work, or are slow in doing so. Moreover, our partial straggler schemes provide fault tolerance while allowing all machines to do partial work. They however require an extra round of communication. An interesting open problem here is whether partial work on all machines is possible without this extra round of communication. Another open question under our framework is that of approximate gradient coding: can we get a vector that is close to the true gradient, with lesser computation overheads ? Ignoring stragglers does give the approximate gradient in a sense. However, is it possible to have a better approximation with on little computation overheads (relative to gradient coding) ?

For several model-cluster configurations that we tested, communication was the bottleneck and hence the additional computation’s effect on iteration times was negligible. This is the regime where gradient coding is most useful. However, this design space needs further exploration, that is also varying as different architectures change the parameter landscape. Overall, we believe that gradient coding is an interesting idea to add in the distributed large-scale learning arsenal.

Acknowledgements

This research has been supported by NSF Grants CCF 1344364, 1407278, 1422549, 1618689 and ARO YIP W911NF-14-1-0258.

References

Appendix - Proofs

Therefore, by construction, we have: $AB=\mathbf{1}_{\binom{n}{s}\times n}$, and the scheme $(A,B)$ is robust to any $s$ stragglers.

2 Proof of Theorem 1

Now, it is easy to see that the degree of the $i^{th}$ worker $W_{i}$ is $\left\lVert b_{i}\right\rVert_{0}$.

Also, for any partition $P_{j}$, its degree must be at least $(s+1)$. If its degree is $s$ or less, then consider the scenario where all its neighbors are stragglers. In this case, there is no non-straggler worker with access to $P_{j}$, which contradicts robustness to any $s$ stragglers.

Based on the above discussion, and using the fact that the sum of degrees of the workers in the bipartite graph must be the same as the sum of degrees of partitions, we get:

Since we assume all workers get access to the same number of partitions, this gives:

3 Proof of Theorem 2

Consider groups of partitions $\{G_{1},\ldots,G_{n/(s+1)}\}$ as follows:

Fix some set $I\subseteq[n],\lvert I\rvert=n-s$. Based on our construction, it is easy to observe that for any group $G_{j}$, there exists some index in $I$, say $i_{G_{j}}\in I$, such that the corresponding row in $B$, $b_{i_{G_{j}}}$ has all $1$s at partitions in $G_{j}$ and s elsewhere. This is because there are $(s+1)$ rows of $B$ that correspond in this way to $G_{j}$ (one in each block $\overline{B}_{\text{block}}$), and so at least one would survive in the set $I$ of cardinality $(n-s)$. Now, it is trivial to see that:

we have $\mathbf{1}\in\text{span}\{b_{i}\,|\,i\in I\}$.

Finally, since the above holds for any set $I$, we get that $B$ satisfies Condition 1. The remainder of the theorem follows from Lemma 1.

4 Proof of Theorem 3

Consider the subspace given by the null space of the random matrix $H$ (constructed in Algorithm 2):

Note that $H$ has $(n-1)s$ different random values ($s$ for each column), since its last column is simply the negative sum of its previous $(n-1)$ columns. Now, we have the following Lemma listing some properties of $H$ and $S$.

Any $s$ columns of $H$ are linearly independent with probability $1$

$\mathbf{1}\in S$, where $\mathbf{1}$ is the all-ones vector

For $i\in[n]$, let $S_{i}$ denote the set $S_{i}=\{i\mod n,(i+1)\mod n,\ldots,(i+s)\mod n\}$. Then, $S_{i}$ corresponds to the support of the $i^{th}$ row of $B$ in our construction, as also given by the support structure in Eq. (3.2).

Recall that we denote the $i^{th}$ row of $B$ by $b_{i}$. By our construction, we have:

Consider the $i^{th}$ row of $B$ constructed using Algorithm 2 (also shown in Eq. 7.4). Then,

Every element of $b_{i}(S_{i}\setminus\{i\})$ is non-zero with probability 1

For any subset $I\subseteq[n]$, $\lvert I\rvert=n-s$, the set of vectors $\{b_{i}\,|\,i\in I\}$ is linearly independent with probability 1

Now, using Lemma 3, we can conclude that for any subset $I\subseteq[n]$, $\lvert I\rvert=n-s$, $dim\left(\text{span}\{b_{i}\,|\,i\in I\}\right)=n-s$ and $\text{span}\{b_{i}\,|\,i\in I\}\subseteq S$. Consequently, from Lemma 2, since $dim(S)=n-s$ and $\mathbf{1}\in S$, this implies that:

and, $\mathbf{1}\in\text{span}\{b_{i}\,|\,i\in I\}$. Taking union bound over every $I$ shows that $B$ satisfies Condition 1. The remainder of the theorem follows from Lemma 1.

Consider any subset $I\subseteq n$, $\lvert I\rvert=s$ such that $n\notin I$. Then, all the elements of $H_{I}$ are independent, and $det(H_{I})$ is a polynomial in the elements of $H_{I}$. Consequently, since every element is drawn from a continuous probability distribution (in particular, Gaussian), the set $\{H_{I}\,|\,det(H_{I})=0\}$ is a zero measure set. So, $P\left(det(H_{I})\neq 0\right)=1$, and thus the columns of $H_{I}$ are linearly independent with probability 1.

where we let $\widetilde{H}=\begin{bmatrix}H_{I\setminus\{n\}},-\sum_{i\in[n]\setminus I}H_{i}\end{bmatrix}$. The elements of $\widetilde{H}$ are independent, so using the same argument as above, we again have $P(det(H_{I})=det(\widetilde{H})\neq 0)=1$. Finally, taking a union bound over all sets $I$ of cardinality $s$ shows that any $s$ columns of $H$ are linearly independent.

Since any $s$ columns in $H$ are linearly independent, this implies that $rank(H)=s$. Since the subspace $S$ is simply the null space of $H$, we have $dim(S)=n-s$.

Finally, since $H_{n}=-\sum_{i\in[n-1]}H_{i}$ (by construction), we have $H\mathbf{1}=0$ and thus $\mathbf{1}\in S$.

4.2 Proof of Lemma 3

Now, if possible, let for some $k\in S_{i}\setminus\{i\}$, $b_{i}(k)=0$. Then, since $b_{i}\in S$, we have:

Consequently, the set of columns $\{j\,|\,j\in S_{i}\setminus\{i,k\}\}\cup\{i\}$ is linearly dependent which contradicts $H$ having any $s$ columns being linearly independent (in Lemma 2). Therefore, we must have every element of $b_{i}(S_{i}\setminus\{i\})$ being non-zero.

Now, consider any subset $I\subseteq[n],\lvert I\rvert=n-s$. We shall show that the matrix $B_{I}$ (corresponding to the rows of $B$ with indices in $I$) has rank $n-s$ with probability $1$. Consequently, the set of vectors $\{b_{i}\,|\,i\in I\}$ would be linearly independent. To show this, we consider some $n-s$ columns of $B_{I}$, say given by the set $J\subseteq[n],\lvert J\rvert=n-s$, and denote the sub-matrix of columns by $B_{I,J}$. Then, it suffices to show that $\text{det}(B_{I,J})\neq 0$. Now, by the construction in Algorithm 2, we have: $\text{det}(B_{I,J})=\text{poly}_{1}(H)/\text{poly}_{2}(H)$, for some polynomials $\text{poly}_{1}(\cdot)$ and $\text{poly}_{2}(\cdot)$ in the entries of $H$. Therefore, if we can show that there exists at least one $H^{\prime}$ with $H^{\prime}\mathbf{1}=\mathbf{0}$ and $\text{poly}_{1}(H^{\prime})/\text{poly}_{2}(H^{\prime})\neq 0$, then under a choice of i.i.d. standard Gaussian entries of $H$, we would have:

Let us pick a random matrix $\widetilde{B}$ as:

where $B^{r}_{I}$ is a matrix with the same support as $B_{I}$ and with each non-zero entry i.i.d. standard Gaussian, and $D$ is a diagonal matrix such that $D_{ii}=\sum_{j=1}^{n-s}B_{I}^{r}(j,i),\,i\in[n]$. Note that a consequence of the above choice of $\widetilde{B}$ is that the sum of all its rows is the all $\mathbf{1}$s vector. Now, it can be shown that any $(n-s)$ columns of $\widetilde{B}$ form an invertible sub-matrix with probability 1. Let $S_{i}$ be the support of the $i^{th}$ row of $B$. The rows of $B^{r}_{I}$ have the supports $S_{i},i\in I$. Now because of the cyclic support structure in $B$, any collection $\{i_{1},i_{2},\ldots,i_{k}\}(0\leq k\leq n-s)$ satisfies the property:

Using Lemma 4 in Dau et al. (2013), this implies that there is a perfect matching between the rows of $B^{r}_{I}$ and any of its $(n-s)$ columns . Consequently, with probability 1, any $(n-s)$ columns of $B^{r}_{I}$ form an invertible sub-matrix. Also, since every column of $B^{r}_{I}$ contains at least one non-zero (again, owing to the support structure of $B$), this implies that with probability 1, all the diagonal entries of $D$ are non-zero. Combining the above two observations, we can infer that any $(n-s)$ columns of $\widetilde{B}$ form an invertible sub-matrix with probability 1.

So far, we have shown existence of a matrix $\widetilde{B}$ with the following properties: (i) $\widetilde{B}$ has the same support structure as $B_{I}$, (ii) any $(n-s)$ columns of $\widetilde{B}$ form invertible sub-matrix, (iii) the sum of all rows of $\widetilde{B}$ is the all $\mathbf{1}$s vector. Now, for any such $\widetilde{B}$, we shall show that there exists an $H^{\prime}$ such that $H^{\prime}\widetilde{B}^{T}=\mathbf{0}$ such that any $s$ columns of $H^{\prime}$ form an invertible sub-matrix. This implies that when we run Algorithm 2 with this $H^{\prime}$, the output matrix would be the same as $\widetilde{B}$ on the rows in the set $I$. The remainder of the proof then follows from our earlier discussion.

Now, consider any set $Q\subseteq[n],\lvert Q\rvert\leq s$. Suppose we pick any invertible $H^{\prime}_{:,Q}$, and set $H^{\prime}_{:,[n]\setminus Q}=-H^{\prime}_{:,Q}\widetilde{B}_{:,Q}^{T}(\widetilde{B}_{:,[n]\setminus Q}^{T})^{-1}$. Then, such an $H^{\prime}$ satisfies $H^{\prime}\widetilde{B}^{T}=0$ and its columns in the set $Q$ form an invertible sub-matrix. Now, since invertibility on the set $Q$ simply corresponds to $\text{det}(H^{\prime}_{:,Q})\neq 0$ (i.e. some fixed polynomial being non-zero), if we actually picked a uniformly random $H^{\prime}$ on the subspace $H^{\prime}\widetilde{B}^{T}=0$, then

Taking a union bound over all $Q$s, we get that

Thus, there exists an $H^{\prime}$ satisfying $H^{\prime}\widetilde{B}^{T}=0$ with any $s$ of its columns forming an invertible sub-matrix. Also, since the sum of all rows of $\widetilde{B}$ is $\mathbf{1}$, this implies $H^{\prime}\mathbf{1}=\mathbf{0}$.