In plain words: Ask whether a learning program will always fit a dataset poorly no matter how long it trains. It turns out no general check can answer that for every such program, so fit can only be bounded in special cases.

Abstract

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.

Sonia Sehra, David Flores, George D. Montanez
arXiv:2102.02850 · cs.LG, cs.AI, cs.FL, cs.IT · submitted Feb 4, 2021 · updated Feb 9, 2021
abstract · pdf · html · Accepted at The 2nd International Conference on Computing and Data Science (CONF-CDS 2021)