Séminaire Jeunes chercheurs (Faniriana Rakoto Endor, jeudi 30 janvier 2025)

La prochaine séance du séminaire Jeunes chercheurs du CEREMADE aura lieu le jeudi 30 janvier 2025 à 17h en salle A707. Nous aurons le plaisir d'écouter Faniriana RAKOTO ENDOR (CEREMADE), qui nous parlera de

Benign landscape for Burer-Monteiro factorizations of MaxCut-type semidefinite programs

Abstract
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 prob- lem is a global minimizer. By applying our theorem, we improve on recent results about the correctness of the Burer-Monteiro approach on Z2 synchronization problems.