Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methods
Baturalp Yalçın, Haixiang Zhang, Javad Lavaei, Somayeh Sojoudi
Abstract
Burer-Monteiro (B-M) factorization approach can efficiently solve low-rank matrix optimization problems under the Restricted Isometry Property (RIP) condition. It is natural to ask whether B-M factorization-based methods can succeed on any low-rank matrix optimization problems with low information-theoretic complexity, i.e., polynomial-time solvable problems that have a unique solution. We provide negative answer to this question. We investigate the landscape of B-M factorized polynomial-time solvable matrix completion (MC) problems, which are the most popular subclass of low-rank matrix optimization problems without the RIP condition. We construct an instance of polynomial-time solvable MC problems with exponentially many spurious local minima, which leads to the failure of most gradient-based methods. We define a new complexity metric that measures the solvability of low-rank matrix optimization problems based on B-M factorization approach. In addition, we show that more measurements can deteriorate the landscape, which further reveals the unfavorable behavior of B-M factorization.
BibTeX
@InProceedings{pmlr-v151-yalcin22a,
title = { Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methods },
author = {Yal\c{c}{\i}n, Baturalp and Zhang, Haixiang and Lavaei, Javad and Sojoudi, Somayeh},
booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics},
pages = {319--341},
year = {2022},
editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel},
volume = {151},
series = {Proceedings of Machine Learning Research},
month = {28--30 Mar},
publisher = {PMLR},
pdf = {https://proceedings.mlr.press/v151/yalcin22a/yalcin22a.pdf},
url = {https://proceedings.mlr.press/v151/yalcin22a.html},
abstract = { Burer-Monteiro (B-M) factorization approach can efficiently solve low-rank matrix optimization problems under the Restricted Isometry Property (RIP) condition. It is natural to ask whether B-M factorization-based methods can succeed on any low-rank matrix optimization problems with low information-theoretic complexity, i.e., polynomial-time solvable problems that have a unique solution. We provide negative answer to this question. We investigate the landscape of B-M factorized polynomial-time solvable matrix completion (MC) problems, which are the most popular subclass of low-rank matrix optimization problems without the RIP condition. We construct an instance of polynomial-time solvable MC problems with exponentially many spurious local minima, which leads to the failure of most gradient-based methods. We define a new complexity metric that measures the solvability of low-rank matrix optimization problems based on B-M factorization approach. In addition, we show that more measurements can deteriorate the landscape, which further reveals the unfavorable behavior of B-M factorization. }
}