A Unified Framework for Gradient-based Clustering of Distributed Data
Aleksandar Armacki Dragana Bajović Dušan Jakovetić Soummya Kar
We develop a family of distributed clustering algorithms that work over
networks of users. In the proposed scenario, users contain a local dataset and
communicate only with their immediate neighbours, with the aim of finding a
clustering of the full, joint data. The proposed family, termed Distributed
Gradient Clustering (DGC-$\mathcal{F}_\rho$), is parametrized by $\rho \geq 1$,
controling the proximity of users' center estimates, with $\mathcal{F}$
determining the clustering loss. Specialized to popular clustering losses like
$K$-means and Huber loss, DGC-$\mathcal{F}_\rho$ gives rise to novel
distributed clustering algorithms DGC-KM$_\rho$ and DGC-HL$_\rho$, while a
novel clustering loss based on the logistic function leads to DGC-LL$_\rho$. We
provide a unified analysis and establish several strong results, under mild
assumptions. First, the sequence of centers generated by the methods converges
to a well-defined notion of fixed point, under any center initialization and
value of $\rho$. Second, as $\rho$ increases, the family of fixed points
produced by DGC-$\mathcal{F}_\rho$ converges to a notion of consensus fixed
points. We show that consensus fixed points of DGC-$\mathcal{F}_{\rho}$ are
equivalent to fixed points of gradient clustering over the full data,
guaranteeing a clustering of the full data is produced. For the special case of
Bregman losses, we show that our fixed points converge to the set of Lloyd
points. Numerical experiments on real data confirm our theoretical findings and
demonstrate strong performance of the methods.