LocalKMeans: Convergence of Lloyd's Algorithm with Distributed Local Iterations
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Lloyd's $K$-Means Clustering Algorithm Is Frank-Wolfe in Disguise
Lloyd's $K$-means algorithm, also known as naïve $K$-means, is a widely used ad hoc optimization heuristic, designed to minimize the sum of squared errors (SSE) across all $K$-partitions of a dataset via iterative cluste…
Image SegmentationNovel Near-Optimal Scalar Quantizers with Exponential Decay Rate and Global Convergence
Many modern distributed real-time signal sensing/monitoring systems require quantization for efficient signal representation. These distributed sensors often have inherent computational and energy limitations. Motivated …
QuantizationClustering with Distributed Data
We consider $K$-means clustering in networked environments (e.g., internet of things (IoT) and sensor networks) where data is inherently distributed across nodes and processing power at each node may be limited. We consi…
ClusteringLog-Time K-Means Clustering for 1D Data: Novel Approaches with Proof and Implementation
Clustering is a key task in machine learning, with $k$-means being widely used for its simplicity and effectiveness. While 1D clustering is common, existing methods often fail to exploit the structure of 1D data, leading…
ClusteringQuantizationConvergence rate of stochastic k-means
We analyze online and mini-batch k-means variants. Both scale up the widely used Lloyd 's algorithm via stochastic approximation, and have become popular for large-scale clustering and unsupervised feature learning. We s…
Clustering