SDP Relaxation for Clustering under Gaussian Mixture Model: Hidden Integrality, Optimality and Robustness
Yingjie Fei (ORIE, Cornell)
We will introduce the clustering problem under Gaussian Mixture Model. After discussing several popular algorithms, we will present an algorithm based on semidefinite programming (SDP). We show that despite being a relaxation, this algorithm achieves a nearly optimal error rate in terms of distance to the target solution, and that this result is enabled by a surprising connection with an Oracle integer program. Moreover, this algorithm is robust under the so-called semirandom model, for which understanding of many algorithms is lacking. Time permitting, we will discuss the optimality and robustness of SDP for the clustering problem under a closely related network model.