Poster

Median Matrix Completion: from Embarrassment to Optimality

Weidong Liu · Xiaojun Mao · Ka Wai Wong

Virtual

Keywords: [ Recommender Systems ] [ Robust Statistics and Machine Learning ] [ Unsupervised and Semi-supervised Learning ] [ Matrix/Tensor Methods ] [ General Machine Learning Techniques ]

[ Abstract ]
[ Slides
Wed 15 Jul 5 a.m. PDT — 5:45 a.m. PDT
Wed 15 Jul 7 p.m. PDT — 7:45 p.m. PDT

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.

Chat is not available.