Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants

Abstract

Clustering is a fundamental problem in statistics and machine learning. Lloyd's algorithm, proposed in 1957, is still possibly the most widely used clustering algorithm in practice due to its simplicity and empirical performance. However, there has been little theoretical investigation on the statistical and computational guarantees of Lloyd's algorithm. This paper is an attempt to bridge this gap between practice and theory. We investigate the performance of Lloyd's algorithm on clustering sub-Gaussian mixtures. Under an appropriate initialization for labels or centers, we show that Lloyd's algorithm converges to an exponentially small clustering error after an order of $\log n$ iterations, where $n$ is the sample size. The error rate is shown to be minimax optimal. For the two-mixture case, we only require the initializer to be slightly better than random guess. In addition, we extend the Lloyd's algorithm and its analysis to community detection and crowdsourcing, two problems that have received a lot of attention recently in statistics and machine learning. Two variants of Lloyd's algorithm are proposed respectively for community detection and crowdsourcing. On the theoretical side, we provide statistical and computational guarantees of the two algorithms, and the results improve upon some previous signal-to-noise ratio conditions in literature for both problems. Experimental results on simulated and real data sets demonstrate competitive performance of our algorithms to the state-of-the-art methods.

References in corpus (4)

• Nonconvex Statistical Optimization: Minimax-Optimal Sparse PCA in Polynomial Time
• Exact Exponent in Optimal Rates for Crowdsourcing
• Statistical Guarantees for Estimating the Centers of a Two-component Gaussian Mixture by EM
• Influential Feature PCA for high dimensional clustering

Cited by in corpus (22)

• Robust Federated Learning in a Heterogeneous Environment
• Optimal estimation of Gaussian mixtures via denoised method of moments
• Polynomial methods in statistical inference: theory and practice
• Statistical Convergence of the EM Algorithm on Gaussian Mixture Models
• Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit
• The EM Algorithm gives Sample-Optimality for Learning Mixtures of Well-Separated Gaussians
• Optimal Structured Principal Subspace Estimation: Metric Entropy and Minimax Rates
• Clustering a Mixture of Gaussians with Unknown Covariance
• The Asymptotic Distribution of Modularity in Weighted Signed Networks
• Optimal Clustering in Anisotropic Gaussian Mixture Models
• Nonparametric Modeling of Higher-Order Interactions via Hypergraphons
• Rate-Distortion Theory of Finite Point Processes
• Efficient Clustering for Stretched Mixtures: Landscape and Optimality
• Minimax estimation in linear models with unknown design over finite alphabets
• Structures of Spurious Local Minima in $k$-means
• Convergence Analysis of Gradient EM for Multi-component Gaussian Mixture
• An ${\ell }_p$ theory of PCA and spectral clustering
• Cutoff for exact recovery of Gaussian mixture models
• Partial recovery bounds for clustering with the relaxed $K$means
• Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labels
• Pair-Matching: Links Prediction with Adaptive Queries
• Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective