High-dimensional networks and mean squared error for possibly misspecified models
Combining ridge regression with minimum description length enables low false positive neighborhood selection in high-dimensional networks.
Key Findings
Methodology
This paper introduces a novel approach for neighborhood selection in high-dimensional network models by integrating ridge regression with minimum description length (MDL). The method leverages the bias-variance trade-off controlled by the ridge parameter (α) to analyze its impact on mean squared error (MSE), especially when the number of parameters exceeds the sample size. The authors employ a nodewise regression framework, transforming the neighborhood detection problem into multiple linear regressions, and utilize the theoretical properties of ridge estimators to demonstrate that, even under model misspecification (nonlinear true models), the combined approach maintains low false positive rates. The study further incorporates insights from machine learning, particularly the double descent phenomenon, to understand the behavior of overparameterized models, emphasizing the importance of model space volume in penalty design. The core contribution lies in proving that MDL-based penalties effectively balance model complexity and fit, leading to accurate neighborhood identification in both correctly and incorrectly specified models.
Key Results
- Simulations across networks with 15, 32, and 320 nodes show that the MDL-based neighborhood selection achieves over 95% accuracy with false positive rates below 5%, outperforming Lasso, AIC, and BIC, especially when the true model is nonlinear. The method robustly captures the true neighborhood structure, even under model misspecification.
- Adjusting the ridge parameter (α) influences the MSE significantly; moderate regularization suppresses overfitting, leading to improved generalization. The experiments reveal that overparameterized models, contrary to classical bias-variance intuition, can exhibit low test error due to the double descent effect, which the MDL penalty effectively counters.
- Theoretical analysis confirms that in high-dimensional settings, the MDL penalty accounts for the large model space volume, ensuring the selection of neighborhoods that are either correct or conservative, thus reducing false positives. The approach demonstrates stability and consistency across different network sizes and model assumptions.
Significance
This work advances the field of high-dimensional network analysis by providing a theoretically grounded, practically effective neighborhood selection method that remains reliable under model misspecification. Its integration of ridge regression's bias-variance properties with MDL's complexity control addresses longstanding issues of false positives and overfitting prevalent in traditional sparse methods. The approach is particularly relevant for complex biological, social, and neural networks where the number of variables far exceeds the number of observations. By bridging statistical theory with machine learning phenomena like double descent, the research offers a new paradigm for model selection in high-dimensional spaces, promising more accurate and interpretable network reconstructions.
Technical Contribution
The key technical innovation is the analytical linking of ridge regression's bias-variance decomposition with the MDL principle, providing a rigorous foundation for neighborhood selection that balances model fit and complexity. The authors derive explicit formulas for the MSE behavior in high-dimensional regimes, demonstrating that overparameterized models can still generalize well due to the double descent effect. They prove that the MDL penalty, which incorporates the volume of the model space, effectively prevents overfitting, ensuring low false positive rates even when the true model is nonlinear. The work extends existing high-dimensional inference theories by explicitly addressing model misspecification and integrating machine learning insights into statistical model selection frameworks.
Novelty
This research is the first to systematically combine ridge regression's bias-variance analysis with the MDL principle for neighborhood selection in high-dimensional networks. It uniquely leverages the double descent phenomenon to explain why overparameterized models can perform well and how MDL penalties can be designed to control false positives robustly. Unlike traditional sparse methods that rely on Lasso or information criteria like AIC/BIC, this approach explicitly accounts for the model space volume, providing a more comprehensive penalty that adapts to model complexity and misspecification. The integration of theoretical insights from machine learning with classical statistical model selection constitutes a significant innovation in high-dimensional network inference.
Limitations
- The effectiveness of the proposed method depends on the appropriate tuning of the ridge parameter (α), which may require computationally intensive cross-validation, especially in very large networks. Mis-specification of the model (e.g., highly nonlinear relationships) can still pose challenges, as the theoretical guarantees primarily assume approximate linearity or manageable nonlinearity.
- The current analysis assumes Gaussianity and independence in the data, limiting its direct applicability to real-world datasets with heteroskedasticity, non-Gaussian distributions, or correlated errors. Extending the framework to handle such complexities remains an open challenge.
- Computational costs increase with network size, particularly for the repeated model fitting and MDL calculations, which may hinder scalability. Future work should focus on developing more efficient algorithms and approximation techniques to facilitate application to ultra-high-dimensional systems.
Future Work
Future research will explore adaptive methods for tuning the ridge parameter based on data-driven criteria, potentially reducing reliance on computationally expensive cross-validation. Extending the theoretical framework to non-Gaussian, heteroskedastic, and dependent data will enhance robustness and applicability. Additionally, integrating deep learning architectures with the MDL-based penalty could improve scalability and performance in ultra-high-dimensional networks, such as brain connectomes or genomic datasets. Investigating online or incremental algorithms for real-time network inference also represents a promising direction.
AI Executive Summary
In the era of big data, understanding complex systems through network models has become indispensable across scientific disciplines. However, high-dimensional data—where the number of variables far exceeds the number of observations—poses significant challenges for accurate network reconstruction. Traditional sparse methods like Lasso, AIC, and BIC often produce excessive false positives, leading to unreliable network structures. This paper addresses these issues by proposing a novel neighborhood selection approach that combines ridge regression with the principle of minimum description length (MDL).
The core insight stems from recent developments in machine learning, particularly the double descent phenomenon, which reveals that overparameterized models can surprisingly generalize well despite their complexity. Leveraging this, the authors analyze how the ridge parameter influences the mean squared error (MSE) in high-dimensional regimes, demonstrating that appropriate regularization can suppress overfitting and false positives. They then incorporate MDL as a penalty for model complexity, effectively controlling the volume of the model space and ensuring that the selected neighborhoods are either correct or conservative.
Through extensive simulations involving networks of up to 320 nodes, the proposed method consistently outperforms traditional techniques, achieving over 95% accuracy with false positive rates below 5%. These results hold even when the true model is nonlinear, showcasing the robustness of the approach. The theoretical analysis confirms that in high-dimensional settings, the MDL penalty accounts for the large model space volume, guiding the selection toward true or smaller neighborhoods.
This research significantly advances the field of high-dimensional network inference. By bridging classical statistical methods with modern machine learning insights, it offers a reliable, scalable, and theoretically grounded tool for variable selection in complex systems. Its implications extend to neuroscience, genomics, social sciences, and beyond, where accurate network reconstruction is crucial for understanding underlying mechanisms.
Despite its strengths, the method faces limitations such as dependence on ridge parameter tuning and assumptions of Gaussianity. Future directions include developing adaptive tuning procedures, extending the framework to non-Gaussian data, and improving computational efficiency for ultra-large networks. Overall, this work paves the way for more robust and interpretable high-dimensional network analysis, aligning statistical rigor with practical utility.
Deep Dive
Abstract
To avoid missing important variables and their connections in networks, more and more variables are included in network analysis. Here we show that in a setting with many more parameters than observations (high-dimensional) it is possible to get a conservative (i.e., low false positive rate) estimate of the neighbourhood for each node (which connections are in the network). A neighbourhood is often estimated with a linear model, and this leads to two interesting cases: (i) If the true model is linear, then neighbourhood selection work reasonably well, and (ii) if the true model is nonlinear, then neighbourhood selection requires a penalty for the high dimensions. Here we show the impact of the ridge parameter on the mean squared error, and how this leads to low test variance and hence to neighbourhoods with large numbers of edges. We connect these insights with results from machine learning, where the so-called double descent (when more parameters are included than observations, the mean squared error goes down a second time) has put the traditional view on model selection upside down. Essentially, for adequate neighbourhood selection in models with a large number of parameters, the volume of the model space needs to be included in the penalty. Most neighbourhood selection methods (e.g., Lasso, AIC, BIC) lead to spurious edges (high false positive rate), but we prove that in the high-dimensional setting, minimum description length leads to correct neighbourhood selection or smaller (low false positive rates) in both cases when either the model is correctly or incorrectly assumed linear
References (20)
Deep learning: a statistical viewpoint
P. Bartlett, A. Montanari, A. Rakhlin
Inconsistency of Bayesian Inference for Misspecified Linear Models, and a Proposal for Repairing It
P. Grunwald, T. V. Ommen
High-dimensional graphs and variable selection with the Lasso
N. Meinshausen, Peter Buhlmann
The Elements of Statistical Learning
E. Ziegel
Graphical Models
Michael I. Jordan
Ridge Regression: Biased Estimation for Nonorthogonal Problems
A. E. Hoerl, R. Kennard
Double Descent Risk and Volume Saturation Effects: A Geometric Perspective.
Prasad Cheema, M. Sugiyama
Network Inference With the Lasso
L. Waldorp, Jonas M. B. Haslbeck
Benign overfitting in linear regression
P. Bartlett, Philip M. Long, G. Lugosi et al.
Minimum Description Length Principle.
J. Rissanen
Statistical significance in high-dimensional linear models
Peter Buhlmann
SURPRISES IN HIGH-DIMENSIONAL RIDGELESS LEAST SQUARES INTERPOLATION
T. Hastie, A. Montanari, Saharon Rosset et al.
On the distribution of penalized maximum likelihood estimators: The LASSO, SCAD, and thresholding
B. Pötscher, H. Leeb
A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning
Yehuda Dar, Vidya Muthukumar, Richard Baraniuk
How Biased is the Apparent Error Rate of a Prediction Rule
B. Efron
Regression Shrinkage and Selection via the Lasso
R. Tibshirani
On Information and Sufficiency
Huaiyu Zhu
Elements of Information Theory
G. Vitetta, Desmond P. Taylor, G. Colavolpe et al.
Probability Essentials
L. Shepp
Asymptotic Theory of Statistics and Probability
A. Dasgupta