AF: Small: Distributed Optimization Beyond Worst Case Topologies

AF：小型：超越最坏情况拓扑的分布式优化

基本信息

批准号：
1910588
负责人：
Bernhard Haeupler
金额：
$ 40万
依托单位：
Carnegie-Mellon University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-07-15 至 2022-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1910588&HistoricalAwards=false
关键词：
AF Small Distributed Optimization Beyond

项目摘要

The modern computation and information processing systems shaping our world are ever increasing in scale and have become massively distributed. A fundamental understanding of distributed algorithms and optimization problems has in the past and inevitably will in the future lead to more efficient, more scalable, and overall vastly more powerful systems and applications with broad impacts on society. With this goal in mind, this project is developing an algorithmic toolbox for designing distributed optimization algorithms which drastically outperform state-of-the-art algorithms on non-worst-case topologies, common in practice. The project will also contribute greatly to the education and professional training of students in this critical field. The project plans to integrate research and education through curriculum development activities spanning graduate and undergraduate courses and provides initiatives and concrete steps taken by the project team to attract, excite, mentor, and support students from underrepresented groups.The shift towards massively distributed systems in practice has led to an increased interest and fast acceleration in our theoretical understanding of distributed optimization problems. However much of this work focuses on the algorithmic performance in worst-case topologies. Real world networks, however, do not always exhibit worst-case behavior and most networks of interest do not share the limiting bottleneck characteristics which dominate the current analyses of worst-case algorithms and their provable performance guarantees. In particular, there is no known barrier for ultra-fast polylogarithmic round distributed algorithms on any network of interest, while most current algorithms require Theta(sqrt(n)) rounds on any (such) topology, mostly because such a running time can be shown to be necessary on some practically irrelevant pathologically bad topologies. This almost exponential gap between worst-case-optimal Theta(sqrt(n)) algorithms and the ultra-fast performance which is likely possible in many, if not all, real-world settings motivates this project. This project provides a detailed program for designing instance-optimal distributed algorithms. Instance-optimal algorithms are competitive with the best algorithm on any given topology and thereby constitute the strongest possible form of algorithmically adjusting to non-worst-case topologies.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.

塑造我们世界的现代计算和信息处理系统的规模越来越高，并且已经大量分布。对分布式算法和优化问题的基本理解在过去，将来不可避免地会导致更有效，更可扩展性和总体更强大的系统和应用程序，并对社会产生广泛的影响。考虑到这个目标，该项目正在开发一种用于设计分布式优化算法的算法工具箱，该算法在实践中常见的是非智能拓扑拓扑的最先进算法。该项目还将为这个关键领域的学生的教育和专业培训做出巨大贡献。该项目计划通过跨越研究生和本科课程的课程开发活动整合研究和教育，并提供项目团队采取的计划和具体步骤，以吸引，激励，指导和支持来自代表性不足的小组的学生。实践中大量分布的系统的转变导致了我们对分布式优化问题的兴趣和加快分布的兴趣，并加快了分布式优化问题的兴趣。但是，这项工作的大部分都集中在最坏情况拓扑中的算法性能上。但是，现实世界网络并不总是表现出最坏的行为，大多数感兴趣的网络都不具有有限的瓶颈特征，这些特征主导了当前对最差案例算法的分析及其可证明的性能保证。特别是，在任何感兴趣的网络上，都没有已知的超快速多组圆形分布式算法的障碍，而当前大多数算法都需要在任何（这样的）拓扑上进行theta（sqrt（n））回合，这主要是因为在某些实际上是不良病理学上的病理学不良的拓扑都可以证明这种运行时间是必不可少的。最糟糕的theta（SQRT（n））算法与超快速性能之间的这种几乎指数的差距在许多（如果不是全部）现实世界的设置中可能会激发该项目。该项目提供了一个详细的程序，用于设计实例 - 最佳分布式算法。实例 - 最佳算法具有任何给定拓扑的最佳算法的竞争力，因此构成了最强的算法形式，算法可以调整为非智障拓扑结构。该奖项反映了NSF的法定任务，并通过使用该基金会的知识优点和广泛的interia来评估来评估NSF的法定任务。