Implementable confidence sets in high dimensional regression

Alexandra CarpentierAISTATS 2015

In high-dimensional regression, where the number of features $p$ significantly exceeds the number of observations $n$, the primary challenge is not just estimation, but uncertainty quantification. While the Lasso and similar methods provide point estimates, constructing confidence sets that are both "honest" (covering the true parameter with high probability) and "adaptive" (shrinking in size when the data is sparse) is a long-standing theoretical hurdle. Alexandra Carpentier's 2015 AISTATS paper presents a breakthrough: a computationally efficient $O(pn)$ algorithm that achieves these goals by focusing on a "maximal model" of parameters.

The Honesty-Adaptivity Dilemma

In the model $Y = X\theta + \epsilon$, we typically assume $\theta$ is sparse. An ideal confidence set would automatically adjust its diameter based on the true sparsity $S$ of $\theta$. However, minimax theory demonstrates a fundamental impossibility: one cannot maintain honesty across the entire parameter space while remaining adaptive. Certain "pathological" parameters—those that are not sparse but appear so to any estimator—force a trade-off. Previous theoretical solutions to this problem were often computationally intractable, requiring $O(p^S)$ operations.

A Computationally Efficient Separation Strategy

Carpentier's approach circumvents these issues through a two-step "Separation Strategy." Instead of attempting honesty over the entire space, the method defines a maximal set that excludes parameters indistinguishable from sparse ones.

Figure 1: The separation strategy illustrates how the algorithm distinguishes between different sparsity levels ($S_0, S_1$) by analyzing the squared components of the parameter vector $\theta$.

The algorithm employs a data-splitting technique. On the first half of the data, a Lasso estimate $\hat{\theta}$ is computed. The critical innovation lies in the subsequent test statistic $\Psi_n$, which evaluates the squared residuals $||Y - X\hat{\theta}||^2$. If the residuals are significantly larger than the expected noise level, it indicates that the Lasso has missed small but significant non-zero components. In such cases, the algorithm "rejects" the higher sparsity assumption and widens the confidence set to maintain honesty.

Empirical Results and Applications

The method's performance was validated through both simulations and real-world image data. In high-dimensional simulations ($p=10,000, n=1,000$), the test statistic correctly identified sparsity classes with error rates typically below 5%.

Figure 2: A sketch of the cathedral image used in the study, featuring a background "cloud" that tests the algorithm's ability to handle approximate sparsity.

A particularly compelling application involved the reconstruction of a $7.2$-million-pixel image of a cathedral from just $36,000$ random Fourier coefficients. The algorithm was tasked with distinguishing between a "clean" sparse image and one containing a background cloud. While the visual reconstructions might appear similar, the confidence sets produced by this method correctly reflected the increased uncertainty in the "cloudy" image, providing a wider margin of error as required by the underlying data structure.

Conclusion

By shifting the focus from theoretical combinatorics to practical residual analysis, this work provides a scalable solution for uncertainty quantification in high dimensions. The resulting confidence sets are minimax optimal, achieving a diameter proportional to $\sqrt{S \log(p)/n}$ without prior knowledge of the sparsity $S$. While constraints like the Restricted Isometry Property (R.I.P.) remain, this method represents a significant step toward reliable, implementable statistical inference in complex datasets.

Summary updated

BibTeX
@inproceedings{carpentier2015implementable,
  author = {Alexandra Carpentier},
  title = {{Implementable confidence sets in high dimensional regression}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2015},
}
Figure