# Matrix Completion with Model-free Weighting

arXiv: https://arxiv.org/abs/2106.05850 · HTML: https://mlsanity.com/paper/2106.05850/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 57 references that are in the map.
- First posted on arXiv 9 Jun 2021.

## Builds on (most cited first, 16 of 16)

- [Recommendations as Treatments: Debiasing Learning and Evaluation](https://mlsanity.com/paper/1602.05352/) (2016)
- [Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares](https://mlsanity.com/paper/1410.2596/) (2014)
- [Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization](https://mlsanity.com/paper/1902.07698/) (2019)
- [Causal Inference with Noisy and Missing Covariates via Matrix Factorization](https://mlsanity.com/paper/1806.00811/) (2018)
- [A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion](https://mlsanity.com/paper/1309.6013/) (2013)
- [Concentration in unbounded metric spaces and algorithmic stability](https://mlsanity.com/paper/1309.1007/) (2013)
- [Matrix Completion via Max-Norm Constrained Optimization](https://mlsanity.com/paper/1303.0341/) (2013)
- [Adaptive Multinomial Matrix Completion](https://mlsanity.com/paper/1408.6218/) (2014)
- [Top-N Recommender System via Matrix Completion](https://mlsanity.com/paper/1601.04800/) (2016)
- [Estimation with Norm Regularization](https://mlsanity.com/paper/1505.02294/) (2015)
- [Probabilistic low-rank matrix completion on finite alphabets](https://mlsanity.com/paper/1412.2632/) (2014)
- [Max-Norm Optimization for Robust Matrix Recovery](https://mlsanity.com/paper/1609.07664/) (2016)
- [Main effects and interactions in mixed and incomplete data frames](https://mlsanity.com/paper/1806.09734/) (2018)
- [Matrix Completion under Low-Rank Missing Mechanism](https://mlsanity.com/paper/1812.07813/) (2018)
- [Active Matrix Factorization for Surveys](https://mlsanity.com/paper/1902.07634/) (2019)
- [Simple Surveys: Response Retrieval Inspired by Recommendation Systems](https://mlsanity.com/paper/1901.09659/) (2018)

## Built on by (most cited first, 6 of 6)

- [Bayesian Simultaneous Factorization and Prediction Using Multi-Omic Data](https://mlsanity.com/paper/2211.16403/) (2022)
- [Generalization Bounds for Inductive Matrix Completion in Low-noise Settings](https://mlsanity.com/paper/2212.08339/) (2022)
- [Two-level monotonic multistage recommender systems](https://mlsanity.com/paper/2110.06116/) (2021)
- [Transformed ℓ1 Regularizations for Robust Principal Component Analysis: Toward a Fine-Grained Understanding](https://mlsanity.com/paper/2510.03624/) (2025)
- [Low-rank Distributional Matrix Completion](https://mlsanity.com/paper/2606.04176/) (2026)
- [Retraction-Based Gradient Projection Algorithms on Manifolds](https://mlsanity.com/paper/2609.30885/) (2026)

## Abstract (arXiv)

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.