LocalKMeans: Convergence of Lloyd's Algorithm with Distributed Local Iterations
Preprint
Abstract
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.
Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Memory and Communication Efficient Federated Kernel k-MeansIEEE Transactions on Neural Networks and Learning Systems, 2022
- Federated K-Means Clustering: A Novel Edge AI Based Approach for Privacy Preservation2020
- Statistical guarantees for the EM algorithm: From population to sample-based analysisThe Annals of Statistics, 2017
- The effectiveness of lloyd-type methods for the k-means problemJournal of the ACM, 2012
- Improved Spectral-Norm Bounds for Clustering2012
- Clustering with Spectral Norm and the k-Means Algorithm2010
- k-means requires exponentially many iterations even in the plane2009
- How slow is the k -means method?2006
- Adaptive estimation of a quadratic functional by model selectionThe Annals of Statistics, 2000
- Least squares quantization in PCMIEEE Transactions on Information Theory, 1982