De-biasing the Lasso: Optimal Sample Size for Gaussian Designs

Performing statistical inference in high-dimension is an outstanding challenge. A major source of difficulty is the absence of precise information on the distribution of high-dimensional estimators. Here, we consider linear regression in the high-dimensional regime pgg n. In this context, we would like to perform inference on a high-dimensional parameters vector θ^*∈mathbb Rp. Important progress has been achieved in computing confidence intervals for single coordinates θ^*i. A key role in these new methods is played by a certain debiased estimator hatθrm d that is constructed from the Lasso. Earlier work establishes that, under suitable assumptions on the design matrix, the coordinates of hatθrm d are asymptotically Gaussian provided θ^* is s0-sparse with s0 = o(√n/log p ). The condition s0 = o(√n/ log p ) is stronger than the one for consistent estimation, namely s0 = o(n/ log p). We study Gaussian designs with known or unknown population covariance. When the covariance is known, we prove that the debiased estimator is asymptotically Gaussian under the nearly optimal condition s0 = o(n/ (log p)2). Note that earlier work was limited to s0 = o(√n/log p) even for perfectly known covariance. The same conclusion holds if the population covariance is unknown but can be estimated sufficiently well, e.g. under the same sparsity conditions on the inverse covariance as assumed by earlier work. For intermediate regimes, we describe the trade-off between sparsity in the coefficients and in the inverse covariance of the design. We further discuss several applications of our results to high-dimensional inference. In particular, we propose a new estimator that is minimax optimal up to a factor 1+on(1) for i.i.d. Gaussian designs.