Research map / Learning theory and algorithms / Matrix and tensor methods
A Pairwise Pseudo-likelihood Approach for Matrix Completion with Informative Missingness
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a regularized pairwise pseudo-likelihood estimator for matrix completion under separable informative (MNAR) missingness, recovering the matrix up to scale-shift equivalence with near-minimax error rates.
Problem
Matrix completion when the observation probability depends on the (mostly unobserved) entry values themselves, i.e., missing-not-at-random, which is generally non-identifiable.
Approach
Under a separable missingness assumant Pr(T=1|Y)=t_ij*s(Y), the conditional likelihood of local pairwise ranks eliminates unknown s(.) and t_ij; a nuclear-norm-regularized pairwise pseudo-likelihood is minimized with a constraint on the shift, yielding estimates identified up to scale and constant shift.</probl em>
Key results
- On the Tobacco dataset, the proposed method's TRMSE is 14.14 vs 12.09 for SNN and 15.89 for MFW, the best non-SNN baseline.
- On the Yahoo! Webscope subset, the proposed method achieves the lowest TRMSE (1.12) vs SNN 1.27 and MFW 1.28.
- In simulations with variance sigma^2=1, only the proposed method produces a symmetric recovered-entry distribution; other methods are left-skewed; SNN has the worst error at large variance.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use pairwise pseudo-likelihood instead of SNN | Matrix completion · Tobacco Dataset | TRMSE: 12.09 (0.16) -> 14.14 (0.36) | Hurt |
| Use pairwise pseudo-likelihood instead of MFW | Matrix completion · Coat Shopping Dataset | TRMSE: 1.07 -> 1.20 | Hurt |
| Use pairwise pseudo-likelihood instead of SNN | Matrix completion · Yahoo! Webscope Dataset (subset) | TRMSE: 1.27 -> 1.12 | Helped |
| Use pairwise pseudo-likelihood instead of SoftImpute | Matrix completion · Simulation, 100 × 100, informative missingness | TRMSE: 1.3973 ± 0.0844 -> 0.6482 ± 0.0396 | Helped |
| Use pairwise pseudo-likelihood instead of SoftImpute | Matrix completion · Simulation, 100 × 100, informative missingness | TMAE: 1.014 ± 0.0636 -> 0.4920 ± 0.0237 | Helped |
| Use pairwise pseudo-likelihood instead of SNN | Matrix completion · Simulation, σ2 = 1 | time (s): 15.23 ± 1.39 -> 8.67 ± 1.23 | Helped |
| Use pairwise pseudo-likelihood instead of SoftImpute | Matrix completion · Simulation, σ2 = 1 | time (s): 0.01 ± 0.005 -> 8.67 ± 1.23 | Hurt |
| Account for informative missingness with the proposed method rather than the compared alternatives | Matrix completion · Simulation, variance σ2 = 0.0, 0.2, 0.4, 0.6, 0.8, 1.0 | TRMSE | Helped |
| Use pairwise pseudo-likelihood instead of the other methods | Matrix completion · Tobacco, Coat Shopping, and Yahoo! Webscope datasets | TRMSE | Mixed |
Surprising findings
- SNN, which handles MNAR, performs worst on the Coat Shopping dataset (TRMSE 2.06) despite being best on Tobacco.
- The method is slower than SVD-based baselines, with runtime 8.67 s vs 0.01 s for SoftImpute in the simulation.
Limitations
- Only scale-shift equivalence is identifiable; the dispersion and constant shift cannot be recovered, so a validation set is needed to learn a shift and scale for reporting errors.
- Requires independence across entries given the true matrix and separable missingness; Tobacco experiment violates the assumption and yields suboptimal performance relative to SNN.
- Pairwise grouping makes computation expensive for large numbers of observed entries.
Experimental setup
Datasets: Tobacco Dataset Coat Shopping Dataset Yahoo! Webscope Dataset simulated Gaussian matrices
Benchmarks: Tobacco Dataset Coat Shopping Dataset Yahoo! Webscope Dataset (subset) simulated matrices
Metrics: test root mean squared error (TRMSE) test mean absolute error (TMAE) computation time
Baselines: SoftImpute CZ (max norm) MFW (model-free weighting) SNN (synthetic nearest neighbors)
Builds on: pairwise pseudo-likelihood (Fong et al.) SoftImpute exponential family matrix completion
Closest papers by meaning
- Scalable Completion of Nonnegative Matrix with Separable Structure (AAAI 2016 · similarity 0.91)
- A New Theory for Matrix Completion (NeurIPS 2017 · similarity 0.90)
- Missing Not at Random in Matrix Completion: The Effectiveness of Estimating Missingness Probabilities Under a Low Nuclear Norm Assumption (NeurIPS 2019 · similarity 0.90)
- RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees (NeurIPS 2025 · similarity 0.88)
- Fast exact recovery of noisy matrix from few entries: the infinity norm approach (NeurIPS 2025 · similarity 0.88)
- Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.