Non-convex Exact Community Recovery In Stochastic Block Model

Nov 30, 2021 04:00 PM Singapore (Registration will open at 03:50 PM.)

Join Zoom Meeting:
https://sutd-edu.zoom.us/j/94607066175?pwd=a3V2aE9DeGlJSGVsK0x3Um8vVGhhQT09

Meeting ID: 946 0706 6175
Passcode: =9iCaj1G

Abstract

In this talk, we consider the problem of exact community recovery in a graph that is generated by the symmetric stochastic block model. Although the maximum likelihood estimation formulation is non-convex and has binary variables, we show that in the logarithmic sparsity regime of the problem, a properly initialized projected gradient-type method can achieve exact recovery of the communities down to the information-theoretic limit in nearly linear time. This demonstrates the potential of non-convex methods in tackling large-scale community recovery problems.

The talk covers joint works with Huikang Liu, Peng Wang, and Zirui Zhou.

The paper can be found at: https://arxiv.org/abs/2006.15843

About the Speaker

Anthony Man-Cho So is currently a Professor in the Department of Systems Engineering and Engineering Management at The Chinese University of Hong Kong (CUHK). His research focuses on optimization theory and its applications in various areas of science and engineering, including computational geometry, machine learning, signal processing, and statistics. Dr. So was appointed as an Outstanding Fellow of the Faculty of Engineering at CUHK in 2019. He has received a number of research awards, including the 2018 IEEE Signal Processing Society Best Paper Award, the 2015 IEEE Signal Processing Society Signal Processing Magazine Best Paper Award, and the 2010 INFORMS Optimization Society Optimization Prize for Young Researchers. He is currently on the editorial boards of Journal of Global Optimization, Optimization Methods and Software, SIAM Journal on Optimization.

For more information about the ESD Seminar, please email esd_invite@sutd.edu.sg

Anthony Man-Cho So (The Chinese University of Hong Kong) - Non-convex Exact Community Recovery In Stochastic Block Model