Sequential Model Selection in Nested Complexity Hierarchies

This direction is split into other directions: hierarchical model selection. Its last version stays readable and citable here.

Version 1 of 141 papers45 conceptsfrozen 2026-10-04

In machine learning, we are often caught between two fires: underfitting and overfitting. A model that is too simple misses the underlying pattern (high bias), while a model that is too complex treats random noise as a "law of nature" (high variance). This is the "Goldilocks" problem of model selection.

Traditionally, researchers have used cross-validation or information criteria like AIC and BIC to find the right balance. However, a growing body of research suggests a more dynamic approach: Sequential Model Selection. Instead of picking a single model class upfront, these methods organize candidate models into a nested hierarchy of increasing complexity and "switch" to more expressive models only when the data provides statistically significant evidence that the current model is insufficient.

The Hierarchy of Parsimony

The core intuition behind this research direction is the principle of parsimony. As Omer Levy and Shaul Markovitch argue in their work on metaphorical learning, systems should prioritize simpler explanations until they are proven wrong.

To implement this, researchers structure the hypothesis space as a sequence of nested sets: $\mathcal{H}_1 \subset \mathcal{H}_2 \subset \dots \subset \mathcal{H}_n$.

  • $\mathcal{H}_1$ might be a simple linear model or a shallow decision tree.
  • $\mathcal{H}_n$ might be a deep neural network or a high-order Markov chain.

By starting at the bottom of this hierarchy, a learner minimizes the "statistical complexity" it has to manage early on. Joel Veness and Marcus Hutter demonstrate this in Context Tree Switching, where prioritizing shallow trees early in a sequence prevents the model from being overwhelmed by parameter redundancy before enough data has arrived to justify a deeper tree.

The Switching Mechanism: Testing for Misspecification

How does a system know when to move from a simple model to a complex one? The answer lies in sequential hypothesis testing.

In the context of bandits and reinforcement learning, Vidya Muthukumar and Akshay Krishnamurthy propose algorithms that monitor for misspecification. The agent starts by assuming the world is simple (e.g., a multi-armed bandit). It only "switches" to a complex linear contextual model if a statistical test detects that the rewards are significantly dependent on the context in a way the simple model cannot explain.

This same logic applies to time-series analysis. When trying to identify change-points in a sequence, Hui Chen and Changliang Zou use a series of tests to compare models. They increment the number of change-points one by one, stopping the moment a more complex model fails to provide a statistically significant improvement in predictive performance.

Why It Works: Managing the Exploration Budget

The reason this approach is so effective—especially in interactive settings like Reinforcement Learning (RL)—is that complex models are "expensive" to explore.

In Offline RL, Jonathan Lee and Ofir Nachum show that model selection must balance three errors: approximation error, statistical complexity, and dataset coverage. A complex model might have low approximation error, but its high statistical complexity requires a massive amount of data to "fill in" the gaps. By using a nested hierarchy, the learner can stay within the "coverage" of the available data, only increasing complexity when the reduction in approximation error is large enough to outweigh the increased risk of overfitting.

This is essentially a data-adaptive version of Structural Risk Minimization, as explored by Charis J. Stamouli and George J. Pappas. By evaluating function classes (like neural networks of increasing width) sequentially, the system finds the "intrinsic dimension" of the problem—the smallest number of features or parameters needed to explain the data.

Beyond Accuracy: MDL and Representation Learning

This sequential approach isn't just about picking the "best" model; it's also a powerful tool for evaluation. Yazhe Li and Marcus Hutter use Readout Model Switching to evaluate neural network representations.

Instead of just checking if a representation can achieve high accuracy with a linear probe, they look at how quickly it can "switch" from a simple linear model to a complex MLP as more data becomes available. This uses the Minimum Description Length (MDL) principle: a good representation is one that allows the learner to compress the data into a simple model quickly, but also supports more complex models as the evidence grows.

Summary of the Intuition

The research across these 39 papers converges on a single, powerful strategy for machine induction: Don't try to find the perfect model complexity all at once. Instead:

  1. Order your potential models from simplest to most complex.
  2. Start with the simplest model to minimize initial error and exploration costs.
  3. Monitor for misspecification or lack of fit using rigorous statistical tests (like Likelihood Ratios or Chi-square tests on manifolds, as suggested by Yao Xie).
  4. Step up the hierarchy only when the data "demands" it.

This sequential refinement ensures that the model's complexity is always justified by the evidence, leading to more robust generalization and more efficient learning.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_sequential_model_selection_in_nested_com_08eee1a9,
  title = {Sequential Model Selection in Nested Complexity Hierarchies},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequential-model-selection-in-nested-complexity-hierarchies/rdr_08eee1a9c72f4fe7a9afde336a43395f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_sequential_model_selection_in_nested_com_08eee1a9_v1,
  title = {Sequential Model Selection in Nested Complexity Hierarchies},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequential-model-selection-in-nested-complexity-hierarchies/rdr_08eee1a9c72f4fe7a9afde336a43395f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}