Skip to main content

Statistics Seminar

Clustering a mixture of Gaussians with unknown covariance by Mateo Diaz

Event Details

Wednesday, April 12, 2023
4-5 p.m.

Date: April 12, 2023

Speaker: Mateo Diaz


Title: Clustering a mixture of Gaussians with unknown covariance.

Abstract: Clustering is a fundamental data scientific task with broad applications. This talk investigates a simple clustering problem with data from a mixture of Gaussians that share a common but unknown and potentially ill-conditioned covariance matrix. We consider Gaussian mixtures with two equally-sized components and derive a Max-Cut integer program based on maximum likelihood estimation. We show 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 iterative 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 present numerical and theoretical evidence that supports the existence of a statistical-computational gap.