  We consider the problem of \emph{pruning} a classification tree, that is,
selecting a suitable subtree that balances bias and variance, in common
situations with inhomogeneous training data. Namely, assuming access to mostly
data from a distribution $P_{X, Y}$, but little data from a desired
distribution $Q_{X, Y}$ with different $X$-marginals, we present the first
efficient procedure for optimal pruning in such situations, when
cross-validation and other penalized variants are grossly inadequate.
Optimality is derived with respect to a notion of \emph{average discrepancy}
$P_{X} \to Q_{X}$ (averaged over $X$ space) which significantly relaxes a
recent notion -- termed \emph{transfer-exponent} -- shown to tightly capture
the limits of classification under such a distribution shift. Our relaxed
notion can be viewed as a measure of \emph{relative dimension} between
distributions, as it relates to existing notions of information such as the
Minkowski and Renyi dimensions.
