Timezone: »
Spotlight
Refined Learning Bounds for Kernel and Approximate $k$Means
Yong Liu
@ None
Kernel $k$means is one of the most popular approaches to clustering and its theoretical properties have been investigated for decades. However, the existing stateoftheart risk bounds are of order $\mathcal{O}(k/\sqrt{n})$, which do not match with the stated lower bound $\Omega(\sqrt{k/n})$ in terms of $k$, where $k$ is the number of clusters and $n$ is the size of the training set. In this paper, we study the statistical properties of kernel $k$means and Nystr\"{o}mbased kernel $k$means, and obtain optimal clustering risk bounds, which improve the existing risk bounds. Particularly, based on a refined upper bound of Rademacher complexity [21], we first derive an optimal risk bound of rate $\mathcal{O}(\sqrt{k/n})$ for empirical risk minimizer (ERM), and further extend it to general cases beyond ERM. Then, we analyze the statistical effect of computational approximations of Nystr\"{o}m kernel $k$means, and prove that it achieves the same statistical accuracy as the original kernel $k$means considering only $\Omega(\sqrt{nk})$ Nystr\"{o}m landmark points. We further relax the restriction of landmark points from $\Omega(\sqrt{nk})$ to $\Omega(\sqrt{n})$ under a mild condition. Finally, we validate the theoretical findings via numerical experiments.
Author Information
Yong Liu (Renmin University of China)
Related Events (a corresponding poster, oral, or spotlight)

2021 Poster: Refined Learning Bounds for Kernel and Approximate $k$Means »
Thu Dec 9th 08:30  10:00 AM Room None
More from the Same Authors

2021 Spotlight: Improved Learning Rates of a Functional Lassotype SVM with Sparse MultiKernel Representation »
shaogao lv · Junhui Wang · Jiankun Liu · Yong Liu 
2021 Poster: Towards Sharper Generalization Bounds for Structured Prediction »
Shaojie Li · Yong Liu 
2021 Poster: Improved Learning Rates of a Functional Lassotype SVM with Sparse MultiKernel Representation »
shaogao lv · Junhui Wang · Jiankun Liu · Yong Liu 
2019 Poster: Two Generator Game: Learning to Sample via Linear GoodnessofFit Test »
Lizhong Ding · Mengyang Yu · Li Liu · Fan Zhu · Yong Liu · Yu Li · Ling Shao 
2018 Poster: MultiClass Learning: From Theory to Algorithm »
Jian Li · Yong Liu · Rong Yin · Hua Zhang · Lizhong Ding · Weiping Wang