Sharper Generalization Bounds for Clustering
Authors: Shaojie Li, Yong Liu
ICML 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we propose a unified clustering learning framework and investigate its excess risk bounds, obtaining state-of-the-art upper bounds under mild assumptions. Specifically, we derive sharper bounds of order O(K2/n) under mild assumptions on the covering number of the hypothesis spaces, where these assumptions are easy to be verified. Moreover, for the hard clustering scheme, such as (kernel) k-means, if just assume the hypothesis functions to be bounded, we improve the upper bounds from the order O(K/ n) to O( K/ n). Furthermore, state-of-the-art bounds of faster order O(K/n) are obtained with the covering number assumptions. |
| Researcher Affiliation | Academia | 1Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China 2Beijing Key Laboratory of Big Data Management and Analysis Methods, Beijing, China. |
| Pseudocode | No | The paper does not contain any pseudocode or clearly labeled algorithm blocks. |
| Open Source Code | No | The paper does not mention providing open-source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments or use datasets, so no information about public datasets is provided. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments, thus no training/validation/test dataset splits are mentioned. |
| Hardware Specification | No | The paper is theoretical and does not conduct experiments, thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not conduct experiments, thus no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | The paper is theoretical and does not conduct experiments, thus no experimental setup details like hyperparameters or training settings are provided. |