A Residual Bootstrap for High-Dimensional Regression with Near Low-Rank Designs

Miles LopesNeurIPS 2014

Introduction & TL;DR

In high-dimensional regression where the number of features ($p$) approaches the number of observations ($n$), traditional bootstrap methods fail because models overfit and produce misleadingly small residuals. This paper proves that if the design matrix is "nearly low-rank" (exhibiting collinearity), a residual bootstrap based on ridge regression can accurately quantify uncertainty and generate valid confidence intervals, even without assuming the underlying signal is sparse.

The Challenge of High-Dimensional Residual Bootstraps

The "residual bootstrap" (RB) is a classic statistical tool for estimating the sampling distribution of regression coefficients. However, it has a well-known breaking point: when the feature-to-observation ratio $p/n \approx 1$, Ordinary Least Squares (OLS) fits the noise too well. This "overfitting" makes the residuals much smaller than the actual errors, causing the bootstrap to underestimate uncertainty significantly.

While much of high-dimensional statistics relies on the assumption of sparsity (that most coefficients in the true parameter $\beta$ are zero), this paper tackles the problem from a different angle. It looks at structure in the design matrix $X$. In many real-world applications, features are highly correlated (collinearity), meaning the design matrix is "nearly low-rank." The author investigates whether this specific type of structure can be leveraged to make the bootstrap work again in the high-dimensional regime.

Proposed Method: Two-Stage Ridge Bootstrap

The paper proposes a two-stage residual bootstrap procedure using ridge regression to overcome the limitations of OLS:

  1. Pilot Estimation: Instead of OLS, the author uses a "pilot" ridge estimator $\hat{\beta}_\varrho$ to calculate residuals. Because ridge regression regularizes the fit, it prevents the residuals from shrinking too much due to overfitting.
  2. Resampling: These residuals are centered and resampled to create "bootstrap errors."
  3. Target Estimation: A second ridge estimator $\hat{\beta}_\rho$ is applied to the bootstrap data to approximate the distribution of linear contrasts (e.g., $c^\top(\hat{\beta}_\rho - \beta)$).

The theoretical heavy lifting involves proving consistency using the Mallows ($d_2$) metric. This is a strong form of convergence that doesn't require the statistics to converge to a specific limiting distribution (like a Normal distribution), which is crucial because such limits often don't exist in high dimensions.

Core Insights

  • Structure vs. Sparsity: Most high-dimensional methods (like the Lasso) require the true parameter $\beta$ to be sparse. This paper requires zero sparsity assumptions on $\beta$. Instead, it relies on the decay of singular values in the design matrix $X$—a condition that can be directly inspected in practice, unlike sparsity.
  • Regularization as a Bootstrap Fix: The core "aha moment" is that regularization (ridge regression) serves a dual purpose. It not only provides a stable estimate in high dimensions but also "saves" the bootstrap by ensuring the residuals remain a good proxy for the true error distribution.
  • Simultaneous Confidence Intervals: The paper shows that for nearly low-rank designs, the bootstrap can simultaneously approximate the laws of all mean response values ($X_i^\top \beta$) across the entire dataset, which is a very strong consistency result.

Simulation Setup

The paper relies on synthetic simulations to validate the theory:

  • Design: Random Gaussian designs where the covariance matrix $\Sigma$ has eigenvalues that decay according to a power law ($\lambda_j(\Sigma) = j^{-\eta}$). This simulates "near low-rank" structures with varying degrees of decay ($\eta = 0.5$ for moderate, $\eta = 1.0$ for fast).
  • Settings: The author tests scenarios where $n=100$ and $p$ ranges from 45 to 95 (approaching the $p \approx n$ limit).
  • Error Distributions: Uses a $t$-distribution with 5 degrees of freedom to test robustness against non-Gaussian errors.

Results and Performance

The author provides a simple criterion for bootstrap consistency based on a bias-variance decomposition. Empirically, the proposed ridge bootstrap vastly outperforms traditional OLS approaches in extreme high-dimensional settings.

Table comparing confidence interval width and coverage across different settings. Notice the severe drop in OLS coverage when p=95.

As shown in the table above, in simulations where $p=95$ and $n=100$ (Settings 2 and 4):

  • OLS Bootstrap Fails: The OLS method provides only 42% coverage for a nominal 90% confidence interval, demonstrating severe underestimation of uncertainty.
  • Proposed Ridge Bootstrap Succeeds: The ridge-based bootstrap maintains near-perfect coverage, achieving 88% to 92% coverage depending on the eigenvalue decay rate.
  • Width Efficiency: Despite being much more accurate in coverage, the ridge-based intervals are not excessively wide, showing that the method provides a tight and reliable measure of uncertainty.

Limitations and Future Directions

  • Gaussian Design Assumption: While the initial theorems are general, the most specific consistency results assume the design matrix $X$ is Gaussian. Extending this to a broader class of random matrices would be a logical next step.
  • Tuning Parameter Sensitivity: The method requires choosing two regularization parameters ($\rho$ and $\varrho$). While the paper suggests cross-validation, the theoretical relationship between these two parameters in the bootstrap context warrants more exploration.
  • Comparison with Normal Approximation: The author notes that a simple Normal approximation also performs well in some cases. Future work is needed to determine exactly when the bootstrap offers a distinct advantage over analytical approximations in high dimensions.

Summary updated

BibTeX
@inproceedings{lopes2014residual,
  author = {Miles Lopes},
  title = {{A Residual Bootstrap for High-Dimensional Regression with Near Low-Rank Designs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure