Scientific Computing and Numerics (SCAN) Seminar

Yingjie FeiORIE, Cornell University
Hidden Integrality of SDP Relaxation for Sub-Gaussian Mixture Models

Monday, November 11, 2019 - 1:25pm
Gates 114

We consider the problem of estimating the discrete clustering structures under Sub-Gaussian Mixture Models. Our main results establish a hidden integrality property of a semidefinite programming (SDP) relaxation for this problem: while the optimal solutions to the SDP are not integer-valued in general, their estimation errors can be upper bounded in terms of the error of an idealized integer program. The error of the integer program, and hence that of the SDP, are further shown to decay exponentially in the signal-to-noise ratio. To the best of our knowledge, this is the first exponentially decaying error bound for convex relaxations of mixture models, and our results reveal the “global-to-local” mechanism that drives the performance of the SDP relaxation.