On Robustness of Kernel Clustering
Clustering is an important unsupervised learning problem in machine learning and statistics. Among many existing algorithms, kernel k-means has drawn much research attention due to its ability to find non-linear cluster boundaries and its inherent simplicity. There are two main approaches for kernel k-means: SVD of the kernel matrix and convex relaxations. Despite the attention kernel clustering has received both from theoretical and applied quarters, not much is known about robustness of the methods. In this paper we first introduce a semidefinite programming relaxation for the kernel clustering problem, then prove that under a suitable model specification, both K-SVD and SDP approaches are consistent in the limit, albeit SDP is strongly consistent, i.e. achieves exact recovery, whereas K-SVD is weakly consistent, i.e. the fraction of misclassified nodes vanish. Also the error bounds suggest that SDP is more resilient towards outliers, which we also demonstrate with experiments.
This paper introduces a semidefinite programming relaxation for the kernel clustering problem, then proves that under a suitable model specification, both the Kernel-SVD and Kernel-SDP approaches are consistent in the limit, albeit SDP is strongly consistent, i.e. achieves exact recovery, whereas K-SVD is weakly consistent. Experimental results on toy datasets are presented.
Here are few comments.   1. The analysis assumes that all inlier clusters are of equal size and uses this fact for analysis. However, this seems to be a very restrictive assumption. In real life, it is very unlikely that all clusters will be of equal size. It will be nice to have a discussion describing how much additional work is necessary to remove this unrealistic assumption.  2.  Using the current notation both the algorithms takes only inliers as input (Y-1,... Y_n are inliers). It will be nice to change the notation so that input to both algorithms can be both inliers as well as outliers.  3. Spectral clustering is based on normalized/unnormalized "Laplacian matrix" and not kernel matrix. It will be nice to have a discussion how they are related. Note that in case of spectral clustering using Laplacian matrix, eigenvectors corresponding to the lowest eigenvalues of Graph laplacian is used for embedding and k-means clustering, where as in case of kernel-PCA eigenvectors corresponding to the largest eigenvalues of the Gram matrix are used for k-means clustering.  4. Theorem 1 is based on Gaussian kernel (line 135) so is Lemma 1. Therefore, notation wise it will be easier to use K, \tilde{K} and exponential in place of function f etc.  5. The theoretical results of this paper are " high probability" results based on theorem 1. Theorem 1 uses an union bound and the failure probability is n^2p^{-c^2\rho}, where c and \rho are constants. Note that c is controllable depending on how much deviation one wants but \rho is just an existential constant. Therefore, for fixed data dimension p, as n tends to infinity the failure probability tends to one. For any fixed p, this limits the maximum size of inliers that the algorithm can handle. In particular if we want a failure probability of \delta, that implies n can be at most \sqrt{\delta p^{c^2\rho}}$.   6. Statement of Lemma 1 is a little unclear. In particular, the inequality in the proof is not clear. Note that only a lower bound of the eigengap is proved. No upper bound Big-Oh is proved and therefore using \Theta notation may not be correct.  7. In the supplementary material (proof of Lemma 1), no justification is not provided for the inequality between line 67 and 68. It is not clear how this inequality is obtained.  8. In proof of theorem 3, first only inliers are considered when no outliers are present and Davis-Kahan theorem is applied. However, in this case the corresponding expression, equation 4, involves $m$ which is the number of ouliers. This sounds strange because this analysis does not consider any outlier and since presence of ouliers are handled right after equation 4 and is given in equation 5.  9. Proof of theorem 3 utilizes results of [22]  which requires that centroids are well separated. It guaranteed in proof of theorem 3 that the centroids are well separated  so that results of [22] can be applied.   10. The accuracy of the clustering process is measured based on the criteria that inliers are assigned to the correct respective clusters. However, in presence of outliers, if an outlier is assigned to a cluster (consists of inliers) that is also an error.  How is this error taken into consideration in the analysis?   11. All experimenal results are on toy datasets involving same \sigma for all clusters. Experimental results can be improved by considering, (a) different sigma values  for different clusters in case of toy (synthetic) datasets, (b) varying dimensionality p for synthetic datasets (choce of specific p=160 seems arbitrary),  (c) applying the proposed method on realworld datasets.