# An Online Learning Approach to Interpolation and Extrapolation in Domain Generalization

arXiv: https://arxiv.org/abs/2102.13128 · HTML: https://mlsanity.com/paper/2102.13128/

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 44 references that are in the map.
- First posted on arXiv 25 Feb 2021.

## Builds on (most cited first, 22 of 22)

- [Domain-Adversarial Training of Neural Networks](https://mlsanity.com/paper/1505.07818/) (2015)
- [Invariant Risk Minimization](https://mlsanity.com/paper/1907.02893/) (2019)
- [Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization](https://mlsanity.com/paper/1911.08731/) (2019)
- [In Search of Lost Domain Generalization](https://mlsanity.com/paper/2007.01434/) (2020)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Out-of-Distribution Generalization via Risk Extrapolation (REx)](https://mlsanity.com/paper/2003.00688/) (2020)
- [Recognition in Terra Incognita](https://mlsanity.com/paper/1807.04975/) (2018)
- [Domain Generalization via Invariant Feature Representation](https://mlsanity.com/paper/1301.2115/) (2013)
- [Causal inference using invariant prediction: identification and confidence intervals](https://mlsanity.com/paper/1501.01332/) (2015)
- [Detecting and Correcting for Label Shift with Black Box Predictors](https://mlsanity.com/paper/1802.03916/) (2018)
- [The Risks of Invariant Risk Minimization](https://mlsanity.com/paper/2010.05761/) (2020)
- [Invariant Causal Prediction for Nonlinear Models](https://mlsanity.com/paper/1706.08576/) (2017)
- [Generalizing to unseen domains via distribution matching](https://mlsanity.com/paper/1911.00804/) (2019)
- [Domain Generalization via Multidomain Discriminant Analysis](https://mlsanity.com/paper/1907.11216/) (2019)
- [A causal framework for distribution generalization](https://mlsanity.com/paper/2006.07433/) (2020)
- [Distributionally Robust Losses for Latent Covariate Mixtures](https://mlsanity.com/paper/2007.13982/) (2020)
- [Causal Discovery from Changes](https://mlsanity.com/paper/1301.2312/) (2013)
- [Does Distributionally Robust Supervised Learning Give Robust Classifiers?](https://mlsanity.com/paper/1611.02041/) (2016)
- [Online Non-Convex Learning: Following the Perturbed Leader is Optimal](https://mlsanity.com/paper/1903.08110/) (2019)
- [A Generalization Error Bound for Multi-class Domain Generalization](https://mlsanity.com/paper/1905.10392/) (2019)
- [Efficient Representations for Life-Long Learning and Autoencoding](https://mlsanity.com/paper/1411.1490/) (2014)
- [Regret Bounds for Lifelong Learning](https://mlsanity.com/paper/1610.08628/) (2016)

## Built on by (most cited first, 30 of 30)

- [Domain Generalization: A Survey](https://mlsanity.com/paper/2103.02503/) (2021)
- [Invariance Principle Meets Information Bottleneck for Out-of-Distribution Generalization](https://mlsanity.com/paper/2106.06607/) (2021)
- [Domain-Adjusted Regression or: ERM May Already Learn Features Sufficient for Out-of-Distribution Generalization](https://mlsanity.com/paper/2202.06856/) (2022)
- [Online DPO: Online Direct Preference Optimization with Fast-Slow Chasing](https://mlsanity.com/paper/2406.05534/) (2024)
- [Credal Learning Theory](https://mlsanity.com/paper/2402.00957/) (2024)
- [Iterative Feature Matching: Toward Provable Domain Generalization with Logarithmic Environments](https://mlsanity.com/paper/2106.09913/) (2021)
- [MADG: Margin-based Adversarial Learning for Domain Generalization](https://mlsanity.com/paper/2311.08503/) (2023)
- [(Almost) Provable Error Bounds Under Distribution Shift via Disagreement Discrepancy](https://mlsanity.com/paper/2306.00312/) (2023)
- [Core Risk Minimization using Salient ImageNet](https://mlsanity.com/paper/2203.15566/) (2022)
- [One-Shot Strategic Classification Under Unknown Costs](https://mlsanity.com/paper/2311.02761/) (2023)
- [A comparison of approaches to improve worst-case predictive model performance over patient subpopulations](https://mlsanity.com/paper/2108.12250/) (2021)
- [Continual learning: a feature extraction formalization, an efficient algorithm, and fundamental obstructions](https://mlsanity.com/paper/2203.14383/) (2022)
- [Do causal predictors generalize better to new domains?](https://mlsanity.com/paper/2402.09891/) (2024)
- [On the Limitations of General Purpose Domain Generalisation Methods](https://mlsanity.com/paper/2202.00563/) (2022)
- [The Curse of Low Task Diversity: On the Failure of Transfer Learning to Outperform MAML and Their Empirical Equivalence](https://mlsanity.com/paper/2208.01545/) (2022)
- [Adversarially Robust Models may not Transfer Better: Sufficient Conditions for Domain Transferability from the View of Regularization](https://mlsanity.com/paper/2202.01832/) (2022)
- [Epistemic Artificial Intelligence is Essential for Machine Learning Models to Truly 'Know When They Do Not Know'](https://mlsanity.com/paper/2505.04950/) (2025)
- [Is Pre-training Truly Better Than Meta-Learning?](https://mlsanity.com/paper/2306.13841/) (2023)
- [Improving Generalization with Domain Convex Game](https://mlsanity.com/paper/2303.13297/) (2023)
- [Causally Inspired Regularization Enables Domain General Representations](https://mlsanity.com/paper/2404.16277/) (2024)
- [Target Conditioned Representation Independence (TCRI); From Domain-Invariant to Domain-General Representations](https://mlsanity.com/paper/2212.11342/) (2022)
- [Achievable distributional robustness when the robust risk is only partially identified](https://mlsanity.com/paper/2502.02710/) (2025)
- [Causality-Inspired Robustness for Nonlinear Models via Representation Learning](https://mlsanity.com/paper/2505.12868/) (2025)
- [Improved Group Robustness via Classifier Retraining on Independent Splits](https://mlsanity.com/paper/2204.09583/) (2022)
- [Distributional Shift Adaptation using Domain-Specific Features](https://mlsanity.com/paper/2211.04670/) (2022)
- [Constrained Maximum Cross-Domain Likelihood for Domain Generalization](https://mlsanity.com/paper/2210.04155/) (2022)
- [Bayesian Domain Invariant Learning via Posterior Generalization of Parameter Distributions](https://mlsanity.com/paper/2310.16277/) (2023)
- [Revisiting Spurious Correlation in Domain Generalization](https://mlsanity.com/paper/2406.11517/) (2024)
- [Robust Domain Generalization under Divergent Marginal and Conditional Distributions](https://mlsanity.com/paper/2602.02015/) (2026)
- [Learning to Test: Latent Representation Learning for Dynamic Instability Detection](https://mlsanity.com/paper/2604.10967/) (2026)

## Abstract (arXiv)

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.