Towards Faster Rates and Oracle Property for Low-Rank Matrix Estimation

Huan Gui, Jiawei Han, Quanquan Gu
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:2300-2309, 2016.

Abstract

We present a unified framework for low-rank matrix estimation with a nonconvex penalty. A proximal gradient homotopy algorithm is proposed to solve the proposed optimization problem. Theoretically, we first prove that the proposed estimator attains a faster statistical rate than the traditional low-rank matrix estimator with nuclear norm penalty. Moreover, we rigorously show that under a certain condition on the magnitude of the nonzero singular values, the proposed estimator enjoys oracle property (i.e., exactly recovers the true rank of the matrix), besides attaining a faster rate. Extensive numerical experiments on both synthetic and real world datasets corroborate our theoretical findings.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-gui16, title = {Towards Faster Rates and Oracle Property for Low-Rank Matrix Estimation}, author = {Gui, Huan and Han, Jiawei and Gu, Quanquan}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {2300--2309}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/gui16.pdf}, url = {https://proceedings.mlr.press/v48/gui16.html}, abstract = {We present a unified framework for low-rank matrix estimation with a nonconvex penalty. A proximal gradient homotopy algorithm is proposed to solve the proposed optimization problem. Theoretically, we first prove that the proposed estimator attains a faster statistical rate than the traditional low-rank matrix estimator with nuclear norm penalty. Moreover, we rigorously show that under a certain condition on the magnitude of the nonzero singular values, the proposed estimator enjoys oracle property (i.e., exactly recovers the true rank of the matrix), besides attaining a faster rate. Extensive numerical experiments on both synthetic and real world datasets corroborate our theoretical findings.} }
Endnote
%0 Conference Paper %T Towards Faster Rates and Oracle Property for Low-Rank Matrix Estimation %A Huan Gui %A Jiawei Han %A Quanquan Gu %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-gui16 %I PMLR %P 2300--2309 %U https://proceedings.mlr.press/v48/gui16.html %V 48 %X We present a unified framework for low-rank matrix estimation with a nonconvex penalty. A proximal gradient homotopy algorithm is proposed to solve the proposed optimization problem. Theoretically, we first prove that the proposed estimator attains a faster statistical rate than the traditional low-rank matrix estimator with nuclear norm penalty. Moreover, we rigorously show that under a certain condition on the magnitude of the nonzero singular values, the proposed estimator enjoys oracle property (i.e., exactly recovers the true rank of the matrix), besides attaining a faster rate. Extensive numerical experiments on both synthetic and real world datasets corroborate our theoretical findings.
RIS
TY - CPAPER TI - Towards Faster Rates and Oracle Property for Low-Rank Matrix Estimation AU - Huan Gui AU - Jiawei Han AU - Quanquan Gu BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-gui16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 2300 EP - 2309 L1 - http://proceedings.mlr.press/v48/gui16.pdf UR - https://proceedings.mlr.press/v48/gui16.html AB - We present a unified framework for low-rank matrix estimation with a nonconvex penalty. A proximal gradient homotopy algorithm is proposed to solve the proposed optimization problem. Theoretically, we first prove that the proposed estimator attains a faster statistical rate than the traditional low-rank matrix estimator with nuclear norm penalty. Moreover, we rigorously show that under a certain condition on the magnitude of the nonzero singular values, the proposed estimator enjoys oracle property (i.e., exactly recovers the true rank of the matrix), besides attaining a faster rate. Extensive numerical experiments on both synthetic and real world datasets corroborate our theoretical findings. ER -
APA
Gui, H., Han, J. & Gu, Q.. (2016). Towards Faster Rates and Oracle Property for Low-Rank Matrix Estimation. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:2300-2309 Available from https://proceedings.mlr.press/v48/gui16.html.

Related Material