
Rank optimality for the Burer-Monteiro factorization
Waldspurger, Irène; Waters, Alden (2020), Rank optimality for the Burer-Monteiro factorization, SIAM Journal on Optimization, 30, 3, p. 2577-2602. 10.1137/19M1255318
View/ Open
Type
Article accepté pour publication ou publiéDate
2020Journal name
SIAM Journal on OptimizationVolume
30Number
3Publisher
SIAM - Society for Industrial and Applied Mathematics
Pages
2577-2602
Publication identifier
Metadata
Show full item recordAuthor(s)
Waldspurger, IrèneCEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Waters, Alden
Bernoulli Institute for Mathematics and Computer Science and Artificial Intelligence
Abstract (EN)
When solving large-scale semidefinite programs that admit a low-rank solution, an efficient heuristic is the Burer--Monteiro factorization: instead of optimizing over the full matrix, one optimizes over its low-rank factors. This reduces the number of variables to optimize but destroys the convexity of the problem, thus possibly introducing spurious second-order critical points. The article [N. Boumal, V. Voroninski, and A. S. Bandeira, Deterministic Guarantees for Burer-Monteiro Factorizations of Smooth Semidefinite Programs, https://arxiv.org/abs/1804.02008, 2018] shows that when the size of the factors is of the order of the square root of the number of linear constraints, this does not happen: for almost any cost matrix, second-order critical points are global solutions. In this article, we show that this result is essentially tight: for smaller values of the size, second-order critical points are not generically optimal, even when the global solution is rank 1.Subjects / Keywords
semidefinite programming; Burer-Monteiro factorizationRelated items
Showing items related by title and author.
-
Waldspurger, Irène (2021) Document de travail / Working paper
-
Mallat, Stéphane; Waldspurger, Irène (2015) Article accepté pour publication ou publié
-
Waldspurger, Irène (2017) Article accepté pour publication ou publié
-
Pluchinotta, Irene; Pagano, Alessandro; Giordano, Raffaele; Tsoukiàs, Alexis (2018) Article accepté pour publication ou publié
-
Pluchinotta, Irene (2015-03) Thèse