PaperlayerView exact revision on arXiv

Source-linked AI summary

High-dimensional networks and mean squared error for possibly misspecified models

Lourens Waldorp

arXiv:2608.13171v1stat.MLcs.LG

TL;DR

High-dimensional network analysis makes nodewise neighbourhood selection vulnerable to overfitting and spurious edges because the parameter space can be much larger than the data. The paper analyzes ridge-based MSE and proves that minimum description length selects the correct or a smaller neighbourhood with high probability under both linear and nonlinear edge relations.

  • Problem

    High-dimensional nodewise selection can overfit because vast parameter spaces produce near-zero training error and graphs with spurious edges.

  • Method

    The paper analyzes ridge-based MSE and bias–variance effects, then uses minimum description length to penalize model-space complexity and tests the theory with simulations.

  • Results

    MDL achieves correct or smaller neighbourhood selection with high probability for both linear and nonlinear edge relations, while AIC and Lasso select overly large neighbourhoods.

  • Takeaways & Limitations

    Accounting for the volume of the parameter space is central to controlling false positives in high-dimensional neighbourhood selection.

  • Takeaways & Limitations

    Under nonlinear misspecification, residual variance may be heterogeneous and the best Kullback–Leibler model may lie outside the model space.

Abstract

from arXiv · show

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

1 Introduction

The paper studies neighbourhood selection when networks are overparameterised, arguing that low high-dimensional MSE can cause overfitting and spurious edges. It proposes accounting for model-space geometry through penalties such as minimum description length to obtain correct or smaller neighbourhoods.

  • Motivation: With 20 nodes, networks already contain 190 edge parameters, while classical estimation would require about 1000 observations for reliable estimation.This motivates methods for settings with more parameters than observations.
  • Background: Lasso and ridge enable estimation in high-dimensional settings, with lasso additionally selecting edges but lacking a closed-form solution.The paper builds on these estimators while focusing on high-dimensional ridge behaviour.
  • Method: The framework uses local nodewise regression, treating each node as a response and identifying its non-zero neighbours from all remaining nodes.Neighbourhood selection is therefore performed separately for each node.
  • High-dimensional MSE: MSE can remain well behaved after interpolation in high dimensions, and its behaviour depends directly on the ridge parameter and constrained parameter space.The introduction motivates later bias–variance analysis under both correct specification and model misspecification.
  • Contribution: High-dimensional overfitting can produce unexpectedly low MSE, making AIC inadequate because it mostly selects too many edges; minimum description length yields correct or smaller neighbourhoods.The analysis connects high-dimensional ridge estimation, MSE, and model-space geometry to neighbourhood selection.

2 Estimation in the Gaussian graphical model

Gaussian graphical models encode conditional dependence through partial correlations, which can be estimated by nodewise regressions; when predictors outnumber observations, ridge regularization provides a unique coefficient estimate. High-dimensional neighbourhood selection must also penalize the large model space to target low false-positive rates.

  • Gaussian graphical models: A Gaussian graphical model represents variables as nodes and conditional dependencies as edges, with zero partial correlation indicating conditional independence and no edge.
  • Nodewise selection: Nodewise selection reduces graph estimation to regressions, where nonzero coefficients identify neighbouring nodes because regression coefficients are proportional to partial covariances [Meinshausen and B¨uhlmann, 2006; B¨uhlmann et al., 2014; Maathuis et al., 2018; Waldorp and Marsman, 2021].
  • High-dimensional estimation: When p > n, XᵀX is rank-deficient, so least squares has no unique solution; ordinary least squares otherwise requires p < n, full rank, and no collinearity.
  • Regularization: Ridge estimation imposes a squared-parameter constraint and uses α > 0 to obtain a unique, biased estimate; α can be selected by k-fold cross-validation.
  • False-positive control: Because a few spurious edges per node produce many false positives in large graphs, the objective is P(Ŝ ⊆ S) = 1 − ϵ rather than merely P(S ⊂ Ŝ) = 1 − ϵ.
  • False-positive control: Low false-positive neighbourhood selection in high dimensions requires penalizing the large space of possible models, which motivates incorporating minimum description length into selection [Dwivedi et al., 2020; Cheema and Sugiyama, 2020].

3 Mean-squared error and the bias-variance trade-off

For nodewise network selection, mean-squared error reflects a bias–variance trade-off that changes under overparameterization: misspecified models can generalize best when heavily overparameterized, risking spurious edges. Therefore, correct or smaller neighbourhoods require strong ridge regularization or an additional high-dimensional penalty.

  • Classical bias–variance trade-off: When the linear model is correct, test MSE is minimized near the true model at p/n ≈0.15, where squared bias and variance jointly determine prediction error.The regression uses training data for estimation and a held-out test set for MSE evaluation.
  • Double descent: After interpolation, both bias and variance can decrease, allowing overparameterized models to generalize despite fitting too many non-zero coefficients, a phenomenon called double descent.This apparent paradox arises because decreasing variance indicates that the overparameterized model captures regularities in other datasets rather than only noise.
  • Implications of misspecification: For approximately correct linear models, overparameterization preserves a global test-MSE minimum at the correct model, whereas misspecification can shift it to a largely overparameterized incorrect model.These results assume normally distributed variables and independent identically distributed predictors.
  • Implications for neighbourhood selection: In nodewise selection, misspecified models can therefore select too many edges because their MSE is lowest at high dimensionality.Nodewise selection reduces Gaussian graphical-model estimation to separate regressions, so these MSE effects apply to neighbourhood estimation.
  • Implications for neighbourhood selection: Obtaining the correct or smaller neighbourhood requires strongly increasing the ridge parameter or using a separate penalty that counteracts the low MSE of high-dimensional misspecified models.The passage questions whether cross-validation alone can reliably choose a sufficiently strong ridge parameter.

4 Mean-squared error decomposition in bias and variance

The section decomposes test MSE into squared bias and variance, showing how ridge regularization can stabilize high-dimensional prediction while trading reduced variance against potentially increased bias. It further argues that, under misspecification, increasing model dimension can reduce mismatch and support correct or smaller neighbourhoods with minimum description length.

  • Bias–variance decomposition: Test excess risk decomposes into squared bias and variance, framing model selection as minimizing their trade-off.The classical view is that reducing bias increases variance and vice versa.
  • Ridge regularization: Ridge regularization introduces non-zero bias, and increasing α can increase squared test bias even while reducing variance.This demonstrates the opposing effects of regularization on the two components of test MSE.
  • Ridge regularization: Increasing the ridge parameter α lowers test variance and can keep prediction stable as more predictors are added, especially when additional eigenvalue contributions are small.Thus, increasing dimensionality does not necessarily inflate variance when ridge regularization stabilizes it.
  • Ridge regularization: Cross-validation removes the apparent ridge test-MSE peak caused by α = 0.0001, while lasso retains generally larger MSE than ridge.The comparison is shown in Figure H.1, which uses a carefully selected ridge parameter.
  • High-dimensional control: High-dimensional variance can be controlled either by increasing α or by constraining ||β||2, both of which limit total signal or model complexity.The latter constraint uses ||β||2 ≤ c, linking regularization to the volume of the model space.
  • Misspecified models: Under nonlinear misspecification, increasing p/n decreases mismatch, and minimum description length can yield the correct or a smaller neighbourhood in high dimensions.The misspecification bound follows from the assumed nonlinear model and a Cauchy–Schwarz argument.

5 Nodewise selection in high dimensions

In high-dimensional nodewise selection, the expanding parameter space drives near-zero training error and complicates model choice. MDL counters this complexity through a parameter-space volume penalty and yields vanishing false-positive probability, including for possibly nonlinear data-generating processes.

  • High-dimensional selection: In high dimensions, near-zero training error arises because the parameter space is sufficiently large to account for nearly all observations, making nodewise selection problematic.The parameter-space volume grows with dimension and can dominate model selection.
  • Method comparison: The proposed high-dimensional penalty counteracts the large number of possible neighbourhood edges, unlike the comparison methods AIC, BIC, Lasso, and an alternative MDL version examined in the paper.The paper states that MDL leads to no false-positive edges with high probability.
  • MDL penalty: MDL penalizes model complexity through the encoded model’s parameter-space volume, whose logarithm increases with dimension and can improve test-set generalisation by reducing variance.This volume term is derived using ridge regression when X⊤X is singular for p > n.
  • Model misspecification: The MDL formulation assumes a correct linear model for its volume calculation, but the proposition extends its false-positive control to possibly nonlinear data-generating processes.The paper notes that misspecification can make the model space non-convex and the best approximation unavailable within it.
  • Proposition 5.1: MDL yields a false-positive probability tending to 0 as p increases, with probability at least 1 − d/p exp(−(p − d)) under Proposition 5.1’s conditions.The result assumes fixed n, p > d, S ⊂ J, and Eσ̂²_J > γ for some γ > 0; it establishes Ŝ ⊆ S.
  • Related formulations: MDL-S omits the integral term and is equivalent to the Bayesian information criterion (BIC).This approximation corresponds to the complexity form of MDL without the integral term.

6 Simulations

Simulations show that high-dimensional misspecification can make large neighbourhoods achieve lower test MSE, undermining standard selection, whereas MDL maintains low or zero false-positive rates across dimensions. Under misspecification, all methods select the correct neighbourhood less often, but MDL avoids overfitting.

  • Simulation design: The simulations use n = 40 observations, graph sizes from p = 3 to p = 320, five true neighbours per node, and an 80/20 training-test split.Data come from a Gaussian graphical model with edge coefficient 1; nodewise coefficients are estimated by ridge regression.
  • MSE: For misspecified models, test MSE falls below the correct-neighbourhood MSE at large dimensions, potentially favouring neighbourhoods with many parameters.The correct model has p = 5 and MSE 0.0877, whereas p/n = 10 has MSE 0.0844; for the correctly specified model, the global minimum remains at p = 5.
  • Neighbourhood selection: With pmax = 320, AIC and Lasso show exacerbated overfit, whereas MDL, MDL-opt, MDL-S, and AIC-CV remain accurate with low overfit.MDL has no overfit in these simulations, attributed to its large penalty for using a high-dimensional model space.
  • Neighbourhood selection: When the model is misspecified, MDL alone avoids selecting too many edges, although every method’s probability of selecting the correct neighbourhood decreases.The misspecified data-generating process uses a logistic or sigmoid conditional mean while estimation remains linear.
  • False-positive rates: MDL maintains zero false-positive rates across model dimensions, unlike most other methods, when the linear model is correctly specified.Figure 6(a) evaluates dimensions with p/n from 0.1 to 10; MDL remains at 0 throughout.

7 Conclusion and discussion · Appendix · A Gaussian graphical model

In high-dimensional Gaussian graphical models, ridge regression enables nodewise neighbourhood estimation when ordinary least squares fails, while MDL controls false positives under both linear and nonlinear relations. The appendix establishes the GGM correspondence between conditional independence, inverse covariance, partial correlations, and nodewise regression coefficients.

  • 7 Conclusion and discussion: Ridge regression resolves the failure of least-squares estimation when nodes outnumber observations, producing a biased but closed-form estimator whose MSE depends on the ridge parameter.When edge relations are linear, MSE is lowest at the correct neighbourhood; under misspecification, an additional nonlinear-to-linear misspecification term contributes to MSE.
  • 7 Conclusion and discussion: The ridge parameter can be interpreted as the inverse signal-to-noise ratio, so low-signal-to-noise settings require a larger ridge penalty.
  • 7 Conclusion and discussion: MDL achieves correct or smaller neighbourhoods with high probability in high-dimensional settings, for both linear and nonlinear edge relations, by accounting for parameter-space volume.This counters the low MSE that can otherwise arise when dimensionality is high.
  • 7 Conclusion and discussion: The MDL low-false-positive result extends beyond graphical modelling to regression settings when conditional-mean misspecification is bounded and residual variance is bounded away from 0.
  • A Gaussian graphical model: A Gaussian graphical model represents jointly Gaussian variables whose edges encode conditional dependence given all remaining variables, with the distribution determined by means and covariances.
  • A Gaussian graphical model: For multivariate normal distributions, a zero inverse-covariance element implies conditional independence, making an edge present exactly when the corresponding partial correlation is non-zero.This conditional-independence correspondence is specific to the multivariate normal distribution.
  • A Gaussian graphical model: Nodewise regression recovers the same edge condition because βij = 0 if and only if θij = 0, after which edges can be selected using either the and-rule or the or-rule.The and-rule requires both directional coefficients to be non-zero, whereas the or-rule requires either one to be non-zero.

B Excess risk and mean squared error (Section 4)

Section 4 decomposes excess risk, equivalently test mean squared error, into squared bias and variance. Under a correct linear model with isotropic covariate covariance, it derives ridge-specific expressions for both components using the eigenvalues of the regularized design matrix.

  • B Excess risk and mean squared error: Excess risk, or test mean squared error, decomposes into squared bias B(J) and variance V(J).The expectation is conditional on the training data X.
  • B Excess risk and mean squared error: For the ridge estimator, the squared-bias expression is derived under a correct linear model and isotropic covariate covariance Σ = σ^2_ξI.The regularized design matrix has eigenvalues λ_j + α, which determine the corresponding inverse-square terms.
  • B Excess risk and mean squared error: Under the same assumptions, the ridge variance expression depends on the eigenvalues λ_j + α of the regularized design matrix and the residual variance σ^2_e.The derivation uses that the residuals have variance σ^2_eI.

B.1 Model misspecification

This section defines misspecification as using a linear model when the true distribution has a nonlinear mean, and characterizes the resulting high-dimensional prediction risk. Under misspecification, the risk decomposes into bias, variance, and a misspecification term, with bounds requiring controlled approximation error.

  • Definition: Misspecification occurs when the true distribution lies outside the considered linear model class, such as when a nonlinear conditional mean is optimized using x^Tβ.The fitted linear model can be viewed as the member of the linear class closest to the true distribution in Kullback–Leibler terms.
  • Risk under misspecification: For p > n, the misspecified-model risk is decomposed as R_f(J) = B_f(J) + V_f(J) + M_f(J).The decomposition separates bias, variance, and misspecification contributions to prediction risk.
  • Risk under misspecification: Unlike the correctly specified case, misspecification leaves nonvanishing cross-product terms in the excess-risk calculation.The proof retains these terms while recovering the bias and variance components without assuming model correctness.
  • Misspecification bound: A misspecification bound assumes additive mean-zero noise with finite variance σ2 and approximation error bounded in probability by K.The estimator uses a linear predictor with |J| = p > n to approximate the nonlinear target function.

C High-dimensional space

In high-dimensional isotropic Gaussian spaces, most observations lie near radius √p rather than near the origin. Correspondingly, unit-ball volume collapses with dimension, while the fraction of points near the outer surface approaches 1 exponentially fast.

  • Most draws from a p-dimensional isotropic Gaussian concentrate near radius √p with high probability as p becomes large.This follows from the geometry of isotropic distributions in high dimensions.
  • The volume of a p-dimensional unit ball becomes close to 0 already around p = 20.
  • For small radii or bounds such as t = 1 or 2, a high probability of lying near the origin is possible only in low dimensions.
  • The fraction of observations near the surface of the p-dimensional ball increases exponentially toward 1, reaching this behavior by about p = 30.The figure measures the fraction outside an inner ball of radius 0.95r.

D Geometry and metric entropy of Gaussian process (Section 5) · E Akaike information criterion · F Minimum description length: optimised

These sections connect ridge regularization to signal-to-noise geometry, showing how tuning α or constraining parameter volume reduces test variance, while defining AIC and an effective-degrees-of-freedom MDL for high-dimensional models. The optimized MDL variant combines this high-dimensional correction with an optimally selected α and a Bayesian prior term.

  • D Geometry and metric entropy of Gaussian process (Section 5): When p > n, the minimum-norm estimator provides the small-α limit of ridge regression, connecting interpolation solutions to the volume-ratio formulation.The minimum-norm solution is obtained at the smallest α making the augmented inverse possible.
  • D Geometry and metric entropy of Gaussian process (Section 5): The signal-to-noise volume ratio for high-dimensional linear models can be expressed through the ridge estimator, with α interpreted as the inverse signal-to-noise ratio.This links geometric model volume directly to ridge regularization.
  • D Geometry and metric entropy of Gaussian process (Section 5): Increasing α reduces test variance and can remove the interpolation peak, indicating that the peak may result from suboptimal tuning rather than an unavoidable effect.The supplied passage attributes disappearance of the peak to careful α selection.
  • D Geometry and metric entropy of Gaussian process (Section 5): Constraining ||β||2 ≤ c reduces model volume and SNR, increases α, and thereby lowers test variance; increasing α directly has the same regularizing effect.Both approaches constrain total signal, either directly through α or indirectly through the ridge constraint.
  • E Akaike information criterion: AIC selects among models by estimating expected out-of-sample log-likelihood, equivalently minimizing Kullback–Leibler divergence after correcting the biased plug-in likelihood estimate.For Gaussian GGMs, the criterion is formed using the ridge estimate and the model’s parameter count.
  • E Akaike information criterion: The standard AIC uses a fixed data-independent ridge parameter α, whereas AIC-CV selects α by k-fold cross-validation.Both criteria plug a ridge estimate into the Gaussian-model formulation.
  • F Minimum description length: optimised: MDL-opt adapts description length to n < p by combining effective degrees of freedom with an α optimized for those degrees of freedom.Its objective retains data-given-model and model-code lengths while adding a Bayesian prior term for β.

G MDL leads to underfit in high-dimensional settings · H Simulation details

The proposition shows that, as dimensionality p increases under its stated conditions, MDL selects a support contained in the true support with vanishing false-positive probability. Simulations compare correctly linear and sigmoid misspecified models while varying p far beyond the fixed sample size.

  • G MDL leads to underfit in high-dimensional settings: As p increases, MDL selects ˆS ⊆ S with probability tending to one, so the false-positive probability tends to zero.This is the proposition’s high-dimensional underfitting guarantee for possibly nonlinear data-generating processes tested with linear models.
  • G MDL leads to underfit in high-dimensional settings: The proof combines bounds for MDL’s empirical-variance, model-complexity, and parameter-description components.The argument uses monotonicity, Jensen’s inequality, Markov’s inequality, Stirling’s approximation, and a Euclidean-ball approximation.
  • G MDL leads to underfit in high-dimensional settings: The bound’s dominant final term vanishes as p increases, driving the proposition’s support-containment result.The first term remains bounded by K/γ, while the last term dominates and converges to zero.
  • H Simulation details: The simulation compares a true linear model f(X) = Xβ with a misspecified sigmoid model f(X) = 1/(1 + exp(Xβ)).Both settings keep d = 5 nonzero coefficients fixed and normalize ||β||2 = 1.
  • H Simulation details: The simulations use n = 40 observations, SNR 2, and noise variance 0.5, with 80% training and 20% testing.This yields ntrain = 32 and ntest = 8.
  • H Simulation details: The parameter count varies from p = 3 to p = 320, producing training ratios p/n from 0.09 to 10.The true model dimension remains fixed at d = 5 while the number of parameters expands beyond the training sample size.
  • H Simulation details: Ridge estimation uses either α = 0.5 or 10-fold cross-validation, while Lasso selects α by 10-fold cross-validation using glmnet.For ridge cross-validation, the α with the smallest MSE is selected.

I Residuals in training and test samples

With 64 predictors but only 5 non-zero coefficients, the model interpolates the training data exactly at the interpolation point. Despite this, test residual variance remains relatively small because ridge regularization hides noise in unimportant predictor directions.

  • Training residuals: At p = n, the 64-predictor model exactly fits every training observation, producing zero training residuals despite only 5 true non-zero coefficients.This is the interpolation behavior shown in the training-residual panel.
  • Test residuals: The ridge parameter keeps predictor noise in unimportant directions, limiting test-residual variance even when all 64 predictors are included.The model uses the ridge estimate for the full 64-predictor model.
  • Test residuals: Test residuals remain relatively small beyond interpolation, showing that exact training fit does not necessarily cause variance to explode.The test-residual panel shows some variance, but not a large increase.
Loading 2608.13171v1…