Consistency of Lloyd's Algorithm Under Perturbations
Dhruv Patel Hui Shen Shankar Bhamidi Yufeng Liu Vladas Pipiras
In the context of unsupervised learning, Lloyd's algorithm is one of the most
widely used clustering algorithms. It has inspired a plethora of work
investigating the correctness of the algorithm under various settings with
ground truth clusters. In particular, in 2016, Lu and Zhou have shown that the
mis-clustering rate of Lloyd's algorithm on $n$ independent samples from a
sub-Gaussian mixture is exponentially bounded after $O(\log(n))$ iterations,
assuming proper initialization of the algorithm. However, in many applications,
the true samples are unobserved and need to be learned from the data via
pre-processing pipelines such as spectral methods on appropriate data matrices.
We show that the mis-clustering rate of Lloyd's algorithm on perturbed samples
from a sub-Gaussian mixture is also exponentially bounded after $O(\log(n))$
iterations under the assumptions of proper initialization and that the
perturbation is small relative to the sub-Gaussian noise. In canonical settings
with ground truth clusters, we derive bounds for algorithms such as
$k$-means$++$ to find good initializations and thus leading to the correctness
of clustering via the main result. We show the implications of the results for
pipelines measuring the statistical significance of derived clusters from data
such as SigClust. We use these general results to derive implications in
providing theoretical guarantees on the misclustering rate for Lloyd's
algorithm in a host of applications, including high-dimensional time series,
multi-dimensional scaling, and community detection for sparse networks via
spectral clustering.