Abstract
We present an analysis for the performance of decentralized consensus-based gradient (DCG) methods for solving optimization problems over a cluster network of nodes. This type of network is composed of a number of densely connected clusters with a sparse connection between them. Decentralized 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. Based on this observation, we present a novel analysis to study the convergence 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, where these methods 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 impact of multiple time-scale dynamics on the convergence of this method. We also illustrate our theoretical results by a number of numerical simulations using DCG methods over different cluster networks.
Introduction
In decentralized optimization, a network of nodes works together to minimize a global objective function, but each node only knows its own local data and can only communicate with its immediate neighbors. The standard tool for this is the Decentralized Consensus-based Gradient (DCG) method. Traditional theoretical models suggest that as the number of nodes ($N$) in a network grows, the time to converge increases significantly. However, many real-world networks—such as power grids or social networks—are not uniformly connected; they are clustered.
These networks feature groups of nodes that are densely connected internally but only sparsely connected to other groups. This structure creates a "two-time-scale" reality: information zips around inside a cluster but crawls between them. This paper addresses the gap in existing theory by proving that if a network is clustered, it converges much faster than previously predicted, scaling with the number of clusters rather than the total number of nodes.
Methodology
The authors analyze a continuous-time version of the DCG method using a two-time-scale analysis inspired by singular perturbation theory. They partition the system's variables into two categories:
- Fast Variables: The differences between a node's local state and its cluster's average. Due to dense intra-cluster connectivity, these differences vanish quickly.
- Slow Variables: The averages of the clusters themselves. Because connections between clusters are sparse, these averages take longer to synchronize across the whole network.
To prove convergence, the authors construct a novel composite Lyapunov function. This mathematical tool tracks three simultaneous dynamics: the distance of clusters from local consensus, the distance between cluster averages, and the distance of the entire system from the optimal solution.
Key Results and Discussion
The primary finding is that the convergence rate scales with the number of clusters ($r$) rather than the total nodes ($N$). For instance, in a network of 10,000 nodes organized into 10 clusters, performance is dictated by those 10 clusters. The authors prove a convergence rate of $O(\ln(T)/T)$, where the scaling factor depends on the connectivity of the "cluster-level" graph rather than the entire massive network.
Numerical simulations on a 60-node network partitioned into 3 clusters (sizes 10, 20, and 30) validate this theory. The results clearly show a "two-step" convergence: a rapid "local synchronization" phase where nodes in a cluster quickly agree, followed by a "global convergence" phase where the clusters slowly align toward the optimal solution. Increasing the number of links between clusters directly speeds up this second "slow" phase, while the "fast" phase remains largely unchanged.
Conclusion
By accounting for the clustered structure of real-world networks, this research provides a much-needed theoretical "tightening" for decentralized optimization. It offers a more optimistic and realistic bound for algorithm performance in large-scale systems. Future work includes extending this analysis to discrete-time implementations and non-convex problems, such as deep learning, as well as exploring dynamic topologies where network structures change over time.
Summary updated