Optimization for Machine Learning / Optimisation pour l’apprentissage automatique

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

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

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

linked URL https://conferences.cirm-math.fr/2133.html

00:00:00 / 00:00:00

2 4

Rank optimality for the Burer-Monteiro factorization

By 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.

Information about the video

Date of recording 10/03/2020
Date of publication 06/04/2020
Institution CIRM
Licence CC BY NC ND
Language English
Audience Researchers
Director(s) Guillaume Hennenfent
Format MP4

Citation data

DOI 10.24350/CIRM.V.19623503
Cite this video 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

Domain(s)

Optimization and Control

Bibliography

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

MSC codes

Document(s)

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

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow

All the collection videos

37:49

published on April 6, 2020

What does back propagation compute?

By Edouard Pauwels

40:11

published on April 6, 2020

Rank optimality for the Burer-Monteiro factorization

By Irène Waldspurger

50:11

published on April 6, 2020

Learning with differentiable perturbed optimizers

By Quentin Berthet

47:31

published on April 6, 2020

Gradient descent for wide two-layer neural networks

By Francis Bach

Copyright Carmin.tv 2024

Give feedback