Optimization for Machine Learning / Optimisation pour l’apprentissage automatique

Collection Optimization for Machine Learning / Optimisation pour l’apprentissage automatique

Organisateur(s) Boyer, Claire ; d'Aspremont, Alexandre ; Gramfort, Alexandre ; Salmon, Joseph ; Villar, Soledad

Date(s) 09/03/2020 - 13/03/2020

URL associée https://conferences.cirm-math.fr/2133.html

00:00:00 / 00:00:00

2 4

Rank optimality for the Burer-Monteiro factorization

De Irène Waldspurger

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.

Informations sur la vidéo

Date de captation 10/03/2020
Date de publication 06/04/2020
Institut CIRM
Licence CC BY NC ND
Langue Anglais
Audience Chercheurs
Réalisateur(s) Guillaume Hennenfent
Format MP4

Données de citation

DOI 10.24350/CIRM.V.19623503
Citer cette vidéo Waldspurger, Irène (10/03/2020). Rank optimality for the Burer-Monteiro factorization. CIRM. Audiovisual resource. DOI: 10.24350/CIRM.V.19623503
URL https://dx.doi.org/10.24350/CIRM.V.19623503

Domaine(s)

Optimisation et contrôle

Bibliographie

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

Codes MSC

Document(s)

https://www.cirm-math.fr/RepOrga/2133/Slides/10_03_waldspurger.pdf

Dernières questions liées sur MathOverflow

Pour poser une question, votre compte Carmin.tv doit être connecté à mathoverflow

Poser une question sur MathOverflow

Toutes les vidéos de la collection

37:49

publiée le 6 avril 2020

What does back propagation compute?

De Edouard Pauwels

40:11

publiée le 6 avril 2020

Rank optimality for the Burer-Monteiro factorization

De Irène Waldspurger

50:11

publiée le 6 avril 2020

Learning with differentiable perturbed optimizers

De Quentin Berthet

47:31

publiée le 6 avril 2020

Gradient descent for wide two-layer neural networks

De Francis Bach

Copyright Carmin.tv 2024

Donner son avis