An Information-Theoretic Perspective on Overfitting and Underfitting
  We present an information-theoretic framework for understanding overfitting
and underfitting in machine learning and prove the formal undecidability of
determining whether an arbitrary classification algorithm will overfit a
dataset. Measuring algorithm capacity via the information transferred from
datasets to models, we consider mismatches between algorithm capacities and
datasets to provide a signature for when a model can overfit or underfit a
dataset. We present results upper-bounding algorithm capacity, establish its
relationship to quantities in the algorithmic search framework for machine
learning, and relate our work to recent information-theoretic approaches to
generalization.
