TY - JOUR
T1 - On the low-rank approach for semidefinite programs arising in synchronization and community detection
AU - Bandeira, Afonso S.
AU - Boumal, Nicolas
AU - Voroninski, Vladislav
N1 - Funding Information:
ASB was supported by NSF grant DMS-1317308. ASB acknowledges Wotao Yin for pointing the author to the relevant reference (Wen and Yin, 2013) which helped motivate the start of the investigation in this paper. NB, formerly hosted by the SIERRA group at Inria and ENS, was supported by the “Fonds Spéciaux de Recherche” (FSR) at UCLouvain and by the Chaire Havas “Chaire Economie et gestion des nouvelles données”, the ERC Starting Grant SIPA and a Research in Paris grant in Paris. VV acknowledges support from the Office of Naval Research.
Publisher Copyright:
© 2016 A.S. Bandeira, N. Boumal & V. Voroninski.
PY - 2016/6/6
Y1 - 2016/6/6
N2 - To address difficult optimization problems, convex relaxations based on semidefinite programming are now common place in many fields. Although solvable in polynomial time, large semidefinite programs tend to be computationally challenging. Over a decade ago, exploiting the fact that in many applications of interest the desired solutions are low rank, Burer and Monteiro proposed a heuristic to solve such semidefinite programs by restricting the search space to low-rank matrices. The accompanying theory does not explain the extent of the empirical success. We focus on Synchronization and Community Detection problems and provide theoretical guarantees shedding light on the remarkable efficiency of this heuristic.
AB - To address difficult optimization problems, convex relaxations based on semidefinite programming are now common place in many fields. Although solvable in polynomial time, large semidefinite programs tend to be computationally challenging. Over a decade ago, exploiting the fact that in many applications of interest the desired solutions are low rank, Burer and Monteiro proposed a heuristic to solve such semidefinite programs by restricting the search space to low-rank matrices. The accompanying theory does not explain the extent of the empirical success. We focus on Synchronization and Community Detection problems and provide theoretical guarantees shedding light on the remarkable efficiency of this heuristic.
KW - Burer-Monteiro heuristic
KW - Community Detection
KW - SDPLR
KW - Semidefinite Programming
KW - Synchronization
UR - http://www.scopus.com/inward/record.url?scp=85061238935&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85061238935&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:85061238935
SN - 1532-4435
VL - 49
SP - 361
EP - 382
JO - Journal of Machine Learning Research
JF - Journal of Machine Learning Research
IS - June
T2 - 29th Conference on Learning Theory, COLT 2016
Y2 - 23 June 2016 through 26 June 2016
ER -