Undecidability of Underfitting in Learning Algorithms
This paper addresses a foundational theoretical problem for machine learning researchers, demonstrating a fundamental limit in predicting algorithm behavior regarding underfitting.
The authors prove that it is undecidable to determine if an encodable learning algorithm will always underfit a dataset, even with unlimited training time. This result is based on recent information-theoretic perspectives on underfitting and overfitting.
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.