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 = {Huan Gui and Jiawei Han and Quanquan Gu}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {2300--2309}, year = {2016}, editor = {Maria Florina Balcan and Kilian Q. Weinberger}, 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 = {http://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 %J Proceedings of Machine Learning Research %P 2300--2309 %U http://proceedings.mlr.press %V 48 %W PMLR %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 PY - 2016/06/11 DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-gui16 PB - PMLR SP - 2300 DP - PMLR EP - 2309 L1 - http://proceedings.mlr.press/v48/gui16.pdf UR - http://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 PMLR 48:2300-2309

Related Material