Distributed optimization for evolving networks of growing connectivity

Abstract

We focus on the problem of distributed optimization for multi-agent networks via distributed dual averaging (DDA) over an evolving network of growing connectivity. It is known that the convergence rate of DDA is influenced by the algebraic connectivity of the underlying network, where better connectivity leads to faster convergence. However, the effect of the growth of network connectivity on the convergence rate has not been fully understood. This paper provides a tractable approach to analyze the improvement in the convergence rate of DDA induced by the growth of network connectivity. This analysis is applicable, for example, to successive refinement strategies in massive multi-core optimizers where an increasing number of local data passage edges are successively added between cores in order to accelerate total run time. Compared to the existing convergence results, our analysis gives tighter bounds on the convergence of DDA over networks of growing connectivity. Numerical experiments show that our analysis leads to orders of improvement for evaluating convergence rate, which is not captured by existing analysis.