# A Unified Framework for Center-based Clustering of Distributed Data

arXiv: https://arxiv.org/abs/2402.01302 · HTML: https://mlsanity.com/paper/2402.01302/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 89 references that are in the map.
- First posted on arXiv 2 Feb 2024.

## Builds on (most cited first, 30 of 30)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [An Efficient Framework for Clustered Federated Learning](https://mlsanity.com/paper/2006.04088/) (2020)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [On the Convergence of Decentralized Gradient Descent](https://mlsanity.com/paper/1310.7063/) (2013)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016)
- [Heterogeneity for the Win: One-Shot Federated Clustering](https://mlsanity.com/paper/2103.00697/) (2021)
- [Network Lasso: Clustering and Optimization in Large Graphs](https://mlsanity.com/paper/1507.00280/) (2015)
- [A general framework for decentralized optimization with first-order methods](https://mlsanity.com/paper/2009.05837/) (2020)
- [Convex Clustering: Model, Theoretical Guarantee and Efficient Algorithm](https://mlsanity.com/paper/1810.02677/) (2018)
- [The Hardness of Approximation of Euclidean k-means](https://mlsanity.com/paper/1502.03316/) (2015)
- [Distributed k-Means and k-Median Clustering on General Topologies](https://mlsanity.com/paper/1306.0604/) (2013)
- [Distributed Optimization Under Adversarial Nodes](https://mlsanity.com/paper/1606.08939/) (2016)
- [Fast decentralized non-convex finite-sum optimization with recursive variance reduction](https://mlsanity.com/paper/2008.07428/) (2020)
- [Convergence rates for distributed stochastic optimization over random networks](https://mlsanity.com/paper/1803.07836/) (2018)
- [A fast randomized incremental gradient method for decentralized non-convex optimization](https://mlsanity.com/paper/2011.03853/) (2020)
- [Distributed Stochastic Gradient Descent: Nonconvexity, Nonsmoothness, and Convergence to Local Minima](https://mlsanity.com/paper/2003.02818/) (2020)
- [Uniform Concentration Bounds toward a Unified Framework for Robust Clustering](https://mlsanity.com/paper/2110.14148/) (2021)
- [Personalized Federated Learning via Convex Clustering](https://mlsanity.com/paper/2202.00718/) (2022)
- [Networked Signal and Information Processing](https://mlsanity.com/paper/2210.13767/) (2022)
- [Secure Distributed Optimization Under Gradient Attacks](https://mlsanity.com/paper/2210.15821/) (2022)
- [Convergence rate of stochastic k-means](https://mlsanity.com/paper/1611.05132/) (2016)
- [Distributed k-Clustering for Data with Heavy Noise](https://mlsanity.com/paper/1810.07852/) (2018)
- [Primal-dual methods for large-scale and distributed convex optimization and data analytics](https://mlsanity.com/paper/1912.08546/) (2019)
- [Gradient Based Clustering](https://mlsanity.com/paper/2202.00720/) (2022)
- [Distributed k-means algorithm](https://mlsanity.com/paper/1312.4176/) (2013)
- [Clustering with Distributed Data](https://mlsanity.com/paper/1901.00214/) (2019)
- [A One-shot Framework for Distributed Clustered Learning in Heterogeneous Environments](https://mlsanity.com/paper/2209.10866/) (2022)

## Abstract (arXiv)

We develop a family of distributed center-based 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-Fρ), is parametrized by ρ ≥ 1, controling the proximity of users' center estimates, with F determining the clustering loss. Our framework allows for a broad class of smooth convex loss functions, including popular clustering losses like K-means and Huber loss. Specialized to popular clustering losses like K-means and Huber loss, DGC-Fρ gives rise to novel distributed clustering algorithms DGC-KMρ and DGC-HLρ, while novel clustering losses based on Logistic and Fair functions lead to DGC-LLρ and DGC-FLρ. We provide a unified analysis and establish several strong results, under mild assumptions. First, we show that the sequence of centers generated by the methods converges to a well-defined notion of fixed point, under any center initialization and value of ρ. Second, we prove that, as ρ increases, the family of fixed points produced by DGC-Fρ converges to a notion of consensus fixed points. We show that consensus fixed points of DGC-Fρ 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. Extensive numerical experiments on synthetic and real data confirm our theoretical findings, show strong performance of our methods and demonstrate the usefulness and wide range of potential applications of our general framework, such as outlier detection.