|
Abstract:
|
Clustering is a fundamental problem in statistics and machine learning. Lloyd's algorithm is the most widely used algorithm in practice due to its simplicity and good empirical performance. However, there has been little theoretical investigation of Lloyd's algorithm. In this paper, we show the statistical and computational guarantees of Lloyd's algorithm for clustering mixtures of spherical sub-Gaussians. When there are two clusters, the initializer needs only to be slightly better than random guess. Results are extended to general number of clusters and the high dimensional setting. By considering two variants of Lloyd's algorithm, we also extend our results to the problem of community detection and crowdsourcing . Our results improve previous signal-to-noise ratio condition for both problems. Experimental results on simulated and real data sets demonstrate competitive performance of our algorithms with the state-of-the-art methods.
|
