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

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.

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.