Efficiently Distributing Optimization over Large-Scale Networks

这个项目将为分布式优化设计新的算法，它可以在不需要任何形式的中央协调器或处理器服务器的情况下工作，并且其渐近性能在较大的网络中总是得到改善。这些算法将在基于对等最近邻居的通信网络上运行，该网络具有随时间变化的连接主干。我们的模型将明确地考虑异步性、通信延迟、消息丢失和不可预测的停机时间，这些在现实世界的分布式计算中很常见；然而，尽管存在所有这些现象，我们的方法的渐近性能将与具有与整个分布式网络相同的计算能力的最佳集中式方法相同。由于具有相同处理器的较大网络具有更高的总计算能力，这将意味着在较大的网络中性能更好。这将与当前技术状态形成对比，在当前技术状态中，由于跨大型网络的协调困难，现有算法的性能通常随着网络大小的增加而变得更加迟缓。计划了与该项目相关的各种推广活动，包括将结果纳入本科生和研究生教育。尽管在过去十年中，分布式优化在控制和网络科学中得到了大量应用，但这些应用很少是大规模的，涉及到数以万计的节点。这在一定程度上是因为分布式优化中的收敛时间往往随着底层网络的反向频谱差距而增长，这可能会随着节点数量的增加而扩展得很差；因此，与较小的网络相比，大型网络的性能会降低。例如，线性网络上的拉普拉斯逆谱隙随节点数的增加而二次增长；在二维网格上，相同的逆谱隙将随着节点数的增加而线性增长。每当这种逆谱隙出现在收敛时间的表达式中时，它们隐藏了节点总数的多项式因数。这个项目将创造出克服这一障碍的技术。通过将对不精确梯度预言的新分析(当梯度只能在有误差的情况下计算时限制一阶优化方法的性能)与连接系统中变量之间的关系链的小增益型变元(有效地证明整个网络中的误差对时间的影响较小)结合在一起，我们将设计新的算法，其性能在瞬变之后完全不依赖于底层网络。这意味着，只要该方法运行足够长的时间，在网络上分发该方法实际上是没有成本的。该奖项反映了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.