Matrix Completion with Model-free Weighting

Jiayi Wang, Raymond K. W. Wong, Xiaojun Mao, Kwun Chuen Gary Chan

Introduction

Matrix completion—the process of reconstructing a full matrix from a limited subset of its entries—is a foundational task in modern data science. It powers recommendation engines, genomic research, and sensor network analysis. However, the theoretical success of most matrix completion algorithms hinges on the assumption of uniform sampling, where every entry has an equal probability of being observed.

In practice, data is rarely missing at random. Popular items receive more ratings, and active users provide more data, creating a non-uniform structure that introduces significant bias into standard recovery algorithms. A recent study by Wang et al., "Matrix Completion with Model-free Weighting," introduces a novel framework to address this bias without requiring an explicit model of the underlying missingness mechanism.

The Challenge of Non-Uniformity

When data is missing non-uniformly, standard methods tend to over-fit the "easy-to-see" entries, leading to poor generalization across the entire matrix. Existing approaches to this problem generally fall into two categories:

  1. Robustness-based methods: These ignore the non-uniformity and rely on the algorithm's inherent stability, which often fails under extreme heterogeneity.
  2. Propensity modeling: These methods attempt to estimate the probability of each entry being observed (Inverse Probability Weighting).

The primary drawback of propensity modeling is the difficulty of accurately estimating these probabilities in high-dimensional settings. If the model for why data is missing is even slightly misspecified, the resulting matrix recovery can be highly inaccurate.

Proposed Methodology: Model-Free Balancing

The authors propose a Balancing Weight approach that bypasses the need to estimate observation probabilities ($\pi_{ij}$). Instead, they seek weights ($W$) that directly minimize a "balancing error," ensuring the weighted empirical risk closely approximates the ideal, fully-observed risk.

Spectral Norm Relaxation

Minimizing the raw balancing error is computationally prohibitive. The researchers addressed this by proving a pivotal lemma (Lemma 1), which demonstrates that the balancing error is bounded by the spectral norm of the weighted observation matrix minus a matrix of ones: $\|T \circ W - J\|$. This transformation allows the weighting problem to be reformulated as a constrained spectral norm minimization, a convex optimization problem that can be solved efficiently.

The Hybrid Estimator

Once the optimal weights are determined, the authors employ a hybrid estimator that integrates both max-norm and nuclear-norm regularization. This combination allows the model to capture the underlying low-rank structure while maintaining stability and robustness against the noise introduced by non-uniform sampling.

Theoretical Contributions

The paper provides a rigorous theoretical foundation for the proposed method, particularly in "asymptotically heterogeneous" settings where observation probabilities can vary by several orders of magnitude.

  • Optimal Error Scaling: The proposed estimator achieves an error scaling of $\pi_L^{-1/2}$ (where $\pi_L$ is the minimum observation probability). The authors prove that this is the minimax lower bound, meaning no estimator can achieve a better rate in these settings.
  • Minimax Lower Bounds: The study establishes new minimax lower bounds for heterogeneous missing structures, providing a benchmark for future research in non-uniform matrix completion.

Experimental Evaluation

The effectiveness of the BalWeights method was validated through both synthetic simulations and real-world datasets.

Simulation Results

In simulations where high-value entries were significantly less likely to be observed (the most challenging "heterogeneous" case), BalWeights demonstrated superior performance. While standard methods like SoftImpute struggled with the resulting bias, the model-free weighting approach remained robust.

Real-World Performance

The method was tested on two benchmark datasets:

  • Coat Shopping Dataset: 290 users rating 300 items.
  • Yahoo! Webscope Dataset: A large-scale dataset of 15,400 users and 1,000 songs.

On the Yahoo! Webscope dataset, BalWeights achieved the lowest Test Root Mean Squared Error (TRMSE) and Test Mean Absolute Error (TMAE) compared to five state-of-the-art competitors, confirming its utility for complex, real-world data distributions.

Conclusion

By shifting the focus from modeling observation probabilities to directly balancing the empirical risk, this research provides a powerful and computationally efficient tool for matrix completion. The "model-free" nature of the approach offers a safeguard against model misspecification, making it particularly valuable for datasets with highly varying and unknown missing patterns.

Future work may focus on closing the theoretical gap regarding the scaling of the max-norm parameter ($\beta$) and optimizing the computational efficiency of the weighting step for ultra-large-scale applications.

Summary updated

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 a 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.
BibTeX
@inproceedings{wang2021matrix,
  author = {Jiayi Wang and Raymond K. W. Wong and Xiaojun Mao and Kwun Chuen Gary Chan},
  title = {{Matrix Completion with Model-free Weighting}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=BZNWZKuC1yc},
}
Figure