Cross-Validation for Structural Model Selection

Cross-validation is widely used in modern machine learning for model selection and hyperpa- rameter tuning. Its appeal comes from its model-agnostic nature: it selects models through held-out predictive performance rather than through problem-specific assumptions. In struc- ture learning and related structural model selection problems, however, model selection has a second consequence. The selected model may encode a graph, a sparsity pattern, a set of active variables, a representation, an architecture, or another structural object. This thesis asks when such a prediction-based selection principle can be trusted for structural model selection, and what must change when it cannot.

We develop this question in three steps. First, in Gaussian graphical model selection, we show that cross-validation can fail to be model-selection consistent even when consistent graph recovery is statistically achievable, revealing a fundamental mismatch between predic- tive validation loss and exact structural recovery. Second, we show that this negative result does not render validation information useless: by using cross-validation-type quantities as scalable signals rather than as the final validation-loss minimizer, we develop approximate cross-validation methods for consistent and efficient graph recovery in general sparse graphi- cal models. Finally, we extend cross-validation-based risk optimal selection to nonparametric and nonlinear deep learning settings, where structural choices are often implicit and exact retraining is infeasible. We develop a predictor-corrector influence function (PCIF) method, a curvature-aware proxy for fold deletion for cross-validation selection, and show that it preserves the cross-validation-style risk optimal model selection under suitable conditions.

Together, these results reposition cross-validation in structure learning and related struc- tural model selection problems. It is not automatically a consistent structural selector, but its validation principle can be diagnosed, redesigned, and computationally extended for classical and modern learning systems.