Coded Distributed Computation with Application to Machine Learning

机器学习算法处理海量数据，必须对其进行密集的计算。分布式计算的思想是将任务划分为较小的子任务(容易解决)，并将子任务分配给几个工作者。每个工作者解决一个子问题，并将结果返回到主节点。主节点必须组合结果以获得整体结果。分布式计算中一个严重的问题是学习速度慢的工作者(称为掉队者)。等待他们的响应会导致机器学习算法的巨大延迟。因此，使用纠错码的目的是能够重建许多(但不是所有)工作人员的整体结果。这个项目为可靠和私有的编码计算开发了新的概念。这包括编码分布式矩阵乘法、随机梯度下降和卷积乘积。对于分布式矩阵乘法，主要目标是减少实值Vandermonde矩阵的病态问题，并从交织码、秩度量码和LDPC码中应用新的编码策略。分布式卷积产品必须首先被分成合适的子任务，以便设计定制的编码方案来处理掉队和敌对工作人员。对于随机梯度下降的分布式计算，将研究加速梯度下降的收敛和最小化通信负荷以及新的编码技术，关键是要保证所涉及数据的保密性。因此，我们将提出保证用户隐私的方案，并分析编码/解码复杂度和隐私约束如何影响系统的总体延迟和计算/通信的权衡。由于人们对联合学习的兴趣与日俱增，我们计划引入编码技术，以加快学习速度并确保相关数据的隐私。在所有方法中，应该通过使用无费率代码来利用网络可能的异质性。

Machine learning algorithms deal with massive amounts of data on which intensive calculations have to be performed. The idea of distributed computation is to divide the task into smaller subtasks (which are easy to solve) and distribute the subtasks to several workers. Each worker solves a subproblem and returns the result to the master node. The master node has to assemble the results to obtain the overall result. A severe problem in distributed computation are slow workers (called stragglers).Waiting for their responses causes a tremendous delay for the machine learning algorithm. Therefore, error-correcting codes are used with the goal to be able to reconstruct the overall result from many (but not all) workers.This project develops new concepts for reliable and private coded computation. This includes coded distributed matrix multiplication, stochastic gradient descent and convolution products. For distributed matrix multiplication, the main goal is to reduce the problem of ill-conditioned real-valued Vandermonde matrices and apply new coding strategies from interleaved codes, rank-metric codes, and LDPC codes. The distributed convolution product has first to be split into suitable subtasks in order to design tailored coding schemes to deal with stragglers and adversarial workers. For the distributed computation of stochastic gradient descent, the convergence of accelerated gradient descent and the minimization of the communication load will be investigated as well as new coding techniques.A crucial point is to guarantee the privacy of the involved data. We will therefore propose schemes that guarantee the privacy of the users and analyze how the encoding/decoding complexity and the privacy constraints influence the overall latency of the system and the computation/communication trade-off. Due to the increasing interest in Federated Learning, we plan to incorporate coding techniques that can speed up learning and guarantee privacy of the involved data. In all approaches, the possible heterogeneity of the network should be leveraged by using rateless codes.