Information-Theoretic Bayes Risk Lower Bounds for Realizable Models
  We derive information-theoretic lower bounds on the Bayes risk and
generalization error of realizable machine learning models. In particular, we
employ an analysis in which the rate-distortion function of the model
parameters bounds the required mutual information between the training samples
and the model parameters in order to learn a model up to a Bayes risk
constraint. For realizable models, we show that both the rate distortion
function and mutual information admit expressions that are convenient for
analysis. For models that are (roughly) lower Lipschitz in their parameters, we
bound the rate distortion function from below, whereas for VC classes, the
mutual information is bounded above by $d_\mathrm{vc}\log(n)$. When these
conditions match, the Bayes risk with respect to the zero-one loss scales no
faster than $\Omega(d_\mathrm{vc}/n)$, which matches known outer bounds and
minimax lower bounds up to logarithmic factors. We also consider the impact of
label noise, providing lower bounds when training and/or test samples are
corrupted.
