Convergence Rates of Decentralized Gradient Dynamics over Cluster Networks: Multiple-Time-Scale Lyapunov Approach

We present a new analysis for the performance of decentralized consensus-based gradient (DCG) dynamics for solving optimization problems over a cluster network of nodes. This type of network is composed of a number of densely connected clusters with sparse connections between them. Decentralized consensus algorithms over cluster networks have been observed to constitute two-time-scale dynamics, where information within any cluster is mixed much faster than the one across clusters. In this paper, we present a novel analysis to study the convergence rates of the DCG methods over cluster networks. In particular, we show that these methods converge at a rate ln(T)/T and only scale with the number of clusters, which is relatively small to the size of the network. Our result improves the existing analysis when applied to study the rates of DCG over cluster networks, where these rates are shown to scale with the size of the network. The key technique in our analysis is to consider a novel Lyapunov function that captures the multiple time-scale dynamics of DCG in cluster networks. We also illustrate our theoretical results by a number of numerical simulations using DCG dynamics over different cluster networks.