Undecidability of Underfitting in Learning Algorithms
  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.
