  Machine learning models have traditionally been developed under the
assumption that the training and test distributions match exactly. However,
recent success in few-shot learning and related problems are encouraging signs
that these models can be adapted to more realistic settings where train and
test distributions differ. Unfortunately, there is severely limited theoretical
support for these algorithms and little is known about the difficulty of these
problems. In this work, we provide novel information-theoretic lower-bounds on
minimax rates of convergence for algorithms that are trained on data from
multiple sources and tested on novel data. Our bounds depend intuitively on the
information shared between sources of data, and characterize the difficulty of
learning in this setting for arbitrary algorithms. We demonstrate these bounds
on a hierarchical Bayesian model of meta-learning, computing both upper and
lower bounds on parameter estimation via maximum-a-posteriori inference.
