Optimal Statistical and Computational Rates for One Bit Matrix Completion

Renkun Ni, Quanquan Gu
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51:426-434, 2016.

Abstract

We consider one bit matrix completion under rank constraint. We present an estimator based on rank constrained maximum likelihood estimation, and an efficient greedy algorithm to solve it approximately based on an extension of conditional gradient descent. The output of the proposed algorithm converges at a linear rate to the underlying true low-rank matrix up to the optimal statistical estimation error rate, i.e., O(\sqrtrn\log(n)/|Ω|), where n is the dimension of the underlying matrix and |Ω| is the number of observed entries. Our work establishes the first computationally efficient approach with provable guarantee for optimal estimation in one bit matrix completion. Our theory is supported by thorough numerical results.

Cite this Paper

BibTeX
@InProceedings{pmlr-v51-ni16, title = {Optimal Statistical and Computational Rates for One Bit Matrix Completion}, author = {Ni, Renkun and Gu, Quanquan}, booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics}, pages = {426--434}, year = {2016}, editor = {Gretton, Arthur and Robert, Christian C.}, volume = {51}, series = {Proceedings of Machine Learning Research}, address = {Cadiz, Spain}, month = {09--11 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v51/ni16.pdf}, url = {https://proceedings.mlr.press/v51/ni16.html}, abstract = {We consider one bit matrix completion under rank constraint. We present an estimator based on rank constrained maximum likelihood estimation, and an efficient greedy algorithm to solve it approximately based on an extension of conditional gradient descent. The output of the proposed algorithm converges at a linear rate to the underlying true low-rank matrix up to the optimal statistical estimation error rate, i.e., O(\sqrtrn\log(n)/|Ω|), where n is the dimension of the underlying matrix and |Ω| is the number of observed entries. Our work establishes the first computationally efficient approach with provable guarantee for optimal estimation in one bit matrix completion. Our theory is supported by thorough numerical results.} }
Endnote
%0 Conference Paper %T Optimal Statistical and Computational Rates for One Bit Matrix Completion %A Renkun Ni %A Quanquan Gu %B Proceedings of the 19th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2016 %E Arthur Gretton %E Christian C. Robert %F pmlr-v51-ni16 %I PMLR %P 426--434 %U https://proceedings.mlr.press/v51/ni16.html %V 51 %X We consider one bit matrix completion under rank constraint. We present an estimator based on rank constrained maximum likelihood estimation, and an efficient greedy algorithm to solve it approximately based on an extension of conditional gradient descent. The output of the proposed algorithm converges at a linear rate to the underlying true low-rank matrix up to the optimal statistical estimation error rate, i.e., O(\sqrtrn\log(n)/|Ω|), where n is the dimension of the underlying matrix and |Ω| is the number of observed entries. Our work establishes the first computationally efficient approach with provable guarantee for optimal estimation in one bit matrix completion. Our theory is supported by thorough numerical results.
RIS
TY - CPAPER TI - Optimal Statistical and Computational Rates for One Bit Matrix Completion AU - Renkun Ni AU - Quanquan Gu BT - Proceedings of the 19th International Conference on Artificial Intelligence and Statistics DA - 2016/05/02 ED - Arthur Gretton ED - Christian C. Robert ID - pmlr-v51-ni16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 51 SP - 426 EP - 434 L1 - http://proceedings.mlr.press/v51/ni16.pdf UR - https://proceedings.mlr.press/v51/ni16.html AB - We consider one bit matrix completion under rank constraint. We present an estimator based on rank constrained maximum likelihood estimation, and an efficient greedy algorithm to solve it approximately based on an extension of conditional gradient descent. The output of the proposed algorithm converges at a linear rate to the underlying true low-rank matrix up to the optimal statistical estimation error rate, i.e., O(\sqrtrn\log(n)/|Ω|), where n is the dimension of the underlying matrix and |Ω| is the number of observed entries. Our work establishes the first computationally efficient approach with provable guarantee for optimal estimation in one bit matrix completion. Our theory is supported by thorough numerical results. ER -
APA
Ni, R. & Gu, Q.. (2016). Optimal Statistical and Computational Rates for One Bit Matrix Completion. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 51:426-434 Available from https://proceedings.mlr.press/v51/ni16.html.

Related Material