# Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization

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

## Key facts

- Cited by 58 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Feb 2019.

## Built on by (most cited first, 30 of 58)

- [Inference for Heteroskedastic PCA with Missing Data](https://mlsanity.com/paper/2107.12365/) (2021)
- [Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model](https://mlsanity.com/paper/2105.14016/) (2021)
- [Uncertainty Quantification of MLE for Entity Ranking with Covariates](https://mlsanity.com/paper/2212.09961/) (2022)
- [On Speeding Up Language Model Evaluation](https://mlsanity.com/paper/2407.06172/) (2024)
- [A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples](https://mlsanity.com/paper/2106.02119/) (2021)
- [Optimal Algorithms for Latent Bandits with Cluster Structure](https://mlsanity.com/paper/2301.07040/) (2023)
- [Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensing](https://mlsanity.com/paper/2204.11516/) (2022)
- [GNMR: A provable one-line algorithm for low rank matrix recovery](https://mlsanity.com/paper/2106.12933/) (2021)
- [Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning](https://mlsanity.com/paper/2310.06793/) (2023)
- [Online Low Rank Matrix Completion](https://mlsanity.com/paper/2209.03997/) (2022)
- [Approximate message passing from random initialization with applications to mathbbZ2 synchronization](https://mlsanity.com/paper/2302.03682/) (2023)
- [Synthetically Controlled Bandits](https://mlsanity.com/paper/2202.07079/) (2022)
- [Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structure](https://mlsanity.com/paper/2206.03569/) (2022)
- [Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA](https://mlsanity.com/paper/2303.06198/) (2023)
- [Matrix Completion with Model-free Weighting](https://mlsanity.com/paper/2106.05850/) (2021)
- [Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization](https://mlsanity.com/paper/2310.06159/) (2023)
- [Learning Treatment Effects in Panels with General Intervention Patterns](https://mlsanity.com/paper/2106.02780/) (2021)
- [Robust Matrix Completion with Heavy-tailed Noise](https://mlsanity.com/paper/2206.04276/) (2022)
- [Low-Rank Covariance Completion for Graph Quilting with Applications to Functional Connectivity](https://mlsanity.com/paper/2209.08273/) (2022)
- [Speed Up the Cold-Start Learning in Two-Sided Bandits with Many Arms](https://mlsanity.com/paper/2210.00340/) (2022)
- [Multi-User Reinforcement Learning with Low Rank Rewards](https://mlsanity.com/paper/2210.05355/) (2022)
- [Context-lumpable stochastic bandits](https://mlsanity.com/paper/2306.13053/) (2023)
- [Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees](https://mlsanity.com/paper/2410.06376/) (2024)
- [Online Policy Learning and Inference by Matrix Completion](https://mlsanity.com/paper/2404.17398/) (2024)
- [Partial Matrix Completion](https://mlsanity.com/paper/2208.12063/) (2022)
- [Generalization Bounds for Inductive Matrix Completion in Low-noise Settings](https://mlsanity.com/paper/2212.08339/) (2022)
- [Blocked Collaborative Bandits: Online Collaborative Filtering with Per-Item Budget Constraints](https://mlsanity.com/paper/2311.03376/) (2023)
- [Statistical Inference For Noisy Matrix Completion Incorporating Auxiliary Information](https://mlsanity.com/paper/2403.14899/) (2024)
- [Optimal Transfer Learning for Missing Not-at-Random Matrix Completion](https://mlsanity.com/paper/2503.00174/) (2025)
- [Tucker Diffusion Model for High-dimensional Tensor Generation](https://mlsanity.com/paper/2604.00481/) (2026)

## Abstract (arXiv)

This paper studies noisy low-rank matrix completion: given partial and noisy entries of a large low-rank matrix, the goal is to estimate the underlying matrix faithfully and efficiently. Arguably one of the most popular paradigms to tackle this problem is convex relaxation, which achieves remarkable efficacy in practice. However, the theoretical support of this approach is still far from optimal in the noisy setting, falling short of explaining its empirical success. We make progress towards demystifying the practical efficacy of convex relaxation vis-`a-vis random noise. When the rank and the condition number of the unknown matrix are bounded by a constant, we demonstrate that the convex programming approach achieves near-optimal estimation errors --- in terms of the Euclidean loss, the entrywise loss, and the spectral norm loss --- for a wide range of noise levels. All of this is enabled by bridging convex relaxation with the nonconvex Burer-Monteiro approach, a seemingly distinct algorithmic paradigm that is provably robust against noise. More specifically, we show that an approximate critical point of the nonconvex formulation serves as an extremely tight approximation of the convex solution, thus allowing us to transfer the desired statistical guarantees of the nonconvex approach to its convex counterpart.