  Meta-learning, or "learning to learn", refers to techniques that infer an
inductive bias from data corresponding to multiple related tasks with the goal
of improving the sample efficiency for new, previously unobserved, tasks. A key
performance measure for meta-learning is the meta-generalization gap, that is,
the difference between the average loss measured on the meta-training data and
on a new, randomly selected task. This paper presents novel
information-theoretic upper bounds on the meta-generalization gap. Two broad
classes of meta-learning algorithms are considered that uses either separate
within-task training and test sets, like MAML, or joint within-task training
and test sets, like Reptile. Extending the existing work for conventional
learning, an upper bound on the meta-generalization gap is derived for the
former class that depends on the mutual information (MI) between the output of
the meta-learning algorithm and its input meta-training data. For the latter,
the derived bound includes an additional MI between the output of the per-task
learning procedure and corresponding data set to capture within-task
uncertainty. Tighter bounds are then developed, under given technical
conditions, for the two classes via novel Individual Task MI (ITMI) bounds.
Applications of the derived bounds are finally discussed, including a broad
class of noisy iterative algorithms for meta-learning.
