When building statistical models, a fundamental challenge is deciding how complex a model should be. If a model is too simple, it underfits, missing the true underlying patterns. If it is too complex, it overfits, treating random noise as genuine signal.
To strike the right balance, researchers traditionally rely on classical information criteria like the Akaike Information Criterion (AIC), the Bayesian Information Criterion (BIC), or the Minimum Description Length (MDL). These tools score models by balancing their goodness-of-fit against a penalty based on the number of parameters.
However, as Yoshua Bengio and Dale Schuurmans point out in their editorial overview, these foundational criteria are derived from asymptotic theory. They assume that the volume of training data is effectively infinite ($N \to \infty$). In real-world scenarios where data is scarce or the number of parameters is large relative to the sample size, these asymptotic assumptions collapse, leading to severe selection biases.
Why Asymptotic Approximations Fail
To understand why classical criteria break down in small-sample regimes, we have to look at what asymptotic derivations leave behind.
When deriving metrics like the BIC, mathematicians use a Taylor expansion (specifically, the Laplace approximation) to estimate the marginal likelihood of the data. As the sample size $N$ grows large, higher-order terms and constant factors become negligible compared to the dominant terms that scale with $N$. Consequently, these constants are dropped from the final formula.
In small datasets, however, these "negligible" terms contain critical information:
- Omitted Posterior Covariance: Sridevi Parise and Max Welling demonstrate in their work on Markov Random Fields that standard BIC fails on small datasets because it omits constant terms that do not scale with the number of observations. These ignored terms contain vital information about the model's posterior covariance, which is essential for accurate structural identification when data is scarce.
- Non-linear Likelihood Curvature: Standard criteria typically apply a linear complexity penalty. However, Pekka Marttinen and Jukka Corander show that linear penalties fail to account for the non-linear curvature of the log-likelihood in small-sample regimes, leading to poor predictive performance or overfitting in graphical models (Bayesian learning of graphical vector autoregressions with unequal lag-lengths).
- Parameter Variance Shifts: Information criteria often act as first-order approximations of leave-one-out cross-validation error. Ayaka Sakata demonstrates that this approximation fails when the ratio of samples to parameters is small because it fails to capture how the variance of a parameter estimate shifts when a single observation is removed from the training set (Prediction Errors for Penalized Regressions based on Generalized Approximate Message Passing).
The Dual Faces of Selection Bias
When these asymptotic assumptions fail, the resulting mathematical errors manifest as systematic selection biases. Depending on the structure of the model and the specific criterion used, this bias can swing in two opposite directions.
Catastrophic Overfitting
In many regression and structural learning tasks, asymptotic formulas drastically underestimate the true generalization error. Olivier Chapelle et al. observe that when the number of parameters is large relative to the number of observations, standard formulas fail to properly penalize complexity, leading to the selection of overly complex models and catastrophic overfitting (Model Selection for Small Sample Regression).
Systematic Underfitting
Conversely, fixed complexity penalties can become overly conservative when data is scarce. Yuhong Guo and Russell Greiner show that in small-sample regimes, fixed penalty terms can dominate the likelihood, causing the selection process to favor overly simplistic models that ignore valid data dependencies (Discriminative Model Selection for Belief Net Structures). Similarly, Kohei Hayashi et al. note that asymptotic approximations can underestimate the true number of latent components in mixture models because the theoretical assumptions require larger datasets to validate complex hidden structures (Rebuilding Factorized Information Criterion: Asymptotically Accurate Marginal Likelihood).
Mechanisms for Finite-Sample Correction
To overcome these limitations, researchers have developed non-asymptotic model selection frameworks that remain mathematically rigorous in low-data regimes. Three primary mechanisms drive these modern solutions.
1. Exact Finite-Sample Criteria
Instead of relying on Taylor series approximations that drop lower-order terms, some approaches derive the exact marginal likelihood for specific model classes. For instance, Marco Corneli et al. derive an exact finite-sample model selection criterion for longitudinal data mixtures (A Bayesian approach for clustering and exact finite-sample model selection in longitudinal data mixtures). By avoiding asymptotic approximations entirely, their method prevents the over-estimation of cluster counts, distinguishing true group structures from random noise even when data is scarce.
2. Leveraging Data Geometry and Noise Characteristics
Rather than counting parameters blindly, finite-sample criteria can inspect the geometric properties of the data itself. In Model Selection for Small Sample Regression, the authors develop a penalization method that looks directly at the eigenvalues of the input covariance matrix to accurately estimate generalization error when data is limited.
In a similar vein, Masashi Sugiyama and Hidemitsu Ogawa introduce the Subspace Information Criterion (SIC) in their paper on subspace models. By leveraging functional analysis and explicit noise characteristics rather than large-sample approximations, SIC manages to maintain an accurate estimate of generalization error in highly constrained data environments.
3. Data-Driven Prior Distribution Tuning
Another way to bypass asymptotic assumptions is to let the data define the complexity constraints dynamically. Heiga Zen et al. demonstrate this in speech recognition models by using cross-validation to automatically inform the model's starting prior distributions (Bayesian context clustering using cross valid prior distribution for HMM-based speech recognition). By substituting rigid asymptotic penalties with data-driven priors, the model naturally adapts its complexity control to the scale of the available training set.
Key Foundational Work
Three Approaches to Probability Model Selection (1994) — contributed 1 concept elements to this direction.
Examples of learning curves from a modified VC-formalism (1995) — contributed 1 concept elements to this direction.