# An Information-Theoretic Perspective on Overfitting and Underfitting

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Oct 2020.

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

- [AdaAugment: A Tuning-Free and Adaptive Approach to Enhance Data Augmentation](https://mlsanity.com/paper/2405.11467/) (2024)
- [AutoMedPrompt: A New Framework for Optimizing LLM Medical Prompts Using Textual Gradients](https://mlsanity.com/paper/2502.15944/) (2025)
- [Adversarial Information Bottleneck](https://mlsanity.com/paper/2103.00381/) (2021)
- [Undecidability of Underfitting in Learning Algorithms](https://mlsanity.com/paper/2102.02850/) (2021)
- [Conformalised data synthesis](https://mlsanity.com/paper/2312.08999/) (2023)
- [IB-AdCSCNet:Adaptive Convolutional Sparse Coding Network Driven by Information Bottleneck](https://mlsanity.com/paper/2405.14192/) (2024)

## Abstract (arXiv)

We present an information-theoretic framework for understanding overfitting and underfitting in machine learning and prove the formal undecidability of determining whether an arbitrary classification algorithm will overfit a dataset. Measuring algorithm capacity via the information transferred from datasets to models, we consider mismatches between algorithm capacities and datasets to provide a signature for when a model can overfit or underfit a dataset. We present results upper-bounding algorithm capacity, establish its relationship to quantities in the algorithmic search framework for machine learning, and relate our work to recent information-theoretic approaches to generalization.