How to tell when a clustering is (approximately) correct using convex relaxations
We introduce the Sublevel Set (SS) method, a generic method to obtain sufficient guarantees of near-optimality and uniqueness (up to small perturbations) for a clustering. This method can be instantiated for a variety of clustering loss functions for which convex relaxations exist. Obtaining the guarantees in practice amounts to solving a convex optimization. We demonstrate the applicability of this method by obtaining distribution free guarantees for K-means clustering on realistic data sets.
This paper presents a general method to derive bounds on how close a given clustering is to an optimal clustering where optimal is defined according to certain loss functions. The method can be used for any clustering loss function for which convex relaxation exists (e.g., K-means, spectral clustering). They show in experiments they obtain much better bounds than the only related work (as far as I know) on K-means [Mei06].  The paper is well-written and easy to follow and addresses an important problem of evaluating the quality of clusterings. The main contribution of the paper is to make use of tighter convex relaxations to derive bounds on the distance between optimal clustering and a given clustering. It is obvious that tighter the convex relaxation the better the bounds are and hence they use SDP relaxation for the K-means problem (which can be computationally prohibitive for large datasets). Usually the convex relaxation already gives a bound on how far the optimal loss value is from the loss of a given clustering. Is this already indicative of how far the optimal solution is from the given clustering?  My main concern is how good the bounds are in more realistic settings. Moreover, the method can fail to get a valid bound if some certain technical condition fails (which is easy to check after solving the convex relaxation). As they show in experiments the method fails to obtain valid bounds for difficult settings (high noise, unequal sizes of clusters).  On the positive side, + the method provides much better bounds than the spectral bounds derived in [Mei06] + several synthetic experiments are conducted under various settings to illustrate the bounds obtained by the method.  Comments: - From Theorem 3 it appears that the method works for spectral clustering as well; experiments on spectral clustering would be interesting, e.g., to check the quality of the solutions obtained by recent methods like [HeiSet11, RMH14]. - It was not clear the need for removing outliers in the synthetic experiments. - The method is computationally expensive; they hint at reducing the complexity by removing data points that do not affect the clustering but this needs to be further formalized. - More experiments on real world data would enhance the paper (currently only one real world data is used). - Missing references: line 248, line 253  [HeiSet11] Beyond spectral clustering: Tight continuous relaxations of balanced graph cuts. NIPS 2011.