{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T08:42:28Z","timestamp":1773218548070,"version":"3.50.1"},"reference-count":56,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"1","license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"am","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["1657420"],"award-info":[{"award-number":["1657420"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["1704828"],"award-info":[{"award-number":["1704828"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"CAREER Award","award":["CCF-2047910"],"award-info":[{"award-number":["CCF-2047910"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Inform. Theory"],"published-print":{"date-parts":[[2022,1]]},"DOI":"10.1109\/tit.2021.3122465","type":"journal-article","created":{"date-parts":[[2021,10,25]],"date-time":"2021-10-25T19:49:08Z","timestamp":1635191348000},"page":"395-422","source":"Crossref","is-referenced-by-count":13,"title":["Structures of Spurious Local Minima in <i>k<\/i>-Means"],"prefix":"10.1109","volume":"68","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4997-604X","authenticated-orcid":false,"given":"Wei","family":"Qian","sequence":"first","affiliation":[]},{"given":"Yuqian","family":"Zhang","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6416-5635","authenticated-orcid":false,"given":"Yudong","family":"Chen","sequence":"additional","affiliation":[]}],"member":"263","reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2009.09.011"},{"key":"ref2","article-title":"The hardness of k-means clustering","author":"Dasgupta","year":"2008"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00202-1_24"},{"key":"ref4","first-page":"754","article-title":"The hardness of approximation of Euclidean k-means","volume-title":"Proc. 31st Int. Symp. Comput. Geometry","author":"Awasthi"},{"issue":"14","key":"ref5","first-page":"281","article-title":"Some methods for classification and analysis of multivariate observations","volume-title":"Proc. 5th Berkeley Symp. Math. Statist. Probab.","volume":"1","author":"MacQueen"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.2307\/2346830"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1037\/1082-989X.8.3.294"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1037\/1082-989X.11.2.178"},{"key":"ref9","article-title":"Learning mixtures of Gaussians using the k-means algorithm","author":"Chaudhuri","year":"2009","journal-title":"arXiv:0912.0086"},{"key":"ref10","first-page":"2676","article-title":"Global analysis of expectation maximization for mixtures of two Gaussians","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Xu"},{"key":"ref11","first-page":"704","article-title":"Ten steps of EM suffice for mixtures of two Gaussians","volume-title":"Proc. Conf. Learn. Theory","author":"Daskalakis"},{"key":"ref12","first-page":"4116","article-title":"Local maxima in the likelihood of Gaussian mixture models: Structural results and algorithmic consequences","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Jin"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"ref14","first-page":"585","article-title":"Convergence properties of the k-means algorithms","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Bottou"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72927-3_47"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1348\/000711005X48266"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.7"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.003"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02293907"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1127-9"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137880"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.35"},{"key":"ref23","article-title":"Statistical and computational guarantees of Lloyd\u2019s algorithm and its variants","author":"Lu","year":"2016","journal-title":"arXiv:1612.02099"},{"key":"ref24","first-page":"1027","article-title":"k-means++: The advantages of careful seeding","volume-title":"Proc. 18th Annu. ACM-SIAM Symp. Discrete Algorithms","author":"Arthur"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395117"},{"key":"ref26","first-page":"203","article-title":"A probabilistic analysis of EM for mixtures of separated, spherical Gaussians","volume":"8","author":"Dasgupta","year":"2007","journal-title":"J. Mach. Learn. Res."},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1007\/11362197_4"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1137\/050641983"},{"key":"ref29","first-page":"19","article-title":"Finding exemplars from pairwise dissimilarities via simultaneous sparse recovery","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Elhamifar"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2015.09.002"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688116"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1333-x"},{"key":"ref33","first-page":"1931","article-title":"Hidden integrality of SDP relaxation for sub-Gaussian mixture models","volume-title":"Proc. Conf. Learn. Theory (COLT)","author":"Fei"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517\u20136161.1977.tb01600.x"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1214\/16-AOS1435"},{"key":"ref36","first-page":"4795","article-title":"Global convergence of least squares EM for demixing two log-concave densities","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Qian"},{"key":"ref37","first-page":"2055","article-title":"Global convergence of the EM algorithm for mixtures of two component linear regression","volume-title":"Proc. Conf. Learn. Theory","author":"Kwon"},{"key":"ref38","first-page":"10662","article-title":"Benefits of over-parameterization with EM","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Xu"},{"key":"ref39","first-page":"1567","article-title":"Regularized EM algorithms: A unified framework and statistical guarantees","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Yi"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2891628"},{"key":"ref41","first-page":"6956","article-title":"Convergence of gradient EM on multi-component mixture of Gaussians","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Yan"},{"key":"ref42","article-title":"EM converges for a mixture of many linear regressions","author":"Kwon","year":"2019","journal-title":"arXiv:1905.12106"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1007\/11503415_30"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1214\/17-AOS1637"},{"key":"ref45","first-page":"3873","article-title":"Global optimality of local search for low rank matrix recovery","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Bhojanapalli"},{"key":"ref46","first-page":"4430","article-title":"Spurious local minima are common in two-layer ReLU neural networks","volume-title":"Proc. Int. Conf. Mach. Learn.","author":"Safran"},{"key":"ref47","first-page":"1","article-title":"Matrix completion has no spurious local minimum","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Ge"},{"key":"ref48","article-title":"PROMENADE\u2014An on-line pattern recognition system","author":"Ball","year":"1967"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.21236\/AD0709067"},{"key":"ref50","first-page":"1","article-title":"Optimized K-means: An algorithm of initial centroids optimization for k-means","volume-title":"Proc. Seminar Soft Comput., Intell. Syst., Inf. Technol. (SIIT)","author":"Barakbah"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1109\/CIDM.2009.4938630"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1007\/s10489-018-1238-7"},{"key":"ref53","article-title":"Empirical study of the benefits of overparameterization in learning latent variable models","author":"Buhai","year":"2019","journal-title":"arXiv:1907.00030"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1214\/19-aos1924"},{"key":"ref55","first-page":"2328","article-title":"Structured local minima in sparse blind deconvolution","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Zhang"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1017\/9781108627771"}],"container-title":["IEEE Transactions on Information Theory"],"original-title":[],"link":[{"URL":"https:\/\/ieeexplore.ieee.org\/ielam\/18\/9660615\/9585110-aam.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/18\/9660615\/09585110.pdf?arnumber=9585110","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,12]],"date-time":"2024-01-12T00:03:21Z","timestamp":1705017801000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/9585110\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1]]},"references-count":56,"journal-issue":{"issue":"1"},"URL":"https:\/\/doi.org\/10.1109\/tit.2021.3122465","relation":{},"ISSN":["0018-9448","1557-9654"],"issn-type":[{"value":"0018-9448","type":"print"},{"value":"1557-9654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1]]}}}