An Online Learning Approach to Interpolation and Extrapolation in Domain Generalization
By Elan Rosenfeld, Pradeep Ravikumar, Andrej Risteski. 2021
40 citations recorded by the source corpus.
A popular assumption for out-of-distribution generalization is that the training data comprises sub-datasets, each drawn from a distinct distribution; the goal is then to"interpolate"these distributions and"extrapolate"beyond them -- this objective is broadly known as domain generalization. A common belief is that ERM can interpolate but not extrapolate and that the latter is considerably more difficult, but these claims are vague and lack formal justification. In this work, we recast generalization over sub-groups as an online game between a player minimizing risk and an adversary presenting new test distributions. Under an existing notion of inter- and extrapolation based on reweighting of sub-group likelihoods, we rigorously demonstrate that extrapolation is computationally much harder than interpolation, though their statistical complexity is not significantly different. Furthermore, we show that ERM -- or a noisy variant -- is provably minimax-optimal for both tasks. Our framework presents a new avenue for the formal analysis of domain generalization algorithms which may be of independent interest.
Subfields: Artificial Intelligence
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Yu Qiao
- Ziwei Liu
- Chen Change Loy
- Kaiyang Zhou
- Tao A. Xiang
- Andrej Risteski
- Binghui Peng
- Pradeep Ravikumar
Citations in the corpus
- Continual learning: a feature extraction formalization, an efficient algorithm, and fundamental obstructions (2022, background): “The work of [31, 30] formulate the problem of out-of-distribution generalization and provide theoretical guarantee, similarly, under the assumption of a good representation.”
- Domain Generalization: A Survey (2021, background): “Specifically, we discuss potential directions from three perspectives: model (§ 5.1), learning (§ 5.2), and benchmarks (§ 5.3).”
- The Risks of Invariant Risk Minimization (2020, background): “In contrast, this paper focuses instead on domain generalization (Blanchard et al., 2011; Rosenfeld et al., 2021), where access to the test distribution is not assumed.”