#  Invariance Learning based on Label Hierarchy

Shoji Toyota, Kenji Fukumizu The Graduate University for Advanced Studies
(SOKENDAI), Japan.The Institute of Statistical Mathematics, Japan.

###### abstract

Deep Neural Networks inherit spurious correlations embedded in training data
and hence may fail to predict desired labels on unseen domains (or
environments), which have different distributions from the domain used in
training. Invariance Learning (IL) has been developed recently to overcome
this shortcoming; using training data in many domains, IL estimates such a
predictor that is invariant to a change of domain. However, the requirement of
training data in multiple domains is a strong restriction of IL, since it
often needs high annotation cost. We propose a novel IL framework to overcome
this problem. Assuming the availability of data from multiple domains for a
higher level of classification task, for which the labeling cost is low, we
estimate an invariant predictor for the target classification task with
training data in a single domain. Additionally, we propose two cross-
validation methods for selecting hyperparameters of invariance regularization
to solve the issue of hyperparameter selection, which has not been handled
properly in existing IL methods. The effectiveness of the proposed framework,
including the cross-validation, is demonstrated empirically, and the
correctness of the hyperparameter selection is proved under some conditions.

##  1 Introduction

Training data used in machine learning unintentionally contain unrelated
factors to the objective of the task, which are called spurious correlations.
Deep Neural Networks (DNNs) often inherit the spurious correlations embedded
in the data in training domains and hence may fail to predict desired labels
in domains which have different distributions from the training domains,
namely unseen domains. For example, in a problem of classifying images of
cows, DNNs tend to misclassify cows in sandy beaches; most training pictures
are taken in green pastures and DNNs inherit context information in training
[3, 9]. Systems trained with medical data collected in one hospital do not
generalize well to other health centers; DNNs unintentionally extract
environmental factors specific to a particular hospital in training [16, 17,
18].

Invariance Learning (IL) is an approach developed rapidly to overcome the
issue of spurious correlation or short-cut learning [10, 14, 13, 12, 11, 15,
21, 33, 34, 35, 36]. Let $e\in{\mathcal{E}}$ be a domain (or environment)
index, and $X^{e}\in{\mathcal{X}}$ and $Y^{e}\in{\mathcal{Y}}$ be an input
object and its label in domain $e\in{\mathcal{E}}$, respectively. Using
training data in multiple training domains
${\mathcal{E}}_{tr}\subset{\mathcal{E}}$, IL estimates a predictor
$f:{\mathcal{X}}\rightarrow{\mathcal{Y}}$ that performs as well in unseen
domains $e\in{\mathcal{E}}-{\mathcal{E}}_{tr}$ as in the training domain, that
is, a predictor invariant to change of domains. In IL, the training data must
be annotated with labels of ${\mathcal{Y}}$ completely.

While the IL approach has attracted much attention as a solution to the
spurious correlation, requiring training data with exact labeling from
multiple domains may hinder wide applications in practice; preparing training
data in many domains are often expensive with data annotation. Even when we
can draw data from multiple domains, they are often only available in an
incompletely labeled form, which are called  pseudo label data  [42, 43, 44,
45], partial label data  [46, 48, 47] and complementary label data [51, 50,
49].

We propose a novel IL framework to reduce the need of training data with exact
labels from multiple domains. We estimate the invariance by the coarser
labeled data, which need lower annotation cost. Specifically, in addition to
the target task of classification, we consider another classification task of
a higher level in the label hierarchy, that is, we suppose that the additional
task has a coarser label set than the target task. We consider the situation
where the training data of the target task is given in only one domain, while
the task of higher label hierarchy has data from multiple domains. This
significantly reduces the annotation cost since the data with coarser labels
are much easier to obtain. More formally, assuming the availability of
additional data $(X^{e},Z^{e})$ from multiple domains
$e\in{\mathcal{E}}_{ad}\subset{\mathcal{E}}$ for the higher level of
classification task, we estimate an invariant predictor for the target task
with training data of a single domain $\\{e^{*}\\}$. Here, the higher level of
classification task means that its label is given by $Z^{e}=g(Y^{e})$ with
some surjective function $g:{\mathcal{Y}}\rightarrow{\mathcal{Z}}$ to define
the label hierarchy. For example, consider the case where
${\mathcal{Y}}:=\\{bird_{1},.....,bird_{10000},no~{}birds\\}$, labels with
10,000 kinds of birds and no birds, and
${\mathcal{Z}}:=\\{there~{}are~{}birds,no~{}birds\\}$, $g(y)=no~{}birds$ if
$y=no~{}birds$ and $g(y)=there~{}are~{}birds$ otherwise. Then, the binary
labels ${\mathcal{Z}}$ are much more easily annotated than the original
$10001$ class labels ${\mathcal{Y}}$. This may be done by humans with crowd-
sourcing or a binary classifier of high accuracy.

Another important issue in IL is hyperparameter selection. Most IL methods
involve some hyperparameters to balance the classification accuracy and the
degree of invariance. As [21] and [19] point out, in the literature of IL, the
best performances of invariance have often been achieved by selecting the
hyperparameters using test data from unseen domains. Moreover, [19]
numerically demonstrated that, without using test data, simple methods of
hyperparameter selection fail to find a preferable hyperparameter. This
illustrates a strong need for establishing an appropriate method of
hyperparameter selection for IL.

We propose two methods of cross-validation (CV) for hyperparameter selection
in our new IL framework. Since we assume training data of a single domain for
the target task, it is impossible to estimate the deviation of the risks over
the domains. We make use of the additional data from multiple domains in the
higher level and provide methods of CV, which is applicable in the current
setting.  Theoretical analysis reveals that our methods select hyperparameter
correctly with some condition.

The main contributions of this paper are as follows:

  * •

We establish a novel framework of invariant learning, which estimates an
invariant predictor from a single domain data, assuming additional data from
multiple domains for a higher level of classification task.

  * •

We propose two methods of cross-validation under the framework for selecting
hyperparameters without accessing any samples from unseen target domains.

  * •

Experimental studies verify that the proposed framework extracts an invariant
predictor more effectively than other existing methods.

  * •

We mathematically prove that the proposed CV methods select the correct
hyperparameter under some settings.

##  2 Invariance Learning based on Label Hierarchy

##### Notations

Throughout this paper, the space of input features and finite class labels are
denoted by ${\mathcal{X}}$ and ${\mathcal{Y}}$, respectively. For given
predictor $f:{\mathcal{X}}\rightarrow{\mathcal{Y}}$ and random variable
$(X,Y)$ on ${\mathcal{X}}\times{\mathcal{Y}}$ with its probability $P_{X,Y}$,
${\mathcal{R}}^{(X,Y)}(f)$ denotes the risk of $f$ on $(X,Y)$; $i.e.$,
${\mathcal{R}}^{(X,Y)}(f):=\int l(f(x),y)dP_{X,Y}$, where
$l:{\mathcal{Y}}\times{\mathcal{Y}}\rightarrow{\mathbb{R}}$ is a loss
function. For $m\in{\mathbb{N}}_{>0}$, $[m]$ denotes the set $\\{1,...,m\\}$.
For a finite set $A$, $|A|\in{\mathbb{N}}$ denotes the number of elements in
$A$.

###  2.1 Review of Invariance Learning

Following [10], to formulate the out-of-distribution (o.o.d.) generalization,
we assume that the joint distribution of data $(X^{e},Y^{e})$ depends on the
domain (or environment) $e\in{\mathcal{E}}$, and consider the dependence of a
predictor $f$ on the domain variable $e$. Suppose we are given training data
sets ${\mathcal{D}}^{e}:=\\{(x^{e}_{i},y^{e}_{i})\\}_{i=1}^{n^{e}}\sim
P_{X^{e},Y^{e}}$ i.i.d. from multiple domains $e\in{\mathcal{E}}_{tr}$. The
final goal of the o.o.d. problem is to predict a desired label
$Y^{e}\in{\mathcal{Y}}$ from $X^{e}\in{\mathcal{X}}$ for larger target domains
${\mathcal{E}}\supset{\mathcal{E}}_{tr}$. To discuss the o.o.d. performance,
[10] introduced the o.o.d. risk

${\mathcal{R}}^{o.o.d.}(f):=\max_{e\in{\mathcal{E}}}{\mathcal{R}}^{e}(f),$ (1)

where ${\mathcal{R}}^{e}(f):={\mathcal{R}}^{(X^{e},Y^{e})}(f)$. This is the
worst case risk over the domains ${\mathcal{E}}$, including unseen domains
${\mathcal{E}}-{\mathcal{E}}_{tr}$.

To solve (1), [10] estimates such a predictor $w\circ\Phi$ that is invariant
to change of domains, where the invariance
$\Phi:{\mathcal{X}}\rightarrow{\mathcal{H}}$ and the predictor
$w:{\mathcal{H}}\rightarrow{\mathcal{Y}}$ function as eliciting the invariant
representation from $X^{e}\in{\mathcal{X}}$, and estimating a label of the
invariant representation $\Phi(X^{e})$ respectively. The estimation are
implemented by solving the following optimization problem:

$\min_{\Phi\in{\mathcal{I}}_{tr},\\\
w:{\mathcal{H}}\rightarrow{\mathcal{Y}}}\sum_{e\in{\mathcal{E}}_{tr}}{\mathcal{R}}^{e}(w\circ\Phi),$
(2)

where ${\mathcal{I}}_{tr}$ is the set of invariances captured by
$\bigcup_{e\in{\mathcal{E}}_{tr}}{\mathcal{D}}^{e}$. All of IL, including
[10], estimate the invariance using the difference among ${\mathcal{E}}_{tr}$,
assuming the availability of multiple training domains in common.

While how to capture the invariance varies slightly among IL, we adopt the
method based on conditional independence as done by [40], [11] and [15]:

${\mathcal{I}}_{tr}:=\bigl{\\{}\Phi:{\mathcal{X}}\rightarrow{\mathcal{H}}\left|\right.\bigl{.}P(Y^{e}|\Phi(X^{e}))\text{
does not depend on }e\in{\mathcal{E}}_{tr}\bigr{\\}}.$

###  2.2 Invariance estimation by higher label data

Our goal is to make an invariant predictor from a single training domain
${\mathcal{E}}_{tr}=\\{e^{*}\\}$. In this case, (2) is reduced to the
empirical risk minimization $\min_{f}{\mathcal{R}}^{e^{*}}(f)$ on $e^{*}$, and
therefore the standard IL is not able to extract invariance.

In this paper, we introduce an assumption that additional data
${\mathcal{D}}^{e}_{ad}$ from $(X^{e},Z^{e})$ with coarser label
$Z^{e}\in{\mathcal{Z}}$ is available for multiple domains
${\mathcal{E}}_{ad}\subset{\mathcal{E}}$. This means that we have data for
another task in a higher label hierarchy than the target task. More formally,
the label $Z^{e}$ is assumed to follow $Z^{e}=g(Y^{e})$ with surjective label
mapping $g:{\mathcal{Y}}\rightarrow{\mathcal{Z}}$ from the lower to the higher
level in the hierarchy. For example, in the problem of animal recognition from
images, ${\mathcal{Y}}$ is
$\\{\text{cow},\text{horse},\text{dog},\ldots,\text{no animal}\\}$ and
${\mathcal{Z}}$ may be $\\{\text{animal},\text{no animal}\\}$. The domain $e$
specifies the background of the image: pasture, sand, room, and so on.

By making use of the data
$\bigcup_{e\in{\mathcal{E}}_{ad}}{\mathcal{D}}^{e}_{ad}$ in the higher level,
our objective for the invariant prediction of $Y^{e}$ is given by

$\min_{\Phi\in{\mathcal{I}}_{ad},\\\
w:{\mathcal{H}}\rightarrow{\mathcal{Y}}}{\mathcal{R}}^{e^{*}}(w\circ\Phi),$
(3)

where ${\mathcal{I}}_{ad}$ is the set of invariances:

${\mathcal{I}}_{ad}:=\bigl{\\{}\Phi:{\mathcal{X}}\rightarrow{\mathcal{H}}\left|\right.\bigl{.}P(g(Y^{e})|\Phi(X^{e}))\text{
does not depend on }e\in{\mathcal{E}}_{ad}\bigr{\\}}.$

The condition of ${\mathcal{I}}_{ad}$ is necessary to the invariance condition
of the target task $(X^{e},Y^{e})$, that is,

“$P(Y^{e}|\Phi(X^{e}))$ does not depend on $e\in{\mathcal{E}}$” $\Rightarrow$

“$P(g(Y^{e})|\Phi(X^{e}))$ does not depend on $e\in{\mathcal{E}}_{ad}$”

holds.

###  2.3 Construction of objective function

While there are many possible variations in the design of losses and models,
we focus a probabilistic output case and evaluate its error by the cross
entropy loss; that is, we model $w$ by maps to
$p_{\theta}:{\mathcal{H}}\rightarrow{\mathcal{P}}_{{\mathcal{Y}}}$, where
${\mathcal{P}}_{{\mathcal{Y}}}$ denotes the set of probabilities on
${\mathcal{Y}}$. The risk is then written by

${\mathcal{R}}^{e}(p_{\theta}\circ\Phi)=\int-\log
p_{\theta}(Y^{e}|\Phi(X^{e}))dP_{X^{e},Y^{e}}.$

We aim to solve (3) by minimizing the following objective function:

$\displaystyle
Objective(\theta,\Phi):=\hat{{\mathcal{R}}}^{e^{*}}(p_{\theta}\circ\Phi)+\lambda\cdot{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(\text{Dependence
measure of $P(Z^{e}|\Phi(X^{e}))$ on }e\in{\mathcal{E}}_{ad})}.$

Here, $\hat{{\mathcal{R}}}^{e^{*}}(p_{\theta}\circ\Phi)$ denotes the empirical
risk of $p_{\theta}\circ\Phi$ evaluated by ${\mathcal{D}}^{e^{*}}$:

$\hat{{\mathcal{R}}}^{e^{*}}(p_{\hat{\theta}}\circ\Phi):=-\frac{1}{|{\mathcal{D}}^{e^{*}}|}\sum_{(x^{e^{*}},y^{e^{*}})\in{\mathcal{D}}^{e^{*}}}\log
p_{\hat{\theta}}(y^{e^{*}}|\Phi(x^{e^{*}}))$

.

Algorithm 1 Two Cross Validation Methods. If CORRECTION = True, $\lambda$ is
selected by method II and if False, Method I.

0: : Split
${\mathcal{D}}^{e^{*}},{\mathcal{D}}^{e_{1}}_{ad},...,{\mathcal{D}}^{e_{n}}_{ad}$
into $K$ parts. Set the hyperparameter candidates $\Lambda$.

0:
:$\hat{P}(Z^{e}=z^{\scalebox{0.2}{$\cancel{\hookrightarrow}$}})\leftarrow\frac{{|{\mathcal{D}}_{ad,z^{\scalebox{0.2}{$\cancel{\hookrightarrow}$}}}^{e}|}}{|{\mathcal{D}}^{e}_{ad}|}$,
where
$D^{e}_{ad,z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}}:=\left\\{(x,z)\in{\mathcal{D}}^{e}_{ad}\left|z=z^{\scalebox{0.2}{$\cancel{\hookrightarrow}$}}\right.\right\\}$
for all
$e\in{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}{\mathcal{E}}_{ad}}$
and
$z^{\scalebox{0.2}{$\cancel{\hookrightarrow}$}}\in{\mathcal{Z}}^{\scalebox{0.2}{$\cancel{\hookrightarrow}$}}$.

1: for $\lambda\in\Lambda$ do

2: for $k=1$ to $K$ do

3: Learn $\theta_{[-k]}^{\lambda},\Phi_{[-k]}^{\lambda}$ by using
${\mathcal{D}}^{e^{*}}_{[-k]},{\mathcal{D}}^{e_{1}}_{ad,[-k]},...,{\mathcal{D}}^{e_{n}}_{ad,[-k]}$.

4:
$\hat{{\mathcal{R}}}_{[k]}^{e^{*}}(p_{\theta_{[-k]}^{\lambda}}\circ\Phi_{[-k]}^{\lambda})\leftarrow\frac{1}{|{\mathcal{D}}^{e^{*}}_{[k]}|}\sum_{(x^{e^{*}},y^{e^{*}})\in{\mathcal{D}}_{[k]}^{e^{*}}}-\log
p_{\theta_{[-k]}^{\lambda}}(y^{e^{*}}|\Phi^{\lambda}_{[-k]}(x^{e^{*}}))$

5:
$C(z^{\scalebox{0.2}{$\cancel{\hookrightarrow}$}})\leftarrow\frac{1}{|{\mathcal{D}}^{e^{*}}_{[k],z^{\scalebox{0.2}{$\cancel{\hookrightarrow}$}}}|}\sum_{(x,y)\in{\mathcal{D}}^{e^{*}}_{[k],z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}}}}-\log
p_{\theta_{[-k]}^{\lambda}}(y|\Phi_{[-k]}^{\lambda}(x),g^{-1}(z^{\scalebox{0.2}{$\cancel{\hookrightarrow}$}}))$
for $z^{\scalebox{0.2}{$\cancel{\hookrightarrow}$}}$ in
${\mathcal{Z}}^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}$.

6: for $e$ $\in$ ${\mathcal{E}}_{ad}$ do

7:
$\hat{{\mathcal{R}}}_{[k]}^{(X^{e},Z^{e})}(p_{\theta_{[-k]}^{\lambda}}\circ\Phi_{[-k]}^{\lambda})\leftarrow\frac{1}{|{\mathcal{D}}^{e}_{ad,[k]}|}\sum_{(x^{e},z^{e})\in{\mathcal{D}}_{ad,[k]}^{e}}-\log
p_{\theta_{[-k]}^{\lambda}}(z^{e}|\Phi^{\lambda}_{[-k]}(x^{e}))$.

8:
$\hat{{\mathcal{R}}}_{[k]}^{e}(p_{\theta^{-k}_{\lambda}}\circ\Phi^{-k}_{\lambda})\leftarrow\hat{{\mathcal{R}}}_{[k]}^{(X^{e},Z^{e})}(p_{\theta_{[-k]}^{\lambda}}\circ\Phi_{[-k]}^{\lambda})+\sum_{z^{\scalebox{0.2}{$\cancel{\hookrightarrow}$}}\in{\mathcal{Z}}^{\scalebox{0.2}{$\cancel{\hookrightarrow}$}}}\bigl{\\{}\hat{P}(Z^{e}=z^{\scalebox{0.2}{$\cancel{\hookrightarrow}$}})\cdot
C(z^{\scalebox{0.2}{$\cancel{\hookrightarrow}$}})\bigr{\\}}$.

9: end for

10: if CORRECTION then

11:
$\hat{{\mathcal{R}}}^{o.o.d.}_{[k]}(p_{\theta_{[-k]}^{\lambda}}\circ\Phi_{[-k]}^{\lambda})\leftarrow\max\\{\max_{e\in{\mathcal{E}}_{ad}}\hat{{\mathcal{R}}}_{[k]}^{(X^{e},g(Y^{e}))}(p_{\theta_{[-k]}^{\lambda}}\circ\Phi_{[-k]}^{\lambda}),\hat{{\mathcal{R}}}_{[k]}^{e^{*}}(p_{\theta_{[-k]}^{\lambda}}\circ\Phi_{[-k]}^{\lambda})\\}$

12: else

13:
$\hat{{\mathcal{R}}}^{o.o.d.}_{[k]}(p_{\theta_{[-k]}^{\lambda}}\circ\Phi_{[-k]}^{\lambda})\leftarrow\max_{e\in{\mathcal{E}}_{ad}\cup\\{e^{*}\\}}\\{\hat{{\mathcal{R}}}_{[k]}^{e}(p_{\theta_{[-k]}^{\lambda}}\circ\Phi_{[-k]}^{\lambda})\\}$

14: end if

15: end for

16: (I)
$\hat{{\mathcal{R}}}^{o.o.d.}(\lambda)=\frac{1}{K}\sum_{k=1}^{K}\hat{{\mathcal{R}}}^{o.o.d.}_{[k]}(p_{\theta_{[-k]}^{\lambda}}\circ\Phi_{[-k]}^{\lambda})$

17: end for

18: Select $\lambda^{*}:=\mathop{\rm
argmin}\limits_{\lambda}\hat{{\mathcal{R}}}^{o.o.d.}(\lambda)$

For the regularization term, among others, we adopt the one introduced in
[10], noting that their definition of invariance agrees with ours in our
setting, as we see below. [10] call $\Phi$ invariant when $\mathop{\rm
argmin}\limits_{w}{\mathcal{R}}^{e}(w\circ\Phi)$ is independent $e$, and to
evaluate such an invariant feature, they propose the regularization term
$\|\nabla_{\hat{w}=w}{\mathcal{R}}^{e}(\hat{w}\circ\Phi)\|^{2}$. The following
lemma ensures that our and their definition of the invariance coincide, and
therefore we may use
$\sum_{e\in{\mathcal{E}}_{ad}}\|\nabla_{\hat{w}=w}{\mathcal{R}}^{e}(\hat{w}\circ\Phi)\|^{2}$
for our regularization term.

######  Lemma 2.1.

When modeling $w$ by conditional probabilities, the following statements are
equivalent:

  * (i)

$P(Z^{e}|\Phi(X^{e}))$ does not depend on $e\in{\mathcal{E}}$.

  * (ii)

$\mathop{\rm
argmin}\limits_{p^{{\mathcal{Z}}|{\mathcal{H}}}_{\theta_{ad}}:{\mathcal{H}}\rightarrow{\mathcal{P}}_{{\mathcal{Z}}}}{\mathcal{R}}^{(X^{e},Z^{e})}(p^{{\mathcal{Z}}|{\mathcal{H}}}_{\theta_{ad}}\circ\Phi)$
does not depend on $e\in{\mathcal{E}}$,

where $p^{{\mathcal{Z}}|{\mathcal{H}}}_{\theta_{ad}}$ in (ii) runs over all
probability densities.

###### Proof.

Noting that $\mathop{\rm
argmin}\limits_{\theta_{ad}}{\mathcal{R}}^{(X^{e},Z^{e})}(p_{\theta_{ad}}\circ\Phi)$
coincides with the probability density function of $P(Z^{e}|\Phi(X^{e}))$, the
above equivalence follows immediately. ∎

In summary, we construct an objective function by

$\displaystyle
Objective(\theta,\theta_{ad},\Phi):=\hat{{\mathcal{R}}}^{e^{*}}(p_{\theta}\circ\Phi)+\lambda\cdot\sum_{e\in{\mathcal{E}}_{ad}}\|\nabla_{\hat{\theta}_{ad}={\theta}_{ad}}\hat{{\mathcal{R}}}^{(X^{e},Z^{e})}(p^{{\mathcal{Z}}|{\mathcal{H}}}_{\hat{\theta}_{ad}}\circ\Phi)\|^{2},$
(4)

where
$p_{\theta}^{{\mathcal{Z}}|{\mathcal{H}}}:{\mathcal{H}}\rightarrow{\mathcal{P}}_{{\mathcal{Z}}}$
is the logistic regression model, same as [10], and
$\hat{{\mathcal{R}}}^{(X^{e},Z^{e})}(p^{{\mathcal{Z}}|{\mathcal{H}}}_{\hat{\theta}_{ad}}\circ\Phi):=-\frac{1}{|{\mathcal{D}}^{e}_{ad}|}\sum_{(x^{e},z^{e})\in{\mathcal{D}}^{e}_{ad}}\log
p^{{\mathcal{Z}}|{\mathcal{H}}}_{\hat{\theta}_{ad}}(z^{e}|\Phi(x^{e}))$.

##  3 Hyperparameter selection method

###  3.1 Hyperparameter Selection in Invarance Learning

Most IL methods involve hyperparameters to control the trade-off between the
classification accuracy and invariance. Thus, hyperparameter selection is
essential in IL methods.

The hyperparameter selection in IL has special difficulty. Since the o.o.d.
problem needs to predict $Y^{e}$ on unseen domains, the hyperparameter must be
chosen without accessing any data in the unseen domains. It was reported [19]
that the success of IL methods depends strongly on the careful choice of
hyperparameters; some of the results used data from unseen domains in the
choice.  [19] reported also experimental results of various IL methods with
two CV methods, training-domain validation (Tr-CV) and leave-one-domain-out
validation (LOD-CV), and showed that the CV methods failed to select
preferable hyperparamters. In Colored MNIST experiment, for example, the
accuracy of Invariant Risk Minimization [10] is $52.0\%$ at best, which is
about the random guess level.

The failure of the CV methods are caused by the improper design of the
objective function for CV; they do not simulate the o.o.d. risk, which is the
maximum risk over the domains. Tr-CV splits data in each training domain into
training and validation subsets, and takes the sum of the validated risks over
the training domains. Obviously, this is not an estimate of the o.o.d. risk.
LOD-CV holds out one domain among the training domains in turn and validates
models with the average of the validated risks over the held-out domains.
Again, this average does not correspond to the o.o.d. risk. In summary, the
problem we need to solve is: How can we construct an evaluation function of
the o.o.d. risk from validation data? In the sequel, we will propose two
methods of CV, which are summarized in Algorithm 1.

###  3.2 Method I: using data of higher level task

We divide each of
${\mathcal{D}}^{e^{*}},{\mathcal{D}}^{e_{1}}_{ad},...,{\mathcal{D}}^{e_{n}}_{ad}$
into $K$ parts, and use the $k$-th sample
$\\{{\mathcal{D}}^{e^{*}}_{[k]},{\mathcal{D}}^{e_{1}}_{ad,[k]},...,{\mathcal{D}}^{e_{n}}_{ad,[k]}\\}$
and the rest
$\\{{\mathcal{D}}^{e^{*}}_{[-k]},{\mathcal{D}}^{e_{1}}_{ad,[-k]},...,{\mathcal{D}}^{e_{n}}_{ad,[-k]}\\}$
for validation and training, respectively. To approximate the o.o.d. risk of
the predictor $p_{\theta_{[-k]}^{\lambda}}\circ\Phi^{\lambda}_{[-k]}$ obtained
by the training set, we wish to estimate
$R^{e}(p_{\theta_{[-k]}^{\lambda}}\circ\Phi^{\lambda}_{[-k]})$ for
$e\in{\mathcal{E}}_{ad}\cup\\{e^{*}\\}$. For $e^{*}$, we use the standard
empirical estimate
$\hat{{\mathcal{R}}}^{e^{*}}(p_{\theta_{[-k]}^{\lambda}}\circ\Phi^{\lambda}_{[-k]}):=\frac{1}{|{\mathcal{D}}^{e^{*}}_{[k]}|}\sum_{(x^{e^{*}},y^{e^{*}})\in{\mathcal{D}}_{[k]}^{e^{*}}}-\log
p_{\theta_{[-k]}^{\lambda}}(y^{e^{*}}|\Phi^{\lambda}_{[-k]}(x^{e^{*}}))$. For
$e\in{\mathcal{E}}_{ad}$, we substitute unavailable $Y^{e}$ with $Z^{e}$ and
use
$\hat{{\mathcal{R}}}^{(X^{e},Z^{e})}(p_{\theta_{[-k]}^{\lambda}}\circ\Phi_{[-k]}^{\lambda}):=\frac{1}{|{\mathcal{D}}^{e}_{ad,[k]}|}\sum_{(x^{e},z^{e})\in{\mathcal{D}}^{e}_{ad,[k]}}-\log
p_{\theta_{[-k]}^{\lambda}}(z^{e}|\Phi_{[-k]}^{\lambda}(x^{e}))$.

###  3.3 Method II: using correction term

Method I can be improved by considering the difference
${\mathcal{R}}^{e}(p_{\theta_{[-k]}^{\lambda}}\circ\Phi^{\lambda}_{[-k]})-{\mathcal{R}}^{(X^{e},Z^{e})}(p_{\theta_{[-k]}^{\lambda}}\circ\Phi^{\lambda}_{[-k]})$,
for which we deduce the following theorem. The proof is given in Appendix A.

######  Theorem 3.1.

Let
${\mathcal{Z}}^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}:=\left\\{z\in{\mathcal{Z}}\left||g^{-1}(z)|>1\right.\right\\}$.
For any map $\Phi:{\mathcal{X}}\rightarrow{\mathcal{H}}$,
$p_{\theta}:{\mathcal{H}}\rightarrow{\mathcal{P}}_{{\mathcal{Y}}}$, and random
variable $(X,Y)$ on ${\mathcal{X}}\times{\mathcal{Y}}$, the following equality
holds:

$\displaystyle{\mathcal{R}}^{(X,Y)}(p_{\theta}\circ\Phi)-{\mathcal{R}}^{(X,g(Y))}(p_{\theta}\circ\Phi)=\sum_{z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}}\in{\mathcal{Z}}^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}}}\Bigl{\\{}P(g(Y)=z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}})\times\int-\log
p_{\theta}\bigl{(}Y|\Phi(X),Y\in
g^{-1}(z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}})\bigr{)}dP_{(X,Y)|Y\in
g^{-1}(z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}})}\Bigl{\\}}.$ (5)

Here, $P_{(X,Y)|Y\in g^{-1}(z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}})}$
denotes the conditional distribution of $(X,Y)$ given the event $Y\in
g^{-1}(z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}})$, and
$p_{\theta}(y|\Phi(x),Y\in
g^{-1}(z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}})):=\frac{p_{\theta}(y|\Phi(x))}{\sum_{y\in
g^{-1}(z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}})}p_{\theta}(y|\Phi(x))}$.

The theorem shows that, to estimate
${\mathcal{R}}^{e}(p_{\theta_{[-k]}^{\lambda}}\circ\Phi^{\lambda}_{[-k]})-{\mathcal{R}}^{(X^{e},Z^{e})}(p_{\theta_{[-k]}^{\lambda}}\circ\Phi^{\lambda}_{[-k]})$,
we need to estimate the following two values:

  * (i)

$P(g(Y^{e})=z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}})=P(Z^{e}=z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}})$
for every
$z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}}\in{\mathcal{Z}}^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}},$

  * (ii)

$\int-\log
p_{\theta_{[-k]}^{\lambda}}(Y^{e}|\Phi^{\lambda}_{[-k]}(X^{e}),g^{-1}(z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}}))dP_{X^{e},Y^{e}|Y^{e}\in
g^{-1}(z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}})}$ for every
$z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}}\in{\mathcal{Z}}^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}$.

(i) is naturally estimated by
${\mathcal{D}}^{e}_{ad}$:$\hat{P}(Z^{e}=z):=\frac{{|{\mathcal{D}}_{ad,z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}}}^{e}|}}{|{\mathcal{D}}^{e}_{ad}|}$,
where
$D^{e}_{ad,z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}}}:=\left\\{(x,z)\in{\mathcal{D}}^{e}_{ad}\left|z=z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}\right.\right\\}$.
(ii) is not directly estimable, as $Y^{e}$ is not observed. For an
approximation of (ii),  we substitute $Y^{e}$ with $Y^{e^{*}}$ and use

$\displaystyle\frac{1}{|{\mathcal{D}}^{e^{*}}_{[k],z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}}}|}\sum_{(x,y)\in{\mathcal{D}}^{e^{*}}_{[k],z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}}}}-\log$
$\displaystyle
p_{\theta_{[-k]}^{\lambda}}(y|\Phi_{[-k]}^{\lambda}(x),g^{-1}(z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}})),$

where

${\mathcal{D}}^{e^{*}}_{[k],z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}}}:=\left\\{(x,y)\in{\mathcal{D}}^{e^{*}}_{[k]}\left|g(y)=z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}}\right.\right\\}\subset{\mathcal{D}}^{e^{*}}_{[k]}.$

###  3.4 Theoretical analysis of our cross validation methods

In Sections 3.2 and 3.3, we approximate ${\mathcal{R}}^{(X^{e},Y^{e})}$ using
$Z^{e}$. While the approximation is not exact, we will prove that the proposed
CV methods still select a correct hyperparameter under some conditions. We
will also elucidate the difference of the two CV methods theoretically. In
this paper, to avoid discussing non-trivial effects of nonlinear $\Phi$, we
focus the case of variable selection, which appears in the invariance problem
of causal inference [11, 12] and regression [40].

Let ${\mathcal{X}}:={\mathcal{X}}_{1}\times{\mathcal{X}}_{2}$ where
${\mathcal{X}}_{1}:={\mathbb{R}}^{n_{1}}$ and
${\mathcal{X}}_{2}:={\mathbb{R}}^{n_{2}}$ with $n_{1},n_{2}\in{\mathbb{N}}$,
and assume that the projection $\Phi^{{\mathcal{X}}_{1}}$ from ${\mathcal{X}}$
onto ${\mathcal{X}}_{1}$ yields the invariance to
$\\{(X^{e},Y^{e})\\}_{e\in{\mathcal{E}}}$, that is,
$P(Y^{e}|\Phi^{{\mathcal{X}}_{1}}(X^{e}))$ are the same over
$\forall(X^{e},Y^{e})\in\\{(X^{e},Y^{e})\\}_{e\in{\mathcal{E}}}$. Suppose that
we have a model $\\{\Phi\\}$ for the feature map, where $\Phi$ is a projection
of ${\mathcal{X}}$ onto some subset of $n_{1}+n_{2}$ variables of
${\mathcal{X}}$. Minimizing (4) with its hyperparameter $\lambda$ over the
model yields the feature map as a projection
$\Phi^{\lambda}:{\mathcal{X}}\rightarrow{\mathbb{R}}^{n_{\lambda}}$
($n_{\lambda}\leq n_{1}+n_{2}$).  Let $\Phi_{2}^{\lambda}$ denote the
${\mathcal{X}}_{2}$-component of $\Phi^{\lambda}$ and, if $\Phi^{\lambda}$
does not have any ${\mathcal{X}}_{2}$-component, we write
$\mathrm{Im}\Phi^{\lambda}_{2}=\emptyset$. For simplicity of theoretical
analysis, we assume that minimization with its hyperparameter $\lambda$ learns
perfectly $p^{*,\lambda}(y|\Phi^{\lambda}(x))$, the conditional probability
density function of $P_{Y^{e^{*}}|\Phi^{\lambda}(X^{e^{*}})}$. Then,
neglecting the estimations, the approximated o.o.d. risk of
$p^{*,\lambda}\circ\Phi^{\lambda}$ used by Methods I and II are represented by
the following ${\mathcal{R}}^{I}(\lambda)$ and ${\mathcal{R}}^{II}(\lambda)$,
respectively:

${\mathcal{R}}^{I}(\lambda):=\max\Biggl{\\{}\max_{e\in{\mathcal{E}}_{ad}}{\mathcal{R}}^{(X^{e},g(Y^{e}))}(p^{*,\lambda}\circ\Phi^{\lambda}),R^{(X^{*},Y^{*})}(p^{*,\lambda}\circ\Phi^{\lambda})\Biggr{\\}},$
$\displaystyle{\mathcal{R}}^{II}(\lambda):=\max_{e\in{\mathcal{E}}_{ad}\cup\\{e^{*}\\}}\Biggl{\\{}{\mathcal{R}}^{(X^{e},g(Y^{e}))}(p^{*,\lambda}\circ\Phi^{\lambda})+\sum_{z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}\in{\mathcal{Z}}^{\cancel{\hookrightarrow}}}\Bigl{\\{}P(g(Y^{e})=z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})\times\int-\log
p^{*,\lambda}(Y^{e^{*}}|\Phi^{\lambda}(X^{e^{*}}),Y^{e^{*}}\in
g^{-1}(z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}}))$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}dP_{(X^{e^{*}},Y^{e^{*}})|Y^{e^{*}}\in
g^{-1}(z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}})}\Bigl{\\}}\Biggl{\\}}.$

We have the following theoretical justification of our CV methods: the chosen
$\lambda$ gives a minimizer of the correct CV criterion. For the proofs, see
Appendices B and C.

######  Theorem 3.2 (Effectiveness of Method I).

Assume that the following four conditions of ${\mathcal{E}}$,
${\mathcal{E}}_{ad}$ and $\Lambda$ hold:

  * (a)

$P_{\Phi^{{\mathcal{X}}_{1}}(X^{e})}$ does not depend on $e\in{\mathcal{E}}$.

  * (b)

For any random variable $(X,Y)$ with
$P_{\Phi^{{\mathcal{X}}_{1}}(X),Y}=P_{\Phi^{{\mathcal{X}}_{1}}(X^{e^{*}}),Y^{e^{*}}}$,
there exists $e\in{\mathcal{E}}$ such that $(X,Y)=(X^{e},Y^{e})$.

  * (c)

$\exists\lambda^{I}\in\Lambda$ s.t.
$\Phi^{\lambda^{I}}=\Phi^{{\mathcal{X}}_{1}}$.

  * (d)

$\forall\lambda$ with $\mathrm{Im}\Phi^{\lambda}_{2}\neq\emptyset$, $\exists
e_{\lambda}\in{\mathcal{E}}_{ad}$ such that
$P\Bigl{(}g(Y^{e^{*}})|\Phi^{\lambda}(X^{e^{*}})\Bigr{)}\leq
e^{-\beta}-{\varepsilon}$, $P_{X^{e_{\lambda}},Y^{e_{\lambda}}}$-a.e. $i.e.$,
$P_{X^{e_{\lambda}},Y^{e_{\lambda}}}(B)=1$, where

$B:=\left\\{(x,y)\in{\mathcal{X}}\times{\mathcal{Y}}\left|\begin{array}[]{l}P\Bigl{(}g(Y^{e^{*}})=g(y)|\Phi^{\lambda}(X^{e^{*}})=\Phi^{\lambda}(x)\Bigr{)}\\\
~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\leq
e^{-\beta}-{\varepsilon}\end{array}\right.\right\\}.$

Here $\beta:=H(Y^{e^{*}}|\Phi^{{\mathcal{X}}_{1}}(X^{e^{*}}))$ is the
conditional entropy of $(\Phi^{{\mathcal{X}}_{1}}(X^{e^{*}}),Y^{e^{*}})$.

Then, we have

$\mathop{\rm
argmin}\limits_{\lambda\in\Lambda}{\mathcal{R}}^{I}(\lambda)\subset\mathop{\rm
argmin}\limits_{\lambda\in\Lambda}{\mathcal{R}}^{o.o.d.}(p^{*,\lambda}\circ\Phi^{\lambda}).$

######  Theorem 3.3 (Effectiveness of Method II).

Assume that (a), (b), (c) and the following condition (d)’ hold:

  * (d)’

$\forall\lambda$ with $\mathrm{Im}\Phi^{\lambda}_{2}\neq\emptyset$, $\exists
e_{\lambda}\in{\mathcal{E}}_{ad}$ such that
$P\Bigl{(}g(Y^{e^{*}})|\Phi^{\lambda}(X^{e^{*}})\Bigr{)}\leq
e^{-\beta_{\lambda}}-{\varepsilon}$,
$P_{X^{e_{\lambda}},Y^{e_{\lambda}}}$-a.e.

$\displaystyle~{}~{}\beta_{\lambda}:=H(Y^{e^{*}}|\Phi^{{\mathcal{X}}_{1}}(X^{e^{*}}))-$
$\displaystyle\sum_{z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}}\in{\mathcal{Z}}^{\cancel{\hookrightarrow}}}\Bigl{\\{}P(g(Y^{e^{*}})=z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}})\times\int-\log
p^{*,\lambda}(Y^{e^{*}}|$
$\displaystyle\Phi^{\lambda}(X^{e^{*}}),g^{-1}(z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}}))$
$\displaystyle dP_{(X^{e^{*}},Y^{e^{*}})|Y^{e^{*}}\in
g^{-1}(z^{\scalebox{0.3}{$\cancel{\hookrightarrow}$}})}\Bigl{\\}}.$

Then, we have

$\mathop{\rm
argmin}\limits_{\lambda\in\Lambda}{\mathcal{R}}^{II}(\lambda)\subset\mathop{\rm
argmin}\limits_{\lambda\in\Lambda}{\mathcal{R}}^{o.o.d.}(p^{*,\lambda}\circ\Phi^{\lambda}).$

The assumptions (d) and (d)’ mean that labeling rules on ${\mathcal{E}}_{ad}$
and $e^{*}$ are different due to a domain-specific factor ($i.e.$, an
${\mathcal{X}}_{2}$-component). (d) and (d)’ mean that, if $\lambda$ fails to
remove environment factors ($i.e.$,
$\mathrm{Im}\Phi^{\lambda}_{2}\neq\emptyset$), for some
$e_{\lambda}\in{\mathcal{E}}_{ad}$, either of the following two inequalities

$P(g(Y^{e^{*}})=g(y)|\Phi^{\lambda}(X^{e^{*}})=\Phi^{\lambda}(x))\leq
e^{-\beta}-{\varepsilon}$
$P(g(Y^{e^{*}})=g(y)|\Phi^{\lambda}(X^{e^{*}})=\Phi^{\lambda}(x))\leq
e^{-\beta_{\lambda}}-{\varepsilon}$

hold on a set of $(x,y)$ with probability $1$ w.r.t.
$P_{(\Phi^{\lambda}(X^{e_{\lambda}}),Y^{e_{\lambda}})}$. Noting that
$(\Phi^{\lambda}(X^{e^{*}}),Y^{e^{*}})$ attaches a label $z$ to
$\Phi^{\lambda}(x)$ such that
$P\Bigl{(}g(Y^{e^{*}})=z|\Phi^{\lambda}(X^{e^{*}})=\Phi^{\lambda}(x)\Bigr{)}$
is large, the inequalities in (d) and (d)’ mean that $Y^{e_{\lambda}}$ and
$Y^{e^{*}}$ attach different labels to the same $x\in{\mathcal{X}}$ with high
probability due to its ${\mathcal{X}}_{2}$-component.

The theoretical analysis shows, while Method I is simpler than Method II,
Method II is more applicable than Method I; that is because Method II eases
the sufficient condition (d) for Method I to succeed. Noting that
$\beta\geq\beta_{\lambda}$ and hence, $e^{-\beta}-{\varepsilon}\leq
e^{-\beta_{\lambda}}-{\varepsilon}$, the condition (d)’ is milder than (d).
The fact implies that we can apply Method II even when labeling rules on
${\mathcal{E}}_{ad}$ and $e^{*}$ due to domain-specific factors are too
similar to apply Method I.

We also show one of the sufficient conditions of $e^{*}$ for there to exist
$(X^{e_{\lambda}},Y^{e_{\lambda}})$ which satisfies the inequalities in (d) or
(d)’ for $\forall\lambda$ with $\mathrm{Im}\Phi^{\lambda}_{2}\neq\emptyset$ in
Appendix D.

##  4 Related work

##### Fine-tuning

The proposed framework uses additional data from multiple domains as well as
the training data for the target task so that it may be relevent to Transfer
learning (TL) [22, 23, 24] and meta-learning [30, 41], which realize fast and
accurate learning for a new target task based on a model pre-trained with
additional data sets or tasks. For example, after initial learning with a
large data set, fine tune [22, 23] re-trains the model with the target task,
while frozen feature [24] fixes the pre-trained model and tunes a head
network. Although they show advantages in many learning problems, they may not
work effectively in the current setting; in the fine-tuning with the target
task $(X^{e^{*}},Y^{e^{*}})$, the model tends to learn spurious correlation in
the data set and does not generalize to o.o.d. domains. Some fine-tuning
methods will be compared with the proposed approach experimentally in Section
5.

##### Domain adaptation by deep feature learning

Domain adaptation strategies by deep feature learning [25, 26, 27, 31, 32]
assume that we can access input data on a test domain in advance, and try to
obtain data representation $\Phi(X^{e})$ that follows the same distribution
for the training and test domains. While the strategies lead to high
predictive performance on a test domain similar to a training domain, such
$\Phi$ does not function by discarding environmental factors from
$X^{e}\in{\mathcal{X}}$ as noted in [10]. Experimental comparisons will be
shown in Section 5.

##  5 Experiments

Table 1: Average Test Accuracies and SEs of Synthesized Data on $e=-e^{*}$ (5
runs): Oracle shows the results of the experiments with the first component.
The best scores are bolded.

| $e^{*}=0$ | $e^{*}=5$ | $e^{*}=10$ | $e^{*}=15$ | $e^{*}=20$ | $e^{*}=25$ | $e^{*}=30$ | $e^{*}=35$ | $e^{*}=40$ | $e^{*}=45$ | $e^{*}=50$
---|---|---|---|---|---|---|---|---|---|---|---
Oracle | 906 (.007)
ERM | .789 (.218) | .791 (.174) | .637 (.188) | .329 (.201) | .324 (.328) | .311 (.260) | .159 (.193) | .140 (.171) | .132 (.161) | .166 (.147) | .051 (.101)
FT | .899 (.000) | .863 (.001) | .575 (.002) | .568 (.001) | .673 (.103) | .583 (.088) | .402 (.004) | .350 (.001) | .003 (.000) | .000 (.000) | .000 (.000)
FE | .899 (.000) | .861 (.002) | .540 (.102) | .568 (.001) | .673 (.102) | .628 (.001) | .401 (.001) | .351 (.002) | .066 (.132) | .000 (.000) | .000 (.000)
DSAN | .684 (.008) | .367 (.016) | .195 (.015) | .112 (.008) | .045 (.008) | .013 (.003) | .006 (.001) | .001(.001) | .000 (.000) | 000 (.000) | .000 (.000)
Ours + Our CV I | .799 (.232) | .784 (.231) | .884 (.021) | .875 (.044) | .815 (.098) | .738 (.209) | .865 (.047) | .659 (.233) | .666 (.285) | .776 (.080) | .699 (.255)
Ours + Our CV II | .799 (.232) | .783 (.231) | .884 (.021) | .875 (.044) | .815 (.098) | .738 (.209) | .865 (.047) | .659 (.233) | .563 (.291) | .776 (.080) | .699 (.255)
Ours + Tr-CV | .790 (.230) | .776 (.225) | .609 (.163) | .491 (.095) | .366 (.147) | .248 (.192) | .376 (.033) | .215 (.168) | .148 (.127) | .189 (.108) | .031 (.138)
Ours + LOD-CV | .662 (.180) | .521 (.145) | .569 (.204) | .538 (.168) | .450 (.158) | .371 (.213) | .641 (.221) | .571 (.221) | .380 (.196) | .423 (.218) | .316 (.127)
Ours + TDV | .915 (.005) | .905 (.006) | .896 (.002) | .895 (.010) | .848 (.059) | .849 (.069) | .887 (.030) | .764 (.152) | .796 (.174) | .848 (.055) | .775 (.179)

Table 2: Comparison of Two CV methods. Average Test Accuracies and SEs of the
estimates (10runs). Best scores are bolded.

| $e_{ad}=-9$ | $e_{ad}=-8$ | $e_{ad}=-7$ | $e_{ad}=-6$ | $e_{ad}=-5$ | $e_{ad}=-4$ | $e_{ad}=-3$ | $e_{ad}=-2$ | $e_{ad}=-1$ | $e_{ad}=0$ | $e_{ad}=1$
---|---|---|---|---|---|---|---|---|---|---|---
TDV | .596 (.078) | .621 (.046) | .630 (.041) | .595 (.061) | .590 (.087) | .621 (.059) | .564 (.071) | .582 (.056) | .535 (.093) | .520 (.121) | .575 (.107)
CV I | .529 (.128) | .555 (.111) | .562 (.086) | .566 (.109) | .375 (.145) | .346 (.172) | .372 (.176) | .358 (.167) | .300 (.146) | .173 (.143) | .218 (.087)
CV II | .527 (.152) | .573 (.089) | .565 (.085) | .572 (.072) | .522 (.110) | $\textbf{.523 (.102})$ | .482 (.113) | .506 (.153) | .430 (.146) | .437 (.157) | .502 (.149)

We study the effectiveness of the proposed framework and CV methods through
experiments, comparing them with several conventional methods: empirical risk
minimization (ERM), fine-tuning methods, and deep domain adaptation
strategies. As fine-turning methods, we employ two typical types of transfer
learning: fine tune (FT) and frozen feature (FF) [22, 23, 24]. As a deep
domain adaptation technique, we adopt the state-of-the-art method $DSAN$ [31].
We also compare our two CV methods (CVI and CVII) with conventional CV
methods: training-domain validation (Tr-CV) and leave-one-domain-out cross-
validation (LOD-CV) [19]. We have two hyperparameters to be selected by CV. In
the training with (4), we set $\lambda=1$ when the training epoch is less than
a certain threshold $t$, and $\lambda=\lambda_{after}$ if the epoch is larger
than $t$. From a set of candidates, each of the CV methods selects a pair
$(t,\lambda_{after})$. To know the best possible performance among the
candidates, we also apply the test-domain validation (TDV) [19], which selects
the hyperparameters with the unseen test domain. Note that TDV is not
applicable in practical situations. The details on the experiments can be
found in Appendix E.

##### Synthesized Data 1

We compared the proposed method with the other approaches using synthesized
data with ${\mathcal{X}}={\mathbb{R}}^{2}$, ${\mathcal{Y}}=[3]$ and
${\mathcal{Z}}:=[2]$. We used distributions
$N_{0}:=\mathcal{N}(0,10^{2})\times\mathcal{N}(e,10^{2})$,
$N_{1}:=\mathcal{N}(30,10^{2})\times\mathcal{N}(-4e,10^{2})$ and
$N_{2}:=\mathcal{N}(-30,10^{2})\times\mathcal{N}(-e,10^{2})$, where
${\mathcal{N}}(a,b)$ denotes a normal distribution with its (mean, variance)
$=(a,b)$. Given $x\sim N_{i}$, the task is to predict $N_{i}$ among $i=0,1,2$.
The aim of IL is to ignore the second component of $x$, as it works as an
environmental factor. Given $e^{*}\in{\mathbb{N}}_{\geq 0}$ ranging from $0$
to $50$, each experiment draws ${\mathcal{D}}^{e^{*}}\sim
P_{X^{e^{*}},Y^{e^{*}}}$ with its sample size $n^{e^{*}}=2000$, and then
predicts $Y^{-e^{*}}$ from $X^{-e^{*}}$. Setting $g$ by $g(0)=0$ and
$g(1)=g(2)=1$, we draw ${\mathcal{D}}^{e}_{ad}\sim P_{X^{e},Z^{e}}$ from
${\mathcal{E}}_{ad}=\\{-100,-50,0,50,100\\}$ with its sample size $n^{e}=1000$
($\forall e\in{\mathcal{E}}_{ad}$). We model $\Phi$ by a $3$-layer neural net.
Setting the maximum epoch $500$, we select $(t,\lambda_{after})$ from $3\times
5$ candidates with $t\in\\{0,100,200\\}$ and
$\lambda_{after}\in\\{10^{0},10^{1},...,10^{4}\\}$ by each of the CV methods.
Table 1 shows the test accuracy of the estimates for $e=-e^{*}$ over 2000
random samples $(x,y)\sim P_{X^{-e^{*}},Y^{-e^{*}}}$. When $e^{*}=0$ and $5$,
The environmental bias of training ($e^{*}$) are similar to the one of test
$(-e^{*})$, and hence, the fine-tuning methods yield high performances, which
may use spurious correlation. As $e^{*}$ increases, the difference between the
training ($e^{*}$) and test $(-e^{*})$ distributions becomes larger, and the
previous methods fail to achieve high accuracy. The proposed methods (Ours)
keep higher performance than the others even for large $e^{*}$. Among the CV
methods, our two methods (CVI, CVII) significantly outperform the others for
larger $e^{*}$. For this data set, CVI and CVII show almost the same
performance.

##### Synthesized Data 2

To highlight the difference of the proposed CVI and CVII, we compare them
regarding the difference between domains ${\mathcal{E}}_{ad}$ and $e^{*}$. We
used synthesized data with ${\mathcal{X}}={\mathbb{R}}^{2}$,
${\mathcal{Y}}=[10]$ and ${\mathcal{Z}}:=[2]$, preparing ten distributions
$\\{N_{i}\\}_{i=1}^{10}$ on ${\mathbb{R}}^{2}$, which include an environmental
bias in the second component depending $e\in{\mathbb{Z}}$ (see Appendix E.1
for explicit representations of $\\{N_{i}\\}_{i=1}^{10}$). The task is to
predict $N_{i}$ ($i=1,\ldots,10$) for $x\sim N_{i}$. Setting $e^{*}:=20$ with
$n^{e^{*}}=60000$, the test task is to predict the label for domain $e=-20$.
Regarding the task with label of higher level, we use $g(y)=0$ if $y$ is odd
and $g(y)=0$ if $y$ is even. We draw ${\mathcal{D}}^{e}_{ad}\sim
P_{X^{e},Z^{e}}$ ($n^{e}=20000$) from ${\mathcal{E}}_{ad}=\\{e_{ad},40\\}$,
where $e_{ad}$ ranges from $-9$ to $1$. As $e_{ad}$ increases, the domains
${\mathcal{E}}_{ad}$ approach to $e^{*}$, and thus the labeling rule on
${\mathcal{E}}_{ad}$ becomes similar to one of $e^{*}$. The model $\Phi$ is a
$3$-layer neural net. We set the maximum epoch $500$, and select the
hyperparameter $(t,\lambda_{after})$ from $4$ candidates with $t\in\\{0\\}$
and $\lambda_{after}\in\\{0,0.001,80,100\\}$ by each CV method. Table 2 shows
the test accuracy of the estimates for $e=-e^{*}$ over 2000 random samples
$(x,y)\sim P_{X^{-e^{*}},Y^{-e^{*}}}$. The results show that, while CVI fails
to select optimal hyperparameters as $e$ increases, CVII keeps higher
performance, which accords with the theoretical implication in Section 3.4.

Table 3: Average Test Accuracies and SEs of Hierarchical Colored MNIST (5runs). TDV selects $\lambda$ which yields the highest performance on $e=0.9$. Best scores are bolded. | $e=0.1~{}~{}~{}~{}~{}~{}$ | $e=0.9~{}~{}~{}~{}~{}~{}$
---|---|---
Best possible | .800
Oracle (grayscale) | .780(.002)
ERM | .796 (.000) | .177 (.006)
FT |  .800 (.001) | .201 (.004)
FE | .796 (.001) | .200 (.007)
DSAN | .789 (.004) | .091 (.005)
Ours +Our CV I | .773 (.003) | .644 (.011)
Ours +Our CV II | .745 (.008) |  .707 (.012)
Ours +Tr-CV | .794 (.004) | .541 (.007)
Ours +LOD CV | .338 (.048) | .334 (.029)
Ours +TDV | .738 (.018) | .732 (.008)

Table 4: Means and SEs of $\\{$(Accuracy of TDV on $e=0.9$) -(Accuracy of Each CV on $e=0.9$) $\\}$ (5runs). Lowest errors are bolded.  CVI | CVII | Tr-CV | LOD-CV
---|---|---|---
.088 (.004) | .025 (.006) | .191 (.019) | .398 (.025)

##### Hierarchical Colored MNIST

We apply our framework to $Hierarchical$ $Colored$ $MNIST$, which is an
extended version of Colored MNIST [10] with ${\mathcal{Y}}=[3]$ and
${\mathcal{Z}}:=[2]$. We aim to predict $Y^{e}$ from digit image data $X^{e}$,
which is in the three categories $0-2$ ($y=0$), $3$ or $4$ ($y=1$) and $5-9$
($y=2$). The label is changed randomly to one of the rest with a probability
of $20\%$, which is denoted by $\hat{y}$. The environment $e$ controls the
color of the digit; for $\hat{y}$= $0,1$, the digit is colored in red with
probability $e$ and for $\hat{y}$= $2$ colored in green with probability
$1-e$. In the experiment, ${\mathcal{D}}^{e^{*}}\sim P_{X^{0.1},Y^{0.1}}$ is
drawn with sample size $n^{e^{*}}=5000$, and $Y^{e}$ is predicted based on
$X^{e}$ for $e=0.1$ and $0.9$. Regarding $Z^{e}$, we consider the task where
we predict $z=0$ for $X^{e}$ in $0-2$ and $z=1$ for $3-9$ (that is, $g(0)=0$
and $g(1)=g(2)=1$). We obtain the final label $\hat{z}$ by flipping $z$ with
$20\%$. As the environment factor, we color the digit red for $\hat{z}$= $0$
with probability $e$ and green for $\hat{z}=1$ with probability $1-e$. We set
${\mathcal{E}}_{ad}=\\{0.1,0.3,0.5,0.7,0.9\\}$ with $n^{e}=5000$ for $\forall
e\in{\mathcal{E}}_{ad}$. We model $\Phi$ by a $3$-layer neural net. With the
maximum epoch $500$, we select $(t,\lambda_{after})$ from $3\times 10$
candidates with
$t\in\\{0,100,200\\},\lambda_{after}\in\\{10^{0},10^{1},...,10^{9}\\}$ by each
CV method. Table 3 shows test accuracies for 2000 random samples in the
environment $e=0.1$ and $e=0.9$. The results, together with Appendix E.3,
demonstrate that the proposed methods significantly outperform the others for
$e=0.9$. Among the two proposed methods, CV II yields the higher test
accuracy. Table 4 shows the difference between accuracies by TDV and each CV
for the same data set with $e=0.9$. The results, together with Appendix E.3,
verify that CVII selects preferable hyperparameters with smaller errors.

Fig 1: Visualization of Bird recognition problem
Table 5: Average Test Accuracies and SEs of Bird recognition problem (5 runs). Oracle shows a result of ERM with samples from both $e_{1}$ and $e_{2}$ given. TDV selects $\lambda$ which yields the highest performance on $e_{2}$. Best scores are bolded. | Test Acc. on $e_{1}$ | Test Acc. on $e_{2}$
---|---|---
Oracle | .875 (.018)
ERM | .902 (.008) | .317 (.044)
FT | .909 (.012) | .364 (.028)
FE | .767 (.024) | .052 (.013)
Ours +Our CV I | .897 (.020) | .727 (.062)
Ours +Our CV II | .897 (.020) | .727 (.062)
Ours +Tr-CV | .919 (.006) | .651 (.031)
Ours +LOD CV | .338 (.048) | .334 (.029)
Ours +TDV | .886 (.035) | .782 (.020)

##### Bird recognition

Our method is applied to the Bird recognition problem [28], which aims to
predict three labels $Y^{e}$ of images $X^{e}$: $waterbird$ ($Y^{e}$= 0),
$landbird$ ($Y^{e}$= 1) and $no$ $bird$ ($Y^{e}$= 2). The dataset is made by
combining background images from the Places dataset [39] and bird images from
the CUB dataset [38] in two different ways ${\mathcal{E}}:=\\{e_{1},e_{2}\\}$.
In domain $e_{1}$, we prepare three types of image: landbird image with land
background, waterbird image with water background, and no bird with land
background (Figure 1, left). In domain $e_{2}$, we have landbird images with
water background, waterbird images with land background, and no bird with
water background (Figure 1, right). For the sample of the target task, we used
the domain $e^{*}=e_{1}$ and generated $n^{e^{*}}=8649$ data
${\mathcal{D}}^{e^{*}}\sim P_{X^{e_{1}},Y^{e_{1}}}$. The sample in the higher
level ${\mathcal{D}}^{e}_{ad}$ of $(X^{e},Z^{e})$, whose label is landbird
($Z^{e}=0$) and no landbird ($Z^{e}=1$) ($i.e.$, $g(1)=0$ and $g(0)=g(2)=1$),
is drawn from both $e_{1}$ and $e_{2}$ with $n^{e_{1}}=n^{e_{2}}=8649$. Here,
we use ${\mathcal{D}}^{e^{*}}$ as ${\mathcal{D}}^{e_{1}}_{ad}$ with labels of
${\mathcal{D}}^{e^{*}}$ re-annotated by $g$. We made a predictor of $Y^{e}$
based on $X^{e}$, and evaluated the test accuracy in the two domains
$e=e_{1},e_{2}$. We model $\Phi$ by ResNet50 [29]. Setting the maximum epoch
$5$, we select $(t,\lambda_{after})$ from $5\times 5$ candidates with
$t\in[5],\lambda_{after}\in\\{10^{0},10^{1},...,10^{4}\\}$ by each CV method.
Table 1 shows test accuracies with $2162$ random samples for $e_{1}$ and
$e_{2}$. We can see that the proposed framework together with CV methods
succeeded in capturing the predictor invariant to the change of background,
while the other methods failed. ERM and FT show much higher accuracy for
$e_{1}$ than Oracle and worst results for $e_{2}$, which implies that these
methods learn spurious correlation in ${\mathcal{D}}^{e^{*}}$.

##  6 Conclusion

We have proposed a new framework of invariance learning – assuming the
availability of datasets for another task in higher label hierarchy, we obtain
an invariant predictor for the target classification task using training data
in a single domain with the help of the multiple data sets for the higher
task. This framework mitigates the difficulty of annotating many labels for
the target task. Additionally, we have proposed two CV methods for
hyperparameter selection, which has been an outstanding problem of previous
methods for invariant learning. Theoretical analysis has revealed that our
methods select hyperparameter correctly under some settings. The experimental
results on synthesized and object recognition tasks have demonstrated the
effectiveness of the proposed framework and CV methods.

## Acknowledgements

The research is supported by the Research Fellowships of Japan Society for the
Promotion of Science for Young Scientists (Project number: 20J21396) and JST
CREST (Project number: JPMJCR2015).

## References

  * [1] V. Vapnik.  Principles of risk minimization for learning theory.  _In NIPS_ , 1992.
  * [2] L. Adolphs, J. Kohler, and A. Lucchi.  Ellipsoidal trust region methods and the marginal value of hessian information for neural network training.  _arXiv:1905.09201 (version 1)_ , 2019.
  * [3] S. Beery, G. V. Horn, P. Perona.  Recognition in terra incognita.  _In ECCV_ , 2019.
  * [4] J. R. Zech, M.A. Badgeley, M. Liu, A. B. Costa, J. J. Titano, E. K. Oermann.  Variable generalization performance of a deep learning model to detect pneumonia in chest radiographs: A cross-sectional study.  _$PLoS$ Medicine 15, e1002683 _, 2018.
  * [5] T. Niven, H.-Y Kao.  Probing neural network comprehension of natural language arguments.  _Proceedings of the 57th Annual Meeting of the Association for Computational_ , 2019.
  * [6] S. Gururangan, S. Swayamdipta, O. Levy, R. Schwartz, S. R. Bowman, N. A. Smith.  Annotation artifacts in Natural Language Inference data.  _Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics_ 2018\.
  * [7] J. Dastin.  Amazon scraps secret AI recruiting tool that showed bias against women.  _https://reut.rs/2Od9fPr._ 2018\.
  * [8] A. Ilyas, S. Santurkar, D. Tsipras, L. Engstrom, B. Tran, A. Madry.  Adversarial examples are not bugs, they are features,.  _In NeurIPS_ , 2019.
  * [9] J. Shane.  Do neural nets dream of electric sheep?  _https://aiweirdness.com/post/171451900302/_ , 2018.
  * [10] M. Arjovsky, L. Bottou, I. Gulrajani, and D. Lopez-Paz.  Invariant Risk Minimization.  _arXiv:1907.02893_ , 2019.
  * [11] J. Peters, P. Bühlmann, and N. Meinshausen.  Causal inference using invariant prediction: identification and confidence intervals.  _JRSS B,_ 2016\.
  * [12] C. Heinze-Deml, J. Peters, and N. Meinshausen.  Invariant causal prediction for nonlinear models.  _Journal of Causal Inference_ , 2018.
  * [13] D. Rothenhausler, P. Buhlmann, N. Meinshausen, and J. Peters.  Anchor regression: heterogeneous data meets causality.  _JRSS B_ , 2018.
  * [14] K. Ahuja, K. Shanmugam, K. Varshney, and A. Dhurandhar.  Invariant risk minimization games.  _In ICML_ , 2020.
  * [15] M. Koyama, S. Yamaguchi.  When is invariance useful in an Out-of-Distribution Generalization problem?  _arXiv_ , 2008.01883, 2020
  * [16] E. A. AlBadawy, A. Saha, and M. A. Mazurowski.  Deep learning for segmentation of brain tumors: Impact of cross-institutional training and testing.  _Medical physics,_ 2018\.
  * [17] C. S. Perone, P. Ballester, R. C. Barros, and J. Cohen-Adad.  Unsupervised domain adaptation for medical imaging segmentation with self-ensembling.  _NeuroImage_ , 2019.
  * [18] W. D. Heaven.  Google’s medical AI was super accurate in a lab. real life was a different story.  _MIT Technology Review,_ 2020\.
  * [19] I. Gulrajani, D. Lopez-Paz.  In Search of Lost Domain Generalization.  _In ICLR,_ 2021\.
  * [20] P. Kamath.  Does Invariant Risk Minimization Capture Invariance?  _In AISTATS,_ 2021\.
  * [21] D. Krueger, E. Caballero, J. Jacobsen, A. Zhang, J. Binas, D. Zhang, R. L. Priol, A. Courville.  Out-of-Distribution Generalization via Risk Extrapolation.  _In ICML,_ 2021\.
  * [22] S. J. Pan, and Q. Yang.  A survey on transfer learning.  _IEEE Transactions on Knowledge and Data Engineering_ , 22(10):1345-1359, 2009.
  * [23] Q. Yang, Y. Zhang, W. Dai, and S. J. Pan.  Transfer Learning.  _Cambridge University Press,_ 2020\.
  * [24] J. Yosinski, J. Clune, Y. Bengio, and H. Lipson.  How transferable are features in deep neural networks?  _In NIPS,_ 2014\.
  * [25] Y. Ganin, E. Ustinova, H. Ajakan, P. Germain, H. Larochelle, F. Laviolette, M. March, and V. Lempitsky.  Domain-adversarial training of neural networks.  _Journal of Machine Learning Research_ , 2016.
  * [26] S. Ben-David, J. Blitzer, K. Crammer, and F. Pereira.  Analysis of representations for domain adaptation.  _In NIPS_ , 2007.
  * [27] G. Louppe, M. Kagan, and K. Cranmer.  Learning to pivot with adversarial networks.  _In NIPS_ , 2017.
  * [28] S. Sagawa, P. W. Koh, T. B. Hashimoto, P. Liang.  Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for worst-case generalization.  _In ECCV_ , 2019.
  * [29] K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition,  _In CVPR_ , 2016.
  * [30] C. Finn, P. Abbeel, and S. Levine.  Model-agnostic meta- learning for fast adaptation of deep networks.  _In ICML_ , 2017.
  * [31] P. Stojanov, Z. Li, M. Gong, Ruichu Cai, J. G. Carbonell, K. Zhang.  Domain Adaptation with Invariant Representation Learning: What Transformations to Learn?  _In NeurIPS_ , 2021.
  * [32] Y. Zhang, H. Tang, K. Jia, M. Tan.  Domain-Symmetric Networks for Adversarial Domain Adaptation.  _In CVPR_ , 2019.
  * [33] J. Liu, Z. Hu, P. Cui, B. Li, Z. Shen.  Heterogeneous Risk Minimization.  _In ICML_ , 2021.
  * [34] J. Liu, Z. Hu, P. Cui, B. Li, Z. Shen.  Kernelized Heterogeneous Risk Minimization.  _In NeurIPS_ , 2021.
  * [35] J. Creager, J. Jacobsen, R. Zemel.  Environment Inference for Invariant Learning.  _In ICML_ , 2021.
  * [36] G. Parascandolo, A. Neitz, A. Orvieto, L. Gresele, B. Scholkopf.  Learning explanations that are hard to vary.  _In ICLR_ , 2021.
  * [37] D. P. Kingma, J. L. Ba.  Adam: A Method for Stochastic Optimization.  _In ICLR_ , 2015.
  * [38] C. Wah, S. Branson, P. Welinder, P. Perona, and S. Belongie,  The Caltech-UCSD Birds-200-2011 dataset.  Technical report, California Institute of Technology, 2011.
  * [39] B. Zhou, A. Lapedriza, A. Khosla, A. Oliva, and A. Torralba.  Places: A 10 million image database for scene recognition.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 40(6): 1452–1464, 2017
  * [40] M. Rojas-Carulla, B. Scholkopf, R. Turner, and J. Peters.  Invariant models for causal transfer learning.  _Journal of Machine Learning Research_ , 2018
  * [41] M. Andrychowicz1, M. Denil1, S. Colmenarejo1, M. W. Hoffman1, D. Pfau1, T. Schaul, B. Shillingford, N. de Freitas.  Learning to learn by gradient descent by gradient descent.  _In NIPS_ , 2016
  * [42] H. Pham, Z. Dai, Q. Xie, Q. V. Le.  Meta Pseudo Labels.  _In CVPR_ , 2021
  * [43] D. Lee.  Pseudo-Label : The Simple and Efficient Semi-Supervised Learning Method for Deep Neural Networks.  _In ICML Workshop_ , 2013
  * [44] Z, Zheng, L. Zheng, Y. Yang.  Unlabeled Samples Generated by GAN Improve the Person Reidentification Baseline in vitro,  _In ICCV_ , 2017
  * [45] X. Gu, J. Sun, Z. Xu.  Spherical Space Domain Adaptation With Robust Pseudo-Label Loss.  _In CVPR_ , 2020
  * [46] T. Cour, B. Sapp, and B. Taskar.  Learning from partial labels.  _Journal of Machine Learning Research_ , 2011.
  * [47] N. Xu, J. Lv, X.Geng.  Partial label learning via label enhancement.  _In AAAI_ , 2019\.
  * [48] Y. Yan, Y. Guo.  Partial Label Learning with Batch Label Correction.  _In AAAI_ , 2021\.
  * [49] T. Ishida, G. Niu, A. Menon, M. Sugiyama.  Complementary-Label Learning for Arbitrary Losses and Models.  _In ICML_ , 2019\.
  * [50] L. Feng, T. Kaneko, B. Han, Ga. Niu, B. An, M. Sugiyama.  Learning with Multiple Complementary Labels.  _In ICML_ , 2020\.
  * [51] Y. Katsura, M. Uchida.  Bridging Ordinary-Label Learning and Complementary-Label Learning.  _In ACML_ , 2020\.
  * [52] M. Rojas-Carulla, B. Scholkopf, R. Turner, and J. Peters.  Invariant models for causal transfer learning.  _JMLR_ , 2018.
  * [53] D. P. Kingma, J. L. Ba.  Adam: A Method for Stochastic Optimization.  _In ICLR_ , 2015.

##  Appendix A Proof of Theorem 3.1

$\displaystyle{\mathcal{R}}^{(X,Y)}(p_{\theta}\circ\Phi)-{\mathcal{R}}^{(X,g(Y))}(p_{\theta}\circ\Phi)$
$\displaystyle=\int-\log p_{\theta}(Y|\Phi(X))dP_{Y,\Phi(X)}+\int\log
p_{\theta}(g(Y)|\Phi(X))dP_{g(Y),\Phi(X)}$
$\displaystyle=-\int\log\frac{p_{\theta}(Y|\Phi(X))}{p_{\theta}(g(Y)|\Phi(X))}dP_{(Y,\Phi(X))}$
$\displaystyle=-\int
dP_{g(Y)}\int\log\frac{p_{\theta}(Y|\Phi(X))}{p_{\theta}(g(Y)|\Phi(X))}dP_{(Y,\Phi(X))|g(Y)}$
(6)

By the definition of $p_{\theta}(y|\Phi(x),Y\in g^{-1}(z)))$ in Theorem 3.1,
$\frac{p_{\theta}(y|\Phi(x))}{p_{\theta}(g(y)|\Phi(x))}=p_{\theta}(y|\Phi(x),Y\in
g^{-1}(z))$ holds, where $z=g(y)$. Therefore, we obtain

$\displaystyle\mathrm{(\ref{eq:ThmHIT-CV1})}$ $\displaystyle=-\int
dP_{g(Y)}\int\log\frac{p_{\theta}(Y|\Phi(X))}{p_{\theta}(g(Y)|\Phi(X))}dP_{(Y,\Phi(X))|g(Y)}$
$\displaystyle=-\int dP_{g(Y)}\int\log
p_{\theta}(Y|\Phi(X),Y=g(Y))dP_{(Y,\Phi(X))|g(Y)}$ (7)
$\displaystyle=-\sum_{z\in{\mathcal{Z}}}P(g(Y)=z)\int\log
p_{\theta}(Y|\Phi(X),Y\in g^{-1}(z))dP_{(Y,\Phi(X))|g(Y)=z}$
$\displaystyle=-\sum_{z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}\in{\mathcal{Z}}^{\cancel{\hookrightarrow}}}P(g(Y)=z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})\int\log
p_{\theta}(Y|\Phi(X),Y\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}))dP_{(Y,\Phi(X))|g(Y)=z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+\sum_{z^{\scalebox{0.5}{$\hookrightarrow$}}\notin{\mathcal{Z}}^{\cancel{\hookrightarrow}}}P(g(Y)=z^{\scalebox{0.5}{$\hookrightarrow$}})\int\log
p_{\theta}(Y|\Phi(X),Y\in
g^{-1}(z^{\scalebox{0.5}{$\hookrightarrow$}}))dP_{(Y,\Phi(X))|g(Y)=z^{\scalebox{0.5}{$\hookrightarrow$}}}.$
(8)

Noting that, for $\forall
z^{\scalebox{0.5}{$\hookrightarrow$}}\notin{\mathcal{Z}}^{\cancel{\hookrightarrow}}$
and
$y:=g^{-1}(z^{\scalebox{0.5}{$\hookrightarrow$}})$111$z^{\scalebox{0.5}{$\hookrightarrow$}}\notin{\mathcal{Z}}^{\cancel{\hookrightarrow}}$
implies that $|g^{-1}(z^{\scalebox{0.5}{$\hookrightarrow$}})|=1$ and
therefore, $g^{-1}(z^{\scalebox{0.5}{$\hookrightarrow$}})$ is determined
uniquely. Note that there is no chance that
$|g^{-1}(z^{\scalebox{0.5}{$\hookrightarrow$}})|=0$ by the surjectivity of
$g$., $p_{\theta}(y|\Phi(x),Y\in
g^{-1}(z^{\scalebox{0.5}{$\hookrightarrow$}})))=1$ holds, we can see that
$\log
p_{\theta}(y,|\Phi(x),Y=g^{-1}(z^{\scalebox{0.5}{$\hookrightarrow$}})))=0$. It
leads us to the equality
$\sum_{z^{\scalebox{0.5}{$\hookrightarrow$}}\notin{\mathcal{Z}}^{\cancel{\hookrightarrow}}}P(g(Y)=z^{\scalebox{0.5}{$\hookrightarrow$}})\int\log
p_{\theta}(Y|\Phi(X),Y\in
g(z^{\scalebox{0.5}{$\hookrightarrow$}}))dP_{(Y,\Phi(X))|g(Y)=z^{\scalebox{0.5}{$\hookrightarrow$}}}=0$,
which concludes the proof. $\Box$

##  Appendix B Proof of Theorem 3.2

We restate Theorem 3.2 with some notation arrangements.

######  Theorem B.1.

Let ${\mathcal{X}}:={\mathcal{X}}_{1}\times{\mathcal{X}}_{2}$ where
${\mathcal{X}}_{1}:={\mathbb{R}}^{n_{1}}$ and
${\mathcal{X}}_{2}:={\mathbb{R}}^{n_{2}}$ with $n_{1},n_{2}\in{\mathbb{N}}$.
For any random variable $X$ on ${\mathcal{X}}$, $X_{1}$ and $X_{2}$ denote its
${\mathcal{X}}_{1}$\- and ${\mathcal{X}}_{2}$-component of $X$, respectively.
Assume that, for $\lambda\in\Lambda$, there corresponds a projection
$\Phi^{\lambda}:{\mathcal{X}}\rightarrow{\mathbb{R}}^{n_{\lambda}}$
($n_{\lambda}\leq n_{1}+n_{2}$). $\Phi_{1}^{\lambda}$ and $\Phi_{2}^{\lambda}$
denote an ${\mathcal{X}}_{1}$ and ${\mathcal{X}}_{2}$ components of
$\Phi^{\lambda}$. For $i=1,2$, if $\Phi^{\lambda}$ does not have an
${\mathcal{X}}_{i}$-component, we denote
$\mathrm{Im}\Phi^{\lambda}_{i}=\emptyset$. $\Phi(X)$, $\Phi^{\lambda}_{1}(X)$
and $\Phi^{\lambda}_{2}(X)$ are abbreviated by $X^{\lambda}$,
$X_{1}^{\lambda}$ and $X_{2}^{\lambda}$, respectively. Fixing a random
variable $(X^{I}_{1},Y^{I})$ on ${\mathcal{X}}_{1}\times{\mathcal{Y}}$, set

$T_{all}:=\left\\{(X,Y):~{}random~{}variable~{}on~{}{\mathcal{X}}\times{\mathcal{Y}}\left|P_{Y,X_{1}}=P_{Y^{I},X^{I}_{1}}\right.\right\\}.$

Fix $(X^{*},Y^{*})\in T_{all}$ and $T_{ad}\subset T_{all}$. For
$\lambda\in\Lambda$,
$p^{*,\lambda}:{\mathbb{R}}^{n_{\lambda}}\rightarrow{\mathcal{P}}_{{\mathcal{Y}}}$
denotes the conditional probability density function of
$P(Y^{*}|\Phi^{\lambda}(X^{*}))=P(Y^{*}|X^{*,\lambda})$. For
$\lambda\in\Lambda$, define ${\mathcal{R}}^{o.o.d.}(\lambda)$ and
${\mathcal{R}}^{I}(\lambda)$ by

$\displaystyle{\mathcal{R}}^{o.o.d.}(\lambda):=\max_{(X,Y)\in
T_{all}}{\mathcal{R}}^{(X,Y)}(p^{*,\lambda}\circ\Phi^{\lambda}),$
$\displaystyle{\mathcal{R}}^{I}(\lambda):=\max\Biggl{\\{}\max_{(X,Y)\in
T_{ad}}{\mathcal{R}}^{(X,g(Y))}(p^{*,\lambda}\circ\Phi^{\lambda}),{\mathcal{R}}^{(X^{*},Y^{*})}(p^{*,\lambda}\circ\Phi^{\lambda})\Biggr{\\}}$

respectively. Assume that the following two conditions hold:

  * (I)

$\exists\lambda^{I}\in\Lambda$ s.t.
$\Phi^{\lambda^{I}}=\Phi^{{\mathcal{X}}_{1}}$.

  * (II)

For sufficiently small ${\varepsilon}\ll 1$, the following statement holds:
$\forall\lambda$ with $\mathrm{Im}\Phi^{\lambda}_{2}\neq\emptyset$, there
exists $(X^{e_{\lambda}},Y^{e_{\lambda}})$ such that
$P(g(Y^{*})|X^{*,\lambda})\leq e^{-\beta}-{\varepsilon}$ holds
$P_{X^{e_{\lambda}},Y^{e_{\lambda}}}$-almost everywhere.

Then, $\mathop{\rm
argmin}\limits_{\lambda\in\Lambda}{\mathcal{R}}^{I}(\lambda)\subset\mathop{\rm
argmin}\limits_{\lambda\in\Lambda}{\mathcal{R}}^{o.o.d.}(\lambda)$ holds.

$T_{all}$, $T_{ad}$ and $(X^{*},Y^{*})$ correspond to
$\\{(X^{e},Y^{e})\\}_{e\in{\mathcal{E}}}$,$\\{(X^{e},Y^{e})\\}_{e\in{\mathcal{E}}_{ad}}$
and $(X^{e^{*}},Y^{e^{*}})$ in Theorem 3.2 respectively. (a) and (b) in
Theorem 3.2 are represented by the construction of $T_{all}$. (c) and (d) in
Theorem 3.2 are represented by (I) and (II) respectively.

To prove Theorem B.1, we prepare three lemmas. In the lemmas, notations are
same as in Theorem B.1 and condition (I) and (II) in Theorem B.1 are also
imposed on.

######  Lemma B.2.

$\lambda^{I}\in\mathop{\rm
argmin}\limits_{\lambda\in\Lambda}{\mathcal{R}}^{o.o.d.}(\lambda)$.

######  Lemma B.3.

Assume that $\hat{\lambda}\in\mathop{\rm
argmin}\limits_{\lambda\in\Lambda}{\mathcal{R}}^{I}(\lambda)$. Then
$\mathrm{Im}\Phi_{2}^{\hat{\lambda}}=\emptyset$.

######  Lemma B.4.

If $\hat{\lambda}\in\Lambda$ satisfies
$\mathrm{Im}\Phi_{2}^{\hat{\lambda}}=\emptyset$,
${\mathcal{R}}^{I}(\hat{\lambda})={\mathcal{R}}^{o.o.d.}(\hat{\lambda})$.

Before proving the above lemmas, we prove Theorem B.1 suppose that they hold.
proof of Theorem B.1.
Take $\hat{\lambda}\in\mathop{\rm argmin}\limits{\mathcal{R}}^{I}(\lambda)$.
Then, $\mathrm{Im}\Phi_{2}^{\hat{\lambda}}=\emptyset$ holds by Lemma B.3 and
therefore,
${\mathcal{R}}^{I}(\hat{\lambda})={\mathcal{R}}^{o.o.d.}(\hat{\lambda})$ holds
by Lemma B.4. Moreover,
${\mathcal{R}}^{o.o.d.}(\hat{\lambda})\geq{\mathcal{R}}^{o.o.d.}(\lambda^{I})$
holds by Lemma B.2 and
${\mathcal{R}}^{o.o.d.}(\lambda^{I})={\mathcal{R}}^{I}(\lambda^{I})$ holds by
B.4.222Note that, since $\Phi^{\lambda^{I}}$ is the projection onto
${\mathcal{X}}_{1}$, $\mathrm{Im}\Phi_{2}^{\lambda^{I}}=\emptyset$. By the
assumption $\hat{\lambda}\in\mathop{\rm
argmin}\limits_{\lambda\in\Lambda}{\mathcal{R}}^{I}(\hat{\lambda})$,
${\mathcal{R}}^{I}(\lambda^{I})\geq{\mathcal{R}}^{I}(\hat{\lambda})$ holds.
Arranging these inequalities, we obtain

${\mathcal{R}}^{I}(\hat{\lambda})={\mathcal{R}}^{o.o.d.}(\hat{\lambda})\geq{\mathcal{R}}^{o.o.d.}(\lambda^{I})={\mathcal{R}}^{I}(\lambda^{I})\geq{\mathcal{R}}^{I}(\hat{\lambda}).$
(9)

Since the left and right ends of (9) are connected by the same value
${\mathcal{R}}^{I}(\hat{\lambda})$, the inequalities in (9) must be
equalities. Hence, we obtain the equality
${\mathcal{R}}^{o.o.d.}(\hat{\lambda})={\mathcal{R}}^{o.o.d.}(\lambda^{I})$.
By the minimality of $\lambda^{I}$ (Lemma B.2), the equality
${\mathcal{R}}^{o.o.d.}(\hat{\lambda})={\mathcal{R}}^{o.o.d.}(\lambda^{I})$
implies $\hat{\lambda}\in\mathop{\rm
argmin}\limits{\mathcal{R}}^{o.o.d.}(\lambda)$, which concludes the proof.
$\Box$
proof of Lemma B.2
It suffices to prove that, for any $\hat{\lambda}\in\Lambda$ and
$(\bar{X},\bar{Y})\in T_{all}$, there exists $(\bar{\bar{X}},\bar{\bar{Y}})\in
T_{all}$ such that $\int-\log
p^{*,\hat{\lambda}}(\bar{\bar{Y}}|\Phi^{\hat{\lambda}}(\bar{\bar{X}}))dP_{\bar{\bar{X}},\bar{\bar{Y}}}\geq\int-\log
p^{*,\lambda^{I}}(\bar{Y}|\Phi^{\lambda^{I}}(\bar{X}))dP_{\bar{X},\bar{Y}}$.
Take $(\bar{\bar{X}},\bar{\bar{Y}})\in T_{all}$ such that its distribution is
$P_{X_{1}^{I},Y^{I}}\times P_{\bar{X}_{2}}$. Here, $P_{\bar{X}_{2}}$ denotes a
marginal distribution of $(\bar{X},\bar{Y})\in T_{all}$ on ${\mathcal{X}}_{2}$
and $P_{X_{1}^{I},Y^{I}}\times P_{\bar{X}_{2}}$ denotes the product of
$P_{X_{1}^{I},Y^{I}}$ and $P_{\bar{X}_{2}}$.

$\displaystyle\int-\log
p^{*,\hat{\lambda}}(\bar{\bar{Y}}|\Phi^{\hat{\lambda}}(\bar{\bar{X}}))dP_{\bar{\bar{X}},\bar{\bar{Y}}}$
$\displaystyle=\int-\log
p^{*,\hat{\lambda}}(\bar{\bar{Y}}|\bar{\bar{X}}^{\hat{\lambda}}_{1},\bar{\bar{X}}^{\hat{\lambda}}_{2})dP_{\bar{\bar{X}},\bar{\bar{Y}}}$
$\displaystyle=\int-\log
p^{*,\hat{\lambda}}(Y^{I}|X^{I,\hat{\lambda}}_{1},\bar{X}^{\hat{\lambda}}_{2})d(P_{X_{1}^{I},Y^{I}}\times
P_{\bar{X}_{2}})$ $\displaystyle=\int dP_{\bar{X}_{2}}\int-\log
p^{*,\hat{\lambda}}(Y^{I}|X^{I,\hat{\lambda}}_{1},\bar{X}^{\hat{\lambda}}_{2})dP_{X_{1}^{I},Y^{I}}.$
(10)

Note that, for $\forall x\in\mathrm{Im}\Phi_{2}^{\hat{\lambda}}$, $\int-\log
p^{*,\hat{\lambda}}(Y^{I}|X^{I,\hat{\lambda}}_{1},\bar{X}^{\hat{\lambda}}_{2}=x^{\hat{\lambda}}_{2}))dP_{X_{1}^{I},Y^{I}}\geq\int-\log
p^{*,\lambda^{I}}(Y^{I}|X^{I}_{1})dP_{X^{I}_{1},Y^{I}}$ holds since a minimum
of the cross entropy loss is attained if and only if $p_{\theta}$ corresponds
to the conditional distribution function $p^{*,\lambda^{I}}$ of
$P_{Y^{I}|X_{1}^{I}}$.333By the construction of $T_{all}$, $P_{Y|X_{1}}$
corresponds to $P_{Y^{I}|X_{1}^{I}}$ for any $(X,Y)\in T_{all}$. Therefore,
$P_{Y^{I}|X_{1}^{I}}=P_{Y^{*}|X^{*}_{1}}=P_{Y^{*}|\Phi^{\lambda^{I}}(X^{*})}$
holds, which implies that the conditional probability density function of
$P_{Y^{I}|X_{1}^{I}}$ is $p^{*,\lambda^{I}}$. Therefore, we can see that

$\displaystyle\mathrm{(\ref{eq:Lem:min of I})}$ $\displaystyle\geq\int
dP_{\bar{X}_{2}}\int-\log
p^{*,\lambda^{I}}(Y^{I}|X^{I}_{1})dP_{X^{I}_{1},Y^{I}}$ $\displaystyle=\int
dP_{\bar{X}_{2}|X_{1}^{I},Y^{I}}\int-\log
p^{*,\lambda^{I}}(Y^{I}|X^{I}_{1})dP_{X^{I}_{1},Y^{I}}$
$\displaystyle=\int\int-\log
p^{*,\lambda^{I}}(Y^{I}|X^{I}_{1})dP_{X^{I}_{1},Y^{I}}dP_{\bar{X}_{2}|X_{1}^{I},Y^{I}}$
$\displaystyle=\int-\log
p^{*,\lambda^{I}}(\bar{Y}|\bar{X}_{1})dP_{\bar{X},\bar{Y}}$
$\displaystyle=\int-\log
p^{*,\lambda^{I}}(\bar{Y}|\Phi^{\lambda^{I}}(\bar{X}))dP_{\bar{X},\bar{Y}},$

and therefore, it concludes the proof. Here, the first equality holds because
$-\log p^{*,\lambda^{I}}(Y^{I}|X^{I}_{1})$ is not affected by
${\mathcal{X}}_{2}$. $\Box$
proof of Lemma B.3.
Let us prove the contraposition of Lemma B.3. Take $\hat{\lambda}\in\Lambda$
with $\mathrm{Im}\Phi_{2}^{\hat{\lambda}}\neq\emptyset$. To prove that
$\hat{\lambda}\notin\mathop{\rm argmin}\limits{\mathcal{R}}^{I}(\lambda)$, we
may prove that
${\mathcal{R}}^{I}(\hat{\lambda})>{\mathcal{R}}^{I}(\lambda^{I})$ since
$\lambda^{I}\in\Lambda$ (Assumption (I) in the statement). To show this, it
suffices to prove the following statement:

$\displaystyle\exists(\bar{X},\bar{Y})\in T_{ad}~{}~{}s.t.~{}~{}\int-\log
p^{*,\hat{\lambda}}(g(\bar{Y})|\bar{X}^{\hat{\lambda}})dP_{\bar{X},g(\bar{Y})}>{\mathcal{R}}^{I}(\lambda^{I}).$
(11)

From Condition (II), we can take
$(X^{e_{\hat{\lambda}}},Y^{e_{\hat{\lambda}}})\in T_{ad}$ such that the
following statement holds:

$P(g(Y^{*})|X^{*,\hat{\lambda}})\leq e^{-\beta}-{\varepsilon}$ holds
$P_{X^{e_{\hat{\lambda}}},Y^{e_{\hat{\lambda}}}}$-almost everywhere.

Before proving (11), we prepare one supplementary inequality:
Supplementary Inequality

$\int-\log
p^{*,\hat{\lambda}}(g(Y^{e_{\hat{\lambda}}})|X^{e_{\hat{\lambda}},\hat{\lambda}})dP_{X^{e_{\hat{\lambda}}},g(Y^{e_{\hat{\lambda}}})}\geq-\log\left\\{{e^{-\beta}-\epsilon}\right\\}.$

To prove the inequality, note that
$P_{X^{e_{\hat{\lambda}}},g(Y^{e_{\hat{\lambda}}})}(A)=0$, where

$A:=\left\\{\bigl{(}x,y\bigr{)}\in{\mathcal{X}}\times{\mathcal{Y}}\left|P(g(Y^{*})=g(y)|X^{*,\hat{\lambda}}=\Phi^{\hat{\lambda}}(x))>e^{-\beta}-{\varepsilon}\right.\right\\}$

since“ $P(g(Y^{*})|X^{*,\hat{\lambda}})\leq e^{-\beta}-{\varepsilon}$ holds
$P_{X^{e_{\hat{\lambda}}},Y^{e_{\hat{\lambda}}}}$-almost everywhere” holds.

Therefore, we can see that

$\int-\log
p^{*,\hat{\lambda}}(g(Y^{e_{\hat{\lambda}}})|X^{e_{\hat{\lambda}},\hat{\lambda}})dP_{X^{e_{\hat{\lambda}}},g(Y^{e_{\hat{\lambda}}})}=\int_{{\mathcal{X}}\times{\mathcal{Y}}-A}-\log
p^{*,\hat{\lambda}}(g(Y^{e_{\hat{\lambda}}})|X^{e_{\hat{\lambda}},\hat{\lambda}})dP_{X^{e_{\hat{\lambda}}},g(Y^{e_{\hat{\lambda}}})}$

. Note that for any $(x,y)\in{\mathcal{X}}\times{\mathcal{Y}}-A$, $-\log
p^{*,\hat{\lambda}}(g(y)|x^{\hat{\lambda}})\geq e^{-\beta}-{\varepsilon}$;
indeed, since

${\mathcal{X}}\times{\mathcal{Y}}-A=\left\\{\bigl{(}x,y\bigr{)}\in{\mathcal{X}}\times{\mathcal{Y}}\left|P(g(Y^{*})=g(y)|X^{*,\hat{\lambda}}=\Phi^{\hat{\lambda}}(x))\leq
e^{-\beta}-{\varepsilon}\right.\right\\},$

for any $(x,y)\in{\mathcal{X}}\times{\mathcal{Y}}-A$,

$-\log p^{*,\hat{\lambda}}(g(y)|x^{\hat{\lambda}})=-\log
P(g(Y^{*})=g(y)|X^{*,\hat{\lambda}}=\Phi^{\hat{\lambda}}(x))\geq-\log\left\\{{e^{-\beta}-\epsilon}\right\\}.$

Then, we obtain

$\displaystyle\int-\log
p^{*,\hat{\lambda}}(g(Y^{e_{\hat{\lambda}}})|X^{e_{\hat{\lambda}},\hat{\lambda}})dP_{X^{e_{\hat{\lambda}}},g(Y^{e_{\hat{\lambda}}})}$
$\displaystyle=\int_{{\mathcal{X}}\times{\mathcal{Y}}-A}-\log
p^{*,\hat{\lambda}}(g(Y^{e_{\hat{\lambda}}})|X^{e_{\hat{\lambda}},\hat{\lambda}})dP_{X^{e_{\hat{\lambda}}},g(Y^{e_{\hat{\lambda}}})}$
$\displaystyle\geq-\log\left\\{{e^{-\beta}-\epsilon}\right\\}.$

Proof of Inequality (11).

$\displaystyle\int-\log
p^{*,\hat{\lambda}}(g(Y^{e_{\hat{\lambda}}})|X^{e_{\hat{\lambda}},\hat{\lambda}})dP_{X^{e_{\hat{\lambda}}},g(Y^{e_{\hat{\lambda}}})}\geq-\log\left\\{{e^{-\beta}-\epsilon}\right\\}>-\log\left\\{{e^{-\beta}}\right\\}=\beta=H(Y^{*}|X_{1}^{*})$
(12)

Note that $H(Y^{*}|X_{1}^{*})={\mathcal{R}}^{o.o.d.}(\lambda^{I})$; indeed,

$\displaystyle{\mathcal{R}}^{o.o.d.}(\lambda^{I})$
$\displaystyle=\max_{(X,Y)\in
T_{all}}{\mathcal{R}}^{(X,Y)}(p^{*,\lambda^{I}}\circ\Phi^{\lambda^{I}})=\max_{(X,Y)\in
T_{all}}\int-\log p^{*,\lambda^{I}}(Y|\Phi^{\lambda^{I}}(X))dP_{X,Y}$
$\displaystyle=\max_{(X,Y)\in T_{all}}\int-\log
p^{*,\lambda^{I}}(Y|\Phi^{\lambda^{I}}(X))dP_{\Phi^{\lambda^{I}}(X),Y}$
$\displaystyle=\max_{(X,Y)\in T_{all}}\int-\log
p^{*,\lambda^{I}}(Y|X_{1})dP_{X_{1},Y}.$ (13)

Noting that $P_{X_{1},Y}=P_{X_{1}^{*},Y^{*}}(=P_{X_{1}^{I},Y^{I}})$ for any
$(X,Y)\in T_{all}$ and $p^{*,\lambda^{I}}$ coincides with the conditional
probability density function of $P_{Y^{*}|X_{1}^{*}}$, we can see that

$\mathrm{(\ref{eq:Lem:min is no II:3 })}=\int-\log
p^{*,\lambda^{I}}(Y^{*}|X_{1}^{*})dP_{X_{1}^{*},Y^{*}}=H(Y^{*}|X_{1}^{*}).$

Hence, we can derive $\int-\log
p^{*,\hat{\lambda}}(g(Y^{e^{\lambda}})|X^{e_{\hat{\lambda}},\hat{\lambda}})dP_{X^{e_{\hat{\lambda}}},g(Y^{e_{\hat{\lambda}}})}>H(Y^{*}|X_{1}^{*})={\mathcal{R}}^{o.o.d.}(\lambda^{I})$,
which concludes the proof. $\Box$

##### proof of Lemma B.4

.
Take $\hat{\lambda}\in\Lambda$ that satisfies
$\mathrm{Im}\Phi_{2}^{\hat{\lambda}}=\emptyset$. Then,
$P_{\Phi(X^{\hat{\lambda}}),Y}=P_{\Phi(X^{I,\hat{\lambda}}),Y^{I}}$ holds for
$\forall(X,Y)\in T_{all}$ because of $P_{X_{1},Y}=P_{X_{1}^{I},Y}$, and
therefore,
${\mathcal{R}}^{(X,g(Y))}(p^{*,\hat{\lambda}}\circ\Phi^{\hat{\lambda}})={\mathcal{R}}^{(X^{I},g(Y^{I}))}(p^{*,\hat{\lambda}}\circ\Phi^{\hat{\lambda}})$
and
${\mathcal{R}}^{(X^{*},Y^{*})}(p^{*,\hat{\lambda}}\circ\Phi^{\hat{\lambda}})={\mathcal{R}}^{(X^{I},Y^{I})}(p^{*,\hat{\lambda}}\circ\Phi^{\hat{\lambda}})$
hold. These two equalities lead the following equality:

$\displaystyle{\mathcal{R}}^{I}(\hat{\lambda})$
$\displaystyle=\max\Biggl{\\{}\max_{(X,Y)\in
T_{ad}}{\mathcal{R}}^{(X,g(Y))}(p^{*,\hat{\lambda}}\circ\Phi^{\hat{\lambda}}),{\mathcal{R}}^{(X^{*},Y^{*})}(p^{*,\hat{\lambda}}\circ\Phi^{\hat{\lambda}})\Biggr{\\}}$
$\displaystyle=\max\Biggl{\\{}{\mathcal{R}}^{(X^{I},g(Y^{I}))}(p^{*,\hat{\lambda}}\circ\Phi^{\hat{\lambda}}),{\mathcal{R}}^{(X^{I},Y^{I})}(p^{*,\hat{\lambda}}\circ\Phi^{\hat{\lambda}})\Biggr{\\}}$
(14)

By Theorem 3.1,

$\displaystyle
R^{(X^{I},Y^{I})}(p^{*,\hat{\lambda}}\circ\Phi^{\hat{\lambda}})$
$\displaystyle={\mathcal{R}}^{(X^{I},g(Y^{I}))}(p^{*,\hat{\lambda}}\circ\Phi^{\hat{\lambda}})+\sum_{z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}\in{\mathcal{Z}}^{\cancel{\hookrightarrow}}}P(Y^{I}=g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}))\int-\log
p^{*,\hat{\lambda}}(Y^{I}|\Phi(X^{I}),Y^{I}\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}))dP_{X^{I},Y^{I}|Y^{I}\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})}$
$\displaystyle\geq{\mathcal{R}}^{(X^{I},g(Y^{I}))}(p^{*,\hat{\lambda}}\circ\Phi^{\hat{\lambda}})$

holds and therefore,
$(\ref{eq_aprrox1})={\mathcal{R}}^{(X^{I},Y^{I})}(p^{*,\hat{\lambda}}\circ\Phi^{\hat{\lambda}})$.
Since $P_{\Phi^{\hat{\lambda}}(X),Y}$ are the same for $T_{all}$,

$\displaystyle{\mathcal{R}}^{(X^{I},Y^{I})}(p^{*,\hat{\lambda}}\circ\Phi^{\lambda})=\max_{(X,Y)\in
T_{all}}{\mathcal{R}}^{(X,Y)}(p^{*,\hat{\lambda}}\circ\Phi^{\hat{\lambda}})={\mathcal{R}}^{o.o.d.}(p^{*,\hat{\lambda}}\circ\Phi^{\hat{\lambda}}),$

which concludes the proof.

##  Appendix C Proof of Theorem 3.3

######  Theorem C.1.

Notations are same as in the statement of Theorem B.1. Define
${\mathcal{R}}^{II}(\lambda)$ by

$\displaystyle{\mathcal{R}}^{II}(\lambda):=\max_{(X,Y)\in
T_{ad}\cup\\{(X^{*},Y^{*})\\}}\Biggl{\\{}{\mathcal{R}}^{(X,g(Y))}(p^{*,\lambda}\circ\Phi^{\lambda})+\sum_{z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}\in{\mathcal{Z}}^{\cancel{\hookrightarrow}}}\Bigl{\\{}P(g(Y)=z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\cdot\int-\log
p^{*,\lambda}(Y^{*}|X^{*,{\lambda}},Y^{*}\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}))dP_{(X^{*},Y^{*})|Y^{*}\in
g^{-1}(^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})}\Bigl{\\}}\Biggl{\\}}.$

In addition to the condition (I), the following condition (II)’ hold:

  * (II)’

For a sufficiently small ${\varepsilon}\ll 1$, the following statement holds:
$\forall\lambda\in\Lambda$ with $\mathrm{Im}\Phi^{\lambda}_{2}\neq\emptyset$,
there exists $(X^{e_{\lambda}},Y^{e_{\lambda}})$ such that
$P(g(Y^{*})|X^{*,\lambda})\leq e^{-\beta_{\lambda}}-{\varepsilon}$ holds
$P_{X^{e_{\lambda}},Y^{e_{\lambda}}}$-almost everywhere. Here,

$\displaystyle\beta_{\lambda}:=H(Y^{*}|X_{1}^{*})-\sum_{z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}\in{\mathcal{Z}}^{\cancel{\hookrightarrow}}}\Bigl{\\{}P(g(Y^{*})=z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})\cdot\int-\log
p^{*,\lambda}(Y^{*}|X^{*,\lambda},Y^{*}\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}))dP_{(X^{*},Y^{*})|Y^{*}\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})}\Bigl{\\}}.$

Then, $\mathop{\rm
argmin}\limits_{\lambda\in\Lambda}{\mathcal{R}}^{II}(\lambda)\subset\mathop{\rm
argmin}\limits_{\lambda\in\Lambda}{\mathcal{R}}^{o.o.d.}(\lambda)$.

######  Lemma C.2.

Assume that $\hat{\lambda}\in\mathop{\rm
argmin}\limits_{\lambda\in\Lambda}{\mathcal{R}}^{II}(\lambda)$. Then
$\mathrm{Im}\Phi_{2}^{\hat{\lambda}}=\emptyset$.

######  Lemma C.3.

If $\hat{\lambda}\in\Lambda$ satisfies
$\mathrm{Im}\Phi_{2}^{\hat{\lambda}}=\emptyset$,
${\mathcal{R}}^{II}(\hat{\lambda})={\mathcal{R}}^{o.o.d.}(\hat{\lambda})$.

proof of Theorem C.1
Combining the above two lemmas and Lemma B.2, we can show the desired
statement essentially the same as the one in the proof of Theorem C.1.
proof of Lemma C.2.
Let us prove the contraposition of Lemma B.3. Take $\hat{\lambda}\in\Lambda$
with $\mathrm{Im}\Phi_{2}^{\hat{\lambda}}\neq\emptyset$. To prove that
$\hat{\lambda}\notin\mathop{\rm argmin}\limits{\mathcal{R}}^{II}(\lambda)$, we
may prove that
${\mathcal{R}}^{II}(\hat{\lambda})>{\mathcal{R}}^{II}(\lambda^{I})$ since
$\lambda^{I}\in\Lambda$ (Assumption (I) in the statement). To show this, it
suffices to prove the following statement:

$\displaystyle\exists(\bar{X},\bar{Y})\in T_{ad}~{}~{}s.t.$
$\displaystyle\int-\log
p^{*,\hat{\lambda}}(g(\bar{Y})|\bar{X}^{\hat{\lambda}})dP_{\bar{X},g(\bar{Y})}+\sum_{z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}\in{\mathcal{Z}}^{\cancel{\hookrightarrow}}}P(g(\bar{Y})=z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})\cdot\int-\log
p^{*,\hat{\lambda}}(Y^{*}|$ $\displaystyle X^{*,\hat{\lambda}},Y^{*}\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}))$ $\displaystyle
dP_{(X^{*},Y^{*})|Y^{*}\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})}$
$\displaystyle>{\mathcal{R}}^{II}(\lambda^{I}).$ (15)

Take $(X^{e_{\hat{\lambda}}},Y^{e_{\hat{\lambda}}})\in T_{ad}$ such that the
following statement holds:

$P(g(Y^{*})|X^{*,\hat{\lambda}})\leq e^{-\beta_{\hat{\lambda}}}-{\varepsilon}$
holds $P_{X^{e_{\hat{\lambda}}},Y^{e_{\hat{\lambda}}}}$-almost everywhere.

Before proving (15), we prepare one supplementary inequality:
Supplementary Inequality

$\int-\log
p^{*,\hat{\lambda}}(g(Y^{e_{\hat{\lambda}}})|X^{e_{\hat{\lambda}},\hat{\lambda}})dP_{X^{e_{\hat{\lambda}}},g(Y^{e_{\hat{\lambda}}})}\geq-\log\left\\{{e^{-\beta_{\hat{\lambda}}}-\epsilon}\right\\}.$

We can prove the inequality same as in the proof of Lemma B.3, and therefore,
omit the proof.
Proof of Inequality (15).

$\displaystyle\int-\log
p^{*,\hat{\lambda}}(g(Y^{e_{\hat{\lambda}}})|X^{e_{\hat{\lambda}},\hat{\lambda}})dP_{X^{e_{\hat{\lambda}}},g(Y^{e_{\hat{\lambda}}})}+\sum_{z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}\in{\mathcal{Z}}^{\cancel{\hookrightarrow}}}P(g({Y^{e_{\hat{\lambda}}}})=z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})\cdot\int-\log
p^{*,\hat{\lambda}}(Y^{*}|X^{*,\hat{\lambda}},Y^{*}\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}))dP_{(X^{*},Y^{*})|Y^{*}\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})}$
$\displaystyle\geq-\log\left\\{{e^{-\beta_{\hat{\lambda}}}-\epsilon}\right\\}+\sum_{z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}\in{\mathcal{Z}}^{\cancel{\hookrightarrow}}}P(g({Y^{e_{\hat{\lambda}}}})=z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})\cdot\int-\log
p^{*,\hat{\lambda}}(Y^{*}|X^{*,\hat{\lambda}},Y^{*}\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}))dP_{(X^{*},Y^{*})|Y^{*}\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})}$
$\displaystyle>-\log\left\\{{e^{-\beta_{\hat{\lambda}}}}\right\\}+\sum_{z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}\in{\mathcal{Z}}^{\cancel{\hookrightarrow}}}P(g({Y^{e_{\hat{\lambda}}}})=z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})\cdot\int-\log
p^{*,\hat{\lambda}}(Y^{*}|X^{*,\hat{\lambda}},Y^{*}\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}))dP_{(X^{*},Y^{*})|Y^{*}\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})}$
$\displaystyle=\beta_{\hat{\lambda}}+\sum_{z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}\in{\mathcal{Z}}^{\cancel{\hookrightarrow}}}P(g({Y^{e_{\hat{\lambda}}}})=z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})\cdot\int-\log
p^{*,\hat{\lambda}}(Y^{*}|X^{*,\hat{\lambda}},Y^{*}\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}))dP_{(X^{*},Y^{*})|Y^{*}\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})}$
$\displaystyle=H(Y^{*}|X_{1}^{*})-\sum_{z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}\in{\mathcal{Z}}^{\cancel{\hookrightarrow}}}\left\\{P(g(Y^{*})=z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})\cdot\int\log
p^{*,\hat{\lambda}}(Y^{*}|X^{*,\hat{\lambda}},Y^{*}\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}))dP_{(X^{*},Y^{*})|Y^{*}\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})}\right\\}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}^{+}\sum_{z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}\in{\mathcal{Z}}^{\cancel{\hookrightarrow}}}P(g({Y^{e_{\hat{\lambda}}}})=z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})\cdot\int-\log
p^{*,\hat{\lambda}}(Y^{*}|X^{*,\hat{\lambda}},Y^{*}\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}))dP_{(X^{*},Y^{*})|Y^{*}\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})}.$ (16)

Since
$P_{X_{1}^{e_{\hat{\lambda}}},g(Y^{e_{\hat{\lambda}}})}=P_{X_{1}^{*},g(Y^{*})}$($=P_{X_{1}^{I},g(Y^{I})}$)
holds by the construction of $T_{all}$, we can see that
$P(g(Y^{e_{\hat{\lambda}}})=z)=P(g(Y^{*})=z)$ for any $z\in{\mathcal{Z}}$.
Therefore, we obtain

$\displaystyle-\sum_{z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}\in{\mathcal{Z}}^{\cancel{\hookrightarrow}}}\left\\{P(g(Y^{*})=z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})\cdot\int\log
p^{*,\hat{\lambda}}(Y^{*}|X^{*,\hat{\lambda}},Y^{*}\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}))dP_{(X^{*},Y^{*})|Y^{*}\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})}\right\\}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}^{+}\sum_{z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}\in{\mathcal{Z}}^{\cancel{\hookrightarrow}}}P(g({Y^{e_{\hat{\lambda}}}})=z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})\cdot\int-\log
p^{*,\hat{\lambda}}(Y^{*}|X^{*,\hat{\lambda}},Y^{*}\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}))dP_{(X^{*},Y^{*})|Y^{*}\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})}=0.$

Hence, we can conclude (16) $=H(Y^{*}|X_{1}^{*})$. Moreover,
$H(Y^{*}|X_{1}^{*})={\mathcal{R}}^{o.o.d.}(\lambda^{I})$; indeed,

$\displaystyle{\mathcal{R}}^{o.o.d.}(\lambda^{I})$
$\displaystyle=\max_{(X,Y)\in_{all}}{\mathcal{R}}^{(X,Y)}(p^{*,\lambda^{I}}\circ\Phi^{\lambda^{I}})=\max_{(X,Y)\in
T_{all}}\int-\log p^{*,\lambda^{I}}(Y|\Phi^{\lambda^{I}}(X))dP_{X,Y}$
$\displaystyle=\max_{(X,Y)\in T_{all}}\int-\log
p^{*,\lambda^{I}}(Y|\Phi^{\lambda^{I}}(X))dP_{\Phi^{\lambda^{I}}(X),Y}$
$\displaystyle=\max_{(X,Y)\in T_{all}}\int-\log
p^{*,\lambda^{I}}(Y|X_{1})dP_{X_{1},Y}$ (17)

Noting that $P_{X_{1},Y}=P_{X_{1}^{*},Y^{*}}(=P_{X_{1}^{I},Y^{I}})$ for any
$(X,Y)\in T_{all}$ and $p^{*,\lambda^{I}}$ coincides with the conditional
probability density function of $P_{Y^{*}|X_{1}^{*}}$, we can see that

$\mathrm{(\ref{eq:Lem:min is no II:3_2 })}=\int-\log
p^{*,\lambda^{I}}(Y^{*}|X_{1}^{*})dP_{X_{1}^{*},Y^{*}}=H(Y^{*}|X_{1}^{*}).$

Hence, we can derive (16)
$=H(Y^{*}|X_{1}^{*})={\mathcal{R}}^{o.o.d.}(\lambda^{I})$, which concludes the
proof. $\Box$
proof of Lemma C.3.
Take $\hat{\lambda}\in\Lambda$ which satisfies
$\mathrm{Im}\Phi_{2}^{\hat{\lambda}}=\emptyset$. Since
$\mathrm{Im}\Phi_{2}^{\hat{\lambda}}=\emptyset$,
$P_{\Phi(X^{\hat{\lambda}}),Y}=P_{\Phi(X^{*,\hat{\lambda}}),Y^{*}}$ holds for
$\forall(X,Y)\in T_{all}$ because of the construction of $T_{all}$. Therefore,

$\displaystyle{\mathcal{R}}^{o.o.d.}(\hat{\lambda})$
$\displaystyle:=\max_{(X,Y)\in
T_{all}}{\mathcal{R}}^{(X,Y)}(p^{*,\hat{\lambda}}\circ\Phi^{\hat{\lambda}})=\max_{(X,Y)\in
T_{ad}\cup\\{(X^{*},Y^{*})\\}}{\mathcal{R}}^{(X,Y)}(p^{*,\hat{\lambda}}\circ\Phi^{\hat{\lambda}})$
$\displaystyle=\max_{(X,Y)\in
T_{ad}\cup\\{(X^{*},Y^{*})\\}}\Biggl{\\{}{\mathcal{R}}^{(X,g(Y))}(p^{*,\hat{\lambda}}\circ\Phi^{\hat{\lambda}})+\sum_{z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}\in{\mathcal{Z}}^{\cancel{\hookrightarrow}}}\left\\{P(g(Y)=z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})\int-\log
p^{*,\hat{\lambda}}(Y|X^{{\hat{\lambda}}},Y\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}))dP_{(X,Y)|Y\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})}\right\\}\Biggl{\\}}$
$\displaystyle=\max_{(X,Y)\in
T_{ad}\cup\\{(X^{*},Y^{*})\\}}\Biggl{\\{}{\mathcal{R}}^{(X,g(Y))}(p^{*,\hat{\lambda}}\circ\Phi^{\hat{\lambda}})+\sum_{z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}\in{\mathcal{Z}}^{\cancel{\hookrightarrow}}}\left\\{P(g(Y)=z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})\int-\log
p^{*,\hat{\lambda}}(Y^{*}|X^{*,{\hat{\lambda}}},Y^{*}\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}}))dP_{(X^{*},Y^{*})|Y^{*}\in
g^{-1}(z^{\scalebox{0.5}{$\cancel{\hookrightarrow}$}})}\right\\}\Biggl{\\}}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}={\mathcal{R}}^{II}(\hat{\lambda})$

and therefore, it concludes the proof. Here, the third equality holds by
Theorem 3.1; the first and forth equalities hold because of the fact that
$P_{\Phi(X^{\hat{\lambda}}),Y}=P_{\Phi(X^{*,\hat{\lambda}}),Y^{*}}$ holds for
$\forall(X,Y)\in T_{all}$.

##  Appendix D Sufficient Conditions of $e^{*}$ for there to exist
$(X^{e_{\lambda}},Y^{e_{\lambda}})$ which satisfies (d) and (d)’

######  Theorem D.1.

Notations are same as in Theorem B.1 and C.1. $(X^{*},Y^{*})$ satisfies the
following condition:

  * (A)

For a sufficiently small ${\varepsilon}\ll 1$, the following statement holds:
$\forall\lambda$ with $\mathrm{Im}\Phi^{\lambda}_{2}\neq\emptyset$,
$\forall{\alpha}\in\mathrm{Im}\Phi^{\lambda}_{1}$, $\forall
b\in{\mathcal{Y}}$, $\exists c(\lambda,a,b)$444$c(\lambda,a,b)$ means
$c\in{\mathcal{X}}_{2}$ is determined by given $\lambda\in\Lambda$,
$a\in{\mathcal{X}}_{1}$, $b\in{\mathcal{Y}}$. s.t.
$P(Y^{*}=b|X_{1}^{*,\lambda}=a,X_{2}^{*,\lambda}=c)\geq(1-e^{-\beta})+{\varepsilon}$.

Then, $\forall\lambda$ with $\mathrm{Im}\Phi^{\lambda}_{2}\neq\emptyset$,
there exists $(X^{e_{\lambda}},Y^{e_{\lambda}})\in T_{all}$ such that the
inequality in (d) holds.

Remark. The condition (A) means that, in the environment $e=e^{*}$, the
affection of environmental factors ($={\mathcal{X}}_{2}$) to the response
variable $Y^{e^{*}}$ is large; indeed, the inequality in (A) means that, if
$\lambda$ fails to remove environment factors ($i.e.$,
$\mathrm{Im}\Phi^{\lambda}_{2}\neq\emptyset$), we can control the probability
of $Y^{e^{*}}=b$ by the selection $c$ for any $b\in{\mathcal{Y}}$.

###### Proof.

Fix $\forall\lambda$ with $\mathrm{Im}\Phi^{\lambda}_{2}\neq\emptyset$. Take
$(\bar{X},\bar{Y})\in T_{all}$ such that its probability measure corresponds
to $\bar{P}_{X_{2}|Y,X_{1}}\times P_{Y^{I},X_{1}^{I}},$ where
$\bar{P}_{X_{2}|Y,X_{1}}$ is defined by, setting $\hat{c}(\hat{\lambda},a,b)$
by

$\hat{c}(\hat{\lambda},a,b)\in\mathop{\rm
argmin}\limits_{c\in{\mathcal{X}}_{2}}P(g(Y^{*})=g(b)|X^{*,\hat{\lambda}}_{1}=\Phi_{1}^{\hat{\lambda}}(a),X^{*,\hat{\lambda}}_{2}=\Phi_{2}^{\hat{\lambda}}(c)),$

$\bar{P}_{X_{2}|Y=b,X_{1}=a}:=\delta_{X_{2}=\hat{c}(\hat{\lambda},a,b)}.$
Here, for $c\in{\mathcal{X}}_{2}$, the probability measure $\delta_{X_{2}=c}$
on ${\mathcal{X}}_{2}$ denotes a Dirac measure at $c\in{\mathcal{X}}_{2}$.

Before proving Theorem D.1, we prepare the following inequalities:
Supplementary Inequality 1.

$\forall a\in{\mathcal{X}}_{1},\forall
b\in{\mathcal{Y}},P\left(g(Y^{*})=g(b)\left|X^{*,\hat{\lambda}}_{1}=\Phi_{1}^{\hat{\lambda}}(a),X^{*,\hat{\lambda}}_{2}=\Phi_{2}^{\hat{\lambda}}\bigl{(}\hat{c}(\hat{\lambda},a,b)\bigr{)}\right.\right)\leq{e^{-\beta}-\epsilon}.$

To see the fact, take $b^{*}\in{\mathcal{Y}}$ such that $g(b^{*})\neq
g(b)$555Such $b^{*}$ always exists by the following reason. Since
$|{\mathcal{Z}}|\geq 2$ (which is imposed on in Chapter 2.1 ), we can take
${\mathcal{Z}}\ni z^{*}\neq g(b)$. By the surjectivity of $g$,
$g^{-1}(z^{*})\neq\emptyset$. Taking $b^{*}\in g^{-1}(z^{*})$,
$g(b^{*})=z^{*}\neq g(b)$.. Then, by the condition (ii) of Theorem 3.3 and
$\mathrm{Im}\Phi_{2}^{\hat{\lambda}}\neq\emptyset$, there exists
$c(\hat{\lambda},a,b)\in{\mathcal{X}}_{2}$ such that

$P\left(Y^{*}=b^{*}\left|X^{*,\hat{\lambda}}_{1}=\Phi_{1}^{\hat{\lambda}}(a),X^{*,\hat{\lambda}}_{2}=\Phi_{2}^{\hat{\lambda}}\bigl{(}c(\hat{\lambda},a,b)\bigr{)}\right.\right)\geq{1-e^{-\beta}+\epsilon}.$

Therefore,

$\displaystyle
P\left(g(Y^{*})=g(b)\left|X^{*,\hat{\lambda}}_{1}=\Phi_{1}^{\hat{\lambda}}(a),X^{*,\hat{\lambda}}_{2}=\Phi_{2}^{\hat{\lambda}}\bigl{(}\hat{c}(\hat{\lambda},a,b)\bigr{)}\right.\right)$
$\displaystyle=\min_{c\in{\mathcal{X}}_{2}}P(g(Y^{*})=g(b)|X^{*,\hat{\lambda}}_{1}=\Phi_{1}^{\hat{\lambda}}(a),X^{*,\hat{\lambda}}_{2}=\Phi_{2}^{\hat{\lambda}}(c))$
$\displaystyle\leq
P\left(g(Y^{*})=g(b)\left|X^{*,\hat{\lambda}}_{1}=\Phi_{1}^{\hat{\lambda}}(a),X^{*,\hat{\lambda}}_{2}=\Phi_{2}^{\hat{\lambda}}\bigl{(}c(\hat{\lambda},a,b)\bigr{)}\right.\right)$
$\displaystyle=1-\sum_{\bar{z}\neq
g(b)}P\left(g(Y^{*})=\bar{z}\left|X^{*,\hat{\lambda}}_{1}=\Phi_{1}^{\hat{\lambda}}(a),X^{*,\hat{\lambda}}_{2}=\Phi_{2}^{\hat{\lambda}}\bigl{(}c(\hat{\lambda},a,b)\bigr{)}\right.\right)$
$\displaystyle\leq
1-P\left(g(Y^{*})=g(b^{*})\left|X^{*,\hat{\lambda}}_{1}=\Phi_{1}^{\hat{\lambda}}(a),X^{*,\hat{\lambda}}_{2}=\Phi_{2}^{\hat{\lambda}}\bigl{(}c(\hat{\lambda},a,b)\bigr{)}\right.\right)$
$\displaystyle\leq
1-P\left(Y^{*}=b^{*}\left|X^{*,\hat{\lambda}}_{1}=\Phi_{1}^{\hat{\lambda}}(a),X^{*,\hat{\lambda}}_{2}=\Phi_{2}^{\hat{\lambda}}\bigl{(}c(\hat{\lambda},a,b)\bigr{)}\right.\right).$
$\displaystyle\leq 1-(1-e^{-\beta}+\epsilon)$
$\displaystyle\leq{e^{-\beta}-\epsilon}.$

Proof of Theorem D.1
We may prove that $P_{\bar{X},\bar{Y}}(A)=1$ where

$\Biggl{\\{}(x,y)\in{\mathcal{X}}\times{\mathcal{Y}}\Biggr{|}P\left(g(Y^{*})=g(b)\left|X^{*,\hat{\lambda}}=\Phi^{\hat{\lambda}}(x)\right)\leq{e^{-\beta}-\epsilon}\right.\Biggr{\\}}.$

Then,

$\displaystyle P_{\bar{X},\bar{Y}}(A)$ $\displaystyle=\int
1_{A}dP_{\bar{X},\bar{Y}}=\int 1_{A}d(\bar{P}_{X_{2}|Y,X_{1}}\times
P_{Y^{I},X_{1}^{I}})$ $\displaystyle=\int dP_{Y^{I},X_{1}^{I}}\int
1_{A}d\bar{P}_{X_{2}|Y,X_{1}}=\int
dP_{Y^{I},X_{1}^{I}}(x_{1},y)\delta_{X_{2}=\hat{c}(\hat{\lambda},x_{1},y)}(A_{(x_{1},y)})$

holds where
$A_{(x_{1},y)}:=\left\\{x_{2}\in{\mathcal{X}}_{2}|((x_{1},x_{2}),y)\in{\mathcal{X}}\times{\mathcal{Y}}\right\\}$.
By the Supplementary Inequality 1, $\hat{c}(\hat{\lambda},x_{1},y)\in
A_{(x_{1},y)}$ holds and therefore,
$\delta_{X_{2}=\hat{c}(\hat{\lambda},x_{1},y)}(A_{(x_{1},y)})=1$, which leads
us to the equation

$\int
dP_{Y^{I},X_{1}^{I}}(x_{1},y)\delta_{X_{2}=\hat{c}(\hat{\lambda},x_{1},y)}(A_{(x_{1},y)})=1$

.

∎

######  Theorem D.2.

Notations are same as in Theorem B.1 and C.1. $(X^{*},Y^{*})$ satisfies the
following condition:

  * (A)’

For a sufficiently small ${\varepsilon}\ll 1$, the following statement holds:
$\forall\lambda$ with $\mathrm{Im}\Phi^{\lambda}_{2}\neq\emptyset$,
$\forall{\alpha}\in\mathrm{Im}\Phi^{\lambda}_{1}$, $\forall
b\in{\mathcal{Y}}$, $\exists c(\lambda,a,b)$ s.t.
$P(Y^{*}=b|X_{1}^{*,\lambda}=a,X_{2}^{*,\lambda}=c)\geq(1-e^{-\beta_{\lambda}})+{\varepsilon}$.

Then, $\forall\lambda$ with $\mathrm{Im}\Phi^{\lambda}_{2}\neq\emptyset$,
there exists $(X^{e_{\lambda}},Y^{e_{\lambda}})\in T_{all}$ such that the
inequality in (d)’ holds.

The proof of Theorem D.2 is essentially same as the one of Theorem D.1 and
therefore, we omit.

##  Appendix E Additional Experiment explanations

###  E.1 Visualizations of Experiment Results

Synthesized data of first experiment is visualized as in Figure 2. Synthesized
data of second experiment is visualized as in Figure 3.

###  E.2 Explicit representation of Second Synthetic data

$\displaystyle N_{1}$
$\displaystyle={\mathcal{N}}(-180,20^{2})\times{\mathcal{N}}(-5e,30^{2}),$
$\displaystyle N_{2}$
$\displaystyle={\mathcal{N}}(-100,20^{2})\times{\mathcal{N}}(-3e,30^{2}),$
$\displaystyle N_{3}$
$\displaystyle={\mathcal{N}}(-20,20^{2})\times{\mathcal{N}}(-1e,30^{2}),$
$\displaystyle N_{4}$
$\displaystyle={\mathcal{N}}(60,20^{2})\times{\mathcal{N}}(-2e,30^{2}),$
$\displaystyle N_{5}$
$\displaystyle={\mathcal{N}}(140,20^{2})\times{\mathcal{N}}(-4e,30^{2}),$
$\displaystyle N_{6}$
$\displaystyle={\mathcal{N}}(-140,20^{2})\times{\mathcal{N}}(4e,30^{2}),$
$\displaystyle N_{7}$
$\displaystyle={\mathcal{N}}(-60,20^{2})\times{\mathcal{N}}(2e,30^{2}),$
$\displaystyle N_{8}$
$\displaystyle={\mathcal{N}}(20,20^{2})\times{\mathcal{N}}(1e,30^{2}),$
$\displaystyle N_{9}$
$\displaystyle={\mathcal{N}}(100,20^{2})\times{\mathcal{N}}(3e,30^{2}),$
$\displaystyle N_{10}$
$\displaystyle={\mathcal{N}}(180,20^{2})\times{\mathcal{N}}(5e,30^{2}).$

Fig 2: Visualization of Synthesized Data 1. Left and middle figures illustrate
training and test data on $e^{*}=5$ and $50$, respectively. As $e^{*}$
increases, the test data and train data are more different, and therefore ERM
yields lower performance. Right figure illustrates ${\mathcal{D}}_{ad}^{e}$.

---

Fig 3: Visualization of Synthesized Data 2. Left figure illustrates the
training and test data of second experiment. Right figure illustrates
${\mathcal{D}}_{ad}^{40}$ and ${\mathcal{D}}_{ad}^{e_{ad}}$ with $e_{ad}=-9$.

---

Table 6: Test Acc. of Hierarchical Colored MNIST (5runs)

flip rate | Test Acc. on | Best passible | Oracle | ERM | FT | FE | DSAN | Ours + CVI | Ours + CVII | Ours+ TDV
---|---|---|---|---|---|---|---|---|---|---
0.25 | $e=0.1$ | .750 | .729 (.004) |  ..771 (.001) |  .771 (.001) |  ..771 (.001) | .767 (.004) | .727 (.004) | .714 (.013) | .673 (.006)
| $e=0.9$ | .125 (.003) | .128 (.002) | $.131(.002)$ | .085 (.003) | .622 (.015) | .644 (.019) | .690 (.009)
0.20 | $e=0.1$ | .800 | .780 (.002) | .796 (.000) |  .800 (.001) | .796 (.001) | .789 (.004) | .773 (.003) | .745 (.008) | .738 (.018)
| $e=0.9$ | .177 (.006) | .201 (.004) | $.200(.007)$ | .091 (.005) | .644 (.011) | .707 (.012) | .732 (.008)
0.15 | $e=0.1$ | .850 | .828 (.004) | .822 (.000) | .823 (.001) | .824 (.002) | .815 (.002) | .814 (.007) | .797 (.011) | .822 (.001)
| $e=0.9$ | .277 (.007) | .323 (.006) | $.312(.012)$ | .091 (.002) | .724 (.037) | .743 (.020) | .782 (.012)
0.10 | $e=0.1$ | .900 | .880 (.004) | .852 (.002) | .855(.001) |  . .856 (.001) | .833(.003) | .848 (.005) | .848 (.005) | .857 (.005)
| $e=0.9$ | .468 (.002) | .497 (.005) | $.500(.007)$ | .106 (.010) | .792 (.005) | .792 (.005) | .829 (.005)

###  E.3 Additional Experiment of Hierarchical Colored MNIST

Although Hierarchical Colored MNIST in Chapter 6 fix its flip rate $20\%$, we
additionally demonstrate by changing its flip rate among
$\\{0.1,0.15,0.2,0.25\\}$. Table 6 shows that our methods outperform other
methods. Table 6 and 7 show that, among several CV methods, our method II
outperform other methods. Table 8 the difference between accuracies by TDV and
each CV for the same data set with $e=0.9$. The result verify that CVII
selects preferable hyperparameters with smaller errors.

Table 7: Baselines of CV methods | Tr-CV | LOD-CV
---|---|---
0.25 | .759 (.008) | .362 (.059)
.459 (.012) | .372 (.037)
0.20 | .794 (.004) | .338 (.048)
.541 (.007) | .334 (.029)
0.15 | .834 (.002) | .348 (.031)
.634 (.008) | .358 (.024)
0.10 | .876 (.003) | .502 (.196)
.708 (.006) | .497 (.194)
Table 8: Means and SEs of $\\{$(Accuracy of TDV on $e=0.9$) -(Accuracy of Each
CV on $e=0.9$) $\\}$ (5runs).

| CV I | CV II | Tr-CV | LOD-CV
---|---|---|---|---
0.25 | .068 (.007) | .046 (.023) | .231 (.013) | .319 (.033)
0.20 | .088 (.004) | .025 (.006) | .191 (.014) | .398 (.025)
0.15 | .059 (.038) | .039 (.022) | .148 (.019) | .430 (.028)
0.10 | .037 (.010) | .037 (.010) | .121 (.008) | .332 (.196)

###  E.4 Experiment Details

Through the experiment in the present paper, all models of competitors are
composed of neural networks where its loss function, activation function, and
optimizer are cross entropy, Relu Networks and Adam [53]. In the following
explanation, NN with its model architecture $a\rightarrow
h_{1}\rightarrow\cdots h_{k}\rightarrow h_{n}\rightarrow{\mathcal{P}}_{[m]}$
means that its input and hidden dimensions are $a$ and $(h_{1},...,h_{)}$
respectively, and its output is probability density functions on $[m]$. NN
with its model architecture $a\rightarrow h_{1}\rightarrow\cdots
h_{k}\rightarrow h_{n}\rightarrow b$ means that its input, hidden and output
dimensions are $a$, $(h_{1},...,h_{n})$ and $b$ respectively. All the
experiment, we add $L^{2}$-reguralized term to our objective function.

We add explanations of previous CV methods. Tr-CV implements cross-validation
with using only ${\mathcal{D}}^{*}$. In LOD-CV, a model is learnt with
excluding one of the ${\mathcal{D}}^{e}\in{\mathcal{D}}^{ad}$ from
${\mathcal{D}}^{ad}$, and evaluate its performance by ${\mathcal{D}}^{e}$.
Changing the role of $e\in{\mathcal{E}}^{ad}$, and taking their mean, we
evaluate final CV-value.

####  E.4.1 Synthesized Data I

We set model architecture of $\Phi$ used in our method $2\rightarrow
20\rightarrow 20\rightarrow 1$. We set model architecture of CB-ERM and ERM
$2\rightarrow 20\rightarrow 20\rightarrow{\mathcal{P}}_{[3]}$. When we use FT
and FE, its model architecture on pre-train phase and retraining phase are
$2\rightarrow 20\rightarrow 20\rightarrow{\mathcal{P}}_{[2]}$ and
$2\rightarrow 20\rightarrow 20\rightarrow{\mathcal{P}}_{[3]}$ respectively. We
set running rate and hyperparameters of $L^{2}$-regularized term $0.0115$ and
$0.01$ respectively. When we use $DSAN$ [31], we inherit learning condition in
the Amazon Review dataset experiment. When training, we use batch learning. We
set $K=10$ of each CV method.

####  E.4.2 Synthesized Data II

We set model architecture of $\Phi$ used in our method $2\rightarrow
8\rightarrow 8\rightarrow 1$. We set running rate and hyperparameters of
$L^{2}$-regularized term $0.05$ and $0.001$ respectively. When training, we
use minibatch learning with dividing ${\mathcal{D}}^{*}$,
${\mathcal{D}}^{e^{ad}}$ and ${\mathcal{D}}^{40}$ into 50 equal parts
respectively. We set $K=10$ of each CV method.

####  E.4.3 Hierarchical Colored MNIST

We set model architecture of $\Phi$ used in our method $2\rightarrow
440\rightarrow 440\rightarrow 440$. We set model architecture of CB-ERM and
ERM $2\rightarrow 440\rightarrow 440\rightarrow{\mathcal{P}}_{[3]}$. When we
use FT and FE, its model architecture on pre-train phase and retraining phase
are $2\rightarrow 440\rightarrow 440\rightarrow{\mathcal{P}}_{[2]}$ and
$2\rightarrow 440\rightarrow 440\rightarrow{\mathcal{P}}_{[3]}$ respectively.
We set running rate and hyperparameter of $L^{2}$-regularized term $0.0004$
and $0.002$ respectively. When we use $DSAN$, we inherit learning condition in
the Amazon Review dataset experiment. When training, we use batch learning. We
set $K=10$ of our CV method.

####  E.4.4 Birds recognition

We set model architecture of $\Phi$ used in our method ResNet50 [29] with
changing its output dimension $256$. We set model architecture of CB-ERM and
ERM ResNet50 [29] with changing its output ${\mathcal{P}}_{[3]}$. When we use
FT and FE, its model architecture on pre-train phase and retraining phase are
ResNet50 [29] with changing its output dimension $2$ and $3$ respectively. We
set running rate and hyperparameter of $L^{2}$-regularized term $0.00004$ and
$0.001$ respectively. When training, we use minibatch learning with its
minibatch size $56$. We set $K=5$ of each CV method.