Matrix Completion with Model-free Weighting

Jiayi Wang, Raymond K. W. Wong, Xiaojun Mao, Kwun Chuen Gary Chan
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:10927-10936, 2021.

Abstract

In this paper, we propose a novel method for matrix completion under general non-uniform missing structures. By controlling an upper bound of a novel balancing error, we construct weights that can actively adjust for the non-uniformity in the empirical risk without explicitly modeling the observation probabilities, and can be computed efficiently via convex optimization. The recovered matrix based on the proposed weighted empirical risk enjoys appealing theoretical guarantees. In particular, the proposed method achieves stronger guarantee than existing work in terms of the scaling with respect to the observation probabilities, under asymptotically heterogeneous missing settings (where entry-wise observation probabilities can be of different orders). These settings can be regarded as a better theoretical model of missing patterns with highly varying probabilities. We also provide a new minimax lower bound under a class of heterogeneous settings. Numerical experiments are also provided to demonstrate the effectiveness of the proposed method.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-wang21x, title = {Matrix Completion with Model-free Weighting}, author = {Wang, Jiayi and Wong, Raymond K. W. and Mao, Xiaojun and Chan, Kwun Chuen Gary}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {10927--10936}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/wang21x/wang21x.pdf}, url = {https://proceedings.mlr.press/v139/wang21x.html}, abstract = {In this paper, we propose a novel method for matrix completion under general non-uniform missing structures. By controlling an upper bound of a novel balancing error, we construct weights that can actively adjust for the non-uniformity in the empirical risk without explicitly modeling the observation probabilities, and can be computed efficiently via convex optimization. The recovered matrix based on the proposed weighted empirical risk enjoys appealing theoretical guarantees. In particular, the proposed method achieves stronger guarantee than existing work in terms of the scaling with respect to the observation probabilities, under asymptotically heterogeneous missing settings (where entry-wise observation probabilities can be of different orders). These settings can be regarded as a better theoretical model of missing patterns with highly varying probabilities. We also provide a new minimax lower bound under a class of heterogeneous settings. Numerical experiments are also provided to demonstrate the effectiveness of the proposed method.} }
Endnote
%0 Conference Paper %T Matrix Completion with Model-free Weighting %A Jiayi Wang %A Raymond K. W. Wong %A Xiaojun Mao %A Kwun Chuen Gary Chan %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-wang21x %I PMLR %P 10927--10936 %U https://proceedings.mlr.press/v139/wang21x.html %V 139 %X In this paper, we propose a novel method for matrix completion under general non-uniform missing structures. By controlling an upper bound of a novel balancing error, we construct weights that can actively adjust for the non-uniformity in the empirical risk without explicitly modeling the observation probabilities, and can be computed efficiently via convex optimization. The recovered matrix based on the proposed weighted empirical risk enjoys appealing theoretical guarantees. In particular, the proposed method achieves stronger guarantee than existing work in terms of the scaling with respect to the observation probabilities, under asymptotically heterogeneous missing settings (where entry-wise observation probabilities can be of different orders). These settings can be regarded as a better theoretical model of missing patterns with highly varying probabilities. We also provide a new minimax lower bound under a class of heterogeneous settings. Numerical experiments are also provided to demonstrate the effectiveness of the proposed method.
APA
Wang, J., Wong, R.K.W., Mao, X. & Chan, K.C.G.. (2021). Matrix Completion with Model-free Weighting. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:10927-10936 Available from https://proceedings.mlr.press/v139/wang21x.html.

Related Material