Median Matrix Completion: from Embarrassment to Optimality

Weidong Liu, Xiaojun Mao, Raymond K. W. Wong
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:6294-6304, 2020.

Abstract

In this paper, we consider matrix completion with absolute deviation loss and obtain an estimator of the median matrix. Despite several appealing properties of median, the non-smooth absolute deviation loss leads to computational challenge for large-scale data sets which are increasingly common among matrix completion problems. A simple solution to large-scale problems is parallel computing. However, embarrassingly parallel fashion often leads to inefficient estimators. Based on the idea of pseudo data, we propose a novel refinement step, which turns such inefficient estimators into a rate (near-)optimal matrix completion procedure. The refined estimator is an approximation of a regularized least median estimator, and therefore not an ordinary regularized empirical risk estimator. This leads to a non-standard analysis of asymptotic behaviors. Empirical results are also provided to confirm the effectiveness of the proposed method.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-liu20k, title = {Median Matrix Completion: from Embarrassment to Optimality}, author = {Liu, Weidong and Mao, Xiaojun and Wong, Raymond K. W.}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {6294--6304}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/liu20k/liu20k.pdf}, url = {https://proceedings.mlr.press/v119/liu20k.html}, abstract = {In this paper, we consider matrix completion with absolute deviation loss and obtain an estimator of the median matrix. Despite several appealing properties of median, the non-smooth absolute deviation loss leads to computational challenge for large-scale data sets which are increasingly common among matrix completion problems. A simple solution to large-scale problems is parallel computing. However, embarrassingly parallel fashion often leads to inefficient estimators. Based on the idea of pseudo data, we propose a novel refinement step, which turns such inefficient estimators into a rate (near-)optimal matrix completion procedure. The refined estimator is an approximation of a regularized least median estimator, and therefore not an ordinary regularized empirical risk estimator. This leads to a non-standard analysis of asymptotic behaviors. Empirical results are also provided to confirm the effectiveness of the proposed method.} }
Endnote
%0 Conference Paper %T Median Matrix Completion: from Embarrassment to Optimality %A Weidong Liu %A Xiaojun Mao %A Raymond K. W. Wong %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-liu20k %I PMLR %P 6294--6304 %U https://proceedings.mlr.press/v119/liu20k.html %V 119 %X In this paper, we consider matrix completion with absolute deviation loss and obtain an estimator of the median matrix. Despite several appealing properties of median, the non-smooth absolute deviation loss leads to computational challenge for large-scale data sets which are increasingly common among matrix completion problems. A simple solution to large-scale problems is parallel computing. However, embarrassingly parallel fashion often leads to inefficient estimators. Based on the idea of pseudo data, we propose a novel refinement step, which turns such inefficient estimators into a rate (near-)optimal matrix completion procedure. The refined estimator is an approximation of a regularized least median estimator, and therefore not an ordinary regularized empirical risk estimator. This leads to a non-standard analysis of asymptotic behaviors. Empirical results are also provided to confirm the effectiveness of the proposed method.
APA
Liu, W., Mao, X. & Wong, R.K.W.. (2020). Median Matrix Completion: from Embarrassment to Optimality. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:6294-6304 Available from https://proceedings.mlr.press/v119/liu20k.html.

Related Material