Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#326885] of Robert Calderbank

Papers Published

  1. Nokleby, M; Beirami, A; Calderbank, R, Rate-distortion bounds on Bayes risk in supervised learning, Ieee International Symposium on Information Theory Proceedings, vol. 2016-August (August, 2016), pp. 2099-2103, ISBN 9781509018062 [doi]
    (last updated on 2018/12/18)

    © 2016 IEEE. An information-theoretic framework is presented for estimating the number of labeled samples needed to train a classifier in a parametric Bayesian setting. Ideas from rate-distortion theory are used to derive bounds for the average L1or L∞distance between the learned classifier and the true maximum a posteriori classifier in terms of familiar information-theoretic quantities and the number of training samples available. The maximum a posteriori classifier is viewed as a random source, labeled training data are viewed as a finite-rate encoding of the source, and the L1or L∞Bayes risk is viewed as the average distortion. The result is a framework dual to the well-known probably approximately correct (PAC) framework. PAC bounds characterize worst-case learning performance of a family of classifiers whose complexity is captured by the Vapnik-Chervonenkis (VC) dimension. The rate-distortion framework, on the other hand, characterizes the average-case performance of a family of data distributions in terms of a quantity called the interpolation dimension, which represents the complexity of the family of data distributions. The resulting bounds do not suffer from the pessimism typical of the PAC framework, particularly when the training set is small.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320