Abstract
We propose an estimator of prediction error using an approximate message passing (AMP) algorithm that can be applied to a broad range of sparse penalties. Following Stein's lemma, the estimator of the generalized degrees of freedom, which is a key quantity for the construction of the estimator of the prediction error, is calculated at the AMP fixed point. The resulting form of the AMP-based estimator does not depend on the penalty function, and its value can be further improved by considering the correlation between predictors. The proposed estimator is asymptotically unbiased when the components of the predictors and response variables are independently generated according to a Gaussian distribution. We examine the behaviour of the estimator for real data under nonconvex sparse penalties, where Akaike's information criterion does not correspond to an unbiased estimator of the prediction error. The model selected by the proposed estimator is close to that which minimizes the true prediction error.
Introduction
In high-dimensional sparse linear regression, selecting the optimal regularization parameter (often denoted as $\eta$ or $\lambda$) is a critical task. This process, known as model selection, aims to minimize the prediction error—the model's performance on unseen data. However, researchers typically only have access to the training error, which is inherently biased due to overfitting on the specific observed data.
To correct this bias, statisticians utilize the Generalized Degrees of Freedom (GDF). While GDF is well-defined for simple models and the $\ell_1$ (LASSO) penalty, it becomes computationally prohibitive and theoretically complex for modern non-convex penalties such as the Smoothly Clipped Absolute Deviation (SCAD) or the Minimax Concave Penalty (MCP). Traditional tools like Akaike’s Information Criterion (AIC) often fail to provide unbiased error estimates for these sophisticated estimators because they do not account for the specific complexities of non-convex optimization.
Methodology
The authors introduce a novel estimator for prediction error leveraging the Approximate Message Passing (AMP) algorithm. AMP is an iterative framework derived from statistical physics and signal processing, designed to solve high-dimensional inference problems with high efficiency.
Stein’s Lemma and the AMP Fixed Point
The core of the proposed method involves Stein’s Lemma, a statistical identity that relates the GDF to the derivative of the model's fit with respect to the observed data. The authors demonstrate that these necessary derivatives can be extracted directly from the state variables at the AMP algorithm's convergence point (the fixed point).
A significant advantage of this approach is its penalty independence. The mathematical form of the AMP-based estimator remains consistent regardless of the specific penalty function employed. This versatility allows it to handle the "transient regions" characteristic of non-convex penalties—areas where coefficients are neither zero nor fully un-shrunk—which are typically ignored by AIC, leading to biased results.
Correlation Correction
Standard AMP assumes that predictors are independent and identically distributed (i.i.d.) Gaussian variables. To adapt the method for real-world datasets where predictors are often correlated, the authors propose a heuristic correction, denoted as $\hat{df}^{(2)}$. This involves re-calculating the variance on the "support set" (the subset of variables selected by the model), effectively bridging the gap between idealized theory and practical application.
Experimental Results
The proposed estimator was validated using both synthetic simulations and real-world data.
Synthetic Validation
Using high-dimensional Gaussian random matrices, the authors compared the AMP-based estimator against theoretical results derived from Replica Analysis. The simulations confirmed that the estimator is asymptotically unbiased, matching the theoretical prediction error perfectly in the Gaussian regime.
Real-World Application: Crime Data
The method was applied to the "Communities and Crime Unnormalized Data Set" from the UCI Machine Learning Repository, modeling the number of murders per 100,000 population using 70 predictors and 302 response variables.
The results highlighted the limitations of traditional AIC, which tended to select overly complex models with too many variables. In contrast, the proposed $\hat{df}^{(2)}$ estimator captured the qualitative behavior of the true prediction error much more accurately. For non-convex penalties like SCAD and MCP, the model selected by the AMP-based method was significantly closer to the true error-minimizing model than those selected by traditional criteria.
Conclusion
This research provides a numerically efficient diagnostic tool for high-dimensional regression. By utilizing the internal state of the AMP algorithm (specifically the rescaled variance $V_\mu$), researchers can obtain a "free" estimate of model complexity alongside the regression coefficients.
While the current approach shows great promise, challenges remain regarding the convergence of AMP on highly correlated or non-Gaussian data. Future work will focus on improving the stability of the algorithm and developing more efficient automated methods for finding the minimum of the estimated error curve without manual hyperparameter sweeps.
Summary updated