High-dimensional estimation with missing data: Statistical and computational limits
This work addresses the challenge of robust estimation in high-dimensional settings with missing data, which is critical for fields like statistics and machine learning, though it is incremental in extending known gaps to new problems.
The paper investigates the statistical and computational limits of high-dimensional estimation with missing data under a contamination model, showing that for mean and covariance estimation, there is a gap where computationally efficient methods require significantly more samples than inefficient ones, but for linear regression, efficient methods can nearly achieve the optimal bound.
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 $\ell_2$ norm, we show that in order to obtain error at most $Ï$, for any constant contamination $ε\in (0, 1)$, (roughly) $n \gtrsim d e^{1/Ï^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 d^{1/Ï^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.