mlsanityData to 14 Oct 2026

Clustering a Mixture of Gaussians with Unknown Covariance

arXiv 2110.01602 ↗First posted 4 Oct 2021stat.ML cs.IT cs.LGcited by 14

Not on the map. Why?

Abstract (arXiv)

We investigate a clustering problem with data from a mixture of Gaussians that share a common but unknown, and potentially ill-conditioned, covariance matrix. We start by considering Gaussian mixtures with two equally-sized components and derive a Max-Cut integer program based on maximum likelihood estimation. We prove its solutions achieve the optimal misclassification rate when the number of samples grows linearly in the dimension, up to a logarithmic factor. However, solving the Max-cut problem appears to be computationally intractable. To overcome this, we develop an efficient spectral algorithm that attains the optimal rate but requires a quadratic sample size. Although this sample complexity is worse than that of the Max-cut problem, we conjecture that no polynomial-time method can perform better. Furthermore, we gather numerical and theoretical evidence that supports the existence of a statistical-computational gap. Finally, we generalize the Max-Cut program to a k-means program that handles multi-component mixtures with possibly unequal weights. It enjoys similar optimality guarantees for mixtures of distributions that satisfy a transportation-cost inequality, encompassing Gaussian and strongly log-concave distributions.

Key facts. Cited by 14 papers in the map (data through 14 Oct 2026). Builds on 25 of its 100 references that are in the map. First posted on arXiv 4 Oct 2021.

Builds on

25 of 100 references.

References · 25

  1. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,349
  2. 2016Matrix Completion has No Spurious Local Minimumcited by 125
  3. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 115
  4. 2019Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratiocited by 85
  5. 2016Statistical and Computational Guarantees of Lloyd's Algorithm and its Variantscited by 54
  6. 2017The power of sum-of-squares for detecting hidden structurescited by 54
  7. 2019Optimality of Spectral Clustering in the Gaussian Mixture Modelcited by 42
  8. 2015Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectorscited by 38
  9. 2018Singularity, Misspecification, and the Convergence Rate of EMcited by 38
  10. 2018Mean Estimation with Sub-Gaussian Rates in Polynomial Timecited by 33
  11. 2020Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limitscited by 30
  12. 2015Learning Mixtures of Gaussians in High Dimensionscited by 29
13 more
  1. 2015When Are Nonconvex Problems Not Scary?cited by 28
  2. 2019Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in O(√n) iterationscited by 27
  3. 2018Partial recovery bounds for clustering with the relaxed Kmeanscited by 25
  4. 2021Optimal Spectral Recovery of a Planted Vector in a Subspacecited by 21
  5. 2020Outlier-Robust Clustering of Non-Spherical Mixturescited by 19
  6. 2015Sum-of-squares lower bounds for planted cliquecited by 12
  7. 2020Statistical Query Lower Bounds for Tensor PCAcited by 11
  8. 2021Optimal Clustering in Anisotropic Gaussian Mixture Modelscited by 7
  9. 2019Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversariescited by 5
  10. 2020An ℓp theory of PCA and spectral clusteringcited by 4
  11. 2019A Tight Degree 4 Sum-of-Squares Lower Bound for the Sherrington-Kirkpatrick Hamiltoniancited by 3
  12. 2019Some compact notations for concentration inequalities and user-friendly resultscited by 3
  13. 2020Robustly Learning Mixtures of k Arbitrary Gaussianscited by 1

Built on by

Cited by year

Citing papers per year: 2021: 2; 2022: 4; 2023: 6; 2024: 1; 2025: 1.

14 papers.

Sort:

  1. 2021Lattice-Based Methods Surpass Sum-of-Squares in Clusteringcited by 25
  2. 2023Pseudo-Labeling for Kernel Ridge Regression under Covariate Shiftcited by 17
  3. 2022Leave-one-out Singular Subspace Perturbation Analysis for Spectral Clusteringcited by 15
  4. 2022Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplaycited by 15
  5. 2021Minimax Supervised Clustering in the Anisotropic Gaussian Mixture Model: A new take on Robust Interpolationcited by 6
  6. 2022Optimal Estimation and Computational Limit of Low-rank Gaussian Mixturescited by 6
  7. 2023Computational Lower Bounds for Graphon Estimation via Low-degree Polynomialscited by 6
  8. 2023SQ Lower Bounds for Random Sparse Planted Vector Problemcited by 3
  9. 2023Sharp-SSL: Selective high-dimensional axis-aligned random projections for semi-supervised learningcited by 2
  10. 2023Consistency of Lloyd's Algorithm Under Perturbationscited by 2
  11. 2022Sketch-and-solve approaches to k-means clustering by semidefinite programmingcited by 1
  12. 2024Factor Adjusted Spectral Clustering for Mixture Modelscited by 1
2 more
  1. 2023SQ Lower Bounds for Learning Bounded Covariance GMMscited by 0
  2. 2025Recovering Imbalanced Clusters via Gradient-Based Projection Pursuitcited by 0