Robust k-means: a Theoretical Revisit
Over the last years, many variations of the quadratic k-means clustering procedure have been proposed, all aiming to robustify the performance of the algorithm in the presence of outliers. In general terms, two main approaches have been developed: one based on penalized regularization methods, and one based on trimming functions. In this work, we present a theoretical analysis of the robustness and consistency properties of a variant of the classical quadratic k-means algorithm, the robust k-means, which borrows ideas from outlier detection in regression. We show that two outliers in a dataset are enough to breakdown this clustering procedure. However, if we focus on "well-structured" datasets, then robust k-means can recover the underlying cluster structure in spite of the outliers. Finally, we show that, with slight modifications, the most general non-asymptotic results for consistency of quadratic k-means remain valid for this robust variant.
This paper examines the statistical property of the “robust k-means clustering” procedure. Specifically, they look at its robustness in terms of the finite sample breakdown point and its consistency.  The idea is to use techniques from variational analysis to study the functional properties of the RKM. In particular, the paper studies the “breakdown point” of a family of robust k-means objective, with different regularization terms (f_lambda). Their main result is that this family of k-means objective is actually not robust at the presence of at most two outliers (Thm 1).  This result shows that “robust” k-means objectives are actually not robust on general datasets. However, they explained that when the dataset has a clusterable structure, the objective is robust to outliers. Finally, they proved consistency of the objective. 
Technical quality:  I want to mainly point out one thing: the experiment section seems to be a little detached from the rest of the paper. The paper aims to study the property of the robust k-means objective, while the experiments compare two different robust methods for clustering, one is based on a heuristic (coordinate descent) that locally decreases the robust k-means objective, and the other is not related to any specific objective, if I understand it correctly.    Novelty/Originality:  I think the novelty of this paper lies in the fact that they apply techniques from optimization to study the properties of robust k-means objective.   Potential impact & Usefulness:  I think it is important to know that in general, the robust k-means is not robust to outliers, and that one needs to focus on dataset with more structure to obtain robustness. This discovery is inline with other recent work on the importance of clusterability for studying clustering procedures. I think the fact that they introduce the method of variational analysis to study clustering objectives could also inspire more work on understanding clustering objectives via this perspective.   Clarity and presentation  The interpretability of their result could be improved: in Section 3.3, it’s not clear to me what does Corollary 2 have to do with the conclusion at the end of this section. Also, it is also not clear to me what is the contribution of this paper regarding the discussion here: Is it already addressed in [2]? If not, how does the paper add insight to robustness of k-means objective with an underlying clusterable structure?  In general, it'd be nice if the authors can put the work in context of related work.