1
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ Please don't delete your question after receiving an answer. Our mission here is not just to help the person who is asking, but also to build up an archive of high-quality questions and answers that will hopefully help others in the future as well. Answerers might be answering on this basis, so it is sometimes considered impolite to delete one's question after receiving an answer. $\endgroup$
    – D.W.
    Apr 1, 2021 at 3:58

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.