Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model

Yingjie Fei () and Yudong Chen ()
Additional contact information
Yingjie Fei: School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14850
Yudong Chen: Department of Computer Sciences, University of Wisconsin–Madison, Madison, Wisconsin 53706

Mathematics of Operations Research, 2022, vol. 47, issue 3, 2464-2493

Abstract: We consider the problem of estimating the discrete clustering structures under the sub-Gaussian mixture model. Our main results establish a hidden integrality property of a semidefinite programming (SDP) relaxation for this problem: while the optimal solution to the SDP is not integer-valued in general, its estimation error can be upper bounded by that 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. In addition, we show that the SDP relaxation is robust under the semirandom setting in which an adversary can modify the data generated from the mixture model. In particular, we generalize the hidden integrality property to the semirandom model and thereby show that SDP achieves the optimal error bound in this setting. These results together highlight the “global-to-local” mechanism that drives the performance of the SDP relaxation. To the best of our knowledge, our result is the first exponentially decaying error bound for convex relaxations of mixture models. A corollary of our results shows that in certain regimes, the SDP solutions are in fact integral and exact. More generally, our results establish sufficient conditions for the SDP to correctly recover the cluster memberships of ( 1 − δ ) fraction of the points for any δ ∈ ( 0 , 1 ) . As a special case, we show that under the d -dimensional stochastic ball model, SDP achieves nontrivial (sometimes exact) recovery when the center separation is as small as 1 / d , which improves upon previous exact recovery results that require constant separation.

Keywords: Primary: H30; secondary: 62; exponential rates; hidden integrality; mixture models; SDP relaxation; semirandom robustness; stochastic ball model (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1216 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:3:p:2464-2493

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().