Year: 2021

Abstract:
Machine learning algorithms typically assume that training and test examples are drawn from the same distribution. However, distribution shifts is a common problem in real-world applications and can cause models to perform dramatically worse at test time. In this paper, we specifically consider the problems of domain shifts and subpopulation shifts, where learning invariant representations by aligning domain-specific representations or balancing the risks across domains with regularizers are popular solutions. However, designing regularizers that are suitable for diverse real-world datasets is challenging. Instead, we shed new light on addressing distribution shifts by directly eliminating domain-related spurious correlations with augmentation, leading to a simple technique based on mixup, called LISA (Learning Invariant Representations via Selective Augmentation). LISA selectively interpolates samples either with the same labels but different domains or with the same domain but different labels. Empirically, we study the effectiveness of LISA on nine benchmarks ranging from subpopulation shifts to domain shifts. The results indicate that LISA consistently outperforms other state-of-theart methods with superior invariant representations. The empirical findings are further strengthened by our theoretical analysis.

heading: 1 INTRODUCTION
text: To deploy machine learning algorithms in real-world applications, we must pay attention to distribution shifts, i.e. when the test distribution is different from the training distribution, which substantially degrades model performance. In this paper, we refer this problem as out-of-distribution (OOD) generalization and specifically consider performance gaps caused by two kinds of distribution shifts: domain shifts and subpopulation shifts. In domain shifts, the test data is sampled from different domains than the training data, which requires the trained model to generalize well to test domains without seeing training data from those domains. Take health risk prediction as an example. We may want to train a model on patients from a few sampled hospitals and then deploy the model to a broader set of hospitals (Koh et al., 2021). In subpopulation shifts, the proportions of subpopulations in the test distribution differ from the proportions in the training distribution. When subpopulation shift occur, models perform poorly when they falsely rely on spurious correlations, which may occur when some subpopulations are under-represented in the training set. For example, in financial risk prediction, a machine learning model trained on the entire population may associate the labels with demographic features (e.g., religion and race), making the model fail on the test set when such an association does not hold in reality.
To improve model robustness under these two kinds of distribution shifts, methods for learning invariant representations have shown effectiveness in various applications. These methods learn features or prediction mechanisms that are invariant to different domains while still containing sufficient information for the targeted task (Li et al., 2018; Arjovsky et al., 2019). Concretely, some prior works learn invariant representations by aligning and regularizing the domain-specific representations (Li et al., 2018; Sun & Saenko, 2016). Other works aim to find invariant representations by balancing the risk across domains using regularizers (Arjovsky et al., 2019; Krueger et al., 2021; Rosenfeld et al., 2021), which further increases the dependency between the invariant representations and labels. However, designing regularizers that are widely suitable to datasets from diverse domains is especially challenging and insuitable regularizers may adversely limit the model’s expressive power, leading to inconsistent performance among various real-world datasets. For example, on the WILDS datasets (Koh et al., 2021), invariant risk minimization (IRM) (Arjovsky et al.,
2019) outperforms empirical risk minimization (ERM) on CivilComments, but fails to improve robustness on a variety of other datasets like Camelyon17 and RxRx1. A similar phenomenon is also reflected in the performance of CORAL (Sun & Saenko, 2016).
Instead of explicitly imposing regularization to learn invariant representations, we turn towards an implicit solution. Inspired by mixup (Zhang et al., 2018), we aim to alleviate the effects of domainrelated spurious information through data interpolation, leading to a simple algorithm called LISA (Learning Invariant Representations with Selective Augmentation). Concretely, LISA linearly interpolates the features for a pair of samples and applies the same interpolation strategy on the corresponding labels. Critically, the pairs are selectively chosen according to two sample selection strategies. In selection strategy I, LISA interpolates samples with the same label but from different domains, aiming to eliminate domain-related spurious correlations. In selection strategy II, LISA interpolates samples with the same domain but different labels, where the model should to ignore the domain information and generate different predicted values as the interpolation ratio changes. In this way, LISA encourages the model to learn domain-invariant predictors without explicitly constraining or regularizing the representation.
The primary contributions of this paper are as follows: (1) We develop a method that tackles the problem of distribution shifts by canceling out the domain-related spurious correlations via data interpolation. (2) We conduct broad empirical experiments to evaluate the effectiveness of LISA on nine benchmark datasets from diverse domains. In these experiments, we make the following observations. First, we find that LISA consistently outperforms seven prior methods in addressing both domain shifts and subpopulation shifts. Second, we identify that the performance gains of LISA are indeed caused by canceling out domain-specific information and learning invariant representations, rather than simply involving more data via interpolation. Third, when the degree of distribution shift increases, LISA achieves more significant performance gains. (3) Finally, we provide theoretical analysis of the phenomena distilled from the empirical studies, where we provably demonstrate that LISA can achieve smaller worst-domain error compared with ERM and vanilla mixup. We also note that to the best of our knowledge, this is the first theoretical analysis of how mixup (with or without the selection strategies) affects mis-classification error.
2 PRELIMINARIES
In this paper, we consider the setting where one predicts the label y ∈ Y based on the input feature x ∈ X . Given a parameter space Θ and a loss function ℓ, we are supposed to train a model fθ under the training distribution Ptr, where θ ∈ Θ. In empirical risk minimization (ERM), assume the empirical distribution over training data is P̂tr, ERM optimizes the following objective:
θ∗ := argmin θ∈Θ E(x,y)∼P̂ [ℓ(fθ(x), y)]. (1)
In a traditional machine learning setting, a test set, sampled from a test distribution Pts, is used to evaluate the generalization of the trained model θ∗, where the test distribution is assumed to be the same as the training distribution, i.e., P tr = P ts. In this paper, we are interested in the setting when distribution shift occurs, i.e., P tr ̸= P ts. Specifically, follow Muandet et al. (2013); Albuquerque et al. (2019); Koh et al. (2021), we regard the overall data distribution containing D = {1, . . . , D} domains and each domain d ∈ D is associated with a data distribution Pd over a set (X,Y, d) = {(xi, yi, d)}N d i=1, where N d is the number of samples in domain d. Then, we formulate the training distribution as the mixture of D domains, i.e., P tr = ∑ d∈D r tr
d Pd, where {rtrd } denotes the mixture probabilities in training set. Here, the training domains are defined as Dtr = {d ∈ D|rtrd > 0}. Similarly, the test distribution could be represented as P ts = ∑ d∈D r ts d Pd, where {rtsd } is the mixture probabilities in test set. The test domains are defined as Dts = {d ∈ D|rtsd > 0}.
In domain shifts, we investigate the problem that the test domains are disjoint from the training domains, i.e., Dtr ∩ Dts = ∅. In general, we assume the test domains share some common properties with the training domains. For example, in Camelyon17 (Koh et al., 2021) data, we train the model on some hospitals and test it in a new hospital. We evaluate the worst-domain or average performance of the classifier among all test domains.
In subpopulation shifts, the test set have domains that have been seen in the training set, but with a different proportion of subpopulations, i.e., Dts ⊆ Dtr but {rtsd } ≠ {rtrd }. Under this setting, follow Sagawa et al. (2020a), we specially consider group-based spurious correlations, where each group g ∈ G is defined to be associated with a domain d and a label y, i.e., g = (d, y). We assume the domain identification is spuriously correlated with the label. For example, we illustrate the Waterbirds dataset in Figure 1, where the background d (water or land) is spuriously correlated with the label y (waterbird or landbird). Based on the group definition, we evaluate the model via the worst test group error, i.e., maxg E(x,y)∼g[ℓ0−1(fθ(x), y)], where ℓ0−1 represents the 0-1 loss.

heading: 3 LEARNING INVARIANT REPRESENTATIONS WITH SELECTIVE AUGMENTATION
text: This section presents LISA, a simple way to improve robustness to domain shifts or subpopulation shifts. The key idea behind LISA is to encourage the model to alleviate the effects of domain-related spurious correlations by selective data interpolation. Before detailing how to select interpolated samples, we first provide a general formulation for data interpolation.
In LISA, we perform linear interpolation between training samples. Specifically, given samples (xi, yi, di) and (xj , yj , dj) drawn from domains di and dj , we apply mixup (Zhang et al., 2018), a simple data interpolation strategy, separately on the input features and corresponding labels as:
xmix = λxi + (1− λ)xj , ymix = λyi + (1− λ)yj , (2)
where the interpolation ratio λ ∈ [0, 1] is sampled from a Beta distribution Beta(α, β) and yi and yj are one-hot vectors for classification problem. Notice that the mixup approach in equation 2 can be replaced by CutMix (Yun et al., 2019), which shows stronger empirical performance in visionbased applications. In text-based applications, we replace the feature interpolation in equation 2 with Manifold Mixup (Verma et al., 2019), where the interpolation strategy is performed on the output representation of a pre-trained model, e.g., the output of BERT (Devlin et al., 2019).
After obtaining the interpolated features and labels, we replace the original features and labels in ERM with the interpolated ones. Then, the optimization process in equation 1 is reformulated as:
θ∗ := argmin θ∈Θ E{(xi,yi,di),(xj ,yj ,dj)}∼P̂ [ℓ(fθ(xmix), ymix)]. (3)
Without additional selection strategies, vanilla mixup will regularize the model and reduce overfitting (Zhang et al., 2021b), allowing it to attain good in-distribution generalization. However, vanilla mixup may not be able to cancel out spurious correlations, causing the model to still fail at attaining good OOD generalization (see empirical comparisons in Section 4.3 and theoretical discussion in Section 5). In LISA, we instead adopt a new strategy where mixup is only applied across specific domains or groups, which leans towards learning invariant representations and thus better OOD performance. Specifically, the two kinds of sample selection strategies are presented as follows:
• Selection Strategy I: Interpolating samples with the same label. In selection strategy I, LISA interpolates samples with the same label but different domains (i.e., di ̸= dj , yi = yj). This produces datapoints that have both domains partially present, effectively eliminating spurious correlations between domain and label in cases where the pair of domains correlate differently with the label. Additionally, if domain information does not fully reflect the spurious correlations in some datasets, we can also enlarge the interpolation scope to cover more potentially spurious correlations by only interpolating samples within the same class regardless domain information (i.e., yi = yj). As a result, LISA with selection strategy I should learn domain-invariant representations for each class and thus achieve better OOD robustness.
• Selection Strategy II: Interpolating samples with the same domain. Supposing domain information is highly spuriously correlated with the label information, selection strategy II applies the
interpolation strategy on samples with the same domain but different labels, i.e., di = dj , yi ̸= yj . Intuitively, even within the same domain, the model is supposed to generate different predicted labels since the interpolation ratio λ is randomly sampled, corresponding to different labels ymix. This causes the model to make predictions that are less dependent on the domain, again improving OOD robustness.
In LISA, we randomly perform selection strategies I or II during the training process with probability psel and 1−psel for each batch of data, where psel is treated as a hyperparameter in our experiments. The choice of psel depends on the number of domains and the relation between domain information and spurious correlations. Empirically, using selection strategy I only brings much more benefits when there are more domains, and/or the domain information can not fully reflect the spurious correlations. LISA with selection strategy II can benefit the performance when domain information is highly spuriously correlated with the label, where we find a balanced ratio (i.e., psel = 0.5) performs the best. The pseudocode of the training procedure of LISA is shown in Algorithm 1.
Algorithm 1 Training Procedure of LISA Require: Training data, Step size η
1: while not converge do 2: Sample λ ∼ Beta(α, β) 3: Sample a set of samples B1 uniformly from the training data 4: Randomly select a sample selection strategy I or II with the probability psel and 1− psel 5: if use selection strategy I then 6: For each sample (xi, yi, di), find another one (xj , yj , dj) from the dataset with the same label (yi = yj) but different domains (di ̸= dj), and construct set B2. 7: else if use selection strategy II then 8: For each sample (xi, yi, di), find another one (xj , yj , dj) from the same domain (di = dj) but different labels (yi ̸= yj), constructing set B2. 9: Update θ with data λB1 + (1− λ)B2.

heading: 4 EXPERIMENTS
text: In this section, we conduct comprehensive experiments to evaluate the effectiveness of LISA. Specifically, we aim to answer the following questions: Q1: Compared to prior methods, can LISA improve robustness to domain shifts and subpopulation shifts (Section 4.1 and Section 4.2)? Q2: Which aspects of LISA are the most important for improving robustness (Section 4.3)? Q3: How does LISA perform with varying degrees of distribution shifts (Section 4.4)? Q4: Does LISA successfully produce invariant representations (Section 4.5)?
To answer Q1, we compare to ERM, IRM (Arjovsky et al., 2019), MMD (Li et al., 2018), DRNN (Ganin & Lempitsky, 2015), GroupDRO (Sagawa et al., 2020a), DomainMix (Xu et al., 2020), and Fish (Shi et al., 2021). Upweighting (UW) is particularly suitable for subpopulation shifts, so we also use it for comparison. We adopt the same model architectures for all approaches.

heading: 4.1 EVALUATING ROBUSTNESS TO DOMAIN SHIFTS
text: Experimental Setup. To study domain shifts, we study five datasets. Four datasets (Camelyon17, FMoW, RxRx1, and Amazon) are selected from WILDS (Koh et al., 2021), covering real-world distribution shifts across diverse domains (e.g., health, natural language process, and vision). Besides the WILDS data, we also apply LISA on the MetaShift datasets (Liang & Zou, 2021), constructed using the real-world images and natural heterogeneity of Visual Genome (Krishna et al., 2016). We summarize the datasets in Table 8 of Appendix A.1.1, including domain information, evaluation metric, model architecture, and the number of classes. Detailed dataset descriptions and other training details are discussed in Appendix A.1.1 and A.1.2, respectively.
Results. We report the results of domain shifts in Table 1, where the full results that include validation performance and other metrics are listed in Appendix A.1.3. The optimal strategy selection probability psel is set as 1.0 for these domain shifts problems, i.e., only selection strategy I is used.
In addition, we only interpolate samples with the same labels regardless the domain information, which empirically leads to the best performance. According to Table 1, we have two key findings:
• There are no significant performance differences between ERM and other invariant representation learning methods (e.g. IRM, CORAL, DomainMix) on most datasets, which is consistent with the reported results on WILDS (Koh et al., 2021). A potential reason is that the existing domain information may not fully reflects the spurious correlation. For example, in Camelyon17-wilds dataset (Koh et al., 2021), the presence of tumor tissue (i.e., label) mainly depends on the demographic of patients (e.g., race, gender), which shows no significant difference across hospitals (i.e., domain information). This could also explain why only interpolating samples with the same labels regardless the domain information achieves the best performance, which also corroborates our claims in the description of the selection strategy I in Section 3.
• The consistent superiority of LISA outperforms prior methods on all five datasets regardless of the model architecture and dataset types (i.e., image or text), demonstrating its effectiveness in improving OOD robustness by canceling out spurious correlations with augmentation.

heading: 4.2 EVALUATING ROBUSTNESS TO SUBPOPULATION SHIFTS
text: Evaluation Protocol. In subpopulation shifts, we evaluate the performance on four binary classification datasets, including Colored MNIST (CMNIST), Waterbirds (Sagawa et al., 2020a), CelebA (Liu et al., 2015), and Civilcomments (Borkan et al., 2019). We summarize brief data statistics in Table 14 of Appendix A.2.1, covering domain information, model architecture, and class information. Full dataset descriptions of subpopulation shifts are also presented in Appendix A.2.1. Following Sagawa et al. (2020a), in subpopulation shifts, we use the worst-group accuracy to evaluate the performance of all approaches and the domain identifications are highly spurious correlated with the label information. For example, as suggested in Figure 1, 95% images in the Waterbirds dataset have the same background and bird type, i.e., waterbirds in water or landbirds in land. Full hyperparameter settings and training details are listed in Appendix A.2.2.
Results. In Table 2, we report the overall performance of LISA and other methods. Similar to the observations in domain shifts, LISA consistently outperforms prior methods in CMNIST, CelebA, and CivilComments. In Waterbirds, LISA outperforms other invariant representation learning methods (e.g., IRM, CORAL, DomainMix, Fish) and shows similar performance to GroupDRO. These results demonstrate the effectiveness of LISA in improving OOD robustness. In CMNIST, Waterbirds, and CelebA, we find that psel = 0.5 works well for choosing selection strategies I and II, while psel is set as 1.0 in CivilComments. This is not surprising because it might be more beneficial to use the strategy I more often to eliminate domain effects when there are more domains, i.e., eight domains in CivilComments v.s. two domains in others.

heading: 4.3 ABLATION STUDY: IS THE PERFORMANCE GAIN FROM DATA AUGMENTATION?
text: In LISA, we apply selective interpolation strategies on samples either with the same label but different domains or with the same domain but different labels. Here, we explore two substitute interpolation strategies: (1) Vanilla mixup: In Vanilla mixup, we do not add any constraint on the
sample selection, i.e., the mixup is performed on any pairs of samples; (2) In-group mixup: This strategy applies data interpolation on samples with the same labels and from the same domains. Notice that all the substitute interpolation strategies use the same mixup types (e.g., mixup/Manifold Mixup/CutMix) as LISA. Finally, since upweighting (UW) small groups significantly improves performance in subpopulation shifts, we also evaluate UW combined with Vanilla/In-group mixup.
The ablation results of domain shifts and subpopulation shifts are in Table 3 and Table 4, respectively. Furthermore, we also conduct experiments on datasets without spurious correlation in Table 18 of Appendix A.3. From the results, we make the following three key observations. First, compared with Vanilla mixup, the performance of LISA verifies that selective data interpolation does improve the out-of-distribution robustness by canceling out the spurious correlations and encouraging invariant representation learning rather than simply data augmentation. This findings are further strengthened by the results in Table 18, where Vanilla mixup outperforms LISA and ERM without spurious correlations but LISA achieves the best performance with spurious correlations. Second, the superiority of LISA over In-group mixup verifies that only interpolating samples within each group is incapable of eliminating out the spurious information, where In-group mixup still performs the role of data augmentation. Finally, though incorporating UW significantly improves the performance of Vanilla mixup and In-group mixup in subpopulation shifts, LISA still achieves larger benefits than these enhanced substitute strategies, demonstrating its stronger power in improving OOD robustness.
4.4 EFFECT OF THE DEGREE OF DISTRIBUTION SHIFTS
We further investigate the performance of LISA with respect to the degree of distribution shifts. Here, we use MetaShift to evaluate performance, where the distance between training and test domains is measured as the node similarity on a metagraph (Liang & Zou, 2021). To vary the distance between training and test domains, we change the backgrounds of training objects (see full experimental details in Appendix A.1.1). The performance with varied distances is illustrated in Table 5, where the top four best methods (i.e., ERM, GroupDRO, IRM, DomainMix) are reported for compar-
ison. We observe that LISA consistently outperforms other methods under all scenarios. Additionally, another interesting finding is that LISA achieves more substantial improvements with the increases of distance. A potential reason is that the models may rely more heavily on domain correlations when there is a larger distance between training and test domains.

heading: 4.5 ANALYSIS ABOUT LEARNED INVARIANCE
text: Finally, we analyze the invariance learned by LISA. Specifically, we investigate representation-level and predictionlevel invariances below.
Representation-level Invariance. For each label y, assume the hidden representation for each domain d as Hyd . The representation-level invariance IVr is measured by the pairwise KL divergence of distribution P (Hyd ) among all domains as IVr = 1|Y||D|2 ∑ y∈Y ∑ d′,d∈D KL(P (H y D | D = d)|P (HyD | D = d′)), where smaller IVr values indicate that the learned representations are more invariant with respect to the labels. We report the results on CMNIST and MetaShift in Table 6. Our key observations are: (1) Compared with ERM, the invariance of LISA indicates its promise in improving the OOD robustness by encouraging invariant representation learning. (2) LISA has greater invariance than vanilla mixup, validating that the invariant representations are not caused by naive data interpolation. (3) LISA provides more invariant representations than regularization-based methods, i.e., IRM and DomainMix.
Prediction-level Invariance. Motivated by Arjovsky et al. (2019); Krueger et al. (2021), the prediction-level invariance IVp is measured by the variance of test risks across all domains, i.e., IVp = Var({R1(θ), . . . ,RD(θ)}), where D represents the number of test domains. A small IVp represents strong prediction-level invariance. The results on CMNIST and MetaShift are reported in Table 7, where the superiority of LISA verifies that it could also improve the prediction-level invariance.

heading: 5 THEORETICAL ANALYSIS
text: In this section, we provide some theoretical understandings that explain several of the empirical phenomena from the previous experiments and theoretically compare the worst-group errors of three methods: the proposed LISA, ERM, and vanilla mixup. Specifically, we consider a Gaussian mixture model with subpopulation and domain shifts, which has been widely adopted in theory to shed light upon complex machine learning phenomenon such as in Montanari et al. (2019); Zhang et al. (2021c). We also note here that despite the popularity of mixup in practice, the theoretical analysis of how mixup (with or without the selection strategies) affects the misclassification error is still largely unexplored in the literature even in the simple models. As discussed in Section 2, here, we define y ∈ {0, 1} as the label, and d ∈ {B,G} as the domain information. For y ∈ {0, 1} and
d ∈ {B,G}, we consider the following model:
xi|yi = y, di = d ∼ N(µ(y,d),Σ(d)), i = 1, . . . , n(y,d), (4)
where µ(y,d) ∈ Rp is the conditional mean vector and Σ(d) ∈ Rp×p is the covariance matrix. Let n = ∑ y∈{0,1},d∈{B,G} n
(y,d). Let π(y,d) = P(yi = y, di = d), π(y) = P(yi = y), and π(d) = P(di = d).
To account for the spurious correlation brought by domains, we consider µ(y,B) ̸= µ(y,G) in general for y ∈ {0, 1} and the imbalanced case where π(0,B), π(1,G) < 1/4. Moreover, we assume there exists some invariance across different domains. Specifically, we assume
µ(1,B) − µ(0,B) = µ(1,G) − µ(0,G) := ∆ and Σ(G) = Σ(B). According to the theory of Fisher’s linear discriminant analysis rule (Anderson, 1962), the optimal classification rule is linear with slope Σ−1∆. The assumption above implies that (Σ−1∆)⊤x is the (unknown) invariant representation in model equation 4.
Suppose we use some method A and obtain a linear classifier xT b + b0 > 0 from a training data, we will apply it to a test data and compute the worst-group misclassification error, where the misclassification error for domain d and class y is E(y,d)(b, b0) := P(1(xTi b + b0 > 1 2 ) ̸= y|di = d, yi = y), and we denote the worst-group error with the method A as
E (wst) A = max d∈{B,G},y∈{0,1} E(y,d)(bA, b0,A),
where bA and b0,A are the slope and intercept based on the method A. Specifically, A = ERM denotes the ERM method (by minimizing the sum of squares loss on the training data altogether), A = mix denotes the vanilla mixup method (without any selection strategy), and A = LISA denotes the mixup strategy for LISA. We also denote its finite sample version by Ê(wst)A .
Let ∆̃ = E[xi|yi = 1]−E[xi|yi = 0] denote the marginal difference and ξ = ∆ TΣ−1∆̃
∥∆∥Σ∥∆̃∥Σ denote the
correlation operator between the domain-specific difference ∆ and the marginal difference ∆̃ with respect to Σ. We see that smaller ξ indicates larger discrepancy between the marginal difference and the domain-specific difference and therefore implies stronger spurious correlation between the domains and labels. We present the following theorem showing that our proposed LISA algorithm outperforms the ERM and vanilla mixup in the subpopulation shifts setting. Theorem 1 (Worst-group error comparison with subpopulation shifts). Consider n independent samples generated from model (4), π(B) = π(1) = 1/2, π(0,B) = π(1,G) = α < 1/4,
maxy,d ∥µ(y,d)∥2 ≤ C, and Σ is positive definite. Suppose (ξ, α) satisfies that ξ ≤ min{∥∆̃∥Σ∥∆∥Σ , 1}− Cα for some large enough constant C and ∥∆̃∥Σ ≤ √ 2E[λ2i ]
max{3var(λi),1/4} . Then for any psel ∈ [0, 1],
Ê (wst) LISA ≤ min{Ê (wst) ERM , Ê (wst) mix }+OP
( p log n
n +
p
αn
) ,
where p is the dimension of x. Theorem 1 implies that when ξ is small (indicating that the domain has strong spurious correlation with the label) and p = o(αn), the worst-group classification errors of LISA are asymptotically smaller than that of ERM and vanilla mixup. In fact, our analysis shows that LISA yields a classification rule closer to the invariant classification rules by leveraging the domain information.
In the next theorem, we present the mis-classification error comparisons with domain shifts. That is, consider samples from a new unseen domain:
x (0,∗) i ∼ N(µ (0,∗),Σ), x (1,∗) i ∼ N(µ (1,∗),Σ).
Let ∆̃∗ = 2(µ(0,∗) − E[xi]), where E[xi] is the mean of the training distribution, and assume µ(1,∗) − µ(0,∗) = ∆. Let ξ∗ = ∆̃ TΣ−1∆̃∗
∥∆̃∥Σ∥∆∥Σ and γ = ∆
TΣ−1∆̃∗
∥∆̃∥Σ∥∆∥Σ denote the correlation for (∆̃∗, ∆̃)
and for (∆̃∗,∆), respectively, with respect to Σ−1. Let E(wst∗)A = maxy∈{0,1} E (y,∗)(bA, b0,A) and its sample version be Ê(wst∗)A .
Theorem 2 (Mis-classification error comparison with domain shifts). Suppose n samples are independently generated from model (4), π(B) = π(1) = 1/2, π(0,B) = π(1,G) = α < 1/4, maxy,d ∥µ(y,d)∥2 ≤ C and Σ is positive definite. Suppose that (ξ, ξ∗, γ) satisfy that 0 ≤ ξ∗ ≤ γξ and ξ ≤ min{γ2 ∥∆̃∥Σ ∥∆∥Σ , 1} − Cα for some large enough constant C and ∥∆̃∥Σ ≤√
2E[λ2i ]
max{3var(λi),1/4} . Then for any psel ∈ [0, 1],
Ê (wst∗) LISA ≤ min{Ê (wst∗) ERM , Ê (wst∗) mix }+OP
( p log n
n +
p
αn
) .
Similar to Theorem 1, this result shows that when domain has strong spurious correlation with the label (corresponding to small ξ), such a spurious correlation leads to the downgraded performance of ERM and vanilla mixup, while our proposed LISA method is able to mitigate such an issue by selective data interpolation. Proofs of Theorem 1 and Theorem 2 are provided in Appendix B.

heading: 6 RELATED WORK AND DISCUSSION
text: In this paper, we focus on improving the robustness of machine learning models to domain shifts and subpopulation shifts. Here, we discuss related approaches from the following three categories:
Learning Invariant Representations with Domain Alignment. Motivated by unsupervised domain adaptation (Ben-David et al., 2010; Ganin et al., 2016), the first category of works learns invariant representations by aligning representations across domains. The major research line of this category aims to eliminate the domain dependency by minimizing the divergence of feature distributions with different distance metrics, e.g., maximum mean discrepancy (Tzeng et al., 2014; Long et al., 2015), an adversarial loss (Ganin et al., 2016; Li et al., 2018), Wassertein distance (Zhou et al., 2020a). Follow-up works applied data augmentation to (1) generate more domains and enhance the consistency of representations during training (Yue et al., 2019; Zhou et al., 2020b; Xu et al., 2020; Yan et al., 2020; Shu et al., 2021; Wang et al., 2020) or (2) generate new domains in an adversarial way to imitate the challenging domains without using training domain information (Zhao et al., 2020; Qiao et al., 2020; Volpi et al., 2018). Unlike these latter methods, LISA instead focuses on canceling out correlations in the dataset between the domain and the label through selective data interpolation, leading to stronger empirical performance.
Learning Invariant Representations with Invariant Predictors. Beyond using domain alignment to learning invariant representations, recent work aims to further enhance the correlations between the invariant representations and the labels (Koyama & Yamaguchi, 2020). Representatively, motivated by casual inference, invariant risk minimization (IRM) (Arjovsky et al., 2019) aims to find a predictor that performs well across all domains. After IRM, the following works propose stronger regularizers by penalizing the variance of risks across all domains (Krueger et al., 2021), by aligning the gradient across domains (Koyama & Yamaguchi, 2020), by smoothing the cross-domain interpolation paths (Chuang & Mroueh, 2021), or through game-theoretic invariant rationalization criterion (Chang et al., 2020). Instead of using regularization, LISA eliminates spurious correlations in the data directly via data interpolation.
Group Robustness. The last category of methods combats spurious correlations and are particularly suitable for subpopulation shifts. These approaches include directly optimizing the worst-group performance with Distributionally Robust Optimization (Sagawa et al., 2020a; Zhang et al., 2021a; Zhou et al., 2021), generating samples around the minority groups (Goel et al., 2021), and balancing the majority and minority groups via reweighting (Sagawa et al., 2020b) or regularizing (Cao et al., 2019; 2020). Here, LISA proposes a more general strategy based on data augmentation that is suitable for both domain shifts and subpopulation shifts.

heading: 7 CONCLUSION
text: To tackle the distribution shifts, we propose LISA, a simple and efficient algorithm, to improve the out-of-distribution robustness. LISA aims to eliminate the domain-related spurious correlations among the training set by selective sample interpolation. We evaluate the effectiveness of LISA on nine datasets under subpopulation shifts and domain shifts settings, demonstrating its promise. Our theoretical results further strengthen the superiority of LISA by showing smaller worst-group mis-classification error compared with ERM and vanilla mixup.

heading: REPRODUCIBILITY STATEMENT
text: We conduct experiments under the setting of domain shifts and subpopulation shifts problems. In terms of the domain shifts, the results are reported in in Table 1. The dataset details are provided in Appendix A.1.1, and the training details along with the hyperparameter settings are in appendix A.1.2. Then, for the subpopulation shifts, we have included the full results including the error bounds in Table 16. The dataset details are discussed in Appendix A.2.1, while the training details and the hyperparameter settings are in Appendix A.2.2. We will release the code upon publication. Besides, The detailed proof of Theorem 1 and Theorem 2 are provided in Appendix B.

heading: A ADDITIONAL EXPERIMENTS

heading: A.1 DOMAIN SHIFTS

heading: A.1.1 DATASET DETAILS
text: In this section, we provide detailed descriptions of datasets used in the experiments of domain shifts and report the data statistics in Table 8.
Camelyon17 We use Camelyon17 from the WILDS benchmark (Koh et al., 2021; Bandi et al., 2018), which provides 450, 000 lymph-node scans sampled from 5 hospitals. Camelyon17 is a medical image classification task where the input x is a 96 × 96 image and the label y is whether there exists tumor tissue in the image. The domain d denotes the hospital that the patch was taken from. The training dataset is drawn from the first 3 hospitals, while out-of-distribution validation and out-of-distribution test datasets are sampled from the 4-th hospital and 5-th hospital respectively.
FMoW The FMoW dataset is from the WILDS benchmark (Koh et al., 2021; Christie et al., 2018) — a satellite image classification task which includes 62 classes and 80 domains (16 years x 5 regions). Concretely, the input x is a 224 × 224 RGB satellite image, the label y is one of the 62 building or land use categories, and the domain d represents the year that the image was taken as well as its corresponding geographical region – Africa, the Americas, Oceania, Asia, or Europe. The train/test/validation splits are based on the time when the images are taken. Specifically, images taken before 2013 are used as the training set. Images taken between 2013 and 2015 are used as the validation set. Images taken after 2015 are used for testing.
RxRx1 RxRx1 (Koh et al., 2021; Taylor et al., 2019) from the WILDS benchmark is a cell image classification task. In the dataset, some cells have been genetically perturbed by siRNA. The goal of RxRx1 is to predict which siRNA that the cells have been treated with. Concretely, the input x is an image of cells obtained by fluorescent microscopy, the label y indicates which of the 1, 139 genetic treatments the cells received, and the domain d denotes the experimental batches. Here, 33 different batches of images are used for training, where each batch contains one sample for each class. The out-of-distribution validation set has images from 4 experimental batches. The out-of-distribution test set has 14 experimental batches. The average accuracy on out-of-distribution test set is reported.
Amazon Each task in the Amazon benchmark (Koh et al., 2021; Ni et al., 2019) is a multi-class sentiment classification task. The input x is the text of a review, the label y is the corresponding star rating ranging from 1 to 5, and the domain d is the corresponding reviewer. The training set has 245, 502 reviews from 1, 252 reviewers, while the out-of-distribution validation set has 100, 050 reviews from another 1, 334 reviewers. The out-of-distribution test set also has 100, 050 reviews from the rest 1, 252 reviewers. We evaluate the models by the 10th percentile of per-user accuracies in the test set.
MetaShift We use the MetaShift (Liang & Zou, 2021), which is derived from Visual Genome (Krishna et al., 2016). MetaShift leverages the natural heterogeneity of Visual Genome to provide many distinct data distributions for a given class (e.g. “cats with cars” or “cats in bathroom” for the “cat” class). A key feature of MetaShift is that it provides explicit explanations of the dataset correlation and a distance score to measure the degree of distribution shift between any pair of sets. We adopt the “Cat vs. Dog” task in MetaShift, where we evaluate the model on the “dog(shelf )” domain with 306 images, and the “cat(shelf )” domain with 235 images. The training data for the “Cat” class is the cat(sofa + bed), including cat(sofa) domain and cat(bed) domain. MetaShift provides 4 different sets of training data for the “Dog” class in an increasingly challenging order, i.e., increasing the amount of distribution shift. Specifically, dog(cabinet + bed), dog(bag + box), dog(bench + bike), dog(boat + surfboard) are selected for training, where their corresponding distances to dog(shelf ) are 0.44, 0.71, 1.12, 1.43.

heading: A.1.2 TRAINING DETAILS
text: Follow WILDS Koh et al. (2021), we adopt pre-trained DenseNet121 (Huang et al., 2017) for Camelyon17 and FMoW datasets, ResNet-50 (He et al., 2016) for RxRx1 and MetaShift datasets, and DistilBert (Sanh et al., 2019) for Amazon datasets.
In each training iteration, we first draw a batch of samples B1 from the training set. With B1, we then select another sample batch B2 with same labels as B1 for data interpolation. The interpolation ratio λ is drawn from the distribution Beta(2, 2). We use the same image transformers as Koh et al. (2021), and all other hyperparameter settings are listed in Table 9.

heading: A.1.3 FULL RESULTS OF WILDS DATA
text: Follow Koh et al. (2021), we reported more results on WILDS datasets in Table 10 - Table 13, including validation performance and the results of other metrics. According to these additional results, we could see that LISA outperforms other baseline approaches in all scenarios. Particularly, we here discuss two additional findings: (1) In Camelyon dataset, the test data is much more visually distinctive compared with the validation data, resulting in the large gap (∼ 10%) between validation and test performance of ERM (see Table 10). However, LISA significantly reduces the performance gap between the validation and test sets, showing its promise in improving OOD robustness; (2) In Amazon dataset, though LISA performs worse than ERM in average accuracy, it achieves the best accuracy at the 10th percentile, which is regarded as a more common and important metric to evaluate whether models perform consistently well across all users (Koh et al., 2021).

heading: A.2 SUBPOPULATION SHIFTS

heading: A.2.1 DATASET DETAILS
text: We detail the data descriptions of subpopulation shifts below and report the detailed data statistics in Table 14.
Colored MNIST (CMNIST): We classify MNIST digits from 2 classes, where classes 0 and 1 indicate original digits (0,1,2,3,4) and (5,6,7,8,9). The color is treated as a spurious attribute. Concretely, in the training set, the proportion between red samples and green samples is 8:2 in class 0, while the proportion is set as 2:8 in class 1. In the validation set, the proportion between green and red samples is 1:1 for all classes. In the test set, the proportion between green and red samples is 1:9 in class 0, while the ratio is 9:1 in class 1. The data sizes of train, validation, and test sets are 30000, 10000, and 20000, respectively.
Waterbirds (Sagawa et al., 2020a): The Waterbirds dataset aims to classify birds as “waterbird” or “landbird”, where each bird image is spuriously associated with the background “water” or “land”. Waterbirds is a synthetic dataset where each image is composed by pasting a bird image sampled from CUB dataset (Wah et al., 2011) to a background drawn from the Places dataset Zhou et al. (2017). The bird categories in CUB are stratified as land birds or water birds. Specifically, the following bird species are selected to construct the waterbird class: albatross, auklet, cormorant, frigatebird, fulmar, gull, jaeger, kittiwake, pelican, puffin, tern, gadwall, grebe, mallard, merganser, guillemot, or Pacific loon. All other bird species are combined as the landbird class. We define (land background, waterbird) and (water background, landbird) are minority groups. There are 4,795 training samples while only 56 samples are “waterbirds on land” and 184 samples are “landbirds on water”. The remaining training data include 3,498 samples from “landbirds on land”, and 1,057 samples from “waterbirds on water”.
CelebA (Liu et al., 2015; Sagawa et al., 2020a): For the CelebA data (Liu et al., 2015), we follow the data preprocess procedure from Sagawa et al. (2020a). CelebA defines a image classification task where the input is a face image of celebrities and the classification label is its corresponding hair color – “blond” or “not blond.” The label is spuriously correlated with gender, i.e., male or female. In CelebA, the minority groups are (blond, male) and (not blond, female). The number of
samples for each group are 71,629 “dark hair, female”, 66,874 “dark hair, male”, 22,880 “blond hair, female”, 1,387 “blond hair, male”.
CivilComments (Borkan et al., 2019; Koh et al., 2021): We use CivilComments from the WILDS benchmark (Koh et al., 2021). CivilComments is a text classification task, aiming to predict whether an online comment is toxic or non-toxic. The spurious domain identifications are defined as the demographic features, including male, female, LGBTQ, Christian, Muslim, other religion, Black, and White. CivilComments contains 450,000 comments collected from online articles. The number of samples for training, validation, and test are 269,038, 45,180, and 133,782, respectively. The readers may kindly refer to Table 17 in Koh et al. (2021) for the detailed group information.

heading: A.2.2 TRAINING DETAILS
text: We adopt pre-trained ResNet-50 (He et al., 2016) and BERT (Sanh et al., 2019) as the model for image data (i.e., CMNIST, Waterbirds, CelebA) and text data (i.e., CivilComments), respectively. In each training iteration, we sample a batch of data per group. For sample selection strategy I, we randomly apply mixup on sample batches with the same labels but different domains. For sample selection strategy II, we instead apply mixup on sample batches with the same domain but different labels. The interpolation ratio λ is sampled from the distribution Beta(2, 2). All hyperparameters are listed in Table 15.

heading: A.2.3 ADDITIONAL RESULTS
text: In this section, we have added the full results of subpopulation shifts in Table 16 and Table 17.

heading: A.3 RESULTS ON DATASETS WITHOUT SPURIOUS CORRELATIONS
text: In order to analyze the factors that lead to the performance gains of LISA, we conduct experiments on datasets without spurious correlations. To be more specific, we balance the number of samples for each group under the subpopulation shifts setting. The results of ERM, Vanilla mixup and LISA on CMNIST, Waterbirds and CelebA are reported in Table 18. The results show that LISA performs similarly compared with ERM when datasets do not have spurious correlations. If there exists any spurious correlation, LISA significantly outperforms ERM. Another interesting finding is that Vanilla mixup outperforms LISA and ERM without spurious correlations, while LISA achieves the best performance with spurious correlations. This finding strengthens our conclusion that the performance gains of LISA are caused by eliminating spurious correlations rather than data augmentation.

heading: B PROOFS OF THEOREM 1 AND THEOREM 2
text: Outline of the proof. We will first find the mis-classification errors based on the population version of OLS with different mixup strategies. Next, we will develop the convergence rate of the empirical OLS based on n samples towards its population version. These two steps together give us the empirical mis-classification errors of different methods. We will separately show that the upper bounds in Theorem 1 and Theorem 2 hold for two strategies of LISA and hence hold for any psel ∈ [0, 1]. Let L1 denote selection strategy I of LISA method and L2 denote selection strategy II of LISA method.
Let π1 = P(yi = 1) and π0 = P(yi = 0) denote the marginal class proportions in the training samples. Let πB = P(di = B) and πG = P(di = G) denote the marginal subpopulation proportions in the training samples. Let πG|1 = P(di = G|yi = 1) and define πG|0, πB|1, and πB|0 similarly.
We consider the setting where α := π(1,G) = π(0,B) is relatively small and π(1) = π(0) = π(G) = π(B) = 1/2.

heading: B.1 DECOMPOSING THE LOSS FUNCTION
text: Recall that ∆ = µ(1,G) − µ(0,G) = µ(1,B) − µ(0,B). We further define ∆̃ = µ(1) − µ(0), θ(G) = µ(0,G) −E[xi], and θ(B) = µ(0,B) −E[xi]. For the mixup estimators, we will repeatedly use the fact that λi has a symmetric distribution with support [0, 1].
For ERM estimator based on (X, y), where b0 = 12 −E[xi] T b, we have
(µ(0,G))T b+ b0 = (µ (0,G) −E[xi])T b+
1
2
= (θ(G))T b+E[yi]
(µ(1,G))T b+ b0 = (µ (1,G) −E[xi])T b+
1
2
= ∆T b+ (θ(G))T b+E[yi],
Notice that based on the estimator b, b0
E(1,d)(b, b0) = Φ( −∆T b− (θ(d))T b√
bTΣb ) and E(0,d)(b, b0) = Φ( (θ(d))T b√ bTΣb ).

heading: B.2 CLASSIFICATION ERRORS OF FOUR METHODS WITH INFINITE TRAINING SAMPLES
text: We first provide the limit of the classification errors when n → ∞.

heading: B.2.1 BASELINE METHOD: ERM
text: For the training data, it is easy to show that
var(x) = E[var(x|y)] + var(E[x|y]) = Σ +E[var(E[x|y,D]|y)] + var((µ(1) − µ(0))y) = Σ +E[var(µ(0,B) − µ(0,G))1(D = B)|y)] + ∆̃⊗2π(1)π(0)
= Σ+ 1
2 (µ(0,B) − µ(0,G))⊗2(πB|1πG|1 + πB|0πG|0) + ∆̃⊗2π(1)π(0)
cov(x, y) = cov(E[x|y], y) = cov(µ(0) + ∆̃y, y)
= cov(∆̃y, y) = ∆̃π(1)π(0)
For a0 = 12 (πB|1πG|1 + πB|0πG|0) and ∆0 = µ (0,G) − µ(0,B), the ERM has slope and intercept being
b = var(x)−1cov(x, y)
∝ (Σ + a0∆⊗20 )−1∆̃
= Σ−1∆̃− Σ−1∆0 · a0∆̃ TΣ−1∆0 1 + a0∆T0 Σ −1∆0
b0 = E[y]−E[xT b]. In the extreme case where π0,B = π1,G = 0, we have
∆̃ = µ(1,B) − µ(0,G), θ(G) = −1 2 ∆̃, θ(B) = 1 2 ∆̃−∆, and ∆0 = ∆− ∆̃.
Hence,
E (wst) 0 = max{Φ
( ( 12∆̃−∆)
T b √ bTΣb
) ,Φ ( − 12∆̃
T b √ bTΣb
) }, (5)
where b is computed via ERM.

heading: B.2.2 BASELINE METHOD: VANILLA MIXUP
text: The vanilla mixup does not use the group information. Let i1 be a random draw from {1, . . . , n}. Let i2 be a random draw from {1, . . . , n} independent of i1. Let
ỹi = λiyi1 + (1− λi)yi2
and x̃i = λixi1 + (1− λi)xi2 . We can find that
cov(x̃i, ỹi) = cov(λixi1 + (1− λi)xi2 , λiyi1 + (1− λi)yi2) = cov(λixi1 , λiyi1) + cov((1− λi)xi2 , (1− λi)yi2) = (E[λ2i ] +E[(1− λi)2])cov(xi, yi).
cov(x̃i) = (E[λ 2 i ] +E[(1− λi)2])cov(xi).
Hence, the population-level slope is the same as the slope in the benchmark method. It is easy to show that the population-level intercept is also the same. Hence,
E (wst) mix = E (wst) 0 .

heading: B.3 LISA WITH SELECTION STRATEGY (LISA-II): MIXUP WITHIN EACH CLASS
text: Define x (λ) i = λix (yi,G) i1
+ (1− λi)x(yi,B)i2 , where i1 is a random draw from {l : yl = yi, Dl = G} and i2 is a random draw from {l : yl = yi, Dl = B}. Then we perform OLS based on (x(λ)i , yi), i = 1, . . . , n. We can calculate that
cov(x (λ) i , yi) = cov(E[x (λ) i |yi], yi) = cov(
1 2 µ(yi,G) + 1 2 µ(yi,B), yi)
= var(yi)∆ = π (1)π(0)∆
cov(x (λ) i ) = E[cov(x (λ) i |yi, λi)] + cov(E[x (λ) i |yi, λi])
= 2E[λ2i ]Σ + cov(λi(µ (0,G) − µ(0,B)) + ∆yi) = 2E[λ2i ]Σ + var(λi)(µ (0,G) − µ(0,B))⊗2 + π(1)π(0)∆⊗2.
Notice that
E[x (λ) i ] =
1 4 (µ(0,G) + µ(1,G) + µ(0,B) + µ(1,B)) = 1 2 (µ(0,G) + µ(1,B)) = E[xi].
For aL1 = var(λi)/(2E[λ2i ]) and ∆0 = µ (0,G) − µ(0,B), the OLS has slope and intercept being
b = var(x (λ) i ) −1cov(x (λ) i , y)
∝ (Σ + var(λi) 2E[λ2i ] (µ(0,G) − µ(0,B))⊗2)−1∆
∝ Σ−1∆− Σ−1∆0 · aL1∆ TΣ−1∆0 1 + aL1∆T0 Σ −1∆0
b0 = E[y]−E[(x(λ))T b].
E (wst) L1 = max{Φ
( ( 12∆̃−∆)
T b √ bTΣb
) ,Φ ( − 12∆̃
T b √ bTΣb
) }, (6)
where b is computed based on (x(λ)i , yi), i = 1, . . . , n.

heading: B.4 LISA WITH SELECTION STRATEGY II (LISA-II): MIXUP WITHIN EACH DOMAIN
text: The interpolated sample can be written as
(ỹi, x̃i) = (λi, λix (1,G) i1 + (1− λi)x(0,G)i2 ) if di = G
(ỹi, x̃i) = (λi, λix (1,B) i1 + (1− λi)x(0,B)i2 ) if di = B,
where i1 is a random draw from {l : dl = di, yi = 1} and i2 is a random draw from {l : dl = di, yi = 0}. We consider regress ỹi on x̃i.
cov(x̃i, ỹi|di = G) = cov(E[x̃i|ỹi, di = G], ỹi|di = G) = var(ỹi)(µ(1,G) − µ(0,G)) var(x̃i|di = G) = E[var(x̃i|, λi, Di = G)|di = G] + var(E[x̃i|, λi, di = G]|Di = G]
= 2E[λ2i ]Σ + var(λiµ (1,G) + (1− λi)µ(0,G)|di = G) = 2E[λ2i ]Σ + var(ỹi)∆ ⊗2.
We further have
cov(x̃i, ỹi) = E[cov(x̃i, ỹi|di)] + cov(E[x̃i|di],E[ỹi|di])
= cov(x̃ (G) i , ỹ (G) i )π (G) + cov(x̃ (B) i , ỹ (B) i )π (B)
= var(ỹi)(µ (1,G) − µ(0,G))π(G) + var(ỹi)(µ(1,B) − µ(0,B))π(B)
= var(ỹi)∆.
Moreover,
var(x̃i) = E[var(x̃i|di)] + var(E[x̃i|di])
= var(x̃ (G) i )π (G) + var(x̃(B))π(B) + (E[x̃(G)]−E[x̃(B)])⊗2π(G)π(B) = 2E[λ2i ]Σ + var(λi)∆ ⊗2 + (µ(0,G) − µ(0,B))⊗2π(G)π(B).
Slope:
b = var(x̃i) −1cov(x̃i, ỹi)
∝ (Σ + aL2∆⊗20 )−1∆
= Σ−1∆− Σ−1∆0 · aL2(∆0)
TΣ−1∆
1 + aL2(∆0)TΣ−1∆0 ,
where aL2 = π (B)π(G)
2E[λ2i ] .
Moreover, b0 = E[ỹi]−E[x̃i]T b = 12 −E[x̃i] T b. Notice that
E[x̃i] = 1
4 (µ(0,G) + µ(1,G) + µ(0,B) + µ(1,B))
= 1
4 (2µ(0,G) +∆+ 2µ(1,B) −∆)
= 1
2 (µ(0,G) + µ(1,B)) = E[xi].
Hence,
E (wst) L2 = max{Φ
( ( 12∆̃−∆)
T b √ bTΣb
) ,Φ ( − 12∆̃
T b √ bTΣb
) }, (7)
where b is computed based on (x̃i, ỹi), i = 1, . . . , n.
Method comparison. We only need to compare (5), (6), and (7).
For the ERM, 0 ≤ a0 ≤ 2α and
b = (1 + a0∆̃ TΣ−1∆0 1 + a0∆T0 Σ −1∆0 )Σ−1∆̃− a0∆̃ TΣ−1∆0 1 + a0∆T0 Σ −1∆0 Σ−1∆
∝ Σ−1∆̃− a0∆̃ TΣ−1∆0
1 + a0∆T0 Σ −1∆0 + a0∆̃TΣ−1∆0
Σ−1∆
∝ Σ−1∆̃− a0∆̃ TΣ−1∆0
1 + a0∆TΣ−1∆0 Σ−1∆.
Let c0 = a0∆̃ TΣ−1∆0 1+a0∆TΣ−1∆0 and c1 = |c0|∥∆∥Σ/∥∆̃∥Σ. For simplicity, let ∥v∥Σ = vTΣ−1v. We first lower bound it via
cor(bERM, ∆̃) = bT ∆̃
∥∆̃∥Σ √ bTΣb
= ∆̃TΣ−1∆̃− c0∆TΣ−1∆̃
∥∆̃∥Σ √ bTΣb
≥ ∆̃ TΣ−1∆̃ ∥∆̃∥Σ(∥∆̃∥Σ + |c0|∥∆∥Σ) − |c0∆ TΣ−1∆̃| ∥∆̃∥Σ √ bTΣb
≥ 1 1 + |c0|∥∆∥Σ/∥∆̃∥Σ − c0ξ∥∆∥Σ ∥∆̃∥Σ − c0∥∆∥Σ
≥ 1− (1 + ξ)c1 − c 2 1
1− c21 = 1− Cα.
Similarly, we have
cor(bERM,∆) = bT∆
∥∆∥Σ √ bTΣb
= ∆TΣ−1∆̃− c0∆TΣ−1∆
∥∆∥Σ √ bTΣb
≤ ∆̃ TΣ−1∆
∥∆∥Σ(∥∆̃∥Σ ± c0∥∆∥Σ) + |c0∆TΣ−1∆| (∥∆̃∥Σ − c0∥∆∥Σ)∥∆∥Σ
≤ 1 1± c0∥∆∥Σ/∥∆̃∥Σ ξ + c0∥∆∥Σ/∥∆̃∥Σ 1− c0∥∆∥Σ/∥∆̃∥Σ
≤ ( ξ 1± c1 − c1 1− c1 )∥∆∥Σ.
Hence,
E (wst) ERM ≥ max
{ Φ(( 1
2 − Cα)∥∆̃∥Σ − (ξ − Cα)∥∆∥Σ),Φ((−
1 2 + Cα)∥∆̃∥Σ)
} (8)
for some constant C depending on the true parameters.
For method LISA-I, using the fact that ∆0 = ∆− ∆̃,
bL1 ∝ (1− aL1∆ TΣ−1∆0 1 + aL1∆T0 Σ −1∆0 )Σ−1∆+ aL1∆ TΣ−1∆0 1 + aL1∆T0 Σ −1∆0 Σ−1∆̃
∝ Σ−1∆̃ + cL1Σ−1∆
for
cL1 = 1 + aL1∆
T 0 Σ −1∆0 − aL1∆TΣ−1∆0 aL1∆TΣ−1∆0 .
Hence,
cor(bL1, ∆̃) = ∆̃T bL1 ∥∆̃∥Σ √ bTL1ΣbL1 = ∥∆̃∥Σ + cL1ξ∥∆∥Σ ∥∆̃ + cL1∆∥Σ
cor(bL1,∆) = bTL1∆ ∥∆∥Σ √ bTL1ΣbL1 = ξ∥∆̃∥Σ∥∆∥Σ + cL1∥∆∥2Σ ∥∆∥Σ∥∆̃ + cL1∆∥Σ .
To have E(wst)L1 ≤ E (wst) ERM , it suffices to require that (− 12 − Cα)∥∆̃∥Σ ≤ ( 1 2 − Cα)∥∆̃∥Σ − (ξ + Cα)∥∆∥Σ and 1
2 cor(bL1, ∆̃)∥∆̃∥Σ − cor(bL1,∆)∥∆∥Σ ≤ (
1 2 − Cα)∥∆̃∥Σ − (ξ + Cα)∥∆∥Σ
− 1 2 cor(bL1, ∆̃)∥∆̃∥Σ ≤ ( 1 2 − Cα)∥∆̃∥Σ − (ξ + Cα)∥∆∥Σ.
A sufficient condition is
ξ ≤ (1 2 + 1 2 cor(bL1, ∆̃)) ∥∆̃∥Σ ∥∆∥Σ − Cα, cor(bL1,∆) ≥ ξ + Cα, cor(bL1, ∆̃) ≤ 1− 2Cα.
We can find that a further sufficient condition is
ξ ≤ ∥∆̃∥Σ ∥∆∥Σ − Cα, cL1 > 0, ξ ≤ ∥∆̃ + cL1∆∥Σ − ∥∆̃∥Σ cL1∥∆∥Σ − ϵ1α (9)
∥∆̃ + cL1∆∥Σ ≥ ∥∆̃∥Σ, ξ ≤ cL1∥∆∥Σ
∥∆̃ + cL1∆∥Σ − ∥∆̃∥Σ − ϵ1α (10)
ξ ≤ (1 2 + 1 2 cor(bL1, ∆̃)) ∥∆̃∥Σ ∥∆∥Σ − Cα. (11)
We first find sufficient conditions for the statements in (9) and (10). Parameterizing t = cL1∥∆∥Σ/∥∆̃∥Σ, we further simplify the condition in (9) and (10) as
ξ ≤ ∥∆̃∥Σ ∥∆∥Σ − Cα, t > 0, − t 2 ≤ ξ ≤ t
ξ ≤ √ 1 + t2 + 2tξ − 1
t − ϵ1α, ξ ≤
1 + √ 1 + t2 + 2tξ
t+ 2ξ − ϵ1α.
We only need to require
t ≥ 2 and ξ ≤ min{∥∆̃∥Σ ∥∆∥Σ , 1} − Cα.
Some tedious calculation shows that t ≥ 2 can be guaranteed by 1
2 ∥∆∥Σ ≤ ∥∆̃∥Σ ≤ 1√ 3aL1 or 1 2 ∥∆∥Σ ≥ ∥∆̃∥Σ.
It is left to consider the constraint in (11). Notice that it holds for any ξ ≤ 0. When ξ > 0, we can see
cor(bL1, ∆̃) = ∥∆̃∥Σ + ξcL1∥∆∥Σ
∥∆̃ + cL1∆∥Σ = 1 + tξ√ 1 + t2 + 2tξ
≥ 1 + tξ 1 + t ≥ ξ.
Hence, it suffices to guarantee that
(1− 1 2 ∥∆̃∥Σ ∥∆∥Σ )ξ < 1 2 ∥∆̃∥Σ ∥∆∥Σ − Cα.
If ∥∆̃∥Σ/∥∆∥Σ ≥ 2, then LHS is negative and it holds. If 1 ≤ ∥∆̃∥Σ/∥∆∥Σ < 2, then the inequality becomes ξ ≤ 1−Cα. If ∥∆̃∥Σ/∥∆∥Σ < 1, then the inequality becomes ξ ≤ ∥∆̃∥Σ∥∆∥Σ −Cα. Because we have required ξ ≤ min{∥∆̃∥Σ∥∆∥Σ , 1} − Cα for some large enough C, the constraint (11) always holds. To summarize, EL1 ≤ EERM given that ξ ≤ min{∥∆̃∥Σ∥∆∥Σ , 1} − Cα for some large enough C and ∥∆̃∥Σ ≤ 1√3aL1 .
For method LISA-II, we can similarly show that EL2 ≤ EERM given that ξ ≤ min{∥∆̃∥Σ∥∆∥Σ , 1} − Cα for some large enough C and ∥∆̃∥Σ ≤ 1√3aL2 .

heading: B.5 FINITE SAMPLE ANALYSIS
text: The empirical loss can be written as
P(1((x G) i ) T b̂+ b̂0 > 1
2 ) ̸= y(G)i ) (12)
= 1
2 P((x
G) i ) T b̂+ b̂0 > 1
2 |y(G)i = 0) +
1 2 P((x G) i ) T b̂+ b̂0 < 1 2 |y(G)i = 1),
where
P((x G) i ) T b̂+ b̂0 > 1
2 |y(G)i = 0) = Φ(−
1 2 − (µ (0,G))T b̂− b̂0√ b̂TΣb̂ ).
P((x G) i ) T b̂+ b̂0 < 1
2 |y(G)i = 1) = Φ(
1 2 − (µ (1,G))T b̂− b̂0√ b̂TΣb̂ ).
First notice that b̂0 = ȳ − x̄T b̂.
We have
(µ(0,G))T b̂+ b̂0 = (µ (0,G) − x̄)T b̂+ ȳ
= (µ(0,G) −E[xi])T b̂+ 1 2 + {(ȳ − x̄T b̂)− (E[yi]−E[xi]T b̂)}︸ ︷︷ ︸
R1
(µ(1,G))T b̂+ b̂0 = (µ (1,G) − x̄)T b̂+ ȳ
= ∆T b̂+ (µ(0,G) −E[xi])T b̂+ 1
2 +R1.
Therefore, according to (12),
1 2 Φ(−
1 2 − (µ (0,G))T b̂− b̂0√ b̂TΣb̂ ) + 1 2 Φ( 1 2 − (µ (1,G))T b̂− b̂0√ b̂TΣb̂ )
= 1
2 Φ( (θ(G))T b̂+R1√ b̂TΣb̂ ) + 1 2 Φ(−∆+ (θ (G))T b̂+R1√ b̂TΣb̂ )
= 1
2 Φ( (θ(G))T b̂+R1√ b̂TΣb̂ ) + 1 2 Φ(− (θ (G))T b̂+R1√ b̂TΣb̂ )
−
{ 1
2 Φ(− (θ (G))T b̂+R1√ b̂TΣb̂ )− 1 2 Φ(−∆+ (Θ (G))T b̂+R1√ b̂TΣb̂ )
}
= 1
2 −
{ 1
2 Φ(− (θ (G))T b̂+R1√ b̂TΣb̂ )− 1 2 Φ(−∆ T b̂+ (θ(G))T b̂+R1√ b̂TΣb̂ )
} .
Then the mis-classification error can be written as
1 2 − 1 2
{ Φ(
(θ(G))T b̂+R1√ b̂TΣb̂ )− Φ((θ (G))T b̂−∆T b̂+R1√ b̂TΣb̂ ) } ︸ ︷︷ ︸
L̂(b̂)
. (13)
Larger the L̂(b̂), smaller the mis-classification error.
We first find that
L̂(b̂)− L(b) ≤ C | (θ (G))T b̂+R1√
b̂TΣb̂ − (θ (G))T b√ bTΣb
|︸ ︷︷ ︸ T1
+C | (θ (G))T b̂−∆T b̂+R1√
b̂TΣb̂ − (θ (G))T b−∆T b√ bTΣb
|︸ ︷︷ ︸ T2 .
In the event that
∥Σ1/2(b̂− b)∥2 = o(1) max y,d ∥µ(y,d)∥2 ≤ C, Σ is positive definite.
for the denominator, we have
|bTΣb− b̂TΣb̂| ≤ (2∥Σ1/2b∥2 + ∥Σ1/2(b̂− b)∥2)∥Σ1/2(b̂− b)∥2 ≤ 2(1 + o(1))∥Σ1/2b∥2∥Σ1/2(b̂− b)∥2
| √ b̂TΣb̂− √ bTΣb| ≤ |b̂
TΣb̂− bTΣb|√ b̂TΣb̂+ √ bTΣb
≤ 2(1 + o(1))∥Σ1/2(b̂− b)∥2.
For the numerator, we have
|1 2 ∆̃T b̂+R1 − 1 2 ∆̃T b| ≤ |R1|+ 1 2 ∥Σ−1/2∆̃∥2∥Σ1/2(b̂− b)∥2.
We arrive at
T1 ≤ (1 + o(1)) |R1|+ 12∥Σ −1/2∆̃∥2∥Σ1/2(b̂− b)∥2 ∥Σ1/2b∥2 + (1 + o(1)) |∆̃T b|√ bTΣb ∥Σ1/2(b̂− b)∥2√ bTΣb .
T2 ≤(1 + o(1)) |R1|+ 12 (∥Σ −1/2∆̃∥2 + ∥Σ−1/2∆∥2)∥Σ1/2(b̂− b)∥2 ∥Σ1/2b∥2
+ (1 + o(1)) | 12∆̃ T b−∆T b| √ bTΣb ∥b̂− b∥2√ bTΣb .
Moreover R1 ≤ ∥b̂− b∥2 +OP ( 1√n ). To summarize,
|L̂(b̂)− L(b)| ≲ (1 + o(1))(∥b̂− b∥2 + 1√ n ).
In the following, we will upper bound ∥b̂− b∥2 for each method. For the ERM method,
b̂ = {(X − X̄)T (X − X̄)}−1(X − X̄)T (y − ȳ). It is easy to show that
∥b̂− b∥22 = OP ( p ∑N
i=1 var(yi|xi) N2 ) = OP ( p N ).
For the vanilla mixup method, we first see that
1
n n∑ i=1 x̃i = 1 n n∑ i=1 (λixi1 + (1− λi)xi2) = x̄+OP (n−1/2) = µ+OP (n−1/2)
1
n n∑ i=1 ỹi = π (1) +OP (n −1/2).
Next,
1
n n∑ i=1 x̃iỹi = 1 n n∑ i=1 { λ2ixi1yi1 + (1− λi)2xi2yi2 + λi(1− λi)xi1yi2 + λi(1− λi)xi2yii } 1
n n∑ i=1 x̃iỹi −E[x̃iỹi] = 1 n n∑ i=1
x̃iỹi −E[x̃iỹi|X, y]︸ ︷︷ ︸ E1 +E[x̃iỹi|X, y]−E[x̃iỹi]︸ ︷︷ ︸ E2 .
For E2,
E2 = 2E[λ2i ]
n n∑ i=1 xiyi −E[x̃iỹi] = 2E[λ2i ]E[xiyi].
Hence, ∥E2∥22 = OP ( p
n ).
For E1, conditioning on (X, y), λ2ixi1yi1 − E[λ2i ]
n ∑n i=1 xiyi are independent sub-Gaussian vectors.
The sub-Gaussian norm of 1N ∑n i=1 λ 2 ixi1,jyi1 − E[λ2i ] n ∑n i=1 xi,jyi (conditioning on (X, y)) can be
upper bounded by cmaxi≤N |xi,j |/ √ n. Hence
P(∥E1∥2 ≥ t|X, y) ≤ 2 exp{− c2nt
2
maxpj=1 maxi≤N x 2 i,j
}.
As xi,j are Gaussian distributed, we know that
P( p∑ j=1 max i≤n x2i,j ≥ p log n) ≤ exp{−c3 log n}.
Hence, with probability at least 1− exp(−c1 log n),
E1 ≤ Cp log n
n .
To summarize,∥∥∥∥∥ 1n n∑
i=1
x̃iỹi − ( 1
n n∑ i=1 x̃i)( 1 n n∑ i=1 ỹi)− cov(x̃i, ỹi) ∥∥∥∥∥ 2
2
= OP ( p log n
n ).
Similarly, we can show that∥∥∥∥∥ 1n n∑
i=1
x̃ix̃ T i − (
1
n n∑ i=1 x̃i)( 1 n n∑ i=1 x̃i) T − cov(x̃i) ∥∥∥∥∥ 2
2
= OP ( p log n
n ).
Hence,
∥b̂− b∥22 = OP ( p log n
n ).
For the LISA-I, we first see that
1
n n∑ i=1 x (λ) i = 1 n ∑ yi=1 (λix (1,G) i1 + (1− λi)x(1,B)i2 ) + 1 n ∑ yi=0 (λix (0,G) i1 + (1− λi)x(0,B)i2 )
= 1
2 (x̄(1,G) + x̄(1,B))π̂1 +
1 2 (x̄(0,G) + x̄(0,B))π̂0
We have
1 n (X(λ))T y − ȳ 1 n n∑ i=1 x (λ) i − cov(x (λ) i , yi) = 1 n (X(λ))T y − ȳ 1 n n∑ i=1 x (λ) i − cov(x
(λ) i , yi|X, y)︸ ︷︷ ︸
E1
+ cov(x (λ) i , yi|X, y)− cov(x (λ) i , yi)︸ ︷︷ ︸
E2
For E2,
E2 = π̂1 2 (x̄(1,G) + x̄(1,B))− π̂1( 1 2 (x̄(1,G) + x̄(1,B))π̂1 + 1 2 (x̄(0,G) + x̄(0,B))π̂0)− cov(x(λ)i , yi)
= 1
2 (x̄(1,G) + x̄(1,B) − x̄(0,G) − x̄(0,B))π̂1π̂0 − π(1)π(0)∆.
It is easy to show that
∥E2∥22 = OP (
p
miny,e n(y,e)
) .
For E1, conditioning on X and y, x (λ) i yi − E[x (λ) i yi|X, y] are independent sub-Gaussian vectors with mean zero. The sub-Gaussian norm of 1n ∑n i=1 x (λ) i,j yi (conditioning on X and y) can be upper
bounded by cmaxi≤n |xi,j |/ √ N .
P(∥E1∥2 ≥ t|X, y) = P  p∑ j=1 | 1 n n∑ i=1 {x(λ)i,j yi −E[x (λ) i,j yi|X, y]}| 2 ≥ t2|X, y  ≤ 2 exp { − c2nt
2∑p j=1 maxi≤n x 2 i,j
} .
Hence,
E1 = OP (
√∑p j=1 maxi≤n x 2 i,j
n ) = OP (
p log n
n ).
To summarize,
∥ 1 n (X(λ))T y −E[x(λ)i yi]∥ 2 2 = OP (
p
miny,e n(y,e) +
p log n
n ).
We can use similar analysis to bound
∥ 1 N (X(λ))TX(λ) −E[x(λ)i (x (λ) i ) T ]∥2.
The sub-exponential norm of 1N ∑N i=1 x (λ) i,j x (λ) i,k (conditioning on X) can be upper bounded by
maxi≤N |xi,j ||xi,k|/ √ N . We can show that
∥ 1 n (X(λ))TX(λ) −E[x(λ)i (x (λ) i ) T ]∥2 = OP ( p miny,e n(y,e) + p log n n ).
For the LISA-II, we first see that
1
n n∑ i=1 x̃i = 1 n ∑ Di=G (λix (1,G) i1 + (1− λi)x(0,G)i2 ) + 1 n ∑ Di=B (λix (1,B) i1 + (1− λi)x(0,B)i2 )
= 1
2 (x̄(1,G) + x̄(0,G))π̂G +
1 2 (x̄(1,B) + x̄(0,B))π̂B
¯̃y = 1
2 .
Next,
1
n n∑ i=1 x̃iỹi = 1 n ∑ Di=G { λ2ix (1,G) i1 + λi(1− λi)x(0,G)i2 } + 1 n ∑ Di=B { λ2ix (1,B) i1 + λi(1− λi)x(0,B)i2 }
1
n n∑ i=1 x̃iỹi − ¯̃x¯̃y − cov(x̃, ỹ) = 1 n n∑ i=1
x̃iỹi − ¯̃x¯̃y − cov(x̃i, ỹi|X, y)︸ ︷︷ ︸ E1 + cov(x̃i, ỹi|X, y)− cov(x̃i, ỹi)︸ ︷︷ ︸ E2 .
For E2,
E2 = π̂ (G)(E[λ2i ](x̄ (1,G) − x̄(0,G)) + 1 2 x̄(0,G)) + π̂(B)(E[λ2i ](x̄ (1,B) − x̄(0,B)) + 1 2 x̄(0,B))−
1 4 (x̄(1,G) + x̄(0,G))π̂G − 1 4 (x̄(1,B) + x̄(0,B))π̂B − var(λi)∆
= π̂(G)var(λi)(x̄ (1,G) − x̄(0,G)) + π̂(B)var(λi)(x̄(1,B) − x̄(0,B))− var(λi)∆.
Notice that E2 is a sub-Gaussian vector with sub-Gaussian norm upper bounded by
π̂2G n(1,G) + π̂2G n(0,G) + π̂2B n(1,B) + π̂2B n(0,B) ≤ 4 n max y,d πd πy|d .
Using sub-Gaussian concentration, we can show that
E2 = OP (
√ p
n max y,d πd πy|d ).
Notice that maxy,d πdπy|d ≥ 1. For E1, conditioning on X and y x̃iỹi−E[x̃iỹi|X, y] are independent sub-Gaussian vectors with mean zero. The sub-Gaussian norm of 1n ∑n i=1 x̃i,j ỹi conditioning on X and y can be upper bounded by cmaxi,j |xi,j |. Similar analysis on E1 leads to
1
n n∑ i=1 x̃iỹi − ¯̃x¯̃y − cov(x̃, ỹ) = OP ( √ p log n n + √ p n max y,d πd πy|d ).
For the sample covariance matrix, we can also show that∥∥∥∥∥ 1n n∑
i=1
x̃ix̃ T i − (
1
n n∑ i=1 x̃i)( 1 n n∑ i=1 x̃i) T − cov(x̃i) ∥∥∥∥∥ 2
2
= OP (
√ p log n
n +
√ p
n max y,d πd πy|d ).

heading: B.6 DOMAIN SHIFTS: PROOF OF THEOREM 2
text: It still holds that ∆̃∗ = 2(µ(0,∗) − E[x(λ)i ]) = 2(µ(0,∗) − E[x̃i]). It is easy to show that the worst group mis-classification error for this new environment is
E (wst,∗) A = max Φ  12 (∆̃∗)T bA√
bTAΣbA
 ,Φ  12 (∆̃∗)T bA −∆T bA√
bTAΣbA  , (14) where A ∈ {ERM,mix,L1,L2}. Notice that
∆̃∗ = 2µ(0,∗) − (µ(0,G) + µ(1,B)) = ∆̃ + µ(0,∗) − µ(0,G)
We assume ∥∆̃∗∥2 = ∥∆̃∥2. Let ξ∗ = cor(∆, ∆̃∗) and γ = cor(∆̃, ∆̃∗). We have
cor(bERM, ∆̃ ∗) = γ∥∆̃∥Σ∥∆̃∗∥Σ − c0ξ∗∥∆∥Σ∥∆̃∗∥Σ ∥∆̃∗∥Σ∥∆̃ + c0∆∥Σ
= γ∥∆̃∥Σ ∥∆̃∥Σ ± ∥c0∆∥Σ ± |c0ξ ∗|∥∆∥Σ ∥∆̃∥Σ ± ∥c0∆∥Σ = γ ± Cα.
Hence,
E (wst) ERM ≥ max
{ Φ(( γ
2 − Cα)∥∆̃∥Σ − (ξ − Cα)∥∆∥Σ),Φ((−
γ 2 − Cα)∥∆̃∥Σ)
} (15)
for some constant C depending on the true parameters.
Hence,
cor(bL1, ∆̃ ∗) =
(∆̃∗)T bL1 ∥∆̃∗∥Σ √ bTL1ΣbL1 = γ∥∆̃∥Σ + cL1ξ∗∥∆∥Σ ∥∆̃ + cL1∆∥Σ .
To have E(wst∗)L1 ≤ E (wst∗) ERM , it suffices to require that (− γ 2 −Cα)∥∆̃∥Σ ≤ ( γ 2 −Cα)∥∆̃∥Σ − (ξ + Cα)∥∆∥Σ and 1
2 cor(bL1, ∆̃
∗)∥∆̃∥Σ − cor(bL1,∆)∥∆∥Σ ≤ ( γ
2 − Cα)∥∆̃∥Σ − (ξ + Cα)∥∆∥Σ
− 1 2 cor(bL1, ∆̃ ∗)∥∆̃∥Σ ≤ ( γ 2 − Cα)∥∆̃∥Σ − (ξ + Cα)∥∆∥Σ.
A sufficient condition is
ξ ≤ (γ 2 + 1 2 cor(bL1, ∆̃ ∗)) ∥∆̃∥Σ ∥∆∥Σ − Cα, cor(bL1,∆) ≥ ξ + Cα, cor(bL1, ∆̃∗) ≤ γ − 2Cα.
We can find that a further sufficient condition is
ξ ≤ 1 + γ 2 ∥∆̃∥Σ ∥∆∥Σ − Cα, cL1 > 0, ξ∗ ≤ γ(∥∆̃ + cL1∆∥Σ − ∥∆̃∥Σ) cL1∥∆∥Σ − ϵ1α (16)
∥∆̃ + cL1∆∥Σ ≥ ∥∆̃∥Σ, ξ ≤ cL1∥∆∥Σ
∥∆̃ + cL1∆∥Σ − ∥∆̃∥Σ − ϵ1α (17)
ξ ≤ (γ 2 + 1 2 cor(bL1, ∆̃ ∗)) ∥∆̃∥Σ ∥∆∥Σ − Cα. (18)
We first find sufficient conditions for the statements in (9) and (10). Parameterizing t = cL1∥∆∥Σ/∥∆̃∥Σ, we further simplify the condition in (16) and (17) as
ξ ≤ 1 + γ 2 ∥∆̃∥Σ ∥∆∥Σ
− Cα, t > 0, ξ∗ ≤ γ( √ 1 + t2 + 2tξ − 1)
t − ϵ1α,
− t 2 ≤ ξ ≤ t, ξ ≤ 1 +
√ 1 + t2 + 2tξ
t+ 2ξ − ϵ1α.
We only need to require
t ≥ 2 and ξ ≤ min{1 + γ 2 ∥∆̃∥Σ ∥∆∥Σ , 1} − Cα, ξ∗ ≤ γξ.
Some tedious calculation shows that t ≥ 2 can be guaranteed by 1
2 ∥∆∥Σ ≤ ∥∆̃∥Σ ≤ 1√ 3aL1 or 1 2 ∥∆∥Σ ≥ ∥∆̃∥Σ.
It is left to consider the constraint in (18). Notice that it holds for any ξ ≤ 0. When ξ > 0, we can see
cor(bL1, ∆̃ ∗) = γ∥∆̃∥Σ + ξ∗cL1∥∆∥Σ ∥∆̃ + cL1∆∥Σ = γ + tξ∗√ 1 + t2 + 2tξ
≥ γ + tξ ∗
1 + t .
Hence, it suffices to guarantee that
ξ∗ + γ ≥ 2∥∆∥Σ ∥∆̃∥Σ ξ + Cα.
To summarize, it suffices to require
∥∆̃∥Σ ≤ 1√ 3aL1 , 0 ≤ ξ∗ ≤ γξ, ξ ≤ min{γ 2 ∥∆̃∥Σ ∥∆∥Σ , 1} − Cα.
For LISA-II, we can similarly show that E(wst∗L2 ≤ E (wst∗ ERM given that
∥∆̃∥Σ ≤ 1√ 3aL2 , 0 ≤ ξ∗ ≤ γξ, ξ ≤ min{γ 2 ∥∆̃∥Σ ∥∆∥Σ , 1} − Cα.

Review summaries:
This paper propose a mixup-style data augmentation method under the data distribution shift context. In particular, data distributions are formulated as mixture of distributions (i.e., domains), and two distribution shift scenarios are considered: (1) domain shift, where the test domain and train domain are disjoint. (2) subpopulation shift, where test distribution has different mixture proportion than train distribution. It's  assumed that domain identification spuriously correlates with labels. To tackle this problem, this paper proposes two mixup strategies: (I) mixup two examples with same label but different domains; (II) mixup two examples with same domain but different labels. It's claimed that such mixup could cancel out the spurious correlations. Extensive experiments on a variety of datasets show its superiority compared to empirical risk minimization (ERM) and alternative data augmentation methods. The paper further provide theoretical analysis that under certain conditions, the proposed method has asymptotically smaller worst case classification errors than ERM and vanilla mixup. 

Authors introduced approaches aimed at learning invariant predictors across data sources. Rather than using distribution/risk matching schemes as often done by previous work, they propose to train models against mixtures of data points as a means to avoid that models rely on spurious correlations between domain and class labels, since such correlations observed during training might not hold at testing time. The proposed setting uses the idea of mixup to combine data instances in two different schemes: I-combine data points from the same class but different domains, and II-combine data points from the same domain but from different classes.