Median Matrix Completion: from Embarrassment to Optimality

Weidong Liu, Xiaojun Mao, Raymond K. W. Wong

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.

Introduction

Matrix Completion (MC) is a fundamental problem in machine learning, underpinning recommendation systems like Netflix or Amazon. The goal is to predict missing entries in a large matrix based on a small subset of observed values. While standard approaches typically employ quadratic loss (least squares), these methods are sensitive to outliers and heavy-tailed noise distributions often found in real-world datasets.

Median Matrix Completion, which uses absolute deviation ($L_1$) loss, offers a robust alternative. However, it introduces two significant challenges:

  1. Computational Complexity: The non-smooth nature of $L_1$ loss makes optimization slow for large-scale matrices.
  2. The Scalability Paradox: Distributed or "embarrassingly parallel" computing—splitting the matrix into blocks—often results in sub-optimal global estimators because low-rankness is a global property that local solvers cannot fully capture.

To address these issues, researchers have developed Distributed Least Absolute Deviation Matrix Completion (DLADMC), a two-stage algorithm that achieves near-optimal accuracy while maintaining high scalability.

Methods

The DLADMC algorithm consists of two primary stages: distributed initial estimation and iterative refinement via pseudo data.

Distributed Initial Estimation

The target matrix is first partitioned into sub-matrices. Each sub-matrix is completed independently and in parallel using a standard (though computationally intensive) Alternating Direction Method of Multipliers (ADMM) algorithm. This provides a fast but "rough" global starting point.

Illustration of a partitioned matrix for distributed completion.

Refinement via Pseudo Data

The core innovation of this work is the refinement step. Inspired by the Newton-Raphson iteration, the authors transform the non-smooth $L_1$ objective into a sequence of smooth regularized quadratic problems. By constructing "pseudo data" using a kernel density estimator to approximate the noise distribution at zero, the algorithm can refine the initial parallel estimates. This process effectively turns a robust estimation problem into a series of standard matrix completion problems that can be solved efficiently using optimized quadratic solvers.

Key Insights and Theoretical Contributions

The refinement step is not merely a heuristic; it is a "Newton-Raphson in Expectation." This allows the bypass of non-smoothness in the median objective function. Theoretically, the paper provides a rigorous proof showing that while the initial parallel step is sub-optimal, the refinement step mathematically "upgrades" the estimator to near-oracle convergence rates. This bridges the gap between the efficiency of distributed computing and the statistical optimality of global solvers.

Empirical Evaluation

The authors evaluated DLADMC against synthetic datasets and the MovieLens benchmarks.

  • Robustness: In simulations with Cauchy noise (where the mean is undefined), standard squared-loss methods like MHT failed completely. DLADMC maintained high accuracy, significantly outperforming non-robust alternatives.
  • Scalability: On the MovieLens-1M dataset, traditional robust algorithms like ACL were too slow to finish. DLADMC successfully completed the matrix, providing superior RMSE and MAE compared to standard methods in the presence of outliers.
  • Efficiency: The refinement process converges quickly; the authors found that only 4–5 iterations are typically needed to reach near-optimal performance.

Conclusion

DLADMC offers a powerful framework for large-scale robust matrix completion. By combining distributed computing with a novel pseudo-data refinement step, it overcomes the computational hurdles of $L_1$ loss. While the method requires a reasonably good initial estimate and careful bandwidth selection for the kernel density estimator, it paves the way for applying robust non-smooth loss functions to massive datasets. Future work may extend this "pseudo data" approach to other areas, such as quantile regression for matrix completion.

Summary updated

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.
BibTeX
@inproceedings{liu2020median,
  author = {Weidong Liu and Xiaojun Mao and Raymond K. W. Wong},
  title = {{Median Matrix Completion: from Embarrassment to Optimality}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=jS25GaqiZW},
}
Figure