A Rigorous, Tractable Measure of Model Complexity
Authors: Oskar Allerbo, Thomas B. Sch"on
Summary
arXiv:2605. 21167v1 Announce Type: new Abstract: An accurate assessment of a model's complexity is crucial for topics such as interpretation, generalization, and model selection.
Relevance
Read next because A Rigorous, Tractable Measure of Model Complexity overlaps with clean result "The marker is a representational handle, not a behavioural one — sharing it between a villain persona and the assistant transfers no misalignment (HIGH confidence)", experiment "Factor screen for marker implantation + leakage (2^5: system-prompt length, answer-format length, persona-presence, on-policy, marker-only-loss)", experiment "#351 follow-up: broader-vocab position-0 sweep at T=1.0 + position-1 suffix isolation". Matching terms: rate, length, model. Source: arxiv stat.ML (Machine Learning).
Abstract
arXiv:2605.21167v1 Announce Type: new Abstract: An accurate assessment of a model's complexity is crucial for topics such as interpretation, generalization, and model selection. However, most 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 the model gradients across inputs. It is thus well-defined for any parametric model, but also for kernel-based non-parametric models. We prove that our measure of complexity generalizes model-specific complexity measures such as polynomial degree (for polynomial regression), kernel length scale (for Mat'ern 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.