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

SHF：小型：用于机器学习的通信高效分布式算法

• 批准号: 1814888
• 负责人: Mert Gurbuzbalaban
• 金额: $ 46.44万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-07-15 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1814888&HistoricalAwards=false
• 关键词: SHF; Small; Communication; Efficient; Distributed

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.

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

项目成果

Robust Accelerated Gradient Methods for Smooth Strongly Convex Functions

• DOI: 10.1137/19m1244925
• 发表时间: 2018-05
• 期刊: SIAM J. Optim.
• 作者: N. Aybat;Alireza Fallah;M. Gürbüzbalaban;A. Ozdaglar

L-DQN: An Asynchronous Limited-Memory Distributed Quasi-Newton Method

• DOI: 10.1109/cdc45484.2021.9682985
• 发表时间: 2021-08
• 期刊: 2021 60th IEEE Conference on Decision and Control (CDC)
• 作者: Bugra Can;Saeed Soori;M. Dehnavi;M. Gürbüzbalaban

DAve-QN: A Distributed Averaged Quasi-Newton Method with Local Superlinear Convergence Rate

• 发表时间: 2019-06
• 作者: Saeed Soori;Konstantin Mischenko;Aryan Mokhtari;M. Dehnavi;Mert Gurbuzbalaban

Breaking Reversibility Accelerates Langevin Dynamics for Non-Convex Optimization

• 发表时间: 2020
• 作者: Xuefeng Gao;M. Gürbüzbalaban;Lingjiong Zhu

Differentially Private Accelerated Optimization Algorithms

• DOI: 10.1137/20m1355847
• 发表时间: 2020-08
• 期刊: SIAM J. Optim.
• 作者: Nurdan Kuru;cS. .Ilker Birbil;Mert Gurbuzbalaban;S. Yıldırım