A Rigorous, Tractable Measure of Model Complexity

• URL: http://arxiv.org/abs/2605.21167v1
• Date: Wed, 20 May 2026 13:37:38 GMT
• Title: A Rigorous, Tractable Measure of Model Complexity
• Abstract summary: We present a mathematically rigorous yet easy-to-parametric measure of model complexity that is based on the similarities between the model across inputs.<n>We prove that our measure of complexity generalizes model-specific complexity measures such as kernel length scale, number of neighbors, and number of trees.<n>We also use our measure to obtain new insights into the double descent phenomenon for random features, random forests, neural networks, and gradient boosting.
• Score: 12.424687747519037
• License: http://creativecommons.org/licenses/by/4.0/
• 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é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 papers

• Algorithmic Simplification of Neural Networks with Mosaic-of-Motifs [10.533982886956002]
  Methods like pruning, quantization, and knowledge distillation have been used to achieve massive reductions in the number of model parameters.<n>We take up the perspective of algorithmic complexity to explain this behavior.
  arXiv  Detail & Related papers  (2026-02-16T16:30:38Z)
• Estimating Ising Models in Total Variation Distance [23.343281561400033]
  We consider the problem of estimating Ising models over $n$ variables in Total Variation (TV) distance, given $l$ independent samples from the model.<n>Our main contribution is a unified analysis of the Maximum Pseudo-Likelihood Estorimator (MPLE) for two general classes of Ising models.<n>Our results yield optimal or near-time algorithms and optimal or near-time sample complexity guarantees in a variety of settings.
  arXiv  Detail & Related papers  (2025-11-26T03:15:41Z)
• Simplicial Gaussian Models: Representation and Inference [13.687470962704744]
  We propose the simplicial Gaussian model (SGM), which extends Gaussian PGM to simplicial complexes.<n>Our model builds upon discrete Hodge theory and incorporates uncertainty at every topological level through independent random components.<n>Motivated by applications, we focus on the marginal edge-level distribution while treating node- and triangle-level variables as latent.
  arXiv  Detail & Related papers  (2025-10-14T20:51:56Z)
• The Power of Random Features and the Limits of Distribution-Free Gradient Descent [14.742677437485273]
  We study the relationship between gradient-based optimization of parametric models (e.g., neural networks) and optimization of linear combinations of random features.<n>Our main result shows that if a parametric model can be learned using mini-batch gradient descent (bSGD) without making assumptions about the data distribution, then with high probability, the target function can also be approximated.
  arXiv  Detail & Related papers  (2025-05-15T15:39:28Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• Sample Complexity of Kernel-Based Q-Learning [11.32718794195643]
  We propose a non-parametric Q-learning algorithm which finds an $epsilon$-optimal policy in an arbitrarily large scale discounted MDP. To the best of our knowledge, this is the first result showing a finite sample complexity under such a general model.
  arXiv  Detail & Related papers  (2023-02-01T19:46:25Z)
• Test Set Sizing Via Random Matrix Theory [91.3755431537592]
  This paper uses techniques from Random Matrix Theory to find the ideal training-testing data split for a simple linear regression. It defines "ideal" as satisfying the integrity metric, i.e. the empirical model error is the actual measurement noise. This paper is the first to solve for the training and test size for any model in a way that is truly optimal.
  arXiv  Detail & Related papers  (2021-12-11T13:18:33Z)
• Goal-directed Generation of Discrete Structures with Conditional Generative Models [85.51463588099556]
  We introduce a novel approach to directly optimize a reinforcement learning objective, maximizing an expected reward. We test our methodology on two tasks: generating molecules with user-defined properties and identifying short python expressions which evaluate to a given target value.
  arXiv  Detail & Related papers  (2020-10-05T20:03:13Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  One of the main challenges in using deep learning-based methods for simulating physical systems is formulating physics-based data. We propose a novel multi-level graph neural network framework that captures interaction at all ranges with only linear complexity. Experiments confirm our multi-graph network learns discretization-invariant solution operators to PDEs and can be evaluated in linear time.
  arXiv  Detail & Related papers  (2020-06-16T21:56:22Z)
• Measuring Model Complexity of Neural Networks with Curve Activation Functions [100.98319505253797]
  We propose the linear approximation neural network (LANN) to approximate a given deep model with curve activation function. We experimentally explore the training process of neural networks and detect overfitting. We find that the $L1$ and $L2$ regularizations suppress the increase of model complexity.
  arXiv  Detail & Related papers  (2020-06-16T07:38:06Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  We adapt an algorithm of Klivans and Meka based on the method of multiplicative weight updates. The algorithm enjoys a sample complexity bound that is qualitatively similar to others in the literature. It has a low runtime $O(mp2)$ in the case of $m$ samples and $p$ nodes, and can trivially be implemented in an online manner.
  arXiv  Detail & Related papers  (2020-02-20T10:50:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.