{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/132789"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/132789","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Statistical and algorithmic foundation of K-means clustering","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Zhuang, Yubo"],"institution":"University of Illinois Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Statistics","degree_department":null,"school":null,"contributors":["Yang, Yun","Liang, Feng","Chen, Xiaohui","Liu, Jingbo"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025-12","date_published":"2025-12","updated_at":"2026-07-22T22:25:07Z","subjects":["Unsupervised learning, clustering, optimization, semidefinite programming"],"languages":["en"],"rights":["Copyright 2025 Yubo Zhuang"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/132789","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Yang, Yun","Liang, Feng","Chen, Xiaohui","Liu, Jingbo"]},{"key":"dc:creator","label":"Author","values":["Zhuang, Yubo"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2025-12","2025-12-04"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Statistics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Unsupervised learning, clustering, optimization, semidefinite programming"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2025 Yubo Zhuang"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/132789"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2027-12-01","The student, Yubo Zhuang, accepted the attached license on 2025-12-01 at 13:38.","The student, Yubo Zhuang, submitted this Dissertation for approval on 2025-12-01 at 13:54.","This Dissertation was approved for publication on 2025-12-04 at 20:12.","DSpace SAF Submission Ingestion Package generated from Vireo submission #23005 on 2026-02-19 at 20:09:50"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Statistical and algorithmic foundation of K-means clustering"]}]}],"canonical_facts":{"dc:contributor":["Yang, Yun","Liang, Feng","Chen, Xiaohui","Liu, Jingbo"],"dc:creator":["Zhuang, Yubo"],"dc:date":["2025-12","2025-12-04"],"dc:description":["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.","Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2027-12-01","The student, Yubo Zhuang, accepted the attached license on 2025-12-01 at 13:38.","The student, Yubo Zhuang, submitted this Dissertation for approval on 2025-12-01 at 13:54.","This Dissertation was approved for publication on 2025-12-04 at 20:12.","DSpace SAF Submission Ingestion Package generated from Vireo submission #23005 on 2026-02-19 at 20:09:50"],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/132789"],"dc:language":["en"],"dc:rights":["Copyright 2025 Yubo Zhuang"],"dc:subject":["Unsupervised learning, clustering, optimization, semidefinite programming"],"dc:title":["Statistical and algorithmic foundation of K-means clustering"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Statistics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:07Z"}