SHF: Small: Communication-Efficient Distributed Algorithms for Machine Learning

传感和处理技术、通信能力和智能设备的进步使得能够部署收集大量数据然后进行处理以做出决策的系统。处理大量数据的平台因应用而异。其中，数据中心是具有巨大计算资源的强大平台，收集的数据可以分布在多个处理器上，这些处理器都通过高带宽网络连接。数据也可以在多智能体系统中生成和处理，多智能体系统由多个相互作用的计算单元（例如通过无线互联网连接的智能设备）组成，在存储，电力，计算和通信能力方面具有有限的资源。数据通信成本，包括带宽和延迟，往往占主导地位的浮点运算成本，因此优化算法的性能，当操作在大数据集上是由多智能体系统和数据中心的数据通信的限制。该项目针对大规模数据分析和机器学习中出现的一类分布式优化问题提出了新的通信高效方法。在本项目范围内开发的方法和技术有助于提高分布式优化算法的效率、实际性能和数学基础。该项目还在开发一个高性能软件框架，以便传播高效的特定领域软件和基准，该项目有三个目标：第一个目标是通过一个分布式算法提高在多智能体系统中解决分布式优化问题的现有算法的通信效率，以提高共识迭代所需的通信总数。该方法是基于利用的概念的有效电阻的链接，以确定瓶颈边缘的通信目的，并修改经典的共识平均考虑到有效的电阻。第二个目标是开发数据中心的通信避免算法，通过一个框架，允许减少通信的可调量，同时保持算术成本和带宽成本相同的一些应用程序和现有的算法。第三个目标是改善混合系统的通信，该混合系统在通信结构方面插入多代理系统和数据中心之间，使用生成算法和架构感知代码的框架，以减少这些混合平台上的通信。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

Advances in sensing and processing technologies, communication capabilities and smart devices have enabled deployment of systems where a massive amount of data is collected and then processed in order to make decisions. The platforms that process this vast amount of data differ depending on the application. Among these, data centers are powerful platforms with vast computational resources where the collected data can be distributed over multiple processors that are all connected through a high-bandwidth network. Data can also be generated and processed in multi-agent systems which are made up of multiple interacting computational units (such as smart devices connected through wireless internet) with limited resources in terms of storage, power, computation, and communication capabilities. Data communication costs, which include the bandwidth and latency, often dominate floating point operation costs thus the performance of optimization algorithms when operating on large data sets is bounded by data communication for both multi-agent systems and data centers. This project proposes novel communication-efficient methods for a class of distributed optimization problems arising in large-scale data analysis and machine learning. The methods and techniques developed under the scope of this project contribute to the efficiency, practical performance and to the mathematical foundations of distributed optimization algorithms. The project is also developing a high-performance software framework that allows the dissemination of efficient domain-specific software and benchmarks.The project has three goals: the first goal is to improve the communication efficiency of existing algorithms for solving distributed optimization problems in the context of multi-agent systems, through a distributed algorithm for improving the total number of communications required in consensus iterations. The approach is based on leveraging the notion of the effective resistance of a link to identify bottleneck edges for communication purposes, and modifying the classical consensus averaging by taking effective resistances into account. The second goal is to develop communication-avoiding algorithms for data centers, through a framework that allows for reduction in communication by a tunable amount while keeping the arithmetic costs and bandwidth costs the same for a number of applications and existing algorithms. The third goal is to improve communication for hybrid systems which interpolate between multi-agents systems and data centers in terms of communication structure, using a framework that generates algorithm- and architecture-aware codes for reducing communication over these hybrid platforms.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.