F Nous contacter

Multi angle

H 1 Rank optimality for the Burer-Monteiro factorization

Auteurs : Waldspurger, Irène (Auteur de la Conférence)
CIRM (Editeur )

    Loading the player...

    Résumé : The Burer-Monteiro factorization is a classical heuristic used to speed up the solving of large scale semidefinite programs when the solution is expected to be low rank: One writes the solution as the product of thinner matrices, and optimizes over the (low-dimensional) factors instead of over the full matrix. Even though the factorized problem is non-convex, one observes that standard first-order algorithms can often solve it to global optimality. This has been rigorously proved by Boumal, Voroninski and Bandeira, but only under the assumption that the factorization rank is large enough, larger than what numerical experiments suggest. We will describe this result, and investigate its optimality. More specifically, we will show that, up to a minor improvement, it is optimal: without additional hypotheses on the semidefinite problem at hand, first-order algorithms can fail if the factorization rank is smaller than predicted by current theory.

    Keywords : nonconvex optimization; phase retrieval; low-rank matrix recovery

    Codes MSC :
    42C40 - Wavelets and other special systems
    90C22 - Semidefinite programming
    90C26 - Nonconvex programming, quasiconvex programming

    Ressources complémentaires :

      Informations sur la Vidéo

      Réalisateur : Hennenfent, Guillaume
      Langue : Anglais
      Date de publication : 06/04/2020
      Date de captation : 10/03/2020
      Collection : Research talks ; Control Theory and Optimization
      Format : MP4
      Durée : 00:40:11
      Domaine : Control Theory & Optimization
      Audience : Chercheurs ; Doctorants , Post - Doctorants
      Download : https://videos.cirm-math.fr/2020-03-10_Waldspurger.mp4

    Informations sur la rencontre

    Nom de la rencontre : Optimization for Machine Learning / Optimisation pour l’apprentissage automatique
    Organisateurs de la rencontre : Boyer, Claire ; d'Aspremont, Alexandre ; Gramfort, Alexandre ; Salmon, Joseph ; Villar, Soledad
    Dates : 09/03/2020 - 13/03/2020
    Année de la rencontre : 2020
    URL Congrès : https://conferences.cirm-math.fr/2133.html

    Citation Data

    DOI : 10.24350/CIRM.V.19623503
    Cite this video as: Waldspurger, Irène (2020). Rank optimality for the Burer-Monteiro factorization. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19623503
    URI : http://dx.doi.org/10.24350/CIRM.V.19623503

    Voir aussi


    1. WALDSPURGER, Irène et WATERS, Alden. Rank optimality for the Burer-Monteiro factorization. arXiv preprint arXiv:1812.03046, 2018. - https://arxiv.org/abs/1812.03046

Imagette Video