Adversarially robust clustering with optimality guarantees
Soham Jana Kun Yang Sanjeev Kulkarni
We consider the problem of clustering data points coming from sub-Gaussian
mixtures. Existing methods that provably achieve the optimal mislabeling error,
such as the Lloyd algorithm, are usually vulnerable to outliers. In contrast,
clustering methods seemingly robust to adversarial perturbations are not known
to satisfy the optimal statistical guarantees. We propose a simple algorithm
that obtains the optimal mislabeling rate even when we allow adversarial
outliers to be present. Our algorithm achieves the optimal error rate in
constant iterations when a weak initialization condition is satisfied. In the
absence of outliers, in fixed dimensions, our theoretical guarantees are
similar to that of the Lloyd algorithm. Extensive experiments on various
simulated data sets are conducted to support the theoretical guarantees of our
method.