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）启用遵守数据隐私约束的数据处理方法。这些属性将通过在基于编码理论的计算中引入受控的冗余量来实现，编码理论是现代数据通信和存储技术的一个领域。为了现实地理解从长远来看什么是可能的，所开发的技术将伴随着计算准确性、数据隐私、容错性和冗余开销之间权衡的基本界限。该项目将通过出版物、教程和课程整合来传播成果，并使更广泛的科学界认识到已开发的研究成果。编码计算是信息和编码理论的一个子领域，它在分布式计算中引入了冗余。编码计算已成为缓解大规模分布式机器学习中的落后者、通信和数据隐私瓶颈的有前途的范例。然而，最先进的编码计算技术（主要是为了精确重建计算输出而设计的）具有基本的效率限制，特别是对于非线性计算任务。该项目开发了近似编码计算技术，其中解码器的目标是在规定的失真限制内获得函数输出，并且数据隐私约束被视为对差分隐私参数的限制。该研究将围绕三个紧密相关的方向进行：（i）容错近似矩阵乘法的编码方案，（ii）矩阵乘法之外的容错近似非线性计算的编码方案，以及（iii）差分隐私计算的编码方案。所开发的技术将结合信息和编码理论、数学逼近理论和差分隐私的思想。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。