  Despite numerous years of research into the merits and trade-offs of various
model selection criteria, obtaining robust results that elucidate the behavior
of cross-validation remains a challenging endeavor. In this paper, we highlight
the inherent limitations of cross-validation when employed to discern the
structure of a Gaussian graphical model. We provide finite-sample bounds on the
probability that the Lasso estimator for the neighborhood of a node within a
Gaussian graphical model, optimized using a prediction oracle, misidentifies
the neighborhood. Our results pertain to both undirected and directed acyclic
graphs, encompassing general, sparse covariance structures. To support our
theoretical findings, we conduct an empirical investigation of this
inconsistency by contrasting our outcomes with other commonly used information
criteria through an extensive simulation study. Given that many algorithms
designed to learn the structure of graphical models require hyperparameter
selection, the precise calibration of this hyperparameter is paramount for
accurately estimating the inherent structure. Consequently, our observations
shed light on this widely recognized practical challenge.
