Statistical and algorithmic foundation of K-means clustering

Clustering is a widely deployed unsupervised learning tool. Given data in the Euclidean spoace, K-means clustering is one of the most commonly used clustering methods, which minimize the distance between each point to the centroid of its assigned cluster. Among the popular clustering methods, SDP clustering enjoys the strongest statistical guarantees under the standard Gaussian mixture models in that it achieves an information-theoretic bound for exact recovery. However, the original SDP method is limited to isotropic covariance matrices for Gaussians, and it has prohibitively high costs of solving the SDP optimization problem. This project wants to develop algorithms to improve the computational efficiency and extend the results to more general cases in the following aspects: Extend the algorithms and results to heterogeneous data as well as other types of data like distributions or measures; develop algorithms to enhance the computational performance for SDP or to efficiently solve the SDP for clustering; propose 1-st order and 2-nd order methods to solve general non-negative SDP optimization problems with minimal assumptions, which can be applied to various hidden community detection tasks.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Statistics

Grantor

University of Illinois Urbana-Champaign

Year dc:date

2025

Author dc:creator

• Zhuang, Yubo

Contributors dc:contributor

• Yang, Yun
• Liang, Feng
• Chen, Xiaohui
• Liu, Jingbo

• Unsupervised learning, clustering, optimization, semidefinite programming

Statement dc:rights

• Copyright 2025 Yubo Zhuang

Language dc:language

en

Handle dc:identifier

https://hdl.handle.net/2142/132789

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/132789