How Many Domains Suffice for Domain Generalization? A Tight Characterization via the Domain Shattering Dimension

The ability to generalize across domains is an important component of human intelligence and a crucial milestone in the development of increasingly powerful artificial intelligence. It is not surprising that an experienced driver in one country can reasonably, albeit imperfectly, drive in another country even without further training. It is also not surprising that a skilled chess player can outperform an average person on a totally different board game. An expert doctor who has studied a disease using data from a few large hospitals can potentially provide reasonable treatment for patients in a geographically remote and biologically different population that does not have access to those large hospitals and has not been the subject of prior study. Such domain generalization abilities are empowered by the capability of the learner (i.e., the driver, chess player, or doctor) to distill and master universal laws (about driving, game playing, or medical treatment) that hold even on unseen domains, while separating them from idiosyncratic patterns that are domain-specific. In this work, we study the theoretical foundations of domain generalization with a focus on capturing this ability of learning "universal laws" while not overfitting to the "idiosyncratic patterns". Consider a family G of domains, where every domain D is a distribution on examples ( x, y) each consisting of an instance x X and a binary label y { 0, 1 }. On a specific domain D, there may be a hypothesis (i.e., classifier) h: X { 0, 1 } with low classification error err