Nearly Optimal Risk Bounds for Kernel K-Means

03/09/2020
by   Yong Liu, et al.
19

In this paper, we study the statistical properties of the kernel k-means and obtain a nearly optimal excess risk bound, substantially improving the state-of-art bounds in the existing clustering risk analyses. We further analyze the statistical effect of computational approximations of the Nyström kernel k-means, and demonstrate that it achieves the same statistical accuracy as the exact kernel k-means considering only √(nk) Nyström landmark points. To the best of our knowledge, such sharp excess risk bounds for kernel (or approximate kernel) k-means have never been seen before.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset