On the low-rank approach for semidefinite programs arising in synchronization and community detection

Afonso S. Bandeira, Nicolas Boumal, Vladislav Voroninski
29th Annual Conference on Learning Theory, PMLR 49:361-382, 2016.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v49-bandeira16, title = {On the low-rank approach for semidefinite programs arising in synchronization and community detection}, author = {Bandeira, Afonso S. and Boumal, Nicolas and Voroninski, Vladislav}, booktitle = {29th Annual Conference on Learning Theory}, pages = {361--382}, year = {2016}, editor = {Feldman, Vitaly and Rakhlin, Alexander and Shamir, Ohad}, volume = {49}, series = {Proceedings of Machine Learning Research}, address = {Columbia University, New York, New York, USA}, month = {23--26 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v49/bandeira16.pdf}, url = {https://proceedings.mlr.press/v49/bandeira16.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T On the low-rank approach for semidefinite programs arising in synchronization and community detection %A Afonso S. Bandeira %A Nicolas Boumal %A Vladislav Voroninski %B 29th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2016 %E Vitaly Feldman %E Alexander Rakhlin %E Ohad Shamir %F pmlr-v49-bandeira16 %I PMLR %P 361--382 %U https://proceedings.mlr.press/v49/bandeira16.html %V 49 %X 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.
RIS
TY - CPAPER TI - On the low-rank approach for semidefinite programs arising in synchronization and community detection AU - Afonso S. Bandeira AU - Nicolas Boumal AU - Vladislav Voroninski BT - 29th Annual Conference on Learning Theory DA - 2016/06/06 ED - Vitaly Feldman ED - Alexander Rakhlin ED - Ohad Shamir ID - pmlr-v49-bandeira16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 49 SP - 361 EP - 382 L1 - http://proceedings.mlr.press/v49/bandeira16.pdf UR - https://proceedings.mlr.press/v49/bandeira16.html 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. ER -
APA
Bandeira, A.S., Boumal, N. & Voroninski, V.. (2016). On the low-rank approach for semidefinite programs arising in synchronization and community detection. 29th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 49:361-382 Available from https://proceedings.mlr.press/v49/bandeira16.html.

Related Material