Sharp analysis of out-of-distribution error for "importance-weighted" estimators in the overparameterized regime

Overparameterized models are ubiquitous in machine learning theory and practice today because of their state-of-the-art generalization guarantees (in the sense of low test error) even while perfectly fitting the training data [30, 7]. However, this "good generalization" property does not extend to test data that is distributed differently from training data, termed out-of-distribution (OOD) data [20, 21, 29]. A particularly acute scenario arises when the data is drawn as a mixture from multiple groups (each with a different distribution) and some groups are very under-represented in training data [2]. Under such models, the worst-group generalization error can be significantly degraded with respect to the average generalization error on all groups [1, 27, 21, 20]. The effect of distribution shift on generalization has been sharply characterized in a worst-case/minimax sense, e.g.