Efficiently Distributing Optimization over Large-Scale Networks

该项目将设计新的分布式优化算法，这些算法可以在没有任何中央协调器或处理器服务器的情况下工作，并且其渐近性能在较大的网络中总是得到改善。这些算法将在基于对等最近邻的通信网络上运行，其连接骨干可以随时间变化。我们的模型将明确地考虑分布式计算中常见的延迟、通信延迟、消息丢失和不可预测的停机时间;然而，尽管存在所有这些现象，我们的方法的渐近性能将与具有与整个分布式网络相同的计算能力的最佳集中式方法相同。由于相同处理器的大型网络具有更高的总计算能力，这意味着大型网络的性能更好。 这与现有技术的现状形成对比，在现有技术中，随着网络规模的增加，现有算法的性能通常变得更加缓慢，这是由于在大型网络上协调的困难。与该项目相关的各种推广活动正在计划中，包括将结果纳入本科生和研究生教育。虽然在过去的十年中，分布式优化已被用于控制和网络科学的大量应用中，但这些应用中很少有大规模的，达到数万个节点的意义。这部分是因为分布式优化中的收敛时间往往会随着底层网络的频谱间隙的倒数而增长，并且这可能会随着节点数量的增加而变差;因此，与较小的网络相比，大型网络的性能会下降。例如，线性网络上拉普拉斯算子的逆谱间隙随节点数的平方增长;在2D网格上，相同的逆谱间隙将随节点数的线性增长。任何时候，这种逆谱间隙出现在收敛时间的表达式中，它们隐藏了节点总数的多项式因子。该项目将创造克服这一障碍的技术。通过对不精确梯度预言的新分析，（当梯度只能在有误差的情况下计算时，这限制了一阶优化方法的性能），具有小增益类型的参数，该参数将系统中变量之间的关系链互连（有效地证明了整个网络中的错误随时间的影响较小），我们将设计新的算法，在瞬态之后，完全不依赖于底层网络。这意味着只要该方法运行足够长的时间，在网络上分发该方法实际上是没有成本的。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

This project will design new algorithms for distributed optimization which can work without any kind of central coordinator or processor server and whose asymptotic performance always improves in larger networks. The algorithms will run over communication networks based on peer-to-peer nearest neighbor with connectivity backbones that can vary with time. Our model will explicitly account for asynchrony, communication delays, message losses, and unpredictable downtime, which are common in real-world in distributed computing; nevertheless, despite all these phenomena, the asymptotic performance of our methods will be identical to the best centralized method with the same computational power as the entire distributed network. Because larger networks of identical processors have more total computational power, this will mean that performance is better in larger networks. This is to be contrasted with the current state of the art, where the performance of existing algorithms typically gets more sluggish as the size of the network increases due to the difficulty of coordination across a large network. A variety of outreach activities related to the project are planned, including incorporation of the results into undergraduate and graduate education.While distributed optimization has been used in a plethora of applications in control and network science over the past decade, few of these applications have been large-scale in the sense of reaching into tens of thousands of nodes. In part this is because convergence times in distributed optimization tend to grow with the inverse spectral gap of the underlying network, and this can scale poorly with the number of nodes; as a result, large networks experience slowdowns in performance compared with smaller ones. For example, the inverse spectral gap of the Laplacian on the line network grows quadratically on the number of nodes; on a 2D grid, the same inverse spectral gap will grow linearly with the number of nodes. Any time such inverse spectral gaps appear in expressions for convergence times, they hide polynomial factors of the total number of nodes. This project will create techniques for overcoming this barrier. By putting together new analysis of inexact gradient oracles (which bound the performance of first-order optimization methods when the gradients can only be computed with error) with small-gain type arguments which interconnect chains of relations among variables in the system (effectively demonstrating that errors throughout the network have less of an effect with time), we will design new algorithms whose performance, after a transient, does not depend at all on the underlying network. This implies there is effectively no cost to distributing the method over the network, provided the method runs for long enough.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.