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

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

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.