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
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:319-341, 2022.

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.

Cite this Paper

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. } }
Endnote
%0 Conference Paper %T Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methods %A Baturalp Yalçın %A Haixiang Zhang %A Javad Lavaei %A Somayeh Sojoudi %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-yalcin22a %I PMLR %P 319--341 %U https://proceedings.mlr.press/v151/yalcin22a.html %V 151 %X 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.
APA
Yalçın, B., Zhang, H., Lavaei, J. & Sojoudi, S.. (2022). Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methods . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:319-341 Available from https://proceedings.mlr.press/v151/yalcin22a.html.

Related Material