Benign landscape for Burer-Monteiro factorizations of MaxCut-type semidefinite programs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917968147906560 |
|---|---|
| author | Endor, Faniriana Rakoto Waldspurger, Irène |
| author_facet | Endor, Faniriana Rakoto Waldspurger, Irène |
| contents | We consider MaxCut-type semidefinite programs (SDP) which admit a low rank solution. To numerically leverage the low rank hypothesis, a standard algorithmic approach is the Burer-Monteiro factorization, which allows to significantly reduce the dimensionality of the problem at the cost of its convexity. We give a sharp condition on the conditioning of the Laplacian matrix associated with the SDP under which any second-order critical point of the non-convex problem is a global minimizer. By applying our theorem, we improve on recent results about the correctness of the Burer-Monteiro approach on $\mathbb{Z}_2$-synchronization problems and the Kuramoto model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_03103 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Benign landscape for Burer-Monteiro factorizations of MaxCut-type semidefinite programs Endor, Faniriana Rakoto Waldspurger, Irène Optimization and Control Computational Complexity Machine Learning We consider MaxCut-type semidefinite programs (SDP) which admit a low rank solution. To numerically leverage the low rank hypothesis, a standard algorithmic approach is the Burer-Monteiro factorization, which allows to significantly reduce the dimensionality of the problem at the cost of its convexity. We give a sharp condition on the conditioning of the Laplacian matrix associated with the SDP under which any second-order critical point of the non-convex problem is a global minimizer. By applying our theorem, we improve on recent results about the correctness of the Burer-Monteiro approach on $\mathbb{Z}_2$-synchronization problems and the Kuramoto model. |
| title | Benign landscape for Burer-Monteiro factorizations of MaxCut-type semidefinite programs |
| topic | Optimization and Control Computational Complexity Machine Learning |
| url | https://arxiv.org/abs/2411.03103 |