Coded Distributed Computation with Application to Machine Learning

机器学习算法处理大量的数据，必须对这些数据进行密集的计算。分布式计算的思想是将任务划分为更小的子任务（这些子任务很容易解决），并将子任务分发给几个工作人员。每个worker解决一个子问题，并将结果返回给主节点。主节点必须组装结果以获得总体结果。分布式计算中的一个严重问题是缓慢的工作者（称为离散者）。等待他们的响应会导致机器学习算法的巨大延迟。因此，使用纠错代码的目的是能够从许多（但不是全部）工作中重构总体结果。该项目开发了可靠和私有编码计算的新概念。这包括编码分布式矩阵乘法，随机梯度下降和卷积积。对于分布式矩阵乘法，主要目标是减少病态实值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.