Efficiently Distributing Optimization Over Large-Scale Networks

Sponsor: National Science Foundation

Award Number: ECCS-1933027

PI: Alexander Olshevsky

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.

For more information: click here.