A Primal-Dual Analysis of Global Optimality in Nonconvex Low-Rank Matrix Recovery

Xiao Zhang, Lingxiao Wang, Yaodong Yu, Quanquan Gu
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:5862-5871, 2018.

Abstract

We propose a primal-dual based framework for analyzing the global optimality of nonconvex low-rank matrix recovery. Our analysis are based on the restricted strongly convex and smooth conditions, which can be verified for a broad family of loss functions. In addition, our analytic framework can directly handle the widely-used incoherence constraints through the lens of duality. We illustrate the applicability of the proposed framework to matrix completion and one-bit matrix completion, and prove that all these problems have no spurious local minima. Our results not only improve the sample complexity required for characterizing the global optimality of matrix completion, but also resolve an open problem in Ge et al. (2017) regarding one-bit matrix completion. Numerical experiments show that primal-dual based algorithm can successfully recover the global optimum for various low-rank problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-zhang18m, title = {A Primal-Dual Analysis of Global Optimality in Nonconvex Low-Rank Matrix Recovery}, author = {Zhang, Xiao and Wang, Lingxiao and Yu, Yaodong and Gu, Quanquan}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {5862--5871}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/zhang18m/zhang18m.pdf}, url = {https://proceedings.mlr.press/v80/zhang18m.html}, abstract = {We propose a primal-dual based framework for analyzing the global optimality of nonconvex low-rank matrix recovery. Our analysis are based on the restricted strongly convex and smooth conditions, which can be verified for a broad family of loss functions. In addition, our analytic framework can directly handle the widely-used incoherence constraints through the lens of duality. We illustrate the applicability of the proposed framework to matrix completion and one-bit matrix completion, and prove that all these problems have no spurious local minima. Our results not only improve the sample complexity required for characterizing the global optimality of matrix completion, but also resolve an open problem in Ge et al. (2017) regarding one-bit matrix completion. Numerical experiments show that primal-dual based algorithm can successfully recover the global optimum for various low-rank problems.} }
Endnote
%0 Conference Paper %T A Primal-Dual Analysis of Global Optimality in Nonconvex Low-Rank Matrix Recovery %A Xiao Zhang %A Lingxiao Wang %A Yaodong Yu %A Quanquan Gu %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-zhang18m %I PMLR %P 5862--5871 %U https://proceedings.mlr.press/v80/zhang18m.html %V 80 %X We propose a primal-dual based framework for analyzing the global optimality of nonconvex low-rank matrix recovery. Our analysis are based on the restricted strongly convex and smooth conditions, which can be verified for a broad family of loss functions. In addition, our analytic framework can directly handle the widely-used incoherence constraints through the lens of duality. We illustrate the applicability of the proposed framework to matrix completion and one-bit matrix completion, and prove that all these problems have no spurious local minima. Our results not only improve the sample complexity required for characterizing the global optimality of matrix completion, but also resolve an open problem in Ge et al. (2017) regarding one-bit matrix completion. Numerical experiments show that primal-dual based algorithm can successfully recover the global optimum for various low-rank problems.
APA
Zhang, X., Wang, L., Yu, Y. & Gu, Q.. (2018). A Primal-Dual Analysis of Global Optimality in Nonconvex Low-Rank Matrix Recovery. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:5862-5871 Available from https://proceedings.mlr.press/v80/zhang18m.html.

Related Material