Two-Stage Sampling, Prediction and Adaptive Regression via Correlation Screening.

Hamed Firouzi, Alfred O. Hero Iii, Bala RajaratnamIEEE Trans. Information Theory 2017 · OpenReview

TL;DR

This paper introduces SPARCS, a novel two-stage adaptive sampling and regression method designed for high-dimensional, budget-limited prediction problems. SPARCS efficiently balances sampling costs and prediction accuracy by first performing a low-cost variable selection on a small, expensive dataset and then building a predictor on a larger, cheaper dataset using only the selected variables.

What Problem Does This Paper Address?

Many real-world prediction problems, particularly in fields like experimental science, medicine, and finance, involve a vast number of potential predictor variables (high dimensions, $p$) but limited resources for data collection. Acquiring data for all variables can be prohibitively expensive, especially when the cost scales with the number of variables. This "small $n$, large $p$" scenario poses challenges for traditional regression methods, leading to issues like overfitting and computational complexity. Existing methods often treat data collection and model building as separate, offline processes. This paper addresses the need for an adaptive, cost-aware approach that intelligently samples data and selects relevant variables to build accurate predictive models under budget constraints.

Methods

The core of the proposed method, SPARCS (Two-stage Sampling, Prediction and Adaptive Regression via Correlation Screening), is a two-stage procedure:

  1. SPARCS Screening Stage: A small number ($n$) of expensive, full-dimensional samples are collected. During this stage, variable selection is performed to reduce the dimensionality from $p$ to a smaller set of $l$ variables. This selection can be done using either:
  2. Sure Independence Screening (SIS): Based on sample marginal cross-correlation between the response ($Y$) and predictor variables ($X$).
  3. Predictive Correlation Screening (PCS): Based on thresholding the min-norm solution to the generalized Ordinary Least Squares (OLS) problem. The paper highlights PCS as generally outperforming SIS in their experiments.
  4. SPARCS Regression Stage: A larger number ($t-n$) of cheaper samples are collected, but only for the $l$ variables identified in the first stage. A final predictor is then constructed using OLS on all $t$ samples (both from stage 1 and stage 2) for these selected $l$ variables.

SPARCS is designed as an adaptive, online algorithm that controls false positives and is scalable to high dimensions. The authors also establish theoretical guarantees for support recovery and optimal sample allocation between the two stages.

Datasets

The paper does not introduce new benchmark datasets. Instead, it uses:

  • Synthetic data: Generated according to a linear model with varying levels of sparsity, multicollinearity, and noise.
  • Real-world data: The Predictive Health and Disease data set, which includes gene expression levels and symptom scores from human subjects.

Key Insights and Ideas

  • Cost-aware adaptive sampling is crucial: In high-dimensional settings with limited budgets, simply collecting more data isn't always the best strategy. SPARCS demonstrates that intelligently how and where to sample (expensive vs. cheap data, full vs. reduced dimension) can significantly improve prediction performance.
  • Two-stage approach offers optimal trade-off: Breaking the problem into a screening stage (for variable selection) and a regression stage (for prediction) allows for an efficient balance between sampling cost and predictor accuracy. This is particularly effective when the cost of acquiring data is high and scales with dimensionality.
  • PCS outperforms SIS: The paper's empirical results suggest that the PCS method for variable selection in the first stage, which uses a pseudo-inverse factor, generally leads to better performance than SIS, especially in low sample regimes.
  • Theoretical guarantees for high dimensions: The authors provide theoretical bounds on false discovery rates and support recovery, demonstrating that SPARCS can effectively identify relevant variables even when $p \gg n$.
  • Optimal sample allocation is data-dependent: The optimal split of samples between the two stages ($n$ and $t-n$) depends on the budget and the sparsity of the underlying model, with $n$ often being on the order of $O(\log t)$.

Key Results

  • Improved Prediction Accuracy: SPARCS, particularly PCS-SPARCS, consistently outperformed LASSO and SIS-SPARCS in terms of Root Mean Squared Error (RMSE) in simulations, especially in low sample regimes and with high dimensionality ($p=10000$). For instance, in one experiment, PCS-SPARCS achieved an RMSE that was a factor of 2 lower than the Oracle OLS predictor.
  • Reduced Mis-selection Error: Figure 4 shows that PCS significantly reduces the number of mis-selected variables compared to SIS and LASSO in high-dimensional settings.
  • Computational Efficiency: SPARCS methods (SIS-SPARCS and PCS-SPARCS) were orders of magnitude faster than LASSO due to their lower computational complexity.
  • Theoretical Support: The paper establishes asymptotic bounds for Family-Wise Error Rate (FWER) and provides theoretical guarantees for support recovery under various assumptions, including those accommodating heavy tails.
  • Real-world Application: In the gene expression and symptom prediction task, PCS-SPARCS showed better prediction performance for 7 out of 10 symptoms compared to SIS-SPARCS and LASSO.

Limitations and Future Work

  • Assumptions: The theoretical analysis relies on certain assumptions about the data distribution (e.g., elliptically contoured distributions) and the sparsity of the underlying model. While these assumptions are often weaker than those in prior work, they may not hold in all practical scenarios.
  • Generalization to Multi-stage: The authors suggest that extending SPARCS to a multi-stage framework could further improve performance and computational efficiency.
  • Non-linear Relationships: The current framework is primarily designed for linear regression. Future work could explore extending SPARCS to handle non-linear relationships between predictors and the response.
  • Hyperparameter Tuning: While the paper discusses optimal sample allocation, further research into robust methods for tuning hyperparameters (like the screening threshold) in practice would be beneficial.

Summary updated

Abstract

This paper proposes a general adaptive procedure for budget-limited predictor design in high dimensions called two-stage Sampling, Prediction and Adaptive Regression via Correlation Screening (SPARCS). The SPARCS can be applied to high-dimensional prediction problems in experimental science, medicine, finance, and engineering, as illustrated by the following. Suppose that one wishes to run a sequence of experiments to learn a sparse multivariate predictor of a dependent variable Y (disease prognosis for instance) based on a p dimensional set of independent variables X = [X <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> ,..., X <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</sub> ] <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</sup> (assayed biomarkers). Assume that the cost of acquiring the full set of variables X increases linearly in its dimension. The SPARCS breaks the data collection into two stages in order to achieve an optimal tradeoff between sampling cost and predictor performance. In the first stage, we collect a few (n) expensive samples {y <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> , s <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> } <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i=1</sub> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> , at the full dimension p ≫ n of X, winnowing the number of variables down to a smaller dimension l <; p using a type of cross correlation or regression coefficient screening. In the second stage, we collect a larger number (t - n) of cheaper samples of the l variables that passed the screening of the first stage. At the second stage, a low-dimensional predictor is constructed by solving the standard regression problem using all t samples of the selected variables. The SPARCS is an adaptive online algorithm that implements false positive control on the selected variables, is well suited to small sample sizes, and is scalable to high dimensions. We establish asymptotic bounds for the familywise error rate, specify high dimensional convergence rates for support recovery, and establish optimal sample allocation rules to the first and second stages.
BibTeX
@article{firouzi2017two,
  author = {Hamed Firouzi and Alfred O. Hero III and Bala Rajaratnam},
  title = {{Two-Stage Sampling, Prediction and Adaptive Regression via Correlation Screening.}},
  journal = {IEEE Trans. Information Theory},
  year = {2017},
  url = {https://openreview.net/forum?id=ARqroZ_zx0H7},
}
Figure