Statistically Optimal $K$-means Clustering via Nonnegative Low-rank Semidefinite Programming
Authors: Yubo Zhuang, Xiaohui Chen, Yun Yang, Richard Y. Zhang
ICLR 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In our experiments, we observe that our algorithm achieves significantly smaller mis-clustering errors compared to the existing state-of-the-art while maintaining scalability. We present numerical results to assess the effectiveness of the proposed NLR method. We first conduct two simulation experiments using GMM to evaluate the convergence and compare the performance of NLR with other methods. Then, we perform a comparison using two real datasets. Finally, we conduct further experiments on three datasets in UCI. |
| Researcher Affiliation | Academia | University of Illinois at Urbana-Champaign University of Southern California |
| Pseudocode | Yes | Algorithm 1 Primal-dual algorithm for solving NLR formulation (6) of K-means clustering Input. Dissimilarity matrix A = XT X, clustering parameter K 1, rank parameter r K, augmentation parameter β > 0, step size α > 0. Output. A second-order locally optimal point U. Algorithm. Initialize y = 0. Do the following:... |
| Open Source Code | No | The paper does not provide an explicit statement or link to its open-source code. It mentions using existing solvers like SDPNAL+ but does not release its own implementation. |
| Open Datasets | Yes | We conduct a comparison of all methods on the CIFAR-10 dataset... UCI datasets. To empirically illustrate the advantages and robustness of our method against the GMM assumption, we conduct further experiments on three datasets in UCI: Msplice, Heart and DNA. (Dua and Graff, 2017). |
| Dataset Splits | No | The paper mentions 'train' and 'test' data, but does not explicitly specify a 'validation' dataset split for hyperparameter tuning or early stopping. |
| Hardware Specification | No | The paper mentions 'a typical workstation hardware' but does not provide specific details on the CPU, GPU, or other hardware components used for the experiments. |
| Software Dependencies | No | The paper mentions software components like 'SDPNAL+ solver' and 'Inception v3 model' but does not provide specific version numbers for these or any other software dependencies. |
| Experiment Setup | Yes | In practice, we start with small step size α = 10 6 and increase α until α = 10 3. Similarly, we start with a small augmentation term β = 1 and increase β until β = 103. The second experiment shows that the choice of r does not significantly affect the convergence rate. In practice, we found that r = K will result in many local minima for small separations. Therefore, we slightly increase r and choose r = 2K for all applications, which turns out to provide desirable statistical performance that is comparable to or slightly better than SDP. |