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.


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.

Related Material