Rate Optimal Estimation and Confidence Intervals for High-dimensional
  Regression with Missing Covariates
  Although a majority of the theoretical literature in high-dimensional
statistics has focused on settings which involve fully-observed data, settings
with missing values and corruptions are common in practice. We consider the
problems of estimation and of constructing component-wise confidence intervals
in a sparse high-dimensional linear regression model when some covariates of
the design matrix are missing completely at random. We analyze a variant of the
Dantzig selector [9] for estimating the regression model and we use a
de-biasing argument to construct component-wise confidence intervals. Our first
main result is to establish upper bounds on the estimation error as a function
of the model parameters (the sparsity level s, the expected fraction of
observed covariates $\rho_*$, and a measure of the signal strength
$\|\beta^*\|_2$). We find that even in an idealized setting where the
covariates are assumed to be missing completely at random, somewhat
surprisingly and in contrast to the fully-observed setting, there is a
dichotomy in the dependence on model parameters and much faster rates are
obtained if the covariance matrix of the random design is known. To study this
issue further, our second main contribution is to provide lower bounds on the
estimation error showing that this discrepancy in rates is unavoidable in a
minimax sense. We then consider the problem of high-dimensional inference in
the presence of missing data. We construct and analyze confidence intervals
using a de-biased estimator. In the presence of missing data, inference is
complicated by the fact that the de-biasing matrix is correlated with the pilot
estimator and this necessitates the design of a new estimator and a novel
analysis. We also complement our mathematical study with extensive simulations
on synthetic and semi-synthetic data that show the accuracy of our asymptotic
predictions for finite sample sizes.
