SDP Relaxation for Clustering Under Gaussian Mixture Model: Hidden Integrality, Statistical Optimality and Semirandom Robustness

• Activity Number: 586 - Theoretical Investigations on Discrete Structure Recovery
• Type: Topic Contributed
• Date/Time: Thursday, August 6, 2020 : 3:00 PM to 4:50 PM
• Sponsor: IMS
• Author(s): Yingjie Fei*
• Companies: Cornell University

Abstract

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, a property many algorithms lack.