SDP Relaxation for Learning Discrete Structures: Optimal Rates, Hidden Integrality, and Semirandom Robustness

Abstract:

We consider the problems of learning discrete structures from network data under statistical settings. Popular examples include various block models, Z2 synchronization and mixture models. Semidefinite programming (SDP) relaxation has emerged as a versatile and robust approach to these problems. We show that despite being a relaxation, SDP achieves the optimal Bayes error rate in terms of distance to the target solution. Moreover, SDP relaxation is provably robust under the so-called semirandom model, which frustrates many existing algorithms. Our proof involves a novel primal-dual analysis that establishes what we call the hidden integrality property: the SDP relaxation tightly approximates the optimal (yet unimplementable) integer programs with oracle information.

Joint work with Yingjie Fei (Cornell Ph.D.), who won 2nd place in INFORMS Nicholson Student Paper Competition.

About the Speaker:   

Yudong Chen is an assistant professor at the School of Operations Research and Information Engineering (ORIE), Cornell University. Before joining Cornell, he was a postdoctoral scholar at the Department of Electrical Engineering and Computer Sciences at University of California, Berkeley. He obtained his Ph.D. in Electrical and Computer Engineering from the University of Texas at Austin, and his M.S. and B.S. from Tsinghua University. His research interests include machine learning, high-dimensional and robust statistics, convex and non-convex optimization, and applications in communication and computer networks.