Home > Events > 2017 Seminars & Colloquia > Yudong Chen, Cornell University

Yudong Chen, Cornell University

Main Content

Exponential error rates of semidefinite programming for block models
14 September 2017 from 4:00 PM to 5:00 PM
201 Thomas Bld
Contact Name
Lorey Burghard
Add event to calendar

We consider the community detection problem under the Stochastic and Censored Block Models. We show that the semidefinite programming (SDP) formulation for this problem achieves an error rate that decays exponentially in the signal-to-noise ratio. Significantly, even though we are estimating a combinatorial structure by solving a continuous optimization problem, this error rate is achieved by the SDP itself without any further pre/post-processing or rounding. Our results improve upon existing polynomially-decaying error bounds obtained via the Grothendieck’s inequality. The analysis highlights the implicit regularization effect of the SDP, and its robustness in the sparse graph regime.


Bio: Yudong Chen is an assistant professor at the School of Operations Research and Information Engineering (ORIE), Cornell University. In 2013-2015 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 in 2013, 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 networks and financial systems.



Filed under: ,

Navigation for this Section