Impact of Community Structure on Consensus Machine Learning
share
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∈[0,1] of the network's normalized Laplacian matrix: τ_ϵ∼𝒪(λ_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.
READ FULL TEXT