# Undecidability of Underfitting in Learning Algorithms

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 13 references that are in the map.
- First posted on arXiv 4 Feb 2021.

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

- [An Information-Theoretic Perspective on Overfitting and Underfitting](https://mlsanity.com/paper/2010.06076/) (2020)
- [The Bias-Expressivity Trade-off](https://mlsanity.com/paper/1911.04964/) (2019)
- [Decidability of Sample Complexity of PAC Learning in finite setting](https://mlsanity.com/paper/2002.11519/) (2020)
- [The Labeling Distribution Matrix (LDM): A Tool for Estimating Machine Learning Algorithm Capacity](https://mlsanity.com/paper/1912.10597/) (2019)

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

- [Impossibility Results in AI: A Survey](https://mlsanity.com/paper/2109.00484/) (2021)
- [AdaAugment: A Tuning-Free and Adaptive Approach to Enhance Data Augmentation](https://mlsanity.com/paper/2405.11467/) (2024)
- [From Undecidability of Non-Triviality and Finiteness to Undecidability of Learnability](https://mlsanity.com/paper/2106.01382/) (2021)
- [Le Nozze di Giustizia. Interactions between Artificial Intelligence, Law, Logic, Language and Computation with some case studies in Traffic Regulations and Health Care](https://mlsanity.com/paper/2402.06487/) (2024)

## Abstract (arXiv)

Using recent machine learning results that present an information-theoretic perspective on underfitting and overfitting, we prove that deciding whether an encodable learning algorithm will always underfit a dataset, even if given unlimited training time, is undecidable. We discuss the importance of this result and potential topics for further research, including information-theoretic and probabilistic strategies for bounding learning algorithm fit.