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

协作研究：CIF：小型：近似编码计算 - 精度、容错性和隐私的基本限制

• 批准号: 2231707
• 负责人: Flavio Calmon
• 金额: $ 25万
• 依托单位: Harvard University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-06-01 至 2026-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2231707&HistoricalAwards=false
• 关键词: Collaborative; Research; CIF; Small; Approximate

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.

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