This paper addresses the gradient coding and coded matrix multiplication problems in distributed optimization and coded computing. We present a computationally efficient coding method which overcomes the drawbacks of the Fractional Repetition Coding gradient coding method proposed by Tandon et al., and can also be leveraged by coded computing networks whose servers are of heterogeneous nature. Specifically, we propose a construction for fractional repetition gradient coding; while ensuring that the generator matrix remains close to perfectly balanced for any set of coding parameters, as well as a low complexity decoding step. The proposed binary encoding avoids operations over the real and complex numbers which inherently introduce numerical and rounding errors, thereby enabling accurate distributed encodings of the partial gradients. We then make connections between gradient coding and coded matrix multiplication. Specifically, we show that any gradient coding scheme can be extended to coded matrix multiplication. Furthermore, we show how the proposed binary gradient coding scheme can be used to construct two different coded matrix multiplication schemes, each achieving different trade-offs.

In this work, we show that if local datasets in a distributed network are appropriately compressed and then aggregated, it can result in a compressed version of the union of the datasets, in terms of an £2-subspace embedding. Specifically, we show that sketching datasets which are locally generated or stored at a node in a network; via oblivious embeddings, and then aggregated, result in a valid sketch of the collective dataset. The key idea is that by applying distinct random projections on the “local” datasets, roughly gives each data point the same importance in the “global” dataset. From this, uniform sampling on the local transformed datasets is close to a uniform sampling on the global dataset, after the local projections take place. Our main arguments are also justified numerically.

Gradient coding is a method for mitigating straggling servers in a centralized computing network that uses erasure-coding techniques to distributively carry out first-order optimization methods. Randomized numerical linear algebra uses randomization to develop improved algorithms for large-scale linear algebra computations. In this paper, we propose a method for distributed optimization that combines gradient coding and randomized numerical linear algebra. The proposed method uses a randomized$\ell _{2}$-subspace embedding and a gradient coding technique to distribute blocks of data to the computational nodes of a centralized network, and at each iteration the central server only requires a small number of computations to obtain the steepest descent update. The novelty of our approach is that the data is replicated according to importance scores, called block leverage scores, in contrast to most gradient coding approaches that uniformly replicate the data blocks. Furthermore, we do not require a decoding step at each iteration, avoiding a bottleneck in previous gradient coding schemes. We show that our approach results in a valid$\ell _{2}$-subspace embedding, and that our resulting approximation converges to the optimal solution.

Large-scale computations are ubiquitous and demand exorbitant resources, with matrix multiplication being a prominent example. Multiplying high-dimensional matrices is cumbersome for an individual server but is frequently needed in many applications. To alleviate the computational cost, one can take a low-rank approximation of the matrix product and distribute it over multiple workers. However, the tail latency of such distributed computations is degraded by straggling workers. One solution is to query extra workers with coded inputs to replace the outputs of straggling workers; this technique is called "coded computing." Nearly all existing coded computing schemes apply to multiplying any matrices. Instead, we propose a new framework to design coded computing schemes to take advantage of the structure induced by compression, which we call compression-informed coded computing. We then showcase the benefits of the framework in two steps. First, we illustrate how sketching can lead to linear dependencies in the matrices multiplied by the workers. Second, we apply locality-based coded computing to leverage these linear dependencies to make do with fewer workers compared to coded computing schemes that ignore the structure of the matrices being multiplied.

In this work, we propose a method for speeding up linear regression distributively, while ensuring security. We leverage randomized sketching techniques, and improve straggler resilience in asynchronous systems. Specifically, we apply a random orthonormal matrix and then subsample in blocks, to simultaneously secure the information and reduce the dimension of the regression problem. In our setup, the transformation corresponds to an encoded encryption in an approximate gradient coding scheme, and the subsampling corresponds to the responses of the non-straggling workers; in a centralized coded computing network. We focus on the special case of the Subsampled Randomized Hadamard Transform, which we generalize to block sampling; and discuss how it can be used to secure the data.

One of the most common operations in signal processing is matrix multiplication. However, it presents a major computational bottleneck when the matrix dimension is high, as can occur for large data size or feature dimension. Two different approaches to overcoming this bottleneck are: 1) low rank approximation of the matrix product; and 2) distributed computation. We propose a scheme that combines these two approaches. To enable distributed low rank approximation, we generalize the approximate matrix CR-multiplication to accommodate weighted block sampling, and we introduce a weighted coded matrix multiplication method. This results in novel approximate weighted CR coded matrix multiplication schemes, which achieve improved performance for distributed matrix multiplication and are robust to stragglers.

A major hurdle in machine learning is scalability to massive datasets. Approaches to overcome this hurdle include compression of the data matrix and distributing the computations. Leverage score sampling provides a compressed approximation of a data matrix using an importance weighted subset. Gradient coding has been recently proposed in distributed optimization to compute the gradient using multiple unreliable worker nodes. By designing coding matrices, gradient coded computations can be made resilient to stragglers, which are nodes in a distributed network that degrade system performance. We present a novel weighted leverage score approach, that achieves improved performance for distributed gradient coding by utilizing an importance sampling.

A major hurdle in machine learning is scalability to massive datasets. One approach to overcoming this is to distribute the computational tasks among several workers. Gradient coding has been recently proposed in distributed optimization to compute the gradient of an objective function using multiple, possibly unreliable, worker nodes. By designing distributed coded schemes, gradient coded computations can be made resilient to stragglers, nodes with longer response time compared to other nodes in a distributed network. Most such schemes rely on operations over the real or complex numbers and are inherently numerically unstable. We present a binary scheme which avoids such operations, thereby enabling numerically stable distributed computation of the gradient. Also, some restricting assumptions in prior work are dropped, and a more efficient decoding is given.