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

2025/05/23 by Harsh Vardhan, Heng Zhu, Vardhan, Harsh +5
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Matrix Theory and Algorithms #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.2505.18420

openalex publication_date 2025/05/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Machine Unlearning of Federated Clusters
• Secure Federated Clustering
• Federated Multi-Task Learning under a Mixture of Distributions
• Heterogeneity for the Win: One-Shot Federated Clustering
• Local SGD: Unified Theory and New Efficient Methods
• Federated Unsupervised Representation Learning
• Minibatch vs Local SGD for Heterogeneous Distributed Learning
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization
• Sparsified SGD with Memory
• Local SGD Converges Fast and Communicates Little
• Federated Learning: Strategies for Improving Communication Efficiency
• Ten Steps of EM Suffice for Mixtures of Two Gaussians
• Solving a Mixture of Many Random Linear Equations by Tensor Decomposition and Alternating Minimization
• Statistical guarantees for the EM algorithm: From population to sample-based analysis
• Improved Spectral-Norm Bounds for Clustering
• Clustering with Spectral Norm and the k-means Algorithm
• Learning Mixtures of Gaussians using the k-means Algorithm
• k-means requires exponentially many iterations even in the plane
• Least squares quantization in PCM

Related

• Modified K-means Algorithm with Local Optimality Guarantees
• Local SGD and Federated Averaging Through the Lens of Time Complexity
• Adapting Local Sequential Algorithms to the Distributed Setting
• Convergence rate of stochastic k-means
• Lloyd's K-Means Clustering Algorithm Is Frank-Wolfe in Disguise