Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model

References

• [1] Abbe E (2018) Community detection and the stochastic block model: Recent developments. J. Machine Learn. Res. 18(177):1−86.Google Scholar
• [2] Abbe E, Sandon C (2015) Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. IEEE 56th Annual Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 670–688.Google Scholar
• [3] Abbe E, Bandeira AS, Hall G (2016) Exact recovery in the stochastic block model. IEEE Trans. Inform. Theory 62(1):471–487.Google Scholar
• [4] Achlioptas D, McSherry F (2005) On spectral learning of mixtures of distributions. Proc. 18th Annual Conf. Comput. Learn. Theory (Springer, Berlin), 458–469.Google Scholar
• [5] Aloise D, Deshpande A, Hansen P, Popat P (2009) NP-hardness of Euclidean sum-of-squares clustering. Machine Learn. 75(2):245–248.Crossref, Google Scholar
• [6] Ames BPW, Vavasis SA (2014) Convex optimization for the planted k-disjoint-clique problem. Math. Programming 143(1–2):299–337.Crossref, Google Scholar
• [7] Amini AA, Levina E (2018) On semidefinite relaxations for the block model. Ann. Statist. 46(1):149–179.Crossref, Google Scholar
• [8] Awasthi P, Sheffet O (2012) Improved spectral-norm bounds for clustering. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Springer, Berlin), 37–49.Crossref, Google Scholar
• [9] Awasthi P, Vijayaraghavan A (2017) Clustering semi-random mixtures of Gaussians. Preprint, submitted November 23, https://arxiv.org/abs/1711.08841.Google Scholar
• [10] Awasthi P, Bandeira AS, Charikar M, Krishnaswamy R, Villar S, Ward R (2015) Relax, no need to round: Integrality of clustering formulations. Proc. 2015 Conf. Innovations Theoret. Comput. Sci. (Association for Computing Machinery, New York), 191–200.Google Scholar
• [11] Balakrishnan S, Wainwright MJ, Yu B (2017) Statistical guarantees for the EM algorithm: From population to sample-based analysis. Ann. Statist. 45(1):77–120.Crossref, Google Scholar
• [12] Bilodeau M, Brenner D (2008) Theory of Multivariate Statistics (Springer, New York).Google Scholar
• [13] Charikar M, Guha S, Tardos É, Shmoys DB (1999) A constant-factor approximation algorithm for the k-median problem. Proc. 31st Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 1–10.Google Scholar
• [14] Chen X, Yang Y (2018) Hanson-Wright inequality in Hilbert spaces with application to k-means clustering for non-Euclidean data. Preprint, submitted October 26, https://arxiv.org/abs/1810.11180.Google Scholar
• [15] Chen Y, Sanghavi S, Xu H (2014) Improved graph clustering. IEEE Trans. Inform. Theory 60(10):6440–6455.Crossref, Google Scholar
• [16] Coja-Oghlan A (2004) Coloring semirandom graphs optimally. Automata, Languages and Programming (Springer, Berlin), 383–395.Crossref, Google Scholar
• [17] Dasgupta S (1999) Learning mixtures of Gaussians. Proc. 40th Annual Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 634–644.Google Scholar
• [18] Daskalakis C, Tzamos C, Zampetakis M (2016) Ten steps of EM suffice for mixtures of two Gaussians. Preprint, submitted September 1, https://arxiv.org/abs/1609.00368.Google Scholar
• [19] Dempster AP, Laird NM, Rubin DB (1977) Maximum likelihood from incomplete data via the EM algorithm. J. Royal Statist. Soc. B 39(1):1–22.Crossref, Google Scholar
• [20] Diakonikolas I, Kane DM, Stewart A (2017) Statistical query lower bounds for robust estimation of high-dimensional Gaussians and Gaussian mixtures. Proc. IEEE 58th Annual Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 73–84.Google Scholar
• [21] Fei Y, Chen Y (2018) Hidden integrality of SDP relaxations for sub-Gaussian mixture models. Proc. 31st Conf. Learn. Theory (MLResearch Press), 1931–1965.Google Scholar
• [22] Fei Y, Chen Y (2019) Achieving the Bayes error rate in stochastic block model by SDP, robustly. Proc. 32nd Conf. Learn. Theory (MLResearch Press), 1235–1269.Google Scholar
• [23] Fei Y, Chen Y (2019) Achieving the Bayes error rate in synchronization and block models by SDP, robustly. Preprint, submitted April 21, https://arxiv.org/abs/1904.09635.Google Scholar
• [24] Fei Y, Chen Y (2019) Exponential error rates of SDP for block models: Beyond Grothendieck’s inequality. IEEE Trans. Inform. Theory 65(1):551–571.Crossref, Google Scholar
• [25] Feige U, Kilian J (2001) Heuristics for semirandom graph problems. J. Comput. System Sci. 63(4):639–671.Crossref, Google Scholar
• [26] Giraud C, Verzelen N (2019) Partial recovery bounds for clustering with the relaxed k-means. Math. Statist. Learn. 1(3):317–374.Crossref, Google Scholar
• [27] Guédon O, Vershynin R (2016) Community detection in sparse networks via Grothendieck’s inequality. Probab. Theory Related Fields 165(3–4):1025–1049.Crossref, Google Scholar
• [28] Hopkins SB, Li J (2018) Mixture models, robustness, and sum of squares proofs. Proc. 50th Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 1021–1034.Google Scholar
• [29] Iguchi T, Mixon DG, Peterson J, Villar S (2017) Probably certifiably correct k-means clustering. Math. Programming 165(2):605–642.Crossref, Google Scholar
• [30] Jain K, Mahdian M, Saberi A (2002) A new greedy approach for facility location problems. Proc. 34th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 731–740.Google Scholar
• [31] Jin C, Zhang Y, Balakrishnan S, Wainwright MJ, Jordan MI (2016) Local maxima in the likelihood of Gaussian mixture models: Structural results and algorithmic consequences. Lee D, Sugiyama M, Luxburg U, Guyon I, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 29 (Curran Associated, Red Hook, NY), 4116–4124.Google Scholar
• [32] Kalai AT, Moitra A, Valiant G (2010) Efficiently learning mixtures of two Gaussians. Proc. 42nd ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 553–562.Google Scholar
• [33] Kanungo T, Mount DM, Netanyahu NS, Piatko CD, Silverman R, Wu AY (2004) A local search approximation algorithm for k-means clustering. Comput. Geomerty 28(2–3):89–112.Crossref, Google Scholar
• [34] Klusowski JM, Brinda WD (2016) Statistical guarantees for estimating the centers of a two-component Gaussian mixture by EM. Preprint, submitted August 7, https://arxiv.org/abs/1608.02280.Google Scholar
• [35] Kothari PK, Steinhardt J (2017) Better agnostic clustering via relaxed tensor norms. Preprint, submitted November 20, https://arxiv.org/abs/1711.07465.Google Scholar
• [36] Krivelevich M, Vilenchik D (2006) Semirandom models as benchmarks for coloring algorithms. Proc. Third Workshop Analytic Algorithmics Combinatorics (Society for Industrial and Applied Mathematics, Philadelphia), 211–221.Google Scholar
• [37] Kumar A, Kannan R (2010) Clustering with spectral norm and the k-means algorithm. Proc. IEEE 51st Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 299–308.Google Scholar
• [38] Li S, Svensson O (2016) Approximating k-median via pseudo-approximation. SIAM J. Comput. 45(2):530–547.Crossref, Google Scholar
• [39] Li X, Chen Y, Xu J (2018) Convex relaxation methods for community detection. Preprint, submitted September 30, https://arxiv.org/abs/1810.00315.Google Scholar
• [40] Li X, Li Y, Ling S, Strohmer T, Wei K (2017) When do birds of a feather flock together? K-means, proximity, and conic programming. Preprint, submitted October 16, https://arxiv.org/abs/1710.06008.Google Scholar
• [41] Lloyd S (1982) Least squares quantization in PCM. IEEE Trans. Inform. Theory 28(2):129–137.Crossref, Google Scholar
• [42] Lu Y, Zhou HH (2016) Statistical and computational guarantees of Lloyd’s algorithm and its variants. Preprint, submitted December 7, https://arxiv.org/abs/1612.02099.Google Scholar
• [43] Mahajan M, Nimbhorkar P, Varadarajan K (2009) The planar k-means problem is NP-hard. Das S, Uehara R, eds. Proc. Internat. Workshop Algorithms Comput. (Springer, Berlin), 274–285.Google Scholar
• [44] Makarychev K, Makarychev Y, Vijayaraghavan A (2012) Approximation algorithms for semi-random partitioning problems. Proc. 44th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 367–384.Google Scholar
• [45] Makarychev K, Makarychev Y, Vijayaraghavan A (2016) Learning communities in the presence of errors. Proc. 29th Annual Conf. Learn. Theory (MLResearch Press), 1258–1291.Google Scholar
• [46] Mitzenmacher M, Upfal E (2005) Probability and Computing: Randomized Algorithms and Probabilistic Analysis (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [47] Mixon DG, Villar S, Ward R (2017) Clustering subgaussian mixtures by semidefinite programming. Inform. Inference 6(4):389–415.Crossref, Google Scholar
• [48] Moitra A, Valiant G (2010) Settling the polynomial learnability of mixtures of Gaussians. Proc. 51st Annual IEEE Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 93–102.Google Scholar
• [49] Moitra A, Perry W, Wein AS (2016) How robust are reconstruction thresholds for community detection? Proc. 48th Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 828–841.Google Scholar
• [50] Montanari A, Sen S (2016) Semidefinite programs on sparse random graphs and their application to community detection. Proc. 48th Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 814–827.Google Scholar
• [51] Ndaoud M (2018) Sharp optimal recovery in the two Gaussian mixture model. Preprint, submitted December 19, https://arxiv.org/abs/1812.08078.Google Scholar
• [52] Nellore A, Ward R (2015) Recovery guarantees for exemplar-based clustering. Inform. Comput. 245:165–180.Crossref, Google Scholar
• [53] Pearson K (1936) Method of moments and method of maximum likelihood. Biometrika 28(1/2):34–59.Crossref, Google Scholar
• [54] Peng J, Wei Y (2007) Approximating K-means-type clustering via semidefinite programming. SIAM J. Optim. 18(1):186–205.Crossref, Google Scholar
• [55] Peng J, Xia Y (2005) A new theoretical framework for k-means-type clustering. Chu W, Young Lin T, eds. Foundations and Advances in Data Mining (Springer, Berlin), 79–96.Crossref, Google Scholar
• [56] Regev O, Vijayaraghavan A (2017) On learning mixtures of well-separated Gaussians. Proc. IEEE 58th Annual Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 85–96.Google Scholar
• [57] Royer M (2017) Adaptive clustering through semidefinite programming. Guyon I, Luxburg UV, Bengio S, Wallach H, Fergus R, Vishwanathan S, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 30 (Curran Associates, Red Hook, NY), 1795–1803.Google Scholar
• [58] Vempala S, Wang G (2004) A spectral algorithm for learning mixture models. J. Comput. System Sci. 68(4):841–860.Crossref, Google Scholar
• [59] Vershynin R (2017) High-dimensional probability.Google Scholar
• [60] Xu J, Hsu DJ, Maleki A (2016) Global analysis of expectation maximization for mixtures of two Gaussians. Lee D, Sugiyama M, Luxburg U, Guyon I, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 29 (Curran Associates, Red Hook, NY), 2676–2684.Google Scholar
• [61] Yan B, Yin M, Sarkar P (2017) Convergence analysis of gradient EM for multi-component Gaussian mixture. Preprint, submitted May 23, https://arxiv.org/abs/1705.08530.Google Scholar