AF: Small: Distributed Optimization Beyond Worst Case Topologies

塑造我们世界的现代计算和信息处理系统的规模不断扩大，并已成为大规模分布。对分布式算法和优化问题的基本理解在过去和将来不可避免地会导致更高效，更可扩展，总体上更强大的系统和应用程序，对社会产生广泛的影响。考虑到这一目标，该项目正在开发一个算法工具箱，用于设计分布式优化算法，该算法在实践中常见的非最坏情况拓扑上大大优于最先进的算法。该项目还将极大地促进这一关键领域学生的教育和专业培训。该项目计划通过跨越研究生和本科课程的课程开发活动将研究和教育结合起来，并提供项目团队采取的倡议和具体步骤，以吸引、激励、指导和支持来自代表性不足群体的学生。在实践中向大规模分布式系统的转变导致了我们对分布式优化问题的理论理解的增加和快速加速。然而，大部分工作都集中在最坏情况拓扑下的算法性能上。然而，现实世界的网络并不总是表现出最坏情况行为，而且大多数感兴趣的网络并不具有限制瓶颈特征，这些特征主导着当前最坏情况算法的分析及其可证明的性能保证。特别是，在任何感兴趣的网络上，对于超快速多对数轮分布式算法来说，没有已知的障碍，而大多数当前算法在任何（这样的）拓扑上都需要Theta（sqrt(n)）轮，主要是因为这样的运行时间可以在一些实际上无关的病态不良拓扑上被证明是必要的。最坏情况下最优Theta（sqrt(n)）算法与在许多（如果不是全部）现实环境中可能实现的超快性能之间几乎呈指数级的差距激励了这个项目。本课题为实例优化分布式算法的设计提供了详细的程序。实例最优算法与任何给定拓扑上的最佳算法竞争，因此构成了适应非最坏情况拓扑的最强可能的算法形式。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.