# High-dimensional estimation with missing data: Statistical and computational limits

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 0 of its 1 references that are in the map.
- First posted on arXiv 17 Mar 2026.

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

- [High-Dimensional Statistics: Reflections on Progress and Open Problems](https://mlsanity.com/paper/2605.05076/) (2026)

## Abstract (arXiv)

We consider computationally-efficient estimation of population parameters when observations are subject to missing data. In particular, we consider estimation under the realizable contamination model of missing data in which an ε fraction of the observations are subject to an arbitrary (and unknown) missing not at random (MNAR) mechanism. When the true data is Gaussian, we provide evidence towards statistical-computational gaps in several problems. For mean estimation in ℓ2 norm, we show that in order to obtain error at most ρ, for any constant contamination ε ∈ (0, 1), (roughly) n gtrsim d e1/ρ2 samples are necessary and that there is a computationally-inefficient algorithm which achieves this error. On the other hand, we show that any computationally-efficient method within certain popular families of algorithms requires a much larger sample complexity of (roughly) n gtrsim d1/ρ2 and that there exists a polynomial time algorithm based on sum-of-squares which (nearly) achieves this lower bound. For covariance estimation in relative operator norm, we show that a parallel development holds. Finally, we turn to linear regression with missing observations and show that such a gap does not persist. Indeed, in this setting we show that minimizing a simple, strongly convex empirical risk nearly achieves the information-theoretic lower bound in polynomial time.