Impact of Community Structure on Consensus Machine Learning
This addresses the efficiency of decentralized learning in clustered networks like IoT or cloud clusters, but it is incremental as it builds on known eigenvalue-based analyses.
The paper tackles the problem of how network community structure affects consensus time in decentralized machine learning, finding that reducing community structure generally decreases consensus time and identifying a critical level beyond which communities no longer limit performance.
Consensus dynamics support decentralized machine learning for data that is distributed across a cloud compute cluster or across the internet of things. In these and other settings, one seeks to minimize the time $τ_ε$ required to obtain consensus within some $ε>0$ margin of error. $τ_ε$ typically depends on the topology of the underlying communication network, and for many algorithms $τ_ε$ depends on the second-smallest eigenvalue $λ_2\in[0,1]$ of the network's normalized Laplacian matrix: $τ_ε\sim\mathcal{O}(λ_2^{-1})$. Here, we analyze the effect on $τ_ε$ of network community structure, which can arise when compute nodes/sensors are spatially clustered, for example. We study consensus machine learning over networks drawn from stochastic block models, which yield random networks that can contain heterogeneous communities with different sizes and densities. Using random matrix theory, we analyze the effects of communities on $λ_2$ and consensus, finding that $λ_2$ generally increases (i.e., $τ_ε$ decreases) as one decreases the extent of community structure. We further observe that there exists a critical level of community structure at which $τ_ε$ reaches a lower bound and is no longer limited by the presence of communities. We support our findings with empirical experiments for decentralized support vector machines.