Clustering Stable Instances of Euclidean k-means
The Euclidean k-means problem is arguably the most widely-studied clustering problem in machine learning. While the k-means objective is NP-hard in the worst-case, practitioners have enjoyed remarkable success in applying heuristics like Lloyd's algorithm for this problem. To address this disconnect, we study the following question: what properties of real-world instances will enable us to design efficient algorithms and prove guarantees for finding the optimal clustering? We consider a natural notion called additive perturbation stability that we believe captures many practical instances of Euclidean k-means clustering. Stable instances have unique optimal k-means solutions that does not change even when each point is perturbed a little (in Euclidean distance). This captures the property that kmeans optimal solution should be tolerant to measurement errors and uncertainty in the points. We design efficient algorithms that provably recover the optimal clustering for instances that are additive perturbation stable. When the instance has some additional separation, we can design a simple, efficient algorithm with provable guarantees that is also robust to outliers. We also complement these results by studying the amount of stability in real datasets, and demonstrating that our algorithm performs well on these benchmark datasets.
The authors propose a notion of additive perturbation stability (APS) for Euclidean distances that maintain the optimal k-means clustering solution when each point in the data is moved by a sufficiently small Euclidean distance. I think the paper is rather interesting; however, the results of the paper are not very surprising.
Here are my comments regarding the paper:
(1) To my understanding, the results of Theorem 1.2 are only under the condition of APS. They only hold for the case of k=2 components and may lead to exponential dependence on $k$ components for large $k$. However, under the additional margin condition between any two pairs of cluster, we will able to guarantee the existence of polynomial algorithm on $k$. Can you provide a high level idea of how this additional assumption actually helps? Is it possible to have situation without that margin condition that there exists no algorithm that is polynomial in terms of $k$?
(2) I find the term $\Delta = (1/2-\epsilon)D$, where $D$ is the maximum distance between any pairs of means, is interesting. It also has a nice geometric meaning, which is the distance between any center to the apex of cone. I wonder whether this term $\Delta$ is intrinsic to the setting of APS? May it still be available under other perturbation notions?
(3) In the result of Theorem 1.3 and later Theorem 3.2, we both require the condition that $\rho$, which is a threshold for the margin between any two pairs of cluster, to be at least the oder of $\Delta/\epsilon^{2}$. As $\epsilon$ is sufficiently small, which is also the challenging theme of APS, the term $\Delta/\epsilon^{2}$ becomes very big, i.e., the distances between any two pairs of cluster become very large.  The fact that there is an algorithm running in time polynomial of $k$ components, sample size $n$, and dimension $d$ under that setting is not surprising. Is it possible to improve the lower bound of the margin between any two pairs of cluster? 
(4) In all the results with running time of the paper, the authors only provide the bound in terms of $n$, $d$, and $k$. I wonder about the constants that are along with these terms. How do they change with margin $\rho$ and $\epsilon$-APS?
(5) As the authors indicate in the paper, data in practice may have very small value of $\epsilon$. It seems that the conditions of the results with polynomial algorithms in the paper, e.g. Theorem 3.2, will not be satisfied by real data.
(6) It seems to me that the results in the paper can be extended to other distances that are different from Euclidean distance. The geometric explanation of additive perturbation stability may be different, which also leads to the modifications of other notions and results in the paper. Such extensions will be very useful in case that we want to work with kernel K-means to deal with sophisticated structures of data.