\section{Conclusion and Future Directions}
\label{sec:conclusion}
Out-of-Distribution generalization problem has aroused much research attention recently, and is critical for the deployment of machine learning algorithms.
In this paper, we systematically and comprehensively review the definition, the main branches of methods, theoretical connections among different methods and the datasets and evaluation metrics of OOD generalization problem.
Based on our analysis, we come up with several potential challenges that could be the directions of future research.
And we hope this paper could inspire the future research of OOD generalization problem.\\\\
\textsc{(a) Theoretical characterization}\\
Although growing popular recently, the theoretical characterization a learnable OOD generalization problem remains vague in recent literatures.
Characterizing the learnability of a problem is a basic question in machine learning.
Though previous research efforts have been made in $i.i.d.$ setting, the learnability is difficult to define and analyze under distributional shifts, since it is impossible to enable models to generalize to arbitrary and unknown distributions.
Therefore, in OOD generalization problem, figuring out what kind of distributional shifts should be taken into consideration is critical for the analysis of learnability.
There is very few exploration\cite{Ye2021a} on this and more research efforts need be paid on this.\\\\
\textsc{(b) Demands for environments}\\
The majority of OOD generalization methods require multiple training environments.
However, modern datasets are often assembled by merging data from multiple sources without maintaining source labels, which greatly restricts the deployment of OOD generalization methods in real scenarios.
Therefore, it is more practical and realistic that we only have access to one training environment with latent heterogeneity.
Recently, while there are some works\cite{creager2020environment, hrm} try to leverage the latent heterogeneity and relax the demands for environments, how to explore and make good use of the latent heterogeneity inside data is critical for the deployment of OOD generalization methods and is a promising future direction.\\\\
\textsc{(c) Reasonable evaluations}\\
Although the evaluation criterions for classic machine learning algorithms under $i.i.d.$ assumption are well-developed, including testing data, model selection mechanisms and so on, they cannot directly be deployed to OOD scenarios.
Since the testing distribution is both unknown and different from the training, how to design reasonable and realistic experimental settings remains a challenging problem.
Further, the model selection mechanism also matters, since the choice of validation data is non-trivial in OOD scenarios, and Gulrajani \textit{et al.} \cite{DBLP:conf/iclr/GulrajaniL21} also demonstrate that domain generalization algorithms without a model selection strategy are incomplete.
Also, Gulrajani \textit{et al.} \cite{DBLP:conf/iclr/GulrajaniL21} notice that the real effects of many domain generalization methods are weak, which indicates that existing evaluation criterions are inadequate to validate an OOD generalization algorithm.
Therefore, it is critical for the community to develop more reasonable evaluation criterions for OOD generalization.\\\\
\textsc{(d) Incorporate self-learning}\\
Recently, there is a rapid development of large-scale self-learning (or pre-trained models), such as BERT\cite{devlin2018bert}, GPT-3\cite{DBLP:conf/nips/BrownMRSKDNSSAA20}, SimCLR\cite{DBLP:conf/icml/ChenK0H20}, which propose to firstly pre-train models on large-scale datasets and then finetune them on downstream tasks.
Since the distributional shifts between downstream tasks and pre-training datasets are inevitable, how to design efficient self-learning methods with good OOD generalization ability or incorporate self-learning methods to achieve better OOD generalization performance remains a promising direction for future.

\ifCLASSOPTIONcompsoc

  \section*{Acknowledgments}
\else

  \section*{Acknowledgment}
\fi

\ifCLASSOPTIONcaptionsoff
  \newpage
\fi

\bibliographystyle{IEEEtran}

\section{Introduction}\label{sec:introduction}}
Modern machine learning techniques have illustrated their excellent capabilities in many areas like computer vision, natural language processing and recommendation, etc.
While enjoying the human-surpassing performance in experimental conditions, many researches have revealed the vulnerability of machine learning model when exposed to data with different distributions.
Such massive gap is induced by the violation of a fundamental assumption that training and test data are identically and independently distributed (a.k.a. $i.i.d.$ assumption), upon which most of the existing learning models are developed.
In many real cases where $i.i.d.$ assumption can hardly be satisfied, especially those high-stake applications such as healthcare, military and autonomous driving, instead of generalization within the training distribution, the ability to generalize under distribution shift is of more critical significance.
Therefore, the investigation of out-of-distribution generalization is of great urgency in both academic and industry fields.

Despite the importance of OOD generalization problem, classic supervised learning methods can not be directly deployed to deal with this problem.
Theoretically, one of the most fundamental assumptions of classic supervised learning is the $i.i.d.$ assumption, which assumes that the training and testing data are independent and identically distributed.
However, distributional shifts are inevitable in OOD generalization problem, which ruins the $i.i.d.$ assumption and renders classic learning theory inapplicable.
Empirically, classic supervised learning methods typically are optimized by minimizing their training errors, which greedily absorb all correlations found in data for prediction.
Though proved to be effective in $i.i.d$ settings, it would hurt the performance under distributional shifts, since not all correlations will hold in unseen testing distributions.
As shown in many literatures\cite{duchi2018learning, arjovsky2019invariant, creager2020environment, shen2020stable, hrm}, when involving strong distributional shifts, models optimized solely with training errors fail dramatically, and sometimes are even worse than random guess, which indicates the urgency to design methods for OOD generalization problems.

In order to deal with the OOD generalization problem, there remain several vital problems to be solved.
Firstly, since training and testing data can be drawn from different distributions, how to formally characterize the distributional shifts is still an open problem.
In the OOD generalization literature, different branches of methods adopt different ways to model the potential testing distribution.
Domain generalization methods \cite{muandet2013domain, ganin2015unsupervised, ganin2016domain, li2018domain} mainly focus on real scenarios and utilize data collected from different domains.
Causal learning methods \cite{peters2016causal, buhlmann2018invariance, arjovsky2019invariant} formulate training and testing distributions with causal structures and the distributional shifts mainly originate from interventions or confounders.
Stable learning methods \cite{kuang2018stable, kuang2020stable, shen2020stable} introduce distributional shifts via selection bias.
Secondly, how to design an algorithm with good OOD generalization performance is the research hot spot and there are many branches of methods with different research focuses, including unsupervised representation learning methods, supervised learning models and optimization methods.
Thirdly, the evaluation of the OOD performance of different methods remains challenging, which requires specific datasets and evaluation metrics, as the classic ways for $i.i.d.$ setting are inapplicable under distributional shifts.
And this also motivates the generation of different datasets and evaluations.

In this paper, we aim to provide a systematic and comprehensive review of research efforts in terms of a fairly broader sense of OOD generalization, covering the whole life cycle of OOD problem from the definition, methodology, evaluation to the implications and future directions.
To the best of our knowledge, we serve as the first effort to discuss out-of-distribution generalization in such a large scope and self-contained form.
There exist some previous works discussing the related topics.
For example, \cite{wang2021generalizing, zhou2021domain} mainly focus on the discussion of domain generalization; \cite{Ye2021b} discuss the evaluation benchmarks for OOD generalization.
Each of the previous works serves as a piece of puzzle for the whole out-of-distribution generalization problem, and in this work, we organically integrate all the ingredients in a clear and concise way.
Specifically, we divide the existing methods into three categories based on their positions in the whole learning pipeline.
We also elaborate the theoretical connections between different methods through the lens of causality.
To promote the future research on OOD generalization, we provide an exhaustive survey on how to evaluate the learning methods under distribution shifts.

The structure of this paper is organized as follows.
We formulate the out-of-generalization problem, discuss its relationship with existing research areas and provide a categorization of methods in Section \ref{sec:problem}.
In the following Section \ref{sec:representation}, \ref{sec:causal}, \ref{sec:optimization}, we describe the representative methods of each category in detail respectively.
We provide some theoretical connections and insights between different methods in Section \ref{sec:theory}.
We also summarize the applicable benchmarks for OOD generalization and its possible implications in Section \ref{sec:benchmark}, \ref{sec:fairness}.
Finally, we conclude this paper in Section \ref{sec:conclusion} and raise some promising directions for future research.

\section{Optimization for OOD Generalization}
\label{sec:optimization}
To address the Out-of-Distribution (OOD) generalization problem, apart from unsupervised representation learning and end-to-end learning models, optimization methods with theoretical guarantees have recently aroused much attention, which are both model agnostic and data structure agnostic.
In this section, we firstly introduce the objective of these OOD optimization methods, and then review the optimization methods, including Distributionally Robust Optimization\cite{esfahani2018data, duchi2018learning, SinhaCertifying,sagawa2019distributionally, liu2021stable} and Invariant-Based Optimization\cite{DBLP:journals/corr/abs-2008-01883, DBLP:rationalization, hrm}.

In order to address the problem from the optimization perspective, the OOD generalization problem is formulated to controlling the worst-case prediction error among $\mathcal{E}_{all}$, which takes the form of:
\begin{equation}
	\label{equ:OOD}
	\arg\min_f \max_{e\in\text{supp}(\mathcal{E}_{all})} \mathcal{L}(f|e)
\end{equation}
where $\mathcal{E}_{all}$ is the random variable on indices of all possible environments, and for all $e\in \mathrm{supp}(\mathcal{E}_{all})$, the data and label distribution $P^e(X,Y)$ can be quite different from that of training distribution $P_{tr}(X,Y)$; $\mathcal{L}(f|e)=\mathbb{E}[l(f(X),Y)|e]=\mathbb{E}^e[l(f(X^e),Y^e)]$ is the risk of predictor $f$ on environment $e$, and $l(\cdot,\cdot):\mathcal{Y}\times\mathcal{Y}\rightarrow\mathbb{R}^+$ is the loss function.
Intuitively, optimization methods aim to guarantee the worst-case performance under distributional shifts.

\subsection{Distributionally Robust Optimization}
\label{subsec:DRO}
Distributionally robust optimization (DRO), from robust optimization literature, directly solves the OOD generalization problem by optimizing for the worst-case error over an uncertainty distribution set, so as to protect the model against the potential distributional shifts within the uncertainty set, which is often constrained by moment or support conditions \cite{10.1287/opre.1090.0741,bertsimas2018data-driven}, $f$-divergence \cite{namkoong2016stochastic,duchi2018learning, sagawa2019distributionally} and Wasserstein distance \cite{esfahani2018data, SinhaCertifying, liu2021stable}.
The objective function of DRO methods can be summarized as:
\begin{equation}
\label{equ:DRO-formulation}
	\arg\min_f \sup\limits_{Q\in \mathcal{P}(P_{tr})}\mathbb{E}_{X,Y\sim Q}[\ell(f(X),Y)]
\end{equation}
where $\mathcal{P}(P_{tr})$ is the distribution set lying around the training distribution $P_{tr}$ and $\ell(\cdot;\cdot):\mathcal{Y}\times\mathcal{Y}\rightarrow\mathbb{R}^+$ is the loss function.
Different DRO methods adopt different kinds of constraints to formulate the distribution set $\mathcal{P}(P_{tr})$ and correspondingly different optimization algorithm.
In this paper, we only introduce two typical DRO methods whose distribution sets are formulated by $f$-divergence and Wasserstein distance respectively, and for a more thorough introduction to DRO methods, one can refer to \cite{rahimian2019distributionally}.

\subsubsection{$f$-Divergence Constraints}
\label{subsubsec:f-div}
The distribution set $\mathcal{P}(P_{tr})$ in $f$-divergence DRO \cite{duchi2018learning} is formulated as:
\begin{equation}
	\mathcal{P}(P_{tr}) = \{Q: D_f(Q\|P_{tr})\leq \rho\}
\end{equation}
where $\rho > 0$ controls the extent of the distributional shift, and $D_f(Q\|P_{tr}) = \int f(\frac{d Q}{d P_{tr}}) d P_{tr}$ is the $f$-divergence between $Q$ and $P_{tr}$.
Intuitively, if the potential testing distribution $P^{e_{test}}(X,Y) \in \mathcal{P}(P_{tr})$, DRO methods can achieve good generalization performance even if $P^{e_{test}}(X,Y) \neq P_{tr}(X,Y)$.
As for the optimization, a simplified dual formulation for the Cressie-Read family of $f$-divergence can be obtained.
\begin{lemma}[Optimization of $f$-divergence \cite{duchi2018learning}]
	For $f_k(t) = \frac{t^k-kt+k-1}{k(k-1)}$ and $k\in (1,+\infty)$, $k_*=k/(k-1)$, and any $\rho > 0$, we have for all $\theta \in \Theta$:
	\begin{small}
		\begin{equation}
			\mathcal{R}_k(\theta;P_{tr}) = \inf_{\eta\in\mathbb{R}}\left\{ c_k(\rho) \mathbb{E}_{P_{tr}}[(\ell(f(X),Y)-\eta)_+^{k_*}]^{\frac{1}{k_*}} + \eta \right\}
		\end{equation}
	\end{small}
	where $c_k(\rho) = (k(k-1)\rho + 1)^{\frac{1}{k}}$.
\end{lemma}

\subsubsection{Wasserstein Distance Constraints}
Since the calculation of $f$-divergence requires the supports of two distributions to be the same while Wasserstein distance does not, the distribution set $\mathcal{P}(P_{tr})$ formulated by Wasserstein distance is more flexible.
Wasserstein distance is defined as:
\begin{definition}
	Let $\mathcal{Z} \subset \mathbb{R}^{m+1}$ and $\mathcal{Z} = \mathcal{X}\times\mathcal{Y}$ , given a transportation cost function $c: \mathcal{Z} \times \mathcal{Z} \rightarrow [0, \infty)$, which is nonnegative, lower semi-continuous and satisfies $c(z,z)=0$, for probability measures $P$ and $Q$ supported on $\mathcal{Z}$, the Wasserstein distance between $P$ and $Q$ is :
	\begin{equation}
		W_c(P, Q) = \inf\limits_{M \in \Pi(P,Q)} \mathbb{E}_{(z,z') \sim M}[c(z,z')]
	\end{equation}
	where $\Pi(P,Q)$ denotes the couplings with $M(A,\mathcal{Z})=P(A)$ and $M(\mathcal{Z},A)=Q(A)$ for measures $M$ on $\mathcal{Z}\times \mathcal{Z}$.
\end{definition}
Then the distribution set $\mathcal{P}(P_{tr})$ of Wasserstein DRO is formulated as:
\begin{equation}
	\mathcal{P}_c(P_{tr}) = \{Q: W_c(Q,P_{tr}) \leq \rho\}
\end{equation}
where the subscript $c$ denotes the transportation cost function $c(\cdot,\cdot)$.
However, Wasserstein DRO is difficult to optimize, and works targeting different models and transportation cost functions have been proposed.
Wasserstein DRO for logistic regression was proposed by Abadeh \textit{et al.}\cite{shafieezadehabadeh2015distributionally}.
Sinha \textit{et al.} \cite{SinhaCertifying} achieved moderate levels of robustness with little computational cost relative to empirical risk minimization with a Lagrangian penalty formulation of WDRL.

\subsubsection{Robustness Guarantees}
\label{subsubsec:robust}
Here we briefly review some theoretical results in DRO literatures, including the relationship with regularization and robustness guarantees.

In order to demonstrate how the robust formulation (\ref{equ:DRO-formulation}) provides distributional robustness, several works establish the relationship between distributional robustness and regularization.
For norm-based DRO methods, El Ghaoui \textit{et al.}\cite{doi:10.1137/S0895479896298130} build the equivalence between the worst-case squared residual within a Frobenius norm-based distribution set and the Tikhonov regularization.
Xu \textit{et al.}\cite{DBLP:journals/corr/abs-0811-1790} show the equivalence between robust linear regression with feature perturbations and the Least Absolute Shrinkage and Selection Operator(LASSO), and Yang \textit{et al.}\cite{DBLP:conf/icml/YangX13} and Bertsimas \textit{et al.}\cite{bertsimas2017characterization} make further extensions.
For $f$-divergence-based DRO methods, Duchi \textit{et al.}\cite{duchi2021statistics} show that the formulation (\ref{equ:DRO-formulation}) with distribution set $\mathcal{P}(P_{tr})=\mathcal{P}_{\rho,n}=\{p \in\mathbb{R}^n: p^T\mathbf{1}=1, p\geq 0, D_f(p\|\mathbf{1}/n)\leq \rho/n\}$ is a convex approximation to regularizing the empirical risk by variance.
For Wasserstein-based DRO methods, Shafieezadeh-Abadeh \textit{et al.}\cite{shafieezadehabadeh2015distributionally} investigate the Wasserstein DRO of logistic regression, and show that the regularized logistic regression is one special case of it.
Chen \textit{et al.}\cite{chen2018robust} also build the connection between the Wasserstein DRO of linear regression with $\ell_1$ loss function and regularization constraints on the regression coefficients.
And Shafieezadeh-Abadeh \textit{et al.}\cite{shafieezadehabadeh2019regularization} and Gao \textit{et al.}\cite{gao2017wasserstein} connect the Wasserstein DRO and regularizations in a unified framework.

As for the OOD generalization ability, in fact, the guarantees for OOD generalization of DRO methods naturally derive their formulation (\ref{equ:DRO-formulation}).
Since DRO methods directly optimize for the worst-case risk within the distribution set $\mathcal{P}(P_{tr})$, as long as the potential testing distribution $P_{te}\in\mathcal{P}(P_{tr})$, the OOD generalization ability is guaranteed.
Therefore, the remaining work is to provide the finite sample convergence guarantees, which ensure that the population-level objective $\sup_{Q\in\mathcal{P}(P_{tr})}\mathbb{E}_Q[\ell(f(X),Y)]$ can be optimized empirically with finite samples.
\begin{theorem}[Theorem 2 in \cite{duchi2018learning}]
\label{theorem: duchi1}
	Assume that $\ell(\theta;x)\in[0,M]$ for all $\theta\in\Theta$ and $x\in\mathcal{X}$, and define $c_k=(k(k-1)\rho + 1)^{1/k}$. For a fixed $\theta\in\Theta$ and $t>0$, with probability at least $1-2e^{-t}$,
	\begin{equation}
		|\mathcal{R}_k(\theta;\hat{P}_{tr,n}) - \mathcal{R}_k(\theta;P_{tr})|\leq c_kMn^{-\frac{1}{k_*\vee 2}}(\frac{2}{k} + \sqrt{t})
	\end{equation}
	where $\mathcal{R}_k(\theta;P) = \sup\limits_{Q\ll P_{tr}}\{\mathbb{E}_Q[\ell(f_\theta(X),Y)]:D_{f_k}(Q\|P_{tr})\leq \rho\}$, and $k_*=\frac{k}{k-1}$.
\end{theorem}
Given by Duchi \textit{et al.}\cite{duchi2018learning}, Theorem \ref{theorem: duchi1} shows that the pointwise concentration of the finite sample objective $\mathcal{R}(\theta;\hat{P}_{tr,n})$ converges to its population counterpart, which also gives that for the empirical minimizer $\hat{\theta}_n$ with probability at least $1-2N(\mathcal{F},\frac{t}{3}, \|\cdot\|_{L^\infty}(\mathcal{X}))e^{-t}$
\begin{small}
\begin{equation}
	\mathcal{R}_k(\hat{\theta}_n;P_{tr})\leq \inf_{\theta\in\Theta} \mathcal{R}_k(\theta;P_{tr}) + 2c_kMn^{-\frac{1}{k_*\vee2}}(\frac{2}{k}+\sqrt{6}t)
\end{equation}
\end{small}
where $N(V,\epsilon,\|\cdot\|)$ is the covering number of $V$ with respect to $\|\cdot\|$, $\mathcal{F}=\{\ell(\theta,\cdot):\theta\in\Theta\}$ equipped with sup-norm $\|h\|_{L^\infty}(\mathcal{X})=\sup_{x\in\mathcal{X}}\|h(x)\|$.
Sinha \textit{et al.} \cite{SinhaCertifying}, Chen \textit{et al.} \cite{chen2018robust} and Liu \textit{et al.}\cite{liu2021stable} also provide similar generalization bounds for Wasserstein DRO as Theorem \ref{theorem:sinha1}.
\begin{theorem}[Theorem 3 in \cite{SinhaCertifying}]
\label{theorem:sinha1}
	Assume $|\ell(f_\theta(X),Y)|\leq M_\ell$ for all $\theta\in\Theta$ and $X\in\mathcal{X}, Y\in\mathcal{Y}$. Then for a fixed $t>0$ and numerical constants $b_2,b_2>0$, with probability at least $1-e^{-t}$, simultaneously for all $\theta\in\Theta$, $\rho\geq 0$, $\gamma \geq 0$,
	\begin{small}
	\begin{equation}
		\sup\limits_{Q:W_c(Q,P_{tr})\leq \rho}\mathbb{E}_Q[\ell(f_\theta(X),Y)]\leq \gamma\rho + \mathbb{E}_{\hat{P}_{tr,n}}[\phi_\gamma(\theta;X,Y)] + \epsilon_n(t)
	\end{equation}
	\end{small}
\end{theorem}

\subsubsection{Over-Pessimism Problem}
\label{subsubsec:over}
Although DRO methods could theoretically guarantee the out-of-distribution generalization ability when $P^{e_{test}}(X,Y)\in\mathcal{P}(P_{tr})$, there has been work questioning their real effects in practice.
Intuitively, in order to achieve good OOD generalization ability, the potential testing distribution should be captured in the built distribution set.
However, in real scenarios, to contain the possible true testing distribution, the uncertainty set is often overwhelmingly large, making the learned model make decisions with fairly low confidence, which is also referred to as the  low confidence problem.
Specifically, Hu \textit{et al.} \cite{hu2016does} proved that in classification tasks, DRO ends up being optimal for the training distribution $P_{tr}$, which is due to the over-flexibility of the built distribution set.
And Fronger \textit{et al.} \cite{frogner2019incorporating} also pointed out the problem of overwhelmingly-large decision set for Wasserstein DRO.

In order to overcome such problem, Blanchet \textit{et al.} propose a data-driven way to select the transportation cost function.
Fronger \textit{et al.} \cite{frogner2019incorporating} propose to further restrict the distribution set with large number of unlabeled data.
Liu \textit{et al.} \cite{liu2021stable} notice that in real scenarios, different covariates may be perturbed in a non- uniform way, and form a more reasonable distribution set according to the stability of covariates across environments.
Duchi \textit{et al.} \cite{duchi2019distributionally} assume that $P(Y|X)$ stays invariant and propose to only perturb the marginal distribution $P(X)$ to deal with covariate shifts.

\subsection{Invariance-Based Optimization}
\label{subsec:Inv-opt}
Different from DRO methods which directly optimize for the worst-case without any additional assumptions, invariance-based optimization methods \cite{DBLP:rationalization, DBLP:journals/corr/abs-2008-01883, hrm} assume the invariance property inside data and leverages multiple environments to find such invariance for generalizing under distributional shifts.
In this section, we introduce two typical methods, namely Maximal Invariant Predictor (MIP, \cite{DBLP:rationalization, DBLP:journals/corr/abs-2008-01883}) and Heterogeneous Risk Minimization (HRM, \cite{hrm}).

Chang \textit{et al.} \cite{DBLP:rationalization} and Koyama \textit{et al.} \cite{DBLP:journals/corr/abs-2008-01883} formulate the desired invariant representation using information theory, and propose to find the maximal invariant predictor (MIP) across training environments to control the worst-case error in equation \ref{equ:OOD}.
The maximal invariant predictor is defined as:
\begin{definition}
	\label{definition2:invariance set}
	The invariance set $\mathcal{I}$ with respect to $\mathcal{E}$ is defined as:
	\begin{small}
		\begin{equation}
			\begin{aligned}
				\mathcal{I}_{\mathcal{E}} &= \{\Phi(X): Y \perp \mathcal{E}|\Phi(X)\}\\
				&= \{\Phi(X): H[Y|\Phi(X)]=H[Y|\Phi(X),\mathcal{E}]\}
			\end{aligned}
		\end{equation}
	\end{small}
	where $H[\cdot]$ is the Shannon entropy of a random variable.
	The corresponding maximal invariant predictor (MIP) of $\mathcal{I}_{\mathcal{E}}$ is defined as:
	\begin{small}
	\begin{equation}
		S_{\mathcal{E}} = \arg\max_{\Phi \in \mathcal{I}_{\mathcal{E}}}I(Y;\Phi)
	\end{equation}
	\end{small}
	where $I(\cdot;\cdot)$ measures Shannon mutual information between two random variables.
\end{definition}
With the invariant predictor $S_{\mathcal{E}_{all}}$, Koyama \textit{et al.} \cite{DBLP:journals/corr/abs-2008-01883} prove that the OOD optimal model is given by $\mathbb{E}[Y|S_{\mathcal{E}_{all}}]$.
Further, to obtain the MIP solution from training environments $\mathcal{E}_{tr}$, Koyama \textit{et al.} \cite{DBLP:journals/corr/abs-2008-01883} derive a regularizer as:
\begin{small}
\begin{equation}
	\text{trace}\left(\mathrm{Var}_{\mathcal{E}_{tr}}(\nabla_\theta \mathcal{L}^e(\theta))\right)
\end{equation}
\end{small}
where the variance is taken with respect to training environments $\mathcal{E}_{tr}$.
Under the controllability condition proposed by Koyama \textit{et al.} \cite{DBLP:journals/corr/abs-2008-01883} which assumes that there exists an environment $e$ such that $X\perp Y | \Phi(X),e$, the optimality of $\mathbb{E}[Y|\Phi(X)]$ can be verified, as shown in Proposition 3.1 in \cite{DBLP:journals/corr/abs-2008-01883} and Theorem 1 in \cite{rojas2018invariant}.

Move one step on, Liu \textit{et al.} \cite{hrm} theoretically characterize the role of environments in invariance-based optimization methods.
Since $\text{supp}(\mathcal{E}_{tr})\subset \text{supp}(\mathcal{E}_{all})$, $\mathcal{I}_{\mathcal{E}_{all}} \subseteq \mathcal{I}_{\mathcal{E}_{tr}}$ holds, which shows that the invariance set regularized by training environments is likely to contain undesired variant components and makes the controllability condition for such optimality in \cite{DBLP:journals/corr/abs-2008-01883} is hard to satisfy since in practice.
Further, in real scenarios, data are often collected from different sources without explicit environment labels, which renders the above methods inapplicable.
Inspired by this, they propose Heterogeneous Risk Minimization (HRM, \cite{hrm}), an optimization framework to achieve joint learning of the latent heterogeneity among the data and the invariant predictor.
\begin{figure}
	\includegraphics[width=\columnwidth]{figure/model}
	\caption{The framework of Heterogeneous Risk Minimization from \cite{hrm}.}
	\label{fig:hrm}
	\vskip -0.15in
\end{figure}
As shown in Figure \ref{fig:hrm}, HRM contains two interactive parts, the frontend $\mathcal{M}_c$ for heterogeneity identification and the backend $\mathcal{M}_p$ for invariant prediction.
Given the pooled heterogeneous data, it starts with the heterogeneity identification module $\mathcal{M}_c$ leveraging the learned variant representation $\Psi(X)$ to generate heterogeneous environments $\mathcal{E}_{learn}$.
Then the learned environments are used by OOD prediction module $\mathcal{M}_p$ to learn the MIP $\Phi(X)$ as well as the invariant prediction model $f(\Phi(X))$.
After that, the better variant part $\Psi(X)$ is derived from the learned MIP $\Phi(X)$ to further boost the process of heterogeneity identification.

\section{Theoretical Connections}
\label{sec:theory}
For branches of methods for OOD generalization, there are some inherent connections among them.
In this section, we will demonstrate the connections among causal learning methods, distributionally robust optimization (DRO) methods and stable learning methods, which may benefit the understanding of OOD generalization methods.

\subsection{DRO and Causality}
\label{sec:dro-causal}
Recall that DRO methods aim to optimize the worst-case error over a pre-defined distribution set, so as to protect the learned model from potential distributional shifts, which often takes the form of:
\begin{small}
\begin{equation}
	\arg\min_f \sup\limits_{Q\in\mathcal{P}(P_{tr})}\mathbb{E}_{X,Y\sim Q}[\ell(f(X),Y)]
\end{equation}
\end{small}
where $\mathcal{P}(P_{tr})$ is the distribution set built around the training distribution $P_{tr}$.
Although in DRO literatures, $\mathcal{P}(P_{tr})$ is often characterized by $f$-divergence or Wasserstein distance, different choices of $\mathcal{P}(P_{tr})$ will render DRO equivalent to causal inference in the structural equation model (SEM) context\cite{8439889}, which shows the inherent relationship between causality-based methods and DRO methods.
Taking linear equation models for example, suppose we have a directed acyclic graph $G=(V,E)$ with $p$ nodes $V=\{1, \dots, p\}$ and correspondingly a $p$-dimension random variable $Z$, then the training distribution is determined by the structural causal model (SCM) as:
\begin{small}
\begin{equation}
	Z = BZ + \epsilon
\end{equation}
\end{small}
where $Z=(X,Y)\in\mathbb{R}^p$ is the random variable of interest, $B\in\mathbb{R}^{p\times p}$ is the coefficient matrix and $\epsilon \sim P_{\epsilon}$ the random noise.
We will show that finding causal coefficients for predicting $Y$ can be reformulated as performing DRO on interventional distribution set, including do-interventional and shift-interventional distributions.

Do-interventions on variables $S \subseteq V$ can be formulated as:
\begin{small}
\begin{align}
	Z_k = (BZ)_k + \epsilon\quad\quad &\text{for $k\not\in S$}\\
	Z_K = A_k\quad\quad\quad &\text{for $k\in S$}
\end{align}
\end{small}
where $A\in\mathbb{R}^p$ and the value of the do-intervention on variable $k\in S$ is $A_k$.
Then the error distribution $P_\epsilon$, coefficient matrix $B$, intervention set $S \subseteq V$ and intervention value $A\in\mathbb{R}^p$ induces a distribution for a random variable $Z(A, S)$, denoted as $Z(A,S) \sim P_{A,S}^{(do)}$.
And the corresponding do-interventional distribution set can be formulated as $\mathcal{P}^{(do)} = \{P_{A, V/\{p\}}^{(do)}: A\in\mathbb{R}^p\}$.
Analogously to do-interventions, the shift-interventions is defined as:
\begin{small}
\begin{equation}
	Z = BZ + \epsilon + A
\end{equation}
\end{small}
where $A\in\mathbb{R}^p$ is the shift direction, and the induced distribution is denoted as $Z(A)\sim P_A^{(shift)}$ and the shift-interventional distribution set can be formulated as $\mathcal{P}^{(shift)} = \{P_A^{(shift)}: A_p=0\}$.

When performing DRO on $\mathcal{P}^{(do)}$ or $\mathcal{P}^{(shift)}$, causal coefficients can be obtained\cite{8439889} since
\begin{small}
\begin{equation}
	\min_\theta\sup\limits_{Q\in \mathcal{P}^{(do)}}\mathbb{E}[\ell(f_\theta(X),Y)] = \left\{
             \begin{array}{lr}
             \infty, &\text{if $\theta\neq \theta_{causal}$}  \\
             \text{Var}(\epsilon_p), &\text{if $\theta= \theta_{causal}$}
             \end{array}
\right.
\end{equation}
\end{small}
and
\begin{small}
\begin{equation}
	\min_\theta\sup\limits_{Q\in \mathcal{P}^{(shift)}}\mathbb{E}[\ell(f_\theta(X),Y)] = \left\{
             \begin{array}{lr}
             \infty, &\text{if $\theta\neq \theta_{causal}$}  \\
             \text{Var}(\epsilon_p), &\text{if $\theta= \theta_{causal}$}
             \end{array}
\right.
\end{equation}
\end{small}
which reveals that causal inference can also be viewed as a special case of distributional robustness.

\subsection{Stable Learning and Causality}
Stable learning algorithms have connections with causality, which can be considered as a feature selection mechanism according to the regression coefficients.
These algorithms will eliminate all variant variables, and the invariant variables selected for predicting $Y$ are closely related to Markov blankets and Markov boundaries \cite{pearl2014probabilistic} in local causal discovery literature.

\begin{figure}[ht]
    \centering
    \subfloat[$S \perp V$]{\includegraphics[width=0.2\linewidth]{figure/SperpV.pdf}\label{fig:SperpV}}
    \,\,\,\,\,\,\,
    \subfloat[$S \rightarrow V$]{\includegraphics[width=0.2\linewidth]{figure/StoV.pdf}\label{fig:StoV}}
    \,\,\,\,\,\,\,
    \subfloat[$S \leftarrow V$]{\includegraphics[width=0.2\linewidth]{figure/VtoS.pdf}\label{fig:VtoS}}
    \caption{Three data-generating processes in \cite{kuang2020stable}.}
    \label{fig:stable-learning}
\end{figure}

Here take the data-generating processes studied in \cite{kuang2020stable} as example, as shown in Figure \ref{fig:stable-learning}.
In all three cases, $V$ are the variant variables to predict $Y$, i.e., they are not correlated with outcome $Y$ (Figure \ref{fig:SperpV}) or influence $Y$ by means of $S$ (Figure \ref{fig:StoV} and \ref{fig:VtoS}).
The algorithm proposed by Shen \textit{et al.}\cite{shen2020stable} will eliminate $V$, i.e., the coefficients of weighted least squares on $V$ will be zero.
For simplicity, assume $S$, $V$, and $Y$ are all scalars, and in these cases, $Y \perp V \mid S$.
Consider any proper weighting function $w(S, V)$ such that $S \perp V$ in the weighted distribution $\tilde{P}(S,V)$.
The existence of $w$ can be fulfilled under proper assumptions.
Then coefficients of weighted least squares under infinite samples are given by:
\begin{small}
\begin{equation}\label{eq:wls}
    \begin{pmatrix}
        \beta_S \\
        \beta_V
    \end{pmatrix} = \begin{pmatrix}
        \text{Var}_{\tilde{P}}(S) & \text{Cov}_{\tilde{P}}(S, V) \\
        \text{Cov}_{\tilde{P}}(S, V) & \text{Var}_{\tilde{P}}(V)
    \end{pmatrix}^{-1}\begin{pmatrix}
        \text{Cov}_{\tilde{P}}(S, Y) \\
        \text{Cov}_{\tilde{P}}(V, Y)
    \end{pmatrix}.
\end{equation}
\end{small}
In addition, the conditional distribution $P(Y | S,V)$ will stay the same if weighting function $w$ is defined on $(S,V)$ only.
Hence, conditional independence $Y \perp V \mid S$ is also satisfied in the weighted distribution $\tilde{P}(S,V,Y)$.
As a result, $Y \perp V$ in $\tilde{P}$, which makes $\text{Cov}_{\tilde{P}}(V, Y) = 0$. Hence,
\begin{small}
\begin{equation}
    \beta_V = \left(\text{Var}_{\tilde{P}}(V)\right)^{-1}\text{Cov}_{\tilde{P}}(V, Y) = 0.
\end{equation}
\end{small}
Actually, the assumption $Y \perp V \mid S$ is closely related to Markov blankets and Markov boundaries and $S$ is a Markov blanket with respect to $Y$ by definition.
One straightforward corollary is that stable learning algorithms\cite{shen2020stable} will eliminate the variables that do not belong to the Markov boundary with respect to outcome $Y$.

\section{Unsupervised Representation Learning}
\label{sec:representation}

In this section, we review methods focusing on the unsupervised representation learning, which can be mainly divided into two branches, namely disentangled representation learning and causal representation learning.
These methods leverage human's prior knowledge to design and restrict the representation learning procedure, which endows the learned representation with certain properties that are potentially helpful for OOD generalization.

\subsection{Disentangled Representation Learning}
\label{subsec:disen}
Disentangled representation learning aims to learn representations where distinct and informative factors of variations in data are seperated\cite{bengio2013representation,locatello2019challenging}, which is considered as one property of good representation and potentially benefits out-of-distribution generalization.
Works for fulfilling disentanglement, typified by VAE-based methods\cite{higgins2016beta,kim2018disentangling}, emphasize both interpretability and sparsity, where sparsity means small distribution changes usually mainifest themselves in a sparse or local way in the disentangled factorization\cite{scholkopf2021toward}.

$\beta$-VAE\cite{higgins2016beta} introduces an extra hyperparameter $\beta$ into vanilla VAE objective function, making a trade-off between latent bottleneck capacity and independence constraints, thus encouraging the model to learn more efficient representation.
The objective function of $\beta$-VAE is as follows:
\begin{small}
\begin{equation}
	\mathcal{L}=\mathbb{E}_{q(z|x)}[\log p(x|z)] - \beta \text{KL}(q(z|x)\|p(z))
\end{equation}
\end{small}
where $z$ is the latent representation, $x$ observed data, $p(z)$ the prior distribution of latent factors, $p(x|z)$ the decoding distribution, and $q(z|x)$ the encoding posterior distribution,
When $\beta$ is set to $1.0$, this formulation degenerates to vanilla VAE, and when $\beta$ is appropriately tuned, $\beta$-VAE can learn disentangled representation from data in an unsupervised way.

FactorVAE\cite{kim2018disentangling} adds the term of Total Correlation into the objective function, which is formulated as the KL-divergence between marginal posterior $q(z)$ and its corresponding factorized distribution $\Bar{q}(z)$:
\begin{small}
\begin{equation}
	\mathcal{L}=\mathbb{E}_{q(z|x)}[\log p(x|z)] - \text{KL}(q(z|x)\|p(z)) - \gamma \text{KL}(q(z)\|\Bar{q}(z))
\end{equation}
\end{small}
where $\Bar{q}(z):=\prod_{j=1}^{d}q(z_j)$.
This formulation encourages independence for the posterior latent representation.
Since the Total Correlation term cannot be computed directly, an extra discriminator is added for density ratio estimation.

Despite of the success of disentangled representation learning, Locatello \textit{et al.}\cite{locatello2019challenging} challenge some common assumptions of unsupervised disentangled representation learning (e.g., independence of latent factors).
It also questions whether disentanglement can improve downstream task performances, inspiring later works to take downstream tasks into consideration, OOD generalization performance included.

However, whether disentangled representation benefits OOD generalization remains controversial.
Leeb \textit{et al.}\cite{2020arXiv200607796L} conduct some quantitative extrapolation experiments, finding that the learned disentangled representation fails to extrapolate to unseen data, while Tr{\"a}uble \textit{et al.}\cite{trauble2021disentangled} and Dittadi \textit{et al.}\cite{dittadi2020transfer} empirically verify the ability to generalize under OOD circumstances.
The advantage of disentangled representation on OOD tasks still requires further research and discussion.

\subsection{Causal Representation Learning}
\label{subsec:causal-rep}
Similar to conventional disentangled representation learning, causal representation learning aims to learn variables in the causal graph in an unsupervised or semi-supervised way.
Further, causal representation can be viewed as the ultimate goal of disentanglement, which satisfies the informal definition of disentangled representation in terms of interpretability and sparsity.
With the learned causal representation, one can capture the latent data generation process, which can help to resist the distributional shifts induced by interventions.

In real scenarios where observations are made in the form of images or sentences instead of structured data, high-level abstract information needs to be extracted from low-level data\cite{bengio2013representation}, and a few existing works\cite{yang2021causalvae, shen2020disentangled,scholkopf2021toward} propose to recover causal factorization through disentanglement.

CausalVAE\cite{yang2021causalvae} combines linear Structural Causal Model (SCM) into VAE model to endow the learned latent representation with causal structure.
Specifically, the causal structure is depicted by an adjacency matrix $A$ as:
\begin{small}
\begin{equation}
	z=A^T z + \epsilon = (I-A^T)^{-1}\epsilon,\quad \epsilon \sim \mathcal{N}(0, I)
\end{equation}
\end{small}
where $\epsilon$ represents the exogenous factors.
In practice, a mild nonlinear function $g_i$ is introduced for stability as $z_i=g_i(A_i\cdot z; \eta_i) + \epsilon_i$.
Further, extra labels $u$ of latent causal variables are used in CausalVAE, which gives the objective function as:
\begin{small}
\begin{equation}
	\mathcal{L}=-\text{ELBO}+\alpha \text{DAG}(A) + \beta l_u + \gamma l_m
\end{equation}
\end{small}
where ELBO represents the Evidence Lower Bound, $\text{DAG}(A)$ the Directed Acyclic Graph (DAG) constraint, $l_u=\mathbb{E}_{q_{\mathcal{X}}}||u-\sigma(A^T u)||_2^2$ measures how well $A$ describes causal relations among labels, and $l_m=\mathbb{E}_{z \sim q_{\phi}} \Sigma_{i=1}^n||z_i-g_i(A_i \cdot z; \eta_i)||_2^2$ measures how well $A$ describes causal relations among latent codes.
$q_{\mathcal{X}}$ is the empirical data distribution and $q_{\phi}$ the approximate posterior distribution.

Move a step on, DEAR\cite{shen2020disentangled} incorporates nonlinear SCM with a bidirectional generative model and assumes the known causal graph structure and extra supervised information of latent factors.
The objective function is given as:
\begin{small}
\begin{equation}
	\mathcal{L}(E, G, F)=\mathcal{L}_{gen}(E, G, F) + \mathcal{L}_{sup}(E)
\end{equation}
\end{small}
where $E,G$ denotes the encoder and generator, respectively.
The first part $\mathcal{L}_{gen}(E, G, F)=\text{KL}(q_E(x,z), p_{G,F}(x,z))$ resembles the VAE loss.
The difference lies in the prior distribution of $z$.
In DEAR, this prior is generated by the nonlinear SCM, while in vanilla VAE, it is simply a factorized Gaussian.
The second part is $\mathcal{L}_{sup}(E)=\mathbb{E}_{x,y}\text{CE}(\Bar{E}(x),u)$, where CE is the cross entropy loss function, $\Bar{E}$ represents the deterministic part of $E$ and $u$ the extra labels.

\section{Implication for fairness and explainability}
\label{sec:fairness}

\subsection{Fairness}
Nowadays, fairness issues have raised great concerns in decision-making systems such as loan applications \cite{mukerjee2002multi}, hiring processes \cite{rivera2012hiring}, and criminal justice \cite{larson2016we}.
Poorly designed algorithms tend to amplify data bias, resulting in discriminations against specific subgroups of individuals based on their inherent characteristics, which are often named sensitive attributes in fairness problems.
Many works define their fairness and propose corresponding fair algorithms, from which the definition of fairness can be divided into three types: individual fairness \cite{dwork2012fairness,yurochkin2021sensei}, group fairness \cite{hardt2016equality, kearns2018preventing, xu2020algorithmic}, and causality-based fairness notions \cite{kilbertus2017avoiding, kusner2017counterfactual,chiappa2019path}.
However, different fairness notions are in conflict \cite{kleinberg2016inherent}. Methods that mitigate unfairness in the algorithms fall under three categories: pre-processing \cite{wang2019repairing, feldman2015certifying, kamiran2012data}, in-processing \cite{zafar2017fairnessa, zafar2017fairnessb, agarwal2018reductions}, and post-processing \cite{hardt2016equality} algorithms.

Fairness has recently been linked to OOD issues, according to \cite{creager2020environment}.
Generally speaking, subgroups split by sensitive attributes in fairness literature correspond to environments in OOD literature.
Following that, both areas need to specify learning objectives with respect to the subgroups/environments. In fairness literature, the learning objectives represent context-specific fairness notions, while in OOD literature, the learning objectives should be designed according to invariance assumptions. Similar learning objectives could be adopted in both areas.
For example, objectives similar to fairness criterion equalized odds \cite{hardt2016equality} are adopted in OOD literature \cite{li2018deep, ahmed2021systematic} to deal with simplicity bias \cite{shah2020pitfalls}.
The learning objective of IRM \cite{arjovsky2019invariant} is also similar to calibration in fairness literature \cite{chouldechova2017fair}.
Meanwhile, classical approaches from OOD literature could be applied to address fairness issues.
Fair representation learning methods \cite{edwards2016censoring,madras2018learning,xu2020algorithmic,zhao2020conditional} originated from domain adaptation (DA) methods \cite{ben2010theory, ganin2016domain}.
When sensitive attributes are unknown, DRO and adversarially learning were introduced in fairness literature \cite{hashimoto2018fairness, lahoti2020fairness, duchi2020distributionally} to obtain a distributionally robust predictor and ensure the worst subgroup performance. \cite{kearns2018preventing, hebert2018multicalibration, kim2019multiaccuracy} also adopt adversarially learning methods to ensure all computationally identifiable subgroups are treated equally.
As a result, Pursuing OOD could be considered as pursuing fairness concerning the subgroups/environments if the invariance assumption adopted for OOD could be viewed as a fairness notion.

In addition to considering subgroups as environments, \cite{mandal2020ensuring}  investigate another scenario in which the environment is a separable variable. They studied fair classifiers that are robust to perturbations in the training distribution and devised a DRO-like method to reach their goal.
Fair and robust learning is also applied in \cite{roh2020fr}. These works differ from works listed in the last paragraph in that fairness and robustness are two objectives here whereas the aforementioned works consider them the same.

\subsection{Explainability}
Explanation methods can be generally divided into post hoc analyses and model-based methods \cite{murdoch2019definitions}. There exist several works in both directions. Post hoc analyses usually explain a black-box model by calculating feature importance \cite{adebayo2018sanity}. Typical methods include gradient-based \cite{selvaraju2017grad,sundararajan2017axiomatic,ramanishka2017top,dabkowski2017real}, influence function \cite{koh2017understanding}, and Shapley values \cite{lundberg2017unified}. Model-based explanation methods often adopt simpler hypothesis such as linear regression \cite{friedman2001elements}, LASSO \cite{tibshirani1996regression}, generalized additive models \cite{hastie1990generalized}, decision trees \cite{friedman2001elements}, and rule-based methods \cite{friedman2008predictive,letham2015interpretable}.

Causality \cite{pearl2009causality} has recently been introduced to model explanation, especially in deep learning methods. Traditional deep learning algorithms are rarely used in high-stakes applications due to their lack of explainability. Causality could provide a way to shed light on the explainability of deep learning. For example, several works adopt causality to explain deep models in textual and visual explanation \cite{alvarez2017causal,anne2018grounding, goyal2019counterfactual}. Futhermore, the Causal And-Or Graph was proposed in robotics \cite{xiong2016robot} and object tracking \cite{xu2018causal} to build explainable algorithms with the knowledge of causality. \cite{kim2017interpretable} also applied a causal filtering step in self-driving automobile problems.

\begin{equation} \label{eq:oodcausalexplain}
	\text{OOD} \longleftarrow \text{Causality} \longrightarrow \text{Explainability}.
\end{equation}

Actually, causality is the crux for both OOD and explainability as shown in equation \ref{eq:oodcausalexplain}. The models will have good OOD performance and explainability simultaneously if they utilize the causal relationship between the features and the outcomes. Hence, explainability would be a side product when pursuing OOD with causality.

\section{Problem Definition and Categorization of Methods}
\label{sec:problem}

In this section, we first formulate the general out-of-distribution (OOD) generalization problem, illustrate its connections and differences with classic $i.i.d.$ learning problem.
Then we categorize the existing methods which aim at addressing OOD generalization into several strands based on their positions through the whole learning pipeline.

\subsection{Problem Definition}
Let $\mathcal{X}$ be the feature space and $\mathcal{Y}$ the label space.
A parametric model is defined as $f_\theta: \mathcal{X} \to \mathcal{Y}$, which serves as a mapping function from original features to the label with learnable paratemeter $\theta$.
A loss function $\ell: \mathcal{Y} \times \mathcal{Y} \to \mathcal{R}$, which measures the distance between predicted label and groundtruth.
Then we can define the classic supervised learning problem.
\begin{problem}[Supervised Learning]
\label{pro:supervised_learning}
Given a set of $n$ training samples of the form $\{(x_1,y_1),\dots,(x_n,y_n)\}$ which are drawn from training distribution $P_{tr}(X,Y)$, a supervised learning problem is to find an optimal model $f_\theta^*$ which can generalize best on data drawn from test distribution $P_{te}(X,Y)$:
\begin{small}
\begin{equation}
\label{equ:supervised_learning}
	f_\theta^* = \arg\min_{f_\theta} \mathbb{E}_{X,Y\sim P_{te}}[\ell(f_\theta(X),Y)].
\end{equation}
\end{small}
\end{problem}

\subsubsection{$i.i.d.$ Learning}
Traditional learning algorithms usually assume that the training samples and test samples are both $i.i.d.$ realizations from a common underlying distribution, which means $P_{tr}(X, Y) = P_{te}(X,Y)$.
Based on such hypothesis, Empirical Risk Minimization (ERM) \cite{vapnik1991principles} which minimizes the average loss on training samples could obtain an optimal model which can successfully generalize to test distribution \cite{vapnik1999an}.
Specifically, ERM minimizes the following objective:
\begin{small}
\begin{equation}
	\label{eqn:erm}
	\mathcal{L}_{ERM}=\frac{1}{n} \sum \limits_{i=1}^n \ell(f_\theta(x_i),y_i).
\end{equation}
\end{small}

\subsubsection{Out-of-Distribution Generalization}
The admirable properties brought by $i.i.d.$ assumption offer a firm ground for the development of a plethora of learning models during the last few decades.
However, in real cases, the test distribution on which model been deployed may deviate from training distribution \cite{quinonero2009dataset}, that is $P_{tr}(X,Y)\neq P_{te}(X,Y)$.
The distribution shift can come into reality for many reasons such as the temporal/spatial evolution of data or the sample selection bias in data collection process.
In any case, it renders Problem \ref{pro:supervised_learning} more complicated than $i.i.d.$ learning scenario.
Moreover, the test distribution we may encounter is usually unknown due to the nature of applications like stream-based online scenario, where test data are generated in the future.
To sum up, the general out-of-distribution (OOD) generalization problem can be defined as the instantiation of supervised learning problem where the test distribution $P_{te}(X,Y)$ shifts from the training distribution $P_{tr}(X,Y)$ and remains unknown during the training phase.

In general, the OOD generalization problem is infeasible unless we make some assumptions on how test distribution may change.
Among the different distribution shifts, the covariate shift is the most common one and has been studied in depth.
Specifically, the covariate shift is defined as $P_{tr}(Y|X)= P_{te}(Y|X)$ and $P_{tr}(X)\neq P_{te}(X)$, which means the marginal distribution of $X$ shifts from training phase to test phase while the label generation mechanism keeps unchanged.
In this work, we mainly focus on the covariate shift and decribe various efforts which have been made to handle it \footnote{Other forms of distribution shifts like label shift \cite{NEURIPS2020_219e0524} and concept shift \cite{gama2014survey} are developed relatively independently and can be found in some well established surveys respectively.}.

A relative field with OOD generalization is domain adaptation, which assumes the availability of test distribution either labeled ($P_{te}(X,Y)$) or unlabeled ($P_{te}(X)$).
In a sense, domain adaptation can be seen as a special instantiation of OOD generalization where we have some prior knowledge on test distribution.
Under such mild conditions, domain adaptation could enjoy theoretical guarantees \cite{ben2010theory} which retain the optimality of trained model on test distribution.
The detailed illustration of domain adaptation methods is beyond the scope of this paper, curious readers may refer to some well established surveys \cite{pan2009survey, Sun2015, zhuang2021a, csurka2017domain}.
In this paper, we are more concerned about the general out-of-distribution generalization problem, which aims to improve the efficiency of model when evaluated on unknown test distribution.

\subsection{The Categorization of OOD Methods}
To tackle the challenges brought by unknown distributrion shift, tremendous efforts have been made in out-of-distribution generalization, resulting in a rich literature of related methods.
The adopted techniques vary greatly ranging from causality to representation learning and from structure-based to optimization-based.
However, to the best of our knowledge, little effort has been made to systematically and comprehensively survey these diverse methods in terms of a fairly broader sense of OOD generalization, as well as clarify the differences and connections between these work.
In this paper, we try to first fill this gap by reviewing the related methods of OOD generalization.

Generally speaking, the supervised learning problem defined as equation \ref{equ:supervised_learning} can be divided into three relatively independent components, namely
(1) the representation of features $X$ (e.g. $g(X)$);
(2) the mapping function $f_\theta(X)$ from features $X$ (or $g(X)$) to the label $Y$, which generally also known as model or the inductive bias;
(3) the formulation of optimization objective.
Therefore, we categorize the existing methods into three parts based on their positions in the whole learning pipeline accordingly:
\begin{itemize}
    \item \textbf{Unsupervised Representation Learning for OOD Generalization} includes Disentangled Representation Learning and Causal Representation Learning, which exploits the unsupervised representation learning techniques (e.g. variational Bayes) to embed prior knowledge into learning process.
    \item \textbf{Supervised Model Learning for OOD Generalization} includes Causal Learning, Stable Learning and Domain Generalization, which designs various model architectures and learning strategies to achieve OOD generalization.
    \item \textbf{Optimization for OOD Generalization} includes Distributionally Robust Optimization and Invariance-Based Optimization, which directly formulates the objective of OOD generalization and conduct optimization with theoretical guarantees for OOD optimality.
\end{itemize}

In the following sections, we provide a comprehensive and detailed review of these methods corresponding to the above order and discuss their differences and theoretical connections.
An overview of OOD generalization methods is shown in Table \ref{tab:overview}.

\section{Supervised Model Learning for OOD Generalization}
\label{sec:causal}

Apart from learning representations solely unsupervisedly, there are branches of works incorporating supervised information to design various model architectures and corresponding learning strategies.
In this section, we review such methods that focus on end-to-end model learning to achieve OOD generalization ability, including domain generalization, causal \& invariant learning and stable learning.

\subsection{Domain Generalization}
\label{subsec:DG}
Incorporating data from several source domains, Domain Generalization (DG) aims to learn models that generalizes well on unseen target domains, which focuses mostly on computer vision related classification problems as predictions are prone to be affected by disturbance on images (e.g., style, background, light, rotation, etc.).
Regarding to different methodological focuses, similar to Wang \textit{et al.}\cite{wang2021generalizing}, we divide DG methods into three branches, namely representation learning, training strategy and data augmentation.
Here we briefly introduce the three branches of methods, and one can refer to existing surveys of this field \cite{wang2021generalizing, zhou2021domain} for more details of DG methods.

\subsubsection{Representation Learning for DG}
\label{subsubsec:Rep-DG}
Representation learning remains a critical part in DG.
There are works\cite{muandet2013domain,albuquerque2020adversarial} that theoretically or empirically prove that if the representations remain invariant when the domain varies, the representations are transferable and robust on different domains.
Methods that attempts to learn invariant representations among different domains can be mainly divided into three categories, namely domain adversarial learning, domain alignment and kernel based methods.\\
\textbf{Domain adversarial learning}.
Ganin \textit{et al.} \cite{ganin2015unsupervised, ganin2016domain} propose domain-adversarial neural network (DANN) for domain adaptation.
DANN learns representations that are discriminative and invariant to the change of domains by jointly optimizing the underlying features, a label predictor that predicts class labels and is used both in the training and inference phase, and a domain classifier that discriminates between the source and the target domains during training.
The representations are trained to confuse the domain classifier so that domain invariant features are learned.
Li \textit{et al.}\cite{li2018domain} adopt this idea for DG and Gong \textit{et al.}\cite{gong2019dlow} further extend adversarial training to a manifold space.
Li \textit{et al.} \cite{li2018deep} propose to learn class-specific adversarial networks via a conditional invariant adversarial network (CIAN).
Garg \textit{et al.}\cite{garg2021learn} and Sicilia \textit{et al.}\cite{sicilia2021domain} provide theoretically guarantees via generalization bounds for domain adversarial training.
Rahman \textit{et al.}\cite{rahman2020correlation} introduce a correlation-aware adversarial framework for both Domain Adaptation (DA) and DG that jointly uses the correlation alignment metric and adversarial learning to decrease the domain discrepancy of the source and target data.
Shao \textit{et al.}\cite{shao2019multi}, Jia \textit{et al.}\cite{jia2020single} and Wang \textit{et al}.\cite{wang2020unseen} propose to use domain adversarial learning for face anti-spoofing and unseen target stance detection.
Zhao \textit{et al.}\cite{zhao2020domain} propose an additional entropy-regularization approach that learns invariant representations via minimizing the KL-divergence between the conditional distribution of different source domains. \\
\textbf{Domain alignment.}
Apart from domain adversarial learning, some works\cite{tzeng2014deep, wang2018visual, li2018domain} propose to learn domain invariant representations via the alignment of the features.
Motiian \textit{et al.}\cite{motiian2017unified} propose to learn semantic alignment between different domains by minimizing the distance between samples from different domains but the same class, and maximizing the distance between samples from different domains and classes.
Some works minimize the divergence of feature distributions by minimizing the maximum mean discrepancy (MMD) distance\cite{pan2010domain, tzeng2014deep, wang2018visual, wang2020transfer}, Wasserstein distance\cite{zhou2020domain}, the second order correlation\cite{sun2016deep, sun2016return, peng2018synthetic}, etc., for DA or DG. \\
\textbf{Feature normalization.}
There are works\cite{sun2016deep, sun2016return, wang2020transfer, jin2020domain} adopting feature normalization to constraint the domain discrepancy.
Pan \textit{et al.}\cite{pan2018two} present IBN-Net, which integrates both Instance Normalization (IN) \cite{ulyanov2017improved} and Batch Normalization (BN) \cite{ioffe2015batch} as building blocks, and learns to capture and eliminate domain variance.
Empirically, Pan \textit{et al.} \cite{pan2018two} find that IN provides visual and appearance invariance but may harm the discriminative information of representations.
Thus they propose to combine IN and BN in shallow layers and only BN in deeper layers.
Huang \textit{et al.}\cite{huang2017arbitrary} propose to enable arbitrary style transfer via an adaptive IN.
Nam \textit{et al.}\cite{nam2018batch} assume that each feature map of a convolutional encoder can be divided into a style-related part and shape-related part, and explicitly combine BN and IN to learn style-invariant representations.
Jin \textit{et al.}\cite{jin2021style} propose a Style Normalization and Restitution (SNR), which distills task-related features from the residual after the style normalization to ensure the discrimination.\\
\textbf{Kernel methods.}
Kernel methods are also extensively applied in DG.
Blanchard \textit{et al.}\cite{blanchard2011generalizing, blanchard2017domain} first address the domain generalization problem via kernel methods and propose to learn a domain-invariant kernel with the training data.
Muandet \textit{et al.}\cite{muandet2013domain} propose a classic kernel method for DG named Domain-Invariant Component Analysis (DICA), which minimizes distributional variance between samples from source domains.
Grubinger \textit{et al.}\cite{grubinger2015domain} propose Multi-TCA, an extension of transfer component analysis (TCA)\cite{pan2010domain} for transfer learning, which enables TCA to deal with multiple source and target domains by learning the shared subspace among source domains.
Gan \textit{et al.}\cite{gan2016learning} extend DICA with attribute regularization.
Erfani \textit{et al.}\cite{erfani2016robust} propose Elliptical Summary Randomization (ESRand), which projects domains into a latent space and minimizes the dissimilarity between data distributions with randomized kernel and elliptical data summarization.
Ghifary \textit{et al.}\cite{ghifary2016scatter} raise a unified framework named Scatter Component Analyis (SCA) for both DA and DG.
Based on scatter operating on reproducing kernel Hilbert space, SCA learn a domain invariant representation space by trading among minimizing the mismatch between domains, maximizing the discrepancy between classes and maximizing the variance of the whole data.
Hu \textit{et al.}\cite{hu2020domain} present a more fine-grained Multi-domain Discriminant Analysis (MDA) and analyze the bound on excess risk and generalization error for kernel-based domain invariant representation learning methods.
Other theoretical analysis for kernel methods for DG are introduced in \cite{blanchard2011generalizing, deshmukh2019generalization}.

\subsubsection{Training strategy}
\label{subsubsec:Tr-DG}
Given that DG focuses mostly on computer vision related classification problems, some works study training strategies to enhance the generalization ability of deep models on image data, which can be divided into four categories, namely meta learning, ensemble learning, unsupervised/semi-supervised DG and others.\\
\textbf{Meta learning.} Meta learning gains experience over multiple learning episodes via an alternative learning paradigm\cite{hospedales2020meta}.
Finn \textit{et al.} \cite{finn2017model} propose model-agnostic meta-learning (MAML) for DA, which introduces the concept of "episodes" in the training phase and greatly influence the research of meta learning for DG.
Li \textit{et al.} \cite{li2018learning} first apply meta-learning to DG and some improvements are made in the following works\cite{balaji2018metareg, otalora2019staining, li2019feature, dou2019domain,liu2020shape, du2020learning, du2020metanorm,zhao2021learning, choi2021meta}.
The main idea of meta learning for DG is to divide the source domains into meta-train and meta-test, where the loss of meta-train and meta-test are optimized simultaneously.

\textbf{Model-ensemble learning.}
Typically, model-ensemble learning based methods learn ensembles of multiple specific models for different source domains to improve the generalization ability.
Some works adopt domain specific subnetworks for different source domains, together with one single classifier\cite{zhou2020domain, d2018domain,ding2017deep} or multiple domain-specific classifier heads\cite{wang2020dofe}.
Others use domain-specific batch normalization for different domains to learn a better normalization\cite{segu2020batch, mancini2018best}.\\
\textbf{Unsupervised/Semi-supervised DG.}
Recently, inspired by unsupervised and semi-supvervised domain adaptation\cite{sun2019unsupervised, daume2010frustratingly, xiao2014feature}, some works propose to enhance model's generalization ability by unsupervised or semi-supervised learning\cite{zhang2021domain, liao2020deep}.
Zhang \textit{et al.} \cite{zhang2021domain} propose Domain-Irrelevant Unsupervised Learning (DIUL) to cope with the distribution shifts between source domains and target domains.
They select valid negative samples for any given queue samples according to the similarity between different domains to learn domain-irrelevant representations. \\
\textbf{Others}
Inspired by the self-supervised learning method\cite{noroozi2016unsupervised}, Carlucci \textit{et al.}\cite{carlucci2019domain} combine a self-learning puzzles task with the classification task to learn robust representations.
Ryu \textit{et al.}\cite{ryu2019generalized} propose to sample positive and negative samples via random forest.
Li \textit{et al.}\cite{li2019episodic} alternatively train convolutional layers and the classifier.
Huang \textit{et al.}\cite{huang2020self} introduce a self-challenging dropout algorithm to prevent the model from overfitting to source domains.

\subsubsection{Data augmentation}
\label{subsubsec:Da-DG}
Data augmentation is a common and effective method in deep learning especially in computer vision.
The generalization ability of deep models largely depends on the heterogeneity of available data.
Thus heterogeneity brought by data augmentation could prevent overfitting and improve the generalization ability.
The data augmentation methods for DG can be divided into randomization based augmentation\cite{yue2019domain, tobin2017domain, peng2018sim, khirodkar2019domain, tremblay2018training, prakash2019structured}, gradient based augmentation\cite{shankar2018generalizing, volpi2018generalizing, zhou2020deep} and generation based augmentation\cite{qiao2020learning, rahman2019multi, zhou2020learning, somavarapu2020frustratingly}.

\subsection{Causal \& Invariant Learning}
\label{subsec:causal}
Comparing with domain generalization which typically targets on vision tasks, causal learning and invariant learning stems from causal inference literature and addresses the OOD generalization problem from a more principle way, which aims to explore causal variables for prediction and becomes more practical recently.
We firstly introduce some preliminaries of causal learning, and then review branches of typical works.

\subsubsection{Preliminaries}
For causal learning methods, it is often assumed that there exist data heterogeneity and causal relationship inside data.
Specifically, causal learning assumes that one has access to data from multiple environments, as demonstrated in Definition \ref{definition:heterogeneity-of-data}.
\begin{definition}[Heterogeneity of Data]
\label{definition:heterogeneity-of-data}
	Consider a dataset $D=\left\{D^e\right\}_{e\in \mathrm{supp}(\mathcal{E}_{tr})}$, which is a mixture of data $D^e=\left\{X^e, Y^e\right\}$ collected from multiple training environments $e\in \mathrm{supp}(\mathcal{E}_{tr})$, $X^e\subset\mathcal{X}$ and $Y^e\subset\mathcal{Y}$ are the collection of data and label from environment $e$, respectively.
$\mathcal{E}_{tr}$ and $\mathcal{E}$ are random variables on indices of training environments
and all possible environments, respectively, such that $\mathrm{supp}(\mathcal{E})\supset \mathrm{supp}(\mathcal{E}_{tr})$.
$P^e$ denotes the distribution of data and label in environment $e$.
Usually, for all $e\in \mathrm{supp}(\mathcal{E})\setminus \mathrm{supp}(\mathcal{E}_{tr})$, the data and label distribution $P^e(X,Y)$ can be quite different from that of training environments $\mathcal{E}_{tr}$.
\end{definition}

\begin{assumption}[Causality Assumption\cite{buhlmann2018invariance}]
\label{assumption: causality}
	The structural equation models:
	\begin{align}
		Y^e &\leftarrow f_Y(X_{\text{pa}(Y)}^e, \epsilon_Y^e),\text{ $\epsilon_Y^e \perp X_{\text{pa}(Y)}^e$}
	\end{align}
	remains the same across all environments $e\in\text{supp}(\mathcal{E}_{all})$, that is, $\epsilon_Y^e$ has the same distribution as $\epsilon_Y$ for all environments.
	$\mathrm{pa}(Y)$ denotes the direct causes of $Y$.
\end{assumption}
And the assumption of causality is given by Assumption \ref{assumption: causality}, which originates from causal inference literature and assumes the causally invariant relationship between the target $Y$ and its direct causes $X_{\text{pa}(Y)}$.
Such assumptions indicate that causal variables $X_{\text{pa}(Y)}$ are stable across different environments or data selection biases, which motivates branches of works to achieve OOD generalization via leveraging only causal variables.

\subsubsection{Causal Inference-Based Methods}
\label{subsubsec:causal}
Firstly, we review methods related to causal inference, which try to obtain causal variables from heterogeneous data.

It is well known that a gold standard for identifying causal effect of a variable is to conduct randomized experiments like A/B testing, but fully randomized experiments are usually expensive and even infeasible in real applications.
Since causal inference or causal structural learning is very ambitious, these inference techniques should be considered as "groundtruth" but not necessarily able to be realized in practice (like typical machine learning settings).
Therefore, it is more practical to design such techniques that have a more "causal explanation" than a standard regression or classification framework and could also gain some sort of invariance across environments.
Follow such intuition, a strand of methods \cite{peters2016causal, Pfister2018, rothenhausler2018anchor, Heinze-Deml2018, Gamella2020, Oberst2021} have been developed by leveraging the heterogeneity inside data (e.g., multiple environments).

\begin{assumption}[Invariance Assumption]
\label{assumption:invariance}
	There exists a subset $S^*\subseteq \{1,\ldots ,p\}$ of the covariate indices (including the empty set) such that
	\begin{eqnarray}
		P(Y^e|X_{S^*}^e)\ \mbox{is the same for all}\ e \in {\cal E}.
	\end{eqnarray}
	That is, when conditioning on the covariates from $S^*$ (denoted by
	$X^e_{S^*}$), the conditional distribution is invariant across all environments from ${\cal E}$.
\end{assumption}
Peters \textit{et al.}\cite{peters2016causal} first try to investigate the fact that "invariance" could, to some extent, infer the causal structure under necessary conditions and propose Invariant Causal Prediction(ICP).
Specifically, they leverage the fact that when considering all direct causes of a target variable, the conditional distribution of the target given the direct causes will not change when interfering all other variables in the model except the target itself.
Then they perform a statistical test whether a subset of covariates $S$ satisfies the invariance assumption \ref{assumption:invariance} for the observed
environments in $\mathcal{E}$.
The null-hypothesis for testing is:
\begin{eqnarray*}
	H_{0,S}({\cal E}):\ \mbox{invariance assumption}\ \mbox{holds}.
\end{eqnarray*}
and all subsets of covariates $S$ which lead to invariance are intersected, that is:
\begin{eqnarray*}\label{icp}
	\Scale[0.9]{\hat{\cal S}({\cal E}) = \bigcap_{S} \{S;\ H_{0,S}({\cal E})\ \mbox{not rejected by test at significance level}\ \alpha\}.}
\end{eqnarray*}
Under the assumption of structural equation model and gaussian residual described in \cite{peters2016causal}, ICP with Chow test \cite{chow1960tests} could, at least with controllable probability 1-$\alpha$, discover subsets of true causal variables, which reads as:
\begin{eqnarray}
	\mathbb{P}[\hat{\cal S}({\cal E}) \subseteq \mathrm{pa}(Y)] \ge 1- \alpha,
\end{eqnarray}
where $\mathrm{pa}(Y)$ denotes the direct causes of target $Y$ (e.g. the parental variables of $Y$ in the causal graph).

Though being the first attempt to connect the invariance to causality, ICP has several limitations.
The most straight-forward one is the strict requirements for heterogeneity, since the power of ICP depends highly on the quality of available environments $\mathcal{E}_{tr}$(or perturbations).
If the available perturbed subpopulations are not enough, or even single environment, the efficacy of ICP will be lost.
As discussed in \cite{Pfister2018}, naively estimating the environments from data and then applying ICP may yield less powerful results, so instead of using static data, Pfister \textit{et al.} \cite{Pfister2018} propose to leverage the sequential data from non-stationary environment to detect instantaneous causal relations in multivariate linear time series, which relaxes the assumption of known environments.
Besides environmental specification, there are other works trying to consolidate the coverage of the so-called invariance-based method.
For example, Heinze-Deml \textit{et al.}\cite{Heinze-Deml2018} extend the ICP into non-linear model and continuous environments; Gamella \textit{et al.}\cite{Gamella2020} apply the ICP into an active learning setting where the interventions (a.k.a. environments) can be proactively chosen during training.

ICP serves as a milestone towards inferring causal structure via invariance property.
However, the invariance assumption may be violated in more complicated scenarios.
Among which, the most common case is the existence of hidden confounders.
Instrument variable(IV) method is one typical method for dealing with hidden confounders, which  require the instrument variable $E$ not to directly act on hidden confounding variable $H$ and outcome variable $Y$, as shown in Figure \ref{subfig:anchor-a}.
\begin{figure}[htbp]
	\vskip -0.1in
	\centering
	\subfloat[SCM of traditional instrument variable model]{
	\label{subfig:anchor-a}
		\includegraphics[width=0.35\linewidth]{figure/IV.png}
	}
	\hspace{0.15in}
	\subfloat[SCM of anchor regression model]{
	\label{subfig:anchor-b}
		\includegraphics[width=0.35\linewidth]{figure/Anchor.png}
	}
	\caption{Comparision of SCM between IV model and Anchor Regression model.}
	\label{fig:anchor}
\end{figure}

Rothenh\"ausler \textit{et al.} \cite{rothenhausler2018anchor} investigate more relaxed conditions than the standard IV model which allow the direct effect of instrument variable (which they called anchor variabls) on $H$ and $Y$, as shown in Figure \ref{subfig:anchor-b}.
They realize that despite the attractive notion of invariance guarantee against arbitrarily large intervention or perturbation, one seldom encounters such extreme cases, and exact invariance could be too conservative for moderately perturbed data.
Specifically, they the following structural equation:
\begin{small}
\begin{eqnarray}
	Y = X^T \beta + H^T \alpha + A^T \xi + \epsilon_Y,
\end{eqnarray}
\end{small}
with $X \in \mathbb{R}^p,\ H \in \mathbb{R}^q$ and $A \in \mathbb{R}^r$, and proposed a regularized formulation of ordinary least squares model by the error projection to the space spanned by anchor variables.
\begin{eqnarray}\label{anchor-est}
	\Scale[0.8]{\hat{\beta}(\gamma) = \mbox{argmin}_b \left(\|(I - \Pi_{\mathbf{A}})(\mathbf{Y} - \mathbf{X}
		b)\|_2^2/n + \gamma \|\Pi_{\mathbf{A}}(\mathbf{Y} - \mathbf{X} b)\|_2^2/n \right).}
\end{eqnarray}
where $\Pi_{\mathbf{A}}$ denotes the projection in $\mathbb{R}^n$ onto the column space of $\mathbf{A}$.
For $\gamma = 1$, $\hat{\beta}(1)$ equals the ordinary least squares estimator, for $\gamma \to \infty$ it obtains the two-stage least squares procedure from IV regression.

Sometimes the observation of instrument $A$ is still hard to fulfill, Oberst \textit{et al.} \cite{Oberst2021} further relax the assumption by introducing the noisy proxy of $A$ and prove the robustness of the method under bounded shifts.

\subsubsection{Invariant Learning}
\label{subsubsec:inv}
Deriving from causal inference based methods, invariant learning methods, typified by invariant risk minimization(IRM, \cite{arjovsky2019invariant}), target on latent causal mechanisms and extend ICP to more practical and general settings.
Different from causal prediction methods that assumes on raw variable level, IRM makes the invariance assumption as:
\begin{assumption}[IRM's Invariance Assumption]
\label{assumption: IRM-invariance}
	There exists data representation $\Phi(X)$ such that for all $e,e' \in \text{supp}(\mathcal{E}_{tr})$, $\mathbb{E}[Y|\Phi(X^e)]=\mathbb{E}[Y|\Phi(X^{e'})]$, where $\mathcal{E}_{tr}$ denotes the available training environments.
\end{assumption}
which generalizes the former invariance assumption to representation level.
Then Arjovsky \textit{et al.}\cite{arjovsky2019invariant} propose to find data representation $\Phi(X)$ that can both predict well and elicit an invariant linear predictor $w$ across $\mathcal{E}_{tr}$, which results in the following objective function:
\begin{small}
\begin{align}
\label{equ:IRM}
	&\ \ \min\limits_{\Phi(X), w}\sum_{e\in\text{supp}(\mathcal{E}_{tr})} \mathcal{L}^e(w\odot \Phi(X),Y)\\
	&\text{s.t. } w\in \arg\min_{\overline{w}}\mathcal{L}^e(\overline{w}\odot\Phi(X)),\text{ for all }e\in\text{supp}(\mathcal{E}_{tr})
\end{align}
\end{small}

In order to achieve invariance across $\mathcal{E}_{all}$ by enforcing low error of equation \ref{equ:IRM} on $\mathcal{E}_{tr}$, IRM requires sufficient diversity across environments and makes the following assumption.

\begin{assumption}[IRM's Condition, Assumption 8 in \cite{arjovsky2019invariant}]
\label{assumption:IRM2}
	A set of training environments $\mathcal{E}_{tr}$ lie in linear general position of degree $r$ if $|\mathcal{E}_{tr}|>d-r+\frac{d}{r}$ for some $r\in \mathbb{N}$, and for all non-zero $x\in\mathbb{R}^d$:
	\begin{small}
	\begin{equation}
		\mathrm{dim}\left(\mathrm{span}\left(\{\mathbb{E}_{X^e}[X^e{X^e}^T]x - \mathbb{E}_{X^e, \epsilon^e}[X^e\epsilon^e]\}_{e\in\mathcal{E}_{tr}}\right)\right) > d-r
	\end{equation}
	\end{small}
\end{assumption}

With Assumption \ref{assumption:IRM2}, IRM proves that in linear case, if a representation $\Phi(X)$ of rank $r$ elicits an invariant predictor $w\circ \Phi(X)$ across $\mathcal{E}_{tr}$ and $\mathcal{E}_{tr}$ lies in linear general position of degree $r$, then $w\circ \Phi(X)$ is invariant across $\mathcal{E}_{all}$(Therorem 9 in \cite{arjovsky2019invariant}).
The assumptions about linearity, centered noise, and independence between the noise $\epsilon^e$ and the causal variables from the theoretical analysis in IRM (Theorem 9 in \cite{arjovsky2019invariant}) also appear in ICP\cite{peters2016causal}, while IRM does not assume as ICP \cite{peters2016causal} that the data is Gaussian, the existence of a causal graph, or that the training environments arise from specific types of interventions.
And the result extends to latent causal variables while ICP \cite{peters2016causal} restricts to raw causal feature level.

Based on IRM which is motivated by the representation $\Phi(X)$ such that $\mathbb{E}[Y|\Phi(X)]$ remains invariant, follow-up works have proposed variations on this objective with stronger regularization of the invariance assumption \ref{assumption: IRM-invariance}, resulting in similar alternatives.
Ahuja \textit{et al.}\cite{ahuja2020invariant} incorporate game theory and replace the linear classifier in IRM with an ensemble of classifiers from different environments.
Jin \textit{et al.}\cite{jin2020domain} replace the regularizer of IRM with a predictive regret and impose stronger constraints on $\Phi(X)$.
Krueger \textit{et al.}\cite{krueger2021out} propose to penalize the variance of the risks across environments, while Xie \textit{et al.}\cite{xie2020risk} raise almost the same objective but replace the original penalty with the square root of the variance.
Mahajan \textit{et al.}\cite{pmlr-v139-mahajan21b} introduce a contrastive regularizer which matches the representation of same objects across environments.
And Creager \textit{et al.} targets on the problem of missing environment labels of IRM, and raise Environment Inference for Invariant Learning(EIIL \cite{creager2020environment}) to learn environments that maximize the IRM's penalty.
The whole algorithm is two-stage, which firstly generates environments according to a biased reference model, and then performs invariant learning with learned environments.

While the results in IRM seems promising, Rosenfeld \textit{et al.}\cite{rosenfeld2020risks} point out some problems of IRM on classification tasks.
In the linear case, they give simple conditions under which the optimal solution succeeds or, more often, fails to recover the optimal invariant predictor.
Specifically, Rosenfeld \textit{et al.}\cite{rosenfeld2020risks} show that there exists a feasible solution which uses \emph{only the environmental features} yet performs better than the optimal invariant predictor on all $e\in\mathcal{E}_{all}$ (Theorem 5.3 in \cite{rosenfeld2020risks}).
In nonlinear regime, they show that IRM can fail catastrophically unless the test data are sufficiently similar to the training distribution (Theorem 6.1 in \cite{rosenfeld2020risks}.
And Kamath \textit{et al.}\cite{kamath2021does} also demonstrate that it is possible for IRM to learn a sub-optimal predictor, due to the loss function not being invariant across environments.
Ahuja \textit{et al.}\cite{ahuja2020empirical} compare IRM with ERM from the sample complexity perspective in different shift patterns (Table 1 in \cite{ahuja2020empirical}), which indicates that under covariate shifts, IRM has no obvious advantage to ERM, and for other distribution shifts such as those involving confounders or anti-causal variables, IRM is guaranteed to be close to the desired OOD solutions in the finite sample regime.

\subsection{Stable Learning}
\label{subsec:stable}
Compared with domain generalization and causal learning, stable learning inspires another way for incorporating causal inference with machine learning, which significantly relaxes the requirements for multiple environments.
The problem setting of stable learning is as following:
\begin{problem}[Settings of Stable Learning]
Given training data $D^{e}=(X^{e},Y^{e})$ from one environment $e\in \text{supp}(\mathcal{E}_{all})$, the goal of stable learning is to learn a predictive model with \textbf{uniformly good performance} on any possible environments in $\text{supp}(\mathcal{E}_{all})$.
\end{problem}
To solve such difficult problem, motivated by the literature of variable balancing strategies \cite{athey2016approximate,zubizarreta2015stable,hainmueller2011entropy}, Shen \textit{et al.} \cite{shen2018causally} propose to consider all the variables as the treatment and learn a set of global sample weights that could remove the confounding bias for all the potential treatments from data distribution.
They derive a global balancing loss which can be easily plugged into standard machine learning tasks as a regularizer, as depicted by equation \ref{equ:causal_regularizer}:
\begin{small}
\begin{equation}
\label{equ:causal_regularizer}
\sum_{j=1}^{p} \left\|\frac{{\boldmath}{X}_{-j}^{T}\cdot(W\odot {\boldmath}{I}_j)}{W^{T}\cdot {\boldmath}{I}_j}-\frac{{\boldmath}{X}_{-j}^{T}\cdot(W\odot (1-{\boldmath}{I}_j))}{W^{T}\cdot (1-{\boldmath}{I}_j)}\right\|_2^2,
\end{equation}
\end{small}
where $W$ denotes the sample weights, $\big\|\frac{{\boldmath}{X}_{-j}^{T}\cdot(W\odot {\boldmath}{I}_j)}{W^{T}\cdot {\boldmath}{I}_j}-\frac{{\boldmath}{X}_{-j}^{T}\cdot(W\odot (1-{\boldmath}{I}_j))}{W^{T}\cdot (1-{\boldmath}{I}_j)}\big\|_2^2$ represents the loss of confounder balancing when setting feature $j$ as treatment variable, and ${\boldmath}{X}_{-j}$ is the remaining features (i.e. confounders) except $j^{th}$ column.
The ${\boldmath}{I}_j$ means the $j^{th}$ column of ${\boldmath}{I}$, and ${\boldmath}{I}_{ij}$ refers to the treatment status of unit $i$ when setting feature $j$ as treatment variable.
By minimizing the global balancing loss, the confounding bias could be removed in a global scale.

Further, Kuang \textit{et al.}\cite{kuang2018stable} incorporate unsupervised feature representation into the global balancing stage with auto-encoders\cite{Sch2007Greedy} and modify the original regularizer to a "deep" version as equation \ref{equ:causal_regularizer_deep}:
\begin{small}
\begin{equation}
\label{equ:causal_regularizer_deep}
\sum_{j=1}^{p}\left\|\frac{\phi\left(\mathbf{X} \cdot_{,-j}\right)^{T} \cdot\left(W \odot \mathbf{X} \cdot_{j}\right)}{W^{T} \cdot \mathbf{X}_{\cdot}, j}-\frac{\phi\left(\mathbf{X} \cdot_{,-j}\right)^{T} \cdot\left(W \odot\left(1-\mathbf{X} \cdot_{, j}\right)\right)}{W^{T} \cdot(1-\mathbf{X} \cdot, j)}\right\|_{2}.
\end{equation}
\end{small}
Above methods are limited to binary features since the main stream discussions about causal inference are within the scope of binary treatment.
When the treatment variable is categorical or continuous, traditional balancing methods are no long feasible as the treatment level could be infinitely large.
To mitigate such limitation and address the continuous treatment problem, Kuang \textit{et al.}\cite{kuang2020stable} propose to learn a set of sample weights so that the weighted distribution of treatment and confounder could satisfy the independent condition, which corresponds to the fact that if the treatment and confounder are independent, the treatment effect can be estimated accurately.

Apart from methods addressing confounder bias, Shen \textit{et al.} \cite{shen2020stable} target on the model mis-specification problem for linear model in stable learning.
The main challenge of stable learning in linear model is the inevitable model mis-specification in real scenarios.
In other words, besides the linear part, the true generation process actually contains an additional mis-specification term which could be non-linear term or interactions between input variables.
\begin{equation}
y=x^{\top} \bar{\beta}_{1 ; p}+\bar{\beta}_{0}+b(x)+\epsilon
\end{equation}
They find that the collinearity between variables play an crucial role on learning a stable model.
If a mis-specified model is used at the training time, the existence of collinearity among variables can inflate a small misspecification error to arbitrarily large, thus causes instability of prediction performance across different distributed test data.

In order to alleviate the collinearity among variables, Shen \textit{et al.}\cite{shen2020stable} propose to learn a set of sample weights which can make the design matrix near orthogonal.
Technically, they construct an uncorrelated design matrix $\tilde{X}$ from original $X$ as the 'oracle', and learn the sample weights $w(x)$ by estimating the density ratio $w(x)=p_{\tilde{D}}(x)/p_{D}(x)$ of underlying uncorrelated distribution $\tilde{D}$ and original distribution $D$.

Further, to mitigate the large variance and shrinkage of the effective sample size brought by sample reweighting, Shen \textit{et al.}\cite{shen2020stableD} propose to leverage the unlabeled data collected from multiple environments and recover the hidden cluster structures among variables.
Under several technical assumptions, they\cite{shen2020stableD} prove that, decorrelating the variables between clusters instead of each other would be sufficient to achieve a stable estimation while preventing the variance inflation.

\begin{figure*}[ht]
    \centering
    \includegraphics[width=0.75\textwidth]{figure/stablenet_structure.jpg}
    \vspace{-8pt}
    \caption{The overall architecture of StableNet from \cite{zhang2021deep}. LSWD refers to \textit{learning sample weighting for decorrelation} and \textit{Final loss} is used to optimized the classification network.}
    \label{fig:stablenet}
    \vspace{-8pt}
\end{figure*}

Recently, Zhang \textit{et al.}\cite{zhang2021deep} propose StableNet, as shown in figure \ref{fig:stablenet}, which extends former linear frameworks\cite{kuang2018stable, shen2020stable, kuang2020stable} to incorporate deep models.
As the complex nonlinear dependencies among features obtained in deep model are much more difficult to measure and eliminate than the linear case, to remedy for this, StableNet proposes a novel nonlinear feature decorrelation approach based on Random Fourier Features (RFF) \cite{rahimi2007random}.
Specifically, StableNet iteratively optimizes sample weights $\mathbf{w}$, representation function $f$, and prediction function $g$ as follows:
\begin{small}
\begin{equation} \label{eq:overall}
    \begin{aligned}
        f^{(t+1)}, g^{(t+1)} = & \underset{f, g}{\arg \min} \sum_{i=1}^n w^{(t)}_i \mathcal{L}(g(f(\mathbf{X}_i)), y_i), \\
        \mathbf{w}^{(t+1)} = & \underset{\mathbf{w} \in \Delta_n}{\arg \min} \sum_{1 \le i < j \le m_Z} \left\Vert\hat{\Sigma}_{\mathbf{Z}^{(t+1)}_{:,i}\mathbf{Z}^{(t+1)}_{:, j};\mathbf{w}}\right\Vert_F^2. \\
    \end{aligned}
\end{equation}
\end{small}
where $\mathbf{Z}^{(t+1)}=f^{(t+1)}(\mathbf{X})$, $\mathcal{L}(\cdot, \cdot)$ represents the cross entropy loss function and $t$ represents the time stamp.
The sample reweighting module and the representation learning network are jointly optimized in StableNet and they can effectively partial out the environment related features and leverage truly category related and discriminative features for prediction, leading to more stable performances in the wild non-stationary environments.

Moreover, Kuang \textit{et al.}\cite{DBLP:journals/corr/abs-2006-04381} subsample the data to reduce the confounding effects induced by the distributional shifts.
Wang \textit{et al.}\cite{DBLP:conf/ijcai/WangFKSLW20} incorporate the decorrelation mechanism into clustering and achieve better clustering performance under data selection bias.
Zhang \textit{et al.}\cite{DBLP:conf/mm/ZhangJWKZZYYW20} propose a Deconfounded Visio-Linguistic Bert framework to mitigate the potential data biases.
And Yuan \textit{et al.}\cite{9428205} propose to identify causal features with meta-learning mechanism for OOD generalization.

\subsection{Datasets}
Datasets can be classified according to different criterions, for example, synthetic data and real-world data, raw feature data and complicated data, and different research fields utilize different kinds of datasets, for example, traditional statistical learning often uses synthetic data; computer vision often uses real-world image data.
As for OOD generalization problem, different from traditional machine learning tasks which are based on $i.i.d.$ assumption, it is necessary to involve or generate the distributional shifts to simulate the unknown testing distribution, so as to test whether an algorithm can generalize to unseen distributions.
Therefore, in line with recent works on OOD generalization, we find it necessary to use both the synthetic \& simple data and real-world \& complicated data to verify the effectiveness of an OOD generalization method.

\subsubsection{Synthetic Data}
Synthetic data are important tools to simulate explainable and controllable distributional shifts.
As Aubin \textit{et al.}\cite{aubin2021linear} find that recent OOD generalization methods perform poorly on some simple low-dimensional linear problems, it is necessary to test OOD generalization methods on such simple but challenging data, which can reflect whether and to what extent an algorithm can resist certain kind of distributional shifts.

Generally speaking, there are three mechanisms to simulate distributional shifts across environments, named by selection bias, confounding bias and anti-causal effect, with which one can simulate certain kind of distributional shifts to various degrees and clearly justify an algorithm's real effect.
In these mechanisms, the covariates $X$ are divided into two groups as $X=[S,V]^T$, corresponding to the invariant and variant parts inside data.
And it is assumed that $P(Y|S)$ remains invariant across environments, and $P(Y|V)$ is perturbed with different mechanisms, which brings distributional shifts.\\\\
\textbf{(a) Selection Bias}\\
Kuang \textit{et al.}\cite{kuang2020stable} propose a selection bias mechanism to introduce distributional shifts, and similar settings are also adopted in \cite{liu2021stable, hrm}.
In this setting, $P(Y|V)$ is perturbed with selection bias.
The data generation process is as following:
\begin{small}
	\begin{align}
		Y = f(S)+\epsilon = \theta_S^TS + \beta S_1\cdot S_2\cdot S_3 + \epsilon
	\end{align}
\end{small}
and the selection probability $\hat{P}(x,y)$ of certain data point $(x,y)$ is calculated as:
\begin{small}
	\begin{align}
		\hat{P} = \prod_{v_i \in V}|r|^{-5*|f(S) - \text{sign}(r)*v_i|}
	\end{align}
\end{small}
where $|r|>1$ is the selection factor and controls the distributional shifts.
Intuitively, $r$ eventually controls the strengths and direction of the spurious correlation between $V$ and $Y$(i.e. if $r>0$, a data point whose $V$ is close to its $Y$ is more probably to be selected.).
The larger value of $|r|$ means the stronger spurious correlation between $V$ and $Y$, and $r \ge 0$ means positive correlation and vice versa.
Since the distributional shift is absolutely controlled by $r$, one can adopt different $r$ to simulate different extents of distributional shifts, as done in \cite{kuang2020stable, liu2021stable, hrm}.\\\\
\textbf{(b) Confounding Bias}\\
Confounding bias is also one of the most common means of distributional shifts\cite{pearl2009causality, subbaswamy2018counterfactual, arjovsky2019invariant}.
Compared to selection bias, in this setting, the variant feature $V$ is related to target $Y$ owing to the unobserved confounder $C$.
For example, the data generation process proposed by Subbaswamy \textit{et al.}\cite{subbaswamy2018counterfactual} is as following:
\begin{small}
\begin{align}
	V &= W^e_VC + \epsilon_V\\
	Y &= W_S^TS + W_cC + \epsilon_Y
\end{align}
\end{small}
where coefficient $W_V^e$ controls the relationship between $V$ and $Y$, and one can change $W_V^e$ across environments to simulate the distributional shifts.\\\\
\textbf{(c) Anti-Causal Effect}\\
Besides the above mechanisms, Arjovsky \textit{et al.}\cite{arjovsky2019invariant} and Liu \textit{et al.}\cite{hrm} introduce an anti-causal mechanism to change $P(Y|V)$.
In this setting, the data generation process is as following:
\begin{small}
\begin{align}
	Y &= W_S^TS + \epsilon_Y\\
	V &= W_V^eY + \epsilon_V^e
\end{align}
\end{small}
where coefficient $W_V^e$ and experimental $\epsilon_y, \epsilon_V^e$ controls the relationship between $V$ and $Y$.
Intuitively, larger $\epsilon_Y$ and smaller $\epsilon_V^e$ will make model easier to utilize $V$ for prediction, making OoD generalization more challenging.

\subsubsection{Real-World Data}
Synthetic data are easy to generate distributional shifts to varying degrees, and they can sufficiently test whether an algorithm can generalize to unseen distributions.
However, synthetic data are rather simple and it is difficult to generate complicated data (e.g., images).
Further, whether an algorithm can solve real-world distributional shift problems is also an important criterion to evaluate an OOD generalization method.
Therefore, it is necessary to involve real-world datasets.
Here, we describe the most popular real-world datasets used in OOD literature, including image datasets and other forms of dataset (e.g., tabular data, language data).
A summary of these datasets can be found in Table \ref{tab:bk}.\\\\
\textbf{Image Datasets}\\
With the rapid development of computer vision, there are a number of image datasets been raised, and we classify them into three categories with respect to the flexibility of simulating distributional shifts, namely synthetic transformation data, fixed wild data and controllable wild data.\\\\
(a) \textsc{synthetic transformation data}.\\
Although most image datasets are not produced for OOD generalization, people modify them with some synthetic transformations to simulate distributional shifts.
The most typical ones, including ImageNet\cite{deng2009imagenet} variants (e.g. ImageNet-A\cite{hendrycks2021natural}, ImageNet-C\cite{hendrycks2019benchmarking}, ImageNet-R\cite{hendrycks2020many}) adopt special data selection policy or perturbations to generate testing data with distributional shifts.
Others, typified by MNIST\cite{lecun1998gradient} variants (e.g. Colored MNIST\cite{arjovsky2019invariant},
    MNIST-R\cite{ghifary2015domain}), simulate different environments by coloring or rotating original images.
Being well-designed, these datasets make it available for preliminary study and effectiveness verification of OOD generalization algorithms.\\\\
(b) \textsc{Fixed wild data}. \\
There are a few datasets built to support OOD generalization validation, which mainly utilize real-world backgrounds or environments.
Widely used in domain generalization, PACS\cite{li2017deeper} and Office-Home\cite{venkateswara2017deep} adopt the image style (e.g., art, cartoon) to differentiate domains/distributions, and VLCS\cite{fang2013unbiased} takes data collected independently from four sources as environments.
Besides, Camelyon17\cite{bandi2018detection} contains tissue slides sampled and post-processed in different hospitals and
DomainNet\cite{zhao2019multi} extends PACS to a far larger scale, consisting of more domains and categories.
Waterbirds\cite{sagawa2019distributionally} contains birds' images with either water or land backgrounds.
iWildCam\cite{beery2021iwildcam} collect images from different locations and produce realistic distributional shifts.
Recently, Koh \textit{et al.} collect several datasets together and produce Wilds\cite{koh2021wilds} as a benchmark for OOD generalization.\\\\
(c) \textsc{Controllable wild data}. \\
Recently, there are datasets enabling more flexible and controllable ways to simulate distributional shifts, typified by NICO\cite{he2021towards}.
NICO\cite{he2021towards} elaborately selects visual contexts with various types, including background, attribute, view and etc., and produce various environments.
With diverse contexts, NICO could simulate different types of realistic distributional shifts, and with balanced sample size in each context, different degrees of distributional shifts could be easily achieved.
These two properties make NICO enable flexible setups of distributional shifts.
Besides, FMoW\cite{christie2018functional} collects satellite images of building or land use token at different times and regions, and PovertyMap\cite{yeh2020using} contains images of an urban or rural area from disjoint sets of countries.\\\\
\textbf{Other Datasets}\\
Besides image data, there are still many other datasets related to OOD literature.
A house sales price dataset on Kaggle\footnote{https://www.kaggle.com/c/house-prices-advanced-regression-techniques/data} is used in \cite{shen2020stable, liu2021stable, hrm}, where environments are generated according to the built year of houses.
OGB-MolPCBA\cite{ren2020open} collects molecular graphs in over 100,000 scaffolds and formulate a molecular property prediction task across different scaffolds.
CivilComments\cite{borkan2019nuanced} and Amazon\cite{ni2019justifying} gather the individual comments of different users and distinctive groups (e.g. male and female).
Towards auto-engineering, Py150\cite{raychev2016probabilistic} contains codes from 8,421 git repositories for code completion generalization.

\subsection{Evaluation Metric}
Besides datasets, evaluation metrics are also important for evaluating an OOD generalization algorithm.
Compared to $i.i.d.$ problem where only one testing distribution is considered, there are often multiple testing distributions in OOD generalization problems, so as to better capture the unseen distributions.
Further, Ye \textit{et al.}\cite{ye2021out} empirically find that the test accuracy in single environment would mislead the judgement to algorithms in OOD scenario.
Therefore, to sufficiently evaluate the OOD generalization algorithms, more statistics of accuracy of multiple test environments should be taken into consideration.
Here, we discuss three evaluation metrics, including the average accuracy, worst-case accuracy and the standard deviation of accuracies.
For convenience, we assume the model's accuracies of $K$ testing environments are $\{\text{acc}_1, ..., \text{acc}_K\}$, respectively.

\subsubsection{Average Accuracy}
The average accuracy $\overline{\text{Acc}}$ over test distributions is the most straightforward way to assess the effectiveness of OOD algorithms, which is commonly used in OOD generalization literatures\cite{shen2020stable, kuang2020stable, hrm}, which is calculated as:
\begin{small}
\begin{equation}
    \overline{\text{Acc}} = \frac{1}{K}\sum_{k=1}^K \text{acc}_k
\end{equation}
\end{small}
The average accuracy measures the overall performances among testing edistributions, but it cannot describe the volatility of an algorithm's performance.
Further, the average accuracy equally treat all testing distributions without considering the property of each, which may be misled by distributions that frequently occurr.
We think it possible to weigh the accuracy according to the discrepancy of each testing distribution with training, which is still an open problem.

\subsubsection{Worst-Case Accuracy}
Widely-used in DRO literatures\cite{sinha2017certifying, duchi2018learning, esfahani2018data, frogner2019incorporating}, the worst-case accuracy $\text{Acc}_{\text{worst}}$ is defined as the worst-case accuracy across testing distributions:
\begin{small}
\begin{equation}
    \text{Acc}_{worst} = \min\limits_{k\in[K]} \text{acc}_k
\end{equation}
\end{small}
which corresponds to the objective functions\cite{sinha2017certifying, duchi2018learning, esfahani2018data, frogner2019incorporating}.
The worst-case accuracy reflects the reliability of an algorithm and is crucial in high-stake applications such as medical diagnoses, criminal justices and financial security.

\subsubsection{Standard Deviation (STD)}
The STD of accuracies over testing distributions $\text{Acc}_{\text{std}}$ measures the variation of performance across different distributions, which is defined as:
\begin{small}
	\begin{equation}
    \text{Acc}_{\text{std}} = \sqrt{\frac{1}{K-1}\sum_{k=1}^K (\text{acc}_k-\overline{\text{Acc}})^2}
\end{equation}
\end{small}
This metric measures the sensitivity of an algorithm and reflects the robustness and stability of algorithm, which is importance for an OOD generalization algorithm.

\begin{table*}
    \centering
    \caption{Commonly used image datasets for OOD generalization. Shift type denotes the type of distributional shifts, and the mixed type in image type means that there are both real and unreal images.}
    \resizebox{0.95\textwidth}{26mm}{
    \begin{tabular}{|l|c|c|c|c|c|c|c|}
    \hline
        \multirow{2}*{Image Data Set} & \bf ImageNet-Variant &\bf Colored MNIST &\bf MNIST-R &\bf Waterbirds &\bf Camelyon17 &\bf VLCS &\bf PACS\\
        & \cite{hendrycks2021natural,hendrycks2019benchmarking,hendrycks2020many} & \cite{arjovsky2019invariant} & \cite{ghifary2015domain} & \cite{sagawa2019distributionally} &
        \cite{bandi2018detection} & \cite{fang2013unbiased} & \cite{li2017deeper}\\
    \hline
        \# Domains & - & 3 & 6 & 2 & 5 & 4 & 4 \\
    \hline
        \# Categories & - & 2 & 10 & 2 & 2 & 5 & 7 \\
    \hline
        \# Examples & - & - & 6,000 & 4,800 & 45w & 2,800 & 10w \\
    \hline
        Shift Type & Adversarial Policy & Color & Angle & Background & Hospital & Data Source & Style \\
    \hline
        Image Type& Mixed Type & Digits & Digits & Birds & Tissue Slides & Real Objects & Mixed Type\\
        \hline
        \hline
        \multirow{2}*{Image Data Set} & \bf Office-Home &\bf DomainNet & \bf iWildCam &\bf FMoW &\bf PovertyMap & \multicolumn{2}{c|}{\bf NICO} \\
        & \cite{venkateswara2017deep} & \cite{zhao2019multi} & \cite{beery2021iwildcam} & \cite{christie2018functional} &
        \cite{yeh2020using} &
        \multicolumn{2}{c|}{\cite{he2021towards}}\\
    \hline
        \# Domains & 4 & 6 & 323 & 16 $\times$ 5 & 23 $\times$ 2 & \multicolumn{2}{c|}{188} \\
    \hline
        \# Categories & 65 & 345 & 182 & 62 & Real Value & \multicolumn{2}{c|}{19} \\
    \hline
        \# Examples & 15w & 50w & 20w & 50w & 2w & \multicolumn{2}{c|}{2.5w} \\
    \hline
        \multirow{2}*{Shift Type} & \multirow{2}*{Style} & \multirow{2}*{Style} & \multirow{2}*{Location} & Time,  & Country,  & \multicolumn{2}{c|}{Background, Attribute, Action,} \\
        & & & & Location &  Urban/Rural & \multicolumn{2}{c|}{View and Co-occurring Object} \\
    \hline
        Image Type & Mixed Type & Mixed Type & Real Animals & Satellite & Satellite & \multicolumn{2}{c|}{Real Objects} \\
    \hline
    \end{tabular}}
    \label{tab:bk}
\end{table*}