Timezone: »
Clustering is an important unsupervised learning problem in machine learning and statistics. Among many existing algorithms, kernel \km 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.
Author Information
Bowei Yan (University of Texas at Austin)
Purnamrita Sarkar (U.C. Berkeley)
More from the Same Authors
-
2021 Spotlight: Bootstrapping the Error of Oja's Algorithm »
Robert Lunde · Purnamrita Sarkar · Rachel Ward -
2021 Poster: Bootstrapping the Error of Oja's Algorithm »
Robert Lunde · Purnamrita Sarkar · Rachel Ward -
2018 Poster: Overlapping Clustering Models, and One (class) SVM to Bind Them All »
Xueyu Mao · Purnamrita Sarkar · Deepayan Chakrabarti -
2018 Spotlight: Overlapping Clustering Models, and One (class) SVM to Bind Them All »
Xueyu Mao · Purnamrita Sarkar · Deepayan Chakrabarti -
2018 Poster: Mean Field for the Stochastic Blockmodel: Optimization Landscape and Convergence Issues »
Soumendu Sundar Mukherjee · Purnamrita Sarkar · Y. X. Rachel Wang · Bowei Yan -
2017 Poster: Convergence of Gradient EM on Multi-component Mixture of Gaussians »
Bowei Yan · Mingzhang Yin · Purnamrita Sarkar -
2017 Poster: On clustering network-valued data »
Soumendu Sundar Mukherjee · Purnamrita Sarkar · Lizhen Lin -
2015 Poster: The Consistency of Common Neighbors for Link Prediction in Stochastic Blockmodels »
Purnamrita Sarkar · Deepayan Chakrabarti · peter j bickel