Collaborative Research: CIF: Small: Approximate Coded Computing - Fundamental Limits of Precision, Fault-tolerance and Privacy

分布式计算在实现现代机器学习和人工智能应用方面发挥着核心作用。该项目为分布式计算和机器学习开发了新的理论框架、分析和技术，旨在(I)通过克服系统瓶颈来加快计算时间，(Ii)确保在存在硬件错误和故障的情况下进行准确的计算，以及(Iii)启用遵守数据隐私限制的数据处理方法。这些属性将通过在基于编码理论的计算中引入受控数量的冗余来实现-编码理论是一个使现代数据通信和存储技术成为可能的领域。为了对长期可能发生的事情有一个现实的理解，开发的技术将伴随着计算精度、数据隐私、容错和冗余开销之间的基本权衡界限。该项目将通过出版物、教程和课程整合向更广泛的科学界传播成果，并使人们意识到发展中的研究。编码计算是信息和编码理论的一个子领域，它将冗余引入分布式计算。编码计算已经成为一种很有前途的范例，可以缓解大规模分布式机器学习中的掉队、通信和数据隐私瓶颈。然而，最先进的编码计算技术，主要是为了能够准确地重建计算输出而设计的，具有根本的效率限制，特别是对于非线性计算任务。这个项目开发了近似编码计算的技术，其中解码器的目标是在规定的失真限制内获得函数输出，并且数据隐私约束被设定为对差分隐私参数的限制。研究将在三个紧密相连的过程中进行：(I)用于容错近似矩阵乘法的编码方案，(Ii)用于超越矩阵乘法的容错近似非线性计算的编码方案，以及(Iii)用于差分私有计算的编码方案。开发的技术将结合信息和编码理论、数学近似理论和差异隐私的想法。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Distributed computing plays a central role in enabling modern machine learning and artificial intelligence applications. This project develops new theoretical frameworks, analyses, and techniques for distributed computing and machine learning aiming to (i) accelerate the computation time by overcoming system bottlenecks, (ii) ensure accurate computation in the presence of hardware errors and faults, and (iii) enable data-processing approaches that adhere to data-privacy constraints. These attributes will be enabled by inducing a controlled amount of redundancy in computations based on coding theory - a field that has enabled modern data communication and storage technologies. To obtain a realistic understanding of what is possible in the long run, the developed techniques will be accompanied by fundamental bounds on the tradeoffs between computation accuracy, data privacy, error tolerance, and redundancy overheads. The project will disseminate outcomes and enable awareness of developed research to the broader scientific community through publications, tutorials, and curricular integration.Coded computing is a sub-area of information and coding theory that induces redundancy into distributed computing. Coded computing has emerged as a promising paradigm to relieve straggler, communication, and data-privacy bottlenecks in large-scale distributed machine learning. Yet, state-of-the-art coded-computing techniques, mostly devised to enable exact reconstruction of the computation output, have fundamental efficiency limitations, particularly for nonlinear computation tasks. This project develops techniques for approximate coded computing, wherein the decoder aims to obtain the function output within a prescribed distortion limit, and data-privacy constraints are posed as limits on differential-privacy parameters. The research will be conducted in three closely connected thrusts: (i) coding schemes for fault-tolerant approximate matrix multiplication, (ii) coding schemes for fault-tolerant approximate nonlinear computations beyond matrix multiplications, and (iii) coding schemes for differentially private computations. The techniques developed will combine ideas from information and coding theories, mathematical approximation theory, and differential privacy.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.