Rate-Distortion Bounds on Bayes Risk in Supervised Learning
  We present an information-theoretic framework for bounding the number of
labeled samples needed to train a classifier in a parametric Bayesian setting.
We derive bounds on the average $L_p$ distance between the learned classifier
and the true maximum a posteriori classifier, which are well-established
surrogates for the excess classification error due to imperfect learning. We
provide lower and upper bounds on the rate-distortion function, using $L_p$
loss as the distortion measure, of a maximum a priori classifier in terms of
the differential entropy of the posterior distribution and a quantity called
the interpolation dimension, which characterizes the complexity of the
parametric distribution family. In addition to expressing the information
content of a classifier in terms of lossy compression, the rate-distortion
function also expresses the minimum number of bits a learning machine needs to
extract from training data to learn a classifier to within a specified $L_p$
tolerance. We use results from universal source coding to express the
information content in the training data in terms of the Fisher information of
the parametric family and the number of training samples available. The result
is a framework for computing lower bounds on the Bayes $L_p$ risk. This
framework complements the well-known probably approximately correct (PAC)
framework, which provides minimax risk bounds involving the Vapnik-Chervonenkis
dimension or Rademacher complexity. Whereas the PAC framework provides upper
bounds the risk for the worst-case data distribution, the proposed
rate-distortion framework lower bounds the risk averaged over the data
distribution. We evaluate the bounds for a variety of data models, including
categorical, multinomial, and Gaussian models. In each case the bounds are
provably tight orderwise, and in two cases we prove that the bounds are tight
up to multiplicative constants.
