mlsanityData to 14 Oct 2026

A Rigorous, Tractable Measure of Model Complexity

arXiv 2605.21167 ↗First posted 20 May 2026stat.ML cs.LGcited by 0

Not on the map. Why?

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.

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

42 of 60 references.

References · 42

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2016Understanding deep learning requires rethinking generalizationcited by 1,674
  3. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 927
  4. 2017Spectrally-normalized margin bounds for neural networkscited by 686
  5. 2019Deep Double Descent: Where Bigger Models and More Data Hurtcited by 672
  6. 2019Benign Overfitting in Linear Regressioncited by 549
  7. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 533
  8. 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 513
  9. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 413
  10. 2014On the Number of Linear Regions of Deep Neural Networkscited by 381
  11. 2016On the Expressive Power of Deep Neural Networkscited by 306
  12. 2019Complexity of Linear Regions in Deep Networkscited by 167
30 more
  1. 2018Rademacher Complexity for Adversarially Robust Generalizationcited by 132
  2. 2017Fisher-Rao Metric, Geometry, and Complexity of Neural Networkscited by 100
  3. 2018Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolatecited by 99
  4. 2019Scaling description of generalization with number of parameters in deep learningcited by 83
  5. 2019A Model of Double Descent for High-dimensional Binary Linear Classificationcited by 81
  6. 2023High-dimensional analysis of double descent for linear regression with random projectionscited by 47
  7. 2021Risk Bounds and Rademacher Complexity in Batch Reinforcement Learningcited by 42
  8. 2020Kernel regression in high dimensions: Refined analysis beyond double descentcited by 39
  9. 2023A U-turn on Double Descent: Rethinking Parameter Counting in Statistical Learningcited by 33
  10. 2023Nearly Optimal VC-Dimension and Pseudo-Dimension Bounds for Deep Neural Network Derivativescited by 30
  11. 2022Improved Bounds on Neural Complexity for Representing Piecewise Linear Functionscited by 26
  12. 2024The Complexity Dynamics of Grokkingcited by 22
  13. 2022Adversarial Rademacher Complexity of Deep Neural Networkscited by 18
  14. 2022On Rademacher Complexity-based Generalization Bounds for Deep Learningcited by 16
  15. 2021On the Expected Complexity of Maxout Networkscited by 15
  16. 2024Why do Random Forests Work? Understanding Tree Ensembles as Self-Regularizing Adaptive Smootherscited by 15
  17. 2016Degrees of Freedom in Deep Neural Networkscited by 14
  18. 2019Double descent in the condition numbercited by 14
  19. 2021On the Generalization Power of Overfitted Two-Layer Neural Tangent Kernel Modelscited by 13
  20. 2017From Fixed-X to Random-X Regression: Bias-Variance Decompositions, Covariance Penalties, and Prediction Error Estimationcited by 12
  21. 2024Deep Learning Through A Telescoping Lens: A Simple Model Provides Empirical Insights On Grokking, Gradient Boosting & Beyondcited by 9
  22. 2024VC Theory for Inventory Policiescited by 8
  23. 2013Effective Degrees of Freedom: A Flawed Metaphorcited by 5
  24. 2024Classical Statistical (In-Sample) Intuitions Don't Generalize Well: A Note on Bias-Variance Tradeoffs, Overfitting and Moving from Fixed to Random Designscited by 5
  25. 2020Robust subgaussian estimation with VC-dimensioncited by 4
  26. 2024Spectral complexity of deep neural networkscited by 3
  27. 2024Revisiting Optimism and Model Complexity in the Wake of Overparameterized Machine Learningcited by 2
  28. 2023Changing the Kernel During Training Leads to Double Descent in Kernel Regressioncited by 1
  29. 2024On the VC dimension of deep group convolutional neural networkscited by 1
  30. 2026Measuring Neural Network Complexity via Effective Degrees of Freedomcited by 1

Built on by

Not cited yet.