mlsanityData to 7 Oct 2026

An Online Learning Approach to Interpolation and Extrapolation in Domain Generalization

arXiv 2102.13128 ↗First posted 25 Feb 2021cs.LG cs.AI cs.GTcited by 30

Not on the map. Why?

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.

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

Builds on

22 of 44 references.

References · 22

  1. 2015Domain-Adversarial Training of Neural Networkscited by 3,023
  2. 2019Invariant Risk Minimizationcited by 1,832
  3. 2019Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalizationcited by 1,232
  4. 2020In Search of Lost Domain Generalizationcited by 1,042
  5. 2019Introduction to Online Convex Optimizationcited by 793
  6. 2020Out-of-Distribution Generalization via Risk Extrapolation (REx)cited by 737
  7. 2018Recognition in Terra Incognitacited by 655
  8. 2013Domain Generalization via Invariant Feature Representationcited by 622
  9. 2015Causal inference using invariant prediction: identification and confidence intervalscited by 533
  10. 2018Detecting and Correcting for Label Shift with Black Box Predictorscited by 364
  11. 2020The Risks of Invariant Risk Minimizationcited by 262
  12. 2017Invariant Causal Prediction for Nonlinear Modelscited by 140
10 more
  1. 2019Generalizing to unseen domains via distribution matchingcited by 109
  2. 2019Domain Generalization via Multidomain Discriminant Analysiscited by 69
  3. 2020A causal framework for distribution generalizationcited by 68
  4. 2020Distributionally Robust Losses for Latent Covariate Mixturescited by 57
  5. 2013Causal Discovery from Changescited by 52
  6. 2016Does Distributionally Robust Supervised Learning Give Robust Classifiers?cited by 38
  7. 2019Online Non-Convex Learning: Following the Perturbed Leader is Optimalcited by 31
  8. 2019A Generalization Error Bound for Multi-class Domain Generalizationcited by 26
  9. 2014Efficient Representations for Life-Long Learning and Autoencodingcited by 23
  10. 2016Regret Bounds for Lifelong Learningcited by 19

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 10; 2023: 6; 2024: 5; 2025: 3; 2026: 2.

30 papers.

Sort:

By area:

  1. 2021Domain Generalization: A Surveycited by 760
  2. 2021Invariance Principle Meets Information Bottleneck for Out-of-Distribution Generalizationcited by 220
  3. 2022Domain-Adjusted Regression or: ERM May Already Learn Features Sufficient for Out-of-Distribution Generalizationcited by 69
  4. 2024Online DPO: Online Direct Preference Optimization with Fast-Slow Chasingcited by 38
  5. 2021Iterative Feature Matching: Toward Provable Domain Generalization with Logarithmic Environmentscited by 30
  6. 2024Credal Learning Theorycited by 30
  7. 2023MADG: Margin-based Adversarial Learning for Domain Generalizationcited by 22
  8. 2023(Almost) Provable Error Bounds Under Distribution Shift via Disagreement Discrepancycited by 16
  9. 2022Core Risk Minimization using Salient ImageNetcited by 15
  10. 2023One-Shot Strategic Classification Under Unknown Costscited by 13
  11. 2021A comparison of approaches to improve worst-case predictive model performance over patient subpopulationscited by 12
  12. 2022Continual learning: a feature extraction formalization, an efficient algorithm, and fundamental obstructionscited by 11
18 more
  1. 2024Do causal predictors generalize better to new domains?cited by 11
  2. 2022On the Limitations of General Purpose Domain Generalisation Methodscited by 10
  3. 2022The Curse of Low Task Diversity: On the Failure of Transfer Learning to Outperform MAML and Their Empirical Equivalencecited by 10
  4. 2022Adversarially Robust Models may not Transfer Better: Sufficient Conditions for Domain Transferability from the View of Regularizationcited by 8
  5. 2025Epistemic Artificial Intelligence is Essential for Machine Learning Models to Truly 'Know When They Do Not Know'cited by 8
  6. 2023Is Pre-training Truly Better Than Meta-Learning?cited by 6
  7. 2023Improving Generalization with Domain Convex Gamecited by 4
  8. 2024Causally Inspired Regularization Enables Domain General Representationscited by 4
  9. 2022Target Conditioned Representation Independence (TCRI); From Domain-Invariant to Domain-General Representationscited by 3
  10. 2025Achievable distributional robustness when the robust risk is only partially identifiedcited by 3
  11. 2025Causality-Inspired Robustness for Nonlinear Models via Representation Learningcited by 3
  12. 2022Improved Group Robustness via Classifier Retraining on Independent Splitscited by 2
  13. 2022Distributional Shift Adaptation using Domain-Specific Featurescited by 2
  14. 2022Constrained Maximum Cross-Domain Likelihood for Domain Generalizationcited by 1
  15. 2023Bayesian Domain Invariant Learning via Posterior Generalization of Parameter Distributionscited by 1
  16. 2024Revisiting Spurious Correlation in Domain Generalizationcited by 1
  17. 2026Robust Domain Generalization under Divergent Marginal and Conditional Distributionscited by 0
  18. 2026Learning to Test: Physics-Informed Representation for Dynamical Instability Detectioncited by 0