# A Rigorous, Tractable Measure of Model Complexity

arXiv: https://arxiv.org/abs/2605.21167 · HTML: https://mlsanity.com/paper/2605.21167/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 42 of its 60 references that are in the map.
- First posted on arXiv 20 May 2026.

## Builds on (most cited first, 30 of 42)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Deep Double Descent: Where Bigger Models and More Data Hurt](https://mlsanity.com/paper/1912.02292/) (2019)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [On the Expressive Power of Deep Neural Networks](https://mlsanity.com/paper/1606.05336/) (2016)
- [Complexity of Linear Regions in Deep Networks](https://mlsanity.com/paper/1901.09021/) (2019)
- [Rademacher Complexity for Adversarially Robust Generalization](https://mlsanity.com/paper/1810.11914/) (2018)
- [Fisher-Rao Metric, Geometry, and Complexity of Neural Networks](https://mlsanity.com/paper/1711.01530/) (2017)
- [Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate](https://mlsanity.com/paper/1806.05161/) (2018)
- [Scaling description of generalization with number of parameters in deep learning](https://mlsanity.com/paper/1901.01608/) (2019)
- [A Model of Double Descent for High-dimensional Binary Linear Classification](https://mlsanity.com/paper/1911.05822/) (2019)
- [High-dimensional analysis of double descent for linear regression with random projections](https://mlsanity.com/paper/2303.01372/) (2023)
- [Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning](https://mlsanity.com/paper/2103.13883/) (2021)
- [Kernel regression in high dimensions: Refined analysis beyond double descent](https://mlsanity.com/paper/2010.02681/) (2020)
- [A U-turn on Double Descent: Rethinking Parameter Counting in Statistical Learning](https://mlsanity.com/paper/2310.18988/) (2023)
- [Nearly Optimal VC-Dimension and Pseudo-Dimension Bounds for Deep Neural Network Derivatives](https://mlsanity.com/paper/2305.08466/) (2023)
- [Improved Bounds on Neural Complexity for Representing Piecewise Linear Functions](https://mlsanity.com/paper/2210.07236/) (2022)
- [The Complexity Dynamics of Grokking](https://mlsanity.com/paper/2412.09810/) (2024)
- [Adversarial Rademacher Complexity of Deep Neural Networks](https://mlsanity.com/paper/2211.14966/) (2022)
- [On Rademacher Complexity-based Generalization Bounds for Deep Learning](https://mlsanity.com/paper/2208.04284/) (2022)
- [On the Expected Complexity of Maxout Networks](https://mlsanity.com/paper/2107.00379/) (2021)
- [Why do Random Forests Work? Understanding Tree Ensembles as Self-Regularizing Adaptive Smoothers](https://mlsanity.com/paper/2402.01502/) (2024)
- [Degrees of Freedom in Deep Neural Networks](https://mlsanity.com/paper/1603.09260/) (2016)
- [Double descent in the condition number](https://mlsanity.com/paper/1912.06190/) (2019)

## Abstract (arXiv)

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.