# Model-agnostic Measure of Generalization Difficulty

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 71 references that are in the map.
- First posted on arXiv 1 May 2023.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Wide Residual Networks](https://mlsanity.com/paper/1605.07146/) (2016)
- [Sharpness-Aware Minimization for Efficiently Improving Generalization](https://mlsanity.com/paper/2010.01412/) (2020)
- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [Meta-World: A Benchmark and Evaluation for Multi-Task and Meta Reinforcement Learning](https://mlsanity.com/paper/1910.10897/) (2019)
- [Visualizing the Loss Landscape of Neural Nets](https://mlsanity.com/paper/1712.09913/) (2017)
- [Big Transfer (BiT): General Visual Representation Learning](https://mlsanity.com/paper/1912.11370/) (2019)
- [Deep Learning Scaling is Predictable, Empirically](https://mlsanity.com/paper/1712.00409/) (2017)
- [Opening the Black Box of Deep Neural Networks via Information](https://mlsanity.com/paper/1703.00810/) (2017)
- [Benchmarking Deep Reinforcement Learning for Continuous Control](https://mlsanity.com/paper/1604.06778/) (2016)
- [ResNet strikes back: An improved training procedure in timm](https://mlsanity.com/paper/2110.00476/) (2021)
- [Deeply-Supervised Nets](https://mlsanity.com/paper/1409.5185/) (2014)
- [Explaining Neural Scaling Laws](https://mlsanity.com/paper/2102.06701/) (2021)
- [The Intrinsic Dimension of Images and Its Impact on Learning](https://mlsanity.com/paper/2104.08894/) (2021)
- [Rademacher Complexity for Adversarially Robust Generalization](https://mlsanity.com/paper/1810.11914/) (2018)
- [Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates](https://mlsanity.com/paper/1911.02151/) (2019)
- [Learning Curve Theory](https://mlsanity.com/paper/2102.04074/) (2021)
- [Multi-digit Number Recognition from Street View Imagery using Deep Convolutional Neural Networks](https://mlsanity.com/paper/1312.6082/) (2013)
- [The Information Complexity of Learning Tasks, their Structure and their Distance](https://mlsanity.com/paper/1904.03292/) (2019)
- [Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?](https://mlsanity.com/paper/2010.08515/) (2020)
- [Theory of Deep Learning III: explaining the non-overfitting puzzle](https://mlsanity.com/paper/1801.00173/) (2017)
- [An Ensemble of Simple Convolutional Neural Network Models for MNIST Digit Recognition](https://mlsanity.com/paper/2008.10400/) (2020)
- [Robustness Implies Generalization via Data-Dependent Generalization Bounds](https://mlsanity.com/paper/2206.13497/) (2022)
- [How far can we go without convolution: Improving fully-connected networks](https://mlsanity.com/paper/1511.02580/) (2015)
- [Multi-class SVMs: From Tighter Data-Dependent Generalization Bounds to Novel Algorithms](https://mlsanity.com/paper/1506.04359/) (2015)
- [Sample complexity and effective dimension for regression on manifolds](https://mlsanity.com/paper/2006.07642/) (2020)
- [Canonical convolutional neural networks](https://mlsanity.com/paper/2206.01509/) (2022)

## Built on by (most cited first, 7 of 7)

- [Neural Redshift: Random Networks are not Random Functions](https://mlsanity.com/paper/2403.02241/) (2024)
- [Towards Exact Computation of Inductive Bias](https://mlsanity.com/paper/2406.15941/) (2024)
- [Stagewise Reinforcement Learning and the Geometry of the Regret Landscape](https://mlsanity.com/paper/2601.07524/) (2026)
- [Revisiting Generalization Power of a DNN in Terms of Symbolic Interactions](https://mlsanity.com/paper/2502.10162/) (2025)
- [IBEX: Information-Bottleneck-EXplored Coarse-to-Fine Molecular Generation under Limited Data](https://mlsanity.com/paper/2508.10775/) (2025)
- [Supervised Learning as Lossy Compression: Characterizing Generalization and Sample Complexity via Finite Blocklength Analysis](https://mlsanity.com/paper/2602.04107/) (2026)
- [Pool-based Active Learning as Noisy Lossy Compression: Characterizing Label Complexity via Finite Blocklength Analysis](https://mlsanity.com/paper/2602.05333/) (2026)

## Abstract (arXiv)

The measure of a machine learning algorithm is the difficulty of the tasks it can perform, and sufficiently difficult tasks are critical drivers of strong machine learning models. However, quantifying the generalization difficulty of machine learning benchmarks has remained challenging. We propose what is to our knowledge the first model-agnostic measure of the inherent generalization difficulty of tasks. Our inductive bias complexity measure quantifies the total information required to generalize well on a task minus the information provided by the data. It does so by measuring the fractional volume occupied by hypotheses that generalize on a task given that they fit the training data. It scales exponentially with the intrinsic dimensionality of the space over which the model must generalize but only polynomially in resolution per dimension, showing that tasks which require generalizing over many dimensions are drastically more difficult than tasks involving more detail in fewer dimensions. Our measure can be applied to compute and compare supervised learning, reinforcement learning and meta-learning generalization difficulties against each other. We show that applied empirically, it formally quantifies intuitively expected trends, e.g. that in terms of required inductive bias, MNIST < CIFAR10 < Imagenet and fully observable Markov decision processes (MDPs) < partially observable MDPs. Further, we show that classification of complex images < few-shot meta-learning with simple images. Our measure provides a quantitative metric to guide the construction of more complex tasks requiring greater inductive bias, and thereby encourages the development of more sophisticated architectures and learning algorithms with more powerful generalization capabilities.