TL;DR
This paper proposes a simple yet effective strategy for high-dimensional linear regression when some covariate data is missing: impute missing values with their conditional mean and then apply standard LASSO or square-root LASSO. This approach achieves optimal estimation rates, even when the conditional mean is only approximated, offering a practical alternative to complex custom algorithms.
What Problem Does This Paper Address?
In many real-world scenarios, especially in high-dimensional settings (where the number of features $p$ is much larger than the number of samples $n$), linear regression models are used. However, a common challenge is that some of the predictor variables (covariates) might be missing. Traditionally, statistical procedures assume complete data. While some recent research has focused on developing specialized, often complex, algorithms for this missing data problem, this paper revisits a simpler strategy: imputation. The authors aim to show that a straightforward imputation of missing covariates with their conditional mean, followed by standard off-the-shelf regression techniques like LASSO, can achieve theoretically optimal results. This is particularly relevant because computing the exact conditional mean is often infeasible in practice, necessitating approximation methods.
Methods
The core of the paper's methodology revolves around an imputation strategy. Specifically, they propose to replace each missing covariate entry $Z_{ia}$ with its conditional expectation given the observed covariates, $\hat{X}_{ia} = E[X_{ia} | Z]$. This imputed matrix, denoted as $\hat{X}$, is then used in place of the complete design matrix $X$ in standard high-dimensional regression algorithms.
The paper analyzes two main scenarios:
- Exact Conditional Expectation: When the conditional expectation $E[X_{ia} | Z]$ can be computed exactly (e.g., for i.i.d. sub-Gaussian covariates), they show that using this imputed matrix with LASSO or square-root LASSO retains the optimal minimax estimation rates.
- Approximate Conditional Expectation: When the conditional expectation needs to be approximated, the authors propose tractable estimators for specific cases, such as autoregressive (AR) models and Gaussian graphical models with sparse precision matrices. They then apply LASSO with these approximated imputed matrices and demonstrate that similar optimal estimation rates are maintained.
A key theoretical tool used is the analysis of restricted eigenvalues, which is crucial for understanding the performance of LASSO-type estimators in high dimensions. The paper also highlights the pivotal nature of the square-root LASSO, meaning its performance is robust to unknown noise variance and the norm of the regression vector.
Datasets
The paper uses synthetic data generated according to various models (standard Gaussian, AR(1), banded inverse covariance) and semi-synthetic data. Specifically, they mention using:
- Gene expression cancer RNA-Seq data from the UCI repository for semi-synthetic experiments.
- Communities and crime data from the UCI repository for real-data simulations.
The authors artificially induce missingness (MCAR) in these datasets to test their imputation strategy.
Key Insights and Ideas
- Simplicity Wins: The paper demonstrates that a simple imputation strategy (using conditional mean) followed by standard LASSO can be as effective as more complex, custom-designed algorithms for high-dimensional regression with missing data. This is a significant practical insight.
- Conditional Mean Imputation is Powerful: Imputing missing values with their conditional expectation, even when approximated, preserves the desirable theoretical properties (like rate-optimality) of standard regression techniques.
- Square-Root LASSO's Robustness: The square-root LASSO, when used with this imputation strategy, is shown to be "pivotal." This means the choice of regularization parameter doesn't require knowledge of the noise variance or the regression vector's norm, making it more user-friendly in practice.
- Leveraging Structure for Approximation: For cases where the conditional expectation is hard to compute, the paper shows that exploiting the underlying structure of the data (like graphical models or AR processes) allows for good approximations that still lead to optimal estimation rates.
Key Results
The paper provides theoretical guarantees for their imputation strategy:
- Rate-Optimality: The proposed imputation method, when combined with LASSO or square-root LASSO, achieves rate-optimal statistical guarantees for high-dimensional linear regression with missing covariates. This means the error bounds match the best possible theoretical limits.
- Pivotal Estimation with Square-Root LASSO: The square-root LASSO, in particular, is shown to be pivotal with respect to noise variance and the regression vector's norm, simplifying practical implementation.
- Performance with Approximated Conditional Expectation: For AR(1) and sparse Gaussian graphical models, the imputation using approximated conditional expectations also yields similar estimation rates to the exact case.
- Empirical Validation: Simulations on synthetic and semi-synthetic datasets (gene expression, communities and crime) support the theoretical findings, showing that the imputation strategy performs well across various missingness levels and data structures.
Limitations and Future Work
- Exact Conditional Expectation Assumption: While the paper addresses approximated conditional expectations, the theoretical analysis often relies on the ability to compute or approximate this quantity. The tractability of this approximation is crucial.
- Linear Model Focus: The current work is focused on linear regression. The authors suggest that extending these ideas to generalized linear models or other statistical models with missing data would be an interesting future direction.
- Non-asymptotic Bounds: The paper provides non-asymptotic bounds for the high-dimensional regime. Characterizing the exact asymptotic performance of their procedures in the proportional regime is mentioned as a potential area for further research.
- Unknown Covariance: While the paper shows that approximated covariance is sufficient for sparse Gaussian graphical models, handling unknown covariance in a more general setting might be an area for future exploration.
Summary updated