  We investigate the fundamental performance limitations of learning algorithms
in several Domain Generalisation (DG) settings. Motivated by the difficulty
with which previously proposed methods have in reliably outperforming Empirical
Risk Minimisation (ERM), we derive upper bounds on the excess risk of ERM, and
lower bounds on the minimax excess risk. Our findings show that in all the DG
settings we consider, it is not possible to significantly outperform ERM. Our
conclusions are limited not only to the standard covariate shift setting, but
also two other settings with additional restrictions on how domains can differ.
The first constrains all domains to have a non-trivial bound on pairwise
distances, as measured by a broad class of integral probability metrics. The
second alternate setting considers a restricted class of DG problems where all
domains have the same underlying support. Our analysis also suggests how
different strategies can be used to optimise the performance of ERM in each of
these DG setting. We also experimentally explore hypotheses suggested by our
theoretical analysis.
