A Rigorous, Tractable Measure of Model Complexity
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "A Rigorous, Tractable Measure of Model Complexity".
Jane: Here's the gist of the paper. An accurate assessment of a model’s complexity is crucial for topics such as interpretation, generalization, and model selection This paper presents a mathematically rigorous yet easy-to-compute measure of model complexity based on the similarities between the model gradients across inputs It proves that this measure generalizes various model-specific complexity measures such as polynomial degree, kernel length scale, number of neighbors, and number of trees One of the most fundamental properties of a machine learning model is its complexity, with applications across topics such as interpretation, generalization, and model selection Despite its importance, there is no canonical, model-agnostic way to assess a model’s complexity Simple heuristics yield crude estimates while hyperparameter-based approaches do not generalize across model classes The authors introduce a measure based on the alignment between the gradients ∇θˆf(x, θˆ) across inputs x They observe that highly aligned gradients imply less freedom for the model to model data (less complex) than independent gradients Definition and Interpretation of GAC The Gradient Alignment Complexity (GAC), K(ˆf), is defined as 1 minus the expected squared cosine difference between the gradients across inputs x and x' The empirical GAC is given by K(ˆf, X):= 1 − 1/n2 − n · ΣXn i,j=1 i̸=j φ(xi, θˆ)⊤φ(xj, θˆ)∥φ(xi, θˆ)∥2 ·∥φ(xj, θˆ)∥2 / 2 This measure is related to the expected degree of orthogonality between gradients, measuring kernel similarity where larger similarity corresponds to a simpler model Generalization Across Model Classes The GAC generalizes several established complexity measures, including: 1.
Tom: Polynomial degree for polynomial regression 2.
Jane: Kernel length scale for Matérn kernels 3.
Tom: Number of neighbors for k-nearest neighbors 4.
Title and authors: Tom: The paper’s title is "A Rigorous, Tractable Measure of Model Complexity," and they put Oskar Allerbo from KTH Royal Institute of Technology and Thomas B. Schön from Uppsala University as the authors.
Jane: That name sounds very academic, but what they are trying to do is make complexity assessment accessible. They are tackling the problem that most existing complexity measures either rely on guesswork or take so long to run that they aren't practical for real use.
Lu: The main point here is that this measure of model complexity can be applied to virtually any parametric model, not just a specific type of algorithm.
Meng: That’s important because if it works across different kinds of models, it stops being just a tool for one specific architecture and becomes something more general.
Lalam: And the authors explicitly state that this measure generalizes several existing complexity metrics we already use in fields like polynomial regression or kernel methods.
The paper's summary: Tom: So, the core idea they are presenting is Gradient Alignment Complexity, or GAC. They define it as one minus the expected squared cosine difference between the model gradients when you look at different inputs.
Jane: It’s essentially measuring how much those gradients are aligned across all your data points, and they show that highly aligned gradients mean the model has less freedom to actually fit the data.
Lu: They give us an empirical formula for GAC, which is calculated by taking one minus a term involving the sample average of some inner products of the feature representations at different inputs.
Meng: And what they really emphasize is that this Empirical GAC is independent of your sample size, n, and it doesn't matter if you take your data from training or test sets, which makes it much more practical for deployment scenarios.
Lalam: They also show that this GAC measure can be used to gain new insights into the double descent phenomenon when looking at things like random Fourier features or random forests.
The paper's improvements: Tom: One of the big improvements they highlight is that GAC generalizes a lot of established complexity measures, so it connects to things like polynomial degree, kernel length scale for Matérn kernels, and even the number of splits in decision trees.
Jane: That’s what I mean when I say it's powerful; it takes those specific rules for different models and puts them under one umbrella.
Lu: They also point out a distinction between complexity measures that look at the whole class of functions versus those that measure the complexity of just one single learned function, which makes calculating things like Vapnik-Chervonenkis dimension much harder in practice.
Meng: From an engineering standpoint, if you can calculate this GAC without needing huge amounts of data or complex theoretical machinery, it simplifies model selection immensely when we are trying to choose the right one for a specific task.
Lalam: They also extend the concept to look at how model gradients relate to feature expansion, which lets us analyze complexity not just in terms of the model structure but also in terms of the features themselves.
Conclusion: Tom: So, to wrap up this paper on "A Rigorous, Tractable Measure of Model Complexity," they’ve given us a mathematically sound and computationally simple way to assess model complexity based on gradient alignment.
Jane: It moves us away from those heuristic guesses and gives us a concrete number that we can use to compare different models regardless of the underlying mathematical structure.
Lu: The implication is that we can get a more accurate picture of generalization without getting bogged down in the heavy theoretical machinery required by other complexity bounds.
Meng: For production, this means we might be able to prune or select models much faster because we have a reliable metric that doesn't depend on how much data you happen to have for your specific run.
Lalam: And I think what’s most exciting is how they are using this GAC concept to look at the double descent phenomenon in random forests, suggesting it could help us understand why certain models perform so well with certain architectures.
Oskar Allerbo, Thomas B. Schön
KTH Royal Institute of Technology · Uppsala University
stat.ML, cs.LG
Submitted: 2026-05-20
Updated: 2026-11-04
Code: https://github.com/llerbo/gradient_
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 79/100
The gist: An accurate assessment of a model’s complexity is crucial for topics such as interpretation, generalization…
Key concepts
- Gradient Alignment Complexity (GAC)
- GAC is a measure of how aligned the gradients of a model are across different inputs. Highly aligned gradients suggest the model has less freedom to fit the data, implying lower complexity. It is calculated using the expected squared cosine difference between these gradients.
- Model Complexity Measures
- These are established ways to quantify how intricate a machine learning model is. Examples include polynomial degree for regression, kernel length scale for kernels, and number of neighbors for k-NN. GAC is shown to be a general measure that encompasses all these specific complexity types.
- Gradient Similarity
- This refers to the degree of similarity or alignment between the gradients calculated by the model at different input points. When gradients are highly similar, it means the model's output changes smoothly across inputs, indicating less complex behavior.
- Generalization Across Model Classes
- The core contribution is demonstrating that GAC works for many different types of models. It successfully generalizes measures used in polynomial regression, kernel methods (like Matérn kernels), and tree-based methods (like decision trees) by providing a unified complexity metric.
Terminology
Summary
An accurate assessment of a model’s complexity is crucial for topics such as interpretation, generalization, and model selection This paper presents a mathematically rigorous yet easy-to-compute measure of model complexity based on the similarities between the model gradients across inputs It proves that this measure generalizes various model-specific complexity measures such as polynomial degree, kernel length scale, number of neighbors, and number of trees
Introduction to Model Complexity
One of the most fundamental properties of a machine learning model is its complexity, with applications across topics such as interpretation, generalization, and model selection Despite its importance, there is no canonical, model-agnostic way to assess a model’s complexity Simple heuristics yield crude estimates while hyperparameter-based approaches do not generalize across model classes The authors introduce a measure based on the alignment between the gradients ∇θˆf(x, θˆ) across inputs x They observe that highly aligned gradients imply less freedom for the model to model data (less complex) than independent gradients
Definition and Interpretation of GAC
The Gradient Alignment Complexity (GAC), K(ˆf), is defined as 1 minus the expected squared cosine difference between the gradients across inputs x and x' The empirical GAC is given by K(ˆf, X):= 1 − 1/n2 − n · ΣXn i,j=1 i̸=j φ(xi, θˆ)⊤φ(xj, θˆ)∥φ(xi, θˆ)∥2 ·∥φ(xj, θˆ)∥2 / 2 This measure is related to the expected degree of orthogonality between gradients, measuring kernel similarity where larger similarity corresponds to a simpler model
Generalization Across Model Classes
The GAC generalizes several established 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
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Gradient Alignment Complexity (GAC) as a model complexity measure allows for an accurate assessment of a model’s complexity by basing it on
the similarities between the model gradients across inputs.
This enables researchers to obtaina mathematically rigorous yet easy-to-compute measure of model complexity
that generalizes measures like polynomial degree and kernel length scale. -
Application to Double Descent Analysis: The GAC can be used to provide new insights into the double descent phenomenon for random Fourier features, random forests, neural networks, and gradient boosting by showing that
the GAC increases with the number of features
and observing asecond descent for the GAC.
-
Model Selection via Complexity Thresholds: Because the GAC is independent of sample size n for parametric models, it offers a robust way to select or compare models based on their inherent complexity, as
the GAC is independent of both the sample size n and whether the sample is drawn from training data, test data, or a mixture of the two.
-
Feature Space Generalization: The measure can be extended to analyze how model gradients relate to feature expansion by using it
to generalize the concept of features from constant to non-constant feature models,
allowing for analysis across both model and function complexities.
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.
Sources
- Classical Statistical (In-Sample) Intuitions Don't Generalize Well: A Note on Bias-Variance Tradeoffs, Overfitting and Moving from Fixed to Random Designs
- Why do Random Forests Work? Understanding Tree Ensembles as Self-Regularizing Adaptive Smoothers
- Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
- Degrees of Freedom in Deep Neural Networks
- Predictive Model Degrees of Freedom in Linear Regression
- Revisiting Optimism and Model Complexity in the Wake of Overparameterized Machine Learning
- Double descent in the condition number
- On the VC dimension of deep group convolutional neural networks
- On Rademacher Complexity-based Generalization Bounds for Deep Learning
- Adversarial Rademacher Complexity of Deep Neural Networks
- VC Theory for Inventory Policies
- Understanding deep learning requires rethinking generalization
- Measuring Neural Network Complexity via Effective Degrees of Freedom
Related papers
- Uniform-in-Time Weak Propagation-of-Chaos in Shallow Neural Networks
- Diffusion Models Observe Only Gradients: A Geometric Perspective on Score Matching Errors
- Quantifying Error Propagation and Model Collapse in Diffusion Models
- Behavior of prediction performance metrics with rare events
- Statistical Inference and Learning for Shapley Additive Explanations (SHAP)
- Control Variate Design for Score-Function Gradient Estimators in Importance-Weighted Variational Inference