Timezone: »
Poster
Randomized Sketches for Clustering: Fast and Optimal Kernel $k$-Means
Rong Yin · Yong Liu · Weiping Wang · Dan Meng
Kernel $k$-means is arguably one of the most common approaches to clustering. In this paper, we investigate the efficiency of kernel $k$-means combined with randomized sketches in terms of both statistical analysis and computational requirements. More precisely, we propose a unified randomized sketches framework to kernel $k$-means and investigate its excess risk bounds, obtaining the state-of-the-art risk bound with only a fraction of computations. Indeed, we prove that it suffices to choose the sketch dimension $\Omega(\sqrt{n})$ to obtain the same accuracy of exact kernel $k$-means with greatly reducing the computational costs, for sub-Gaussian sketches, the randomized orthogonal system (ROS) sketches, and Nystr\"{o}m kernel $k$-means, where $n$ is the number of samples. To the best of our knowledge, this is the first result of this kind for unsupervised learning. Finally, the numerical experiments on simulated data and real-world datasets validate our theoretical analysis.
Author Information
Rong Yin (Institute of Information Engineering, Chinese Academy of Sciences)
Yong Liu (Renmin University of China)
Weiping Wang (Institute of Information Engineering, CAS, China)
Dan Meng (Institute of information engineering, Chinese Academy of Sciences)
More from the Same Authors
-
2021 Spotlight: Improved Learning Rates of a Functional Lasso-type SVM with Sparse Multi-Kernel Representation »
shaogao lv · Junhui Wang · Jiankun Liu · Yong Liu -
2021 Spotlight: Refined Learning Bounds for Kernel and Approximate $k$-Means »
Yong Liu -
2022 Poster: A Win-win Deal: Towards Sparse and Robust Pre-trained Language Models »
Yuanxin Liu · Fandong Meng · Zheng Lin · Jiangnan Li · Peng Fu · Yanan Cao · Weiping Wang · Jie Zhou -
2022 Poster: Fine-Grained Analysis of Stability and Generalization for Modern Meta Learning Algorithms »
Jiechao Guan · Yong Liu · Zhiwu Lu -
2022 Spotlight: A Win-win Deal: Towards Sparse and Robust Pre-trained Language Models »
Yuanxin Liu · Fandong Meng · Zheng Lin · Jiangnan Li · Peng Fu · Yanan Cao · Weiping Wang · Jie Zhou -
2022 Spotlight: Lightning Talks 6A-1 »
Ziyi Wang · Nian Liu · Yaming Yang · Qilong Wang · Yuanxin Liu · Zongxin Yang · Yizhao Gao · Yanchen Deng · Dongze Lian · Nanyi Fei · Ziyu Guan · Xiao Wang · Shufeng Kong · Xumin Yu · Daquan Zhou · Yi Yang · Fandong Meng · Mingze Gao · Caihua Liu · Yongming Rao · Zheng Lin · Haoyu Lu · Zhe Wang · Jiashi Feng · Zhaolin Zhang · Deyu Bo · Xinchao Wang · Chuan Shi · Jiangnan Li · Jiangtao Xie · Jie Zhou · Zhiwu Lu · Wei Zhao · Bo An · Jiwen Lu · Peihua Li · Jian Pei · Hao Jiang · Cai Xu · Peng Fu · Qinghua Hu · Yijie Li · Weigang Lu · Yanan Cao · Jianbin Huang · Weiping Wang · Zhao Cao · Jie Zhou -
2022 Spotlight: Fine-Grained Analysis of Stability and Generalization for Modern Meta Learning Algorithms »
Jiechao Guan · Yong Liu · Zhiwu Lu -
2022 Spotlight: Lightning Talks 4A-1 »
Jiawei Huang · Su Jia · Abdurakhmon Sadiev · Ruomin Huang · Yuanyu Wan · Denizalp Goktas · Jiechao Guan · Andrew Li · Wei-Wei Tu · Li Zhao · Amy Greenwald · Jiawei Huang · Dmitry Kovalev · Yong Liu · Wenjie Liu · Peter Richtarik · Lijun Zhang · Zhiwu Lu · R Ravi · Tao Qin · Wei Chen · Hu Ding · Nan Jiang · Tie-Yan Liu -
2022 Spotlight: Stability and Generalization of Kernel Clustering: from Single Kernel to Multiple Kernel »
Weixuan Liang · Xinwang Liu · Yong Liu · sihang zhou · Jun-Jie Huang · Siwei Wang · Jiyuan Liu · Yi Zhang · En Zhu -
2022 Poster: Stability and Generalization of Kernel Clustering: from Single Kernel to Multiple Kernel »
Weixuan Liang · Xinwang Liu · Yong Liu · sihang zhou · Jun-Jie Huang · Siwei Wang · Jiyuan Liu · Yi Zhang · En Zhu -
2021 Poster: Towards Sharper Generalization Bounds for Structured Prediction »
Shaojie Li · Yong Liu -
2021 Poster: Refined Learning Bounds for Kernel and Approximate $k$-Means »
Yong Liu -
2021 Poster: Improved Learning Rates of a Functional Lasso-type SVM with Sparse Multi-Kernel Representation »
shaogao lv · Junhui Wang · Jiankun Liu · Yong Liu -
2019 Poster: Two Generator Game: Learning to Sample via Linear Goodness-of-Fit Test »
Lizhong Ding · Mengyang Yu · Li Liu · Fan Zhu · Yong Liu · Yu Li · Ling Shao -
2018 Poster: Multi-Class Learning: From Theory to Algorithm »
Jian Li · Yong Liu · Rong Yin · Hua Zhang · Lizhong Ding · Weiping Wang