A Rigorous, Tractable Measure of Model Complexity
Abstract
An accurate assessment of a model's complexity is crucial for topics such as interpretation, generalization, and model selection. However, existing complexity measures either rely on heuristic assumptions or are computationally prohibitive. In this paper, we present a mathematically rigorous yet easy-to-compute measure of model complexity that is based on the similarities between feature vectors for different inputs. It is thus well-defined for any parametric model (via NTK feature generalization) and for kernel-based non-parametric models (via the induced kernel). We prove that our measure of complexity generalizes model-specific complexity measures, including polynomial degree (for polynomial regression), kernel length scale (for Matérn kernels), number of neighbors (for k-nearest neighbors), number of splits (for decision trees), and number of trees (for random forests). We also use our measure to obtain new insights into the double descent phenomenon for random Fourier features, random forests, neural networks, and gradient boosting.
Related
- A computationally-tractable measure of global sensitivity for sampling-based Bayesian inference
- Sparse Dictionary Learning for Measure-Valued Data via Linearized Optimal Transport: Efficient Algorithms and Sample Complexity
- Learning in Inverse Games: Tractable Training with Probabilistic Guarantees
- Tractable Relaxations of Multivariate Stochastic Dominance via Optimal Transport and CVaR
- Tractable Inference with Kolmogorov-Arnold Networks
BibTeX
@misc{allerbo2026rigorous,
title = {{A Rigorous, Tractable Measure of Model Complexity}},
author = {Oskar Allerbo and Thomas B. Schön},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2605.21167},
eprint = {2605.21167},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.21167},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Rigorous, Tractable Measure of Model Complexity
AU - Oskar Allerbo
AU - Thomas B. Schön
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2605.21167
UR - https://arxiv.org/abs/2605.21167
AB - An accurate assessment of a model's complexity is crucial for topics such as interpretation, generalization, and model selection. However, existing complexity measures either rely on heuristic assumptions or are computationally prohibitive. In this paper, we present a mathematically rigorous yet easy-to-compute measure of model complexity that is based on the similarities between feature vectors for different inputs. It is thus well-defined for any parametric model (via NTK feature generalization) and for kernel-based non-parametric models (via the induced kernel). We prove that our measure of complexity generalizes model-specific complexity measures, including polynomial degree (for polynomial regression), kernel length scale (for Matérn kernels), number of neighbors (for k-nearest neighbors), number of splits (for decision trees), and number of trees (for random forests). We also use our measure to obtain new insights into the double descent phenomenon for random Fourier features, random forests, neural networks, and gradient boosting.
ER -