Hypothesis Testing in High-Dimensional Regression under the Gaussian Random Design Model: Asymptotic Theory

We consider linear regression in the high-dimensional regime where the number\nof observations $n$ is smaller than the number of parameters $p$. A very\nsuccessful approach in this setting uses $\\ell_1$-penalized least squares\n(a.k.a. the Lasso) to search for a subset of $s_0< n$ parameters that best\nexplain the data, while setting the other parameters to zero. Considerable\namount of work has been devoted to characterizing the estimation and model\nselection problems within this approach.\n In this paper we consider instead the fundamental, but far less understood,\nquestion of \\emph{statistical significance}. More precisely, we address the\nproblem of computing p-values for single regression coefficients.\n On one hand, we develop a general upper bound on the minimax power of tests\nwith a given significance level. On the other, we prove that this upper bound\nis (nearly) achievable through a practical procedure in the case of random\ndesign matrices with independent entries. Our approach is based on a debiasing\nof the Lasso estimator. The analysis builds on a rigorous characterization of\nthe asymptotic distribution of the Lasso estimator and its debiased version.\nOur result holds for optimal sample size, i.e., when $n$ is at least on the\norder of $s_0 \\log(p/s_0)$.\n We generalize our approach to random design matrices with i.i.d. Gaussian\nrows $x_i\\sim N(0,\\Sigma)$. In this case we prove that a similar distributional\ncharacterization (termed `standard distributional limit') holds for $n$ much\nlarger than $s_0(\\log p)^2$.\n Finally, we show that for optimal sample size, $n$ being at least of order\n$s_0 \\log(p/s_0)$, the standard distributional limit for general Gaussian\ndesigns can be derived from the replica heuristics in statistical physics.\n