# LocalKMeans: Convergence of Lloyd's Algorithm with Distributed Local Iterations

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 35 references that are in the map.
- First posted on arXiv 23 May 2025.

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

- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [Federated Multi-Task Learning under a Mixture of Distributions](https://mlsanity.com/paper/2108.10252/) (2021)
- [Minibatch vs Local SGD for Heterogeneous Distributed Learning](https://mlsanity.com/paper/2006.04735/) (2020)
- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization](https://mlsanity.com/paper/1910.13598/) (2019)
- [Federated Unsupervised Representation Learning](https://mlsanity.com/paper/2010.08982/) (2020)
- [Local SGD: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2011.02828/) (2020)
- [Heterogeneity for the Win: One-Shot Federated Clustering](https://mlsanity.com/paper/2103.00697/) (2021)
- [Ten Steps of EM Suffice for Mixtures of Two Gaussians](https://mlsanity.com/paper/1609.00368/) (2016)
- [Solving a Mixture of Many Random Linear Equations by Tensor Decomposition and Alternating Minimization](https://mlsanity.com/paper/1608.05749/) (2016)
- [Machine Unlearning of Federated Clusters](https://mlsanity.com/paper/2210.16424/) (2022)
- [Secure Federated Clustering](https://mlsanity.com/paper/2205.15564/) (2022)
- [Towards the Theory of Unsupervised Federated Learning: Non-asymptotic Analysis of Federated EM Algorithms](https://mlsanity.com/paper/2310.15330/) (2023)

## Abstract (arXiv)

In this paper, we analyze the classical K-means alternating-minimization algorithm, also known as Lloyd's algorithm (Lloyd, 1956), for a mixture of Gaussians in a data-distributed setting that incorporates local iteration steps. Assuming unlabeled data distributed across multiple machines, we propose an algorithm, LocalKMeans, that performs Lloyd's algorithm in parallel in the machines by running its iterations on local data, synchronizing only every L of such local steps. We characterize the cost of these local iterations against the non-distributed setting, and show that the price paid for the local steps is a higher required signal-to-noise ratio. While local iterations were theoretically studied in the past for gradient-based learning methods, the analysis of unsupervised learning methods is more involved owing to the presence of latent variables, e.g. cluster identities, than that of an iterative gradient-based algorithm. To obtain our results, we adapt a virtual iterate method to work with a non-convex, non-smooth objective function, in conjunction with a tight statistical analysis of Lloyd steps.