Undecidability of Underfitting in Learning Algorithms

Sonia Sehra, David Flores, George D. Montanez

Using recent machine learning results that present an information-theoretic perspective on underfitting and overfitting, we prove that deciding whether an encodable learning algori…