Revisiting the Landscape of Matrix Factorization

Hossein Valavi, Sulin Liu, Peter Ramadge
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:1629-1638, 2020.

Abstract

Prior work has shown that low-rank matrix factorization has infinitely many critical points, each of which is either a global minimum or a (strict) saddle point. We revisit this problem and provide simple, intuitive proofs of a set of extended results for low-rank and general-rank problems. We couple our investigation with a known invariant manifold M0 of gradient flow. This restriction admits a uniform negative upper bound on the least eigenvalue of the Hessian map at all strict saddles in M0. The bound depends on the size of the nonzero singular values and the separation between distinct singular values of the matrix to be factorized.

Cite this Paper

BibTeX
@InProceedings{pmlr-v108-valavi20a, title = {Revisiting the Landscape of Matrix Factorization}, author = {Valavi, Hossein and Liu, Sulin and Ramadge, Peter}, booktitle = {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics}, pages = {1629--1638}, year = {2020}, editor = {Chiappa, Silvia and Calandra, Roberto}, volume = {108}, series = {Proceedings of Machine Learning Research}, month = {26--28 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v108/valavi20a/valavi20a.pdf}, url = {https://proceedings.mlr.press/v108/valavi20a.html}, abstract = {Prior work has shown that low-rank matrix factorization has infinitely many critical points, each of which is either a global minimum or a (strict) saddle point. We revisit this problem and provide simple, intuitive proofs of a set of extended results for low-rank and general-rank problems. We couple our investigation with a known invariant manifold M0 of gradient flow. This restriction admits a uniform negative upper bound on the least eigenvalue of the Hessian map at all strict saddles in M0. The bound depends on the size of the nonzero singular values and the separation between distinct singular values of the matrix to be factorized.} }
Endnote
%0 Conference Paper %T Revisiting the Landscape of Matrix Factorization %A Hossein Valavi %A Sulin Liu %A Peter Ramadge %B Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2020 %E Silvia Chiappa %E Roberto Calandra %F pmlr-v108-valavi20a %I PMLR %P 1629--1638 %U https://proceedings.mlr.press/v108/valavi20a.html %V 108 %X Prior work has shown that low-rank matrix factorization has infinitely many critical points, each of which is either a global minimum or a (strict) saddle point. We revisit this problem and provide simple, intuitive proofs of a set of extended results for low-rank and general-rank problems. We couple our investigation with a known invariant manifold M0 of gradient flow. This restriction admits a uniform negative upper bound on the least eigenvalue of the Hessian map at all strict saddles in M0. The bound depends on the size of the nonzero singular values and the separation between distinct singular values of the matrix to be factorized.
APA
Valavi, H., Liu, S. & Ramadge, P.. (2020). Revisiting the Landscape of Matrix Factorization. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:1629-1638 Available from https://proceedings.mlr.press/v108/valavi20a.html.

Related Material