PAC learning: success of learning when receiving a sample from a different distribution

Question

I've come across this question and I think I'm on the right track with the idea I just don't really know how to formalize it properly or understand why everything said in the question is required for the proof. The question is as follows:

Let $\mathcal X$ be a finite example domain and let $\mathcal Y = \{0, 1\}$. Let $H ⊆ \mathcal Y^ \mathcal X$ be a finite hypothesis class. Let $\mathcal D$ be a distribution over $\mathcal X \times \mathcal Y$. Let $\mathcal G$ be a different distribution over $\mathcal X × \mathcal Y$, such that $G_{Y |X} = D_{Y |X}$. Suppose that an ERM algorithm $\mathcal A$ receives a sample from $\mathcal G$ instead of a sample from $ \mathcal D$, that is: $S \sim \mathcal G^m$. Prove that if $\mathcal D$ and $\mathcal G$ are realizable by $\mathcal H$, and $supp(\mathcal D_\mathcal X) ⊆ supp(\mathcal G_\mathcal X)$, then for every $\epsilon, \delta \in (0, 1)$, there exists a sample size $m$ (that can depend on $\mathcal D, \mathcal G, \mathcal H, \epsilon, \delta)$ such that $\mathbb P_{S\sim \mathcal G^m}[err(\mathcal A[S], \mathcal D) \geq \epsilon)] \leq \delta$.

My idea was that since the conditional distributions are equal and the realizability assumption holds it must be that the labeling function for each distribution, say f and g, are the same as well. Now since the support of D is contained in the support of G, any example that can be observed in the sample drawn from D can also be observed in a sample drawn from G, hence enough examples drawn from G will suffice to achieve a training set S that contains all of the support of D. However, I can't quite formalize this idea.

Thanks in advance!

Answer 1

Let $x_1,...,x_N$ denote the elements of $\mathcal{X}$ and consider the marginal distributions $D_\mathcal{X}=(p_1,...,p_N)$ and $G_\mathcal{X}=(q_1,...,q_N)$. Recall that $p_i>0$ implies that $q_i>0$, hence the ratio $R=\max_i\frac{p_i}{q_i}$ is well defined. Also denote the output of the algorithm on a sample set $S$ by $h_S$, then:

\begin{align*} err_G(h_S)&=\sum\limits_{i=1}^N q_i\Pr\limits_{(x,y)\sim G}[h_S(x_i)\neq y | x=x_i]=\sum\limits_{i=1}^N q_i\Pr\limits_{(x,y)\sim D}[h_S(x_i)\neq y | x=x_i]\\ &=R^{-1}\sum\limits_{i=1}^N q_iR\Pr\limits_{(x,y)\sim D}[h_S(x_i)\neq y | x=x_i]\ge R^{-1}\sum\limits_{i=1}^Np_i\Pr\limits_{(x,y)\sim D}[h_S(x_i)\neq y | x=x_i]\\ &=R^{-1}err_D(h_S) \end{align*}

Thus, to show $err_D(h_S)$ is small with high probability when given samples from $G$, it suffices to show that $err_G(h_S)$ is small and using the bound $err_D(h_S)\le R \cdot err_G(h_S)$ where $R$ is a constant depending on the distributions. This is the standard problem of showing that the ERM is able to learn a finite hypothesis class, so I leave the details to you.