The VC dimension when the samples are fixed

Question

The VC dimension is usually used in the following way. There is a space of hypotheses. There is an unknown probability distribution. We sample some training-samples from this distribution. We find the hypothesis that scores best on the training-samples. If the VC dimension is sufficiently small and the number of samples is sufficiently large, then this best hypothesis will also perform probably-approximately-well on any set of test-samples drawn from the same distribution. Specifically, if the VC-dimension is $D$ and the number of samples is at least: $$ N := \Theta\bigg(\frac{D + \ln{1\over \delta}}{\epsilon}\bigg) $$ then, with probability at least $1-\delta$, the test-error will be at most $\epsilon$.

I am interested in the following alternative setting. Instead of a probability distribution, we have a ''fixed'' set of samples, determined by an adversary. We pick half of these samples at random, calculate the best hypothesis on this half, and then test it on the other half.

MY QUESTION IS: is it possible to use the VC dimension in the second setting? I.e, is there a formula, similar to the one above, that relates the total number of samples in the population, the probability of learning, and the learning error?

Answer 1

Suppose were in the realizable model, i.e. we want to learn some $f^*\in\mathcal{H}\subseteq 2^\mathcal{X}$ where $VCdim(\mathcal{H})=d$.

Let $M(\epsilon,\delta)$ be the minimal number of samples required to obtain an error of at most $\epsilon$ with probability at least $1-\delta$. Since the bound you mentioned on $M(\epsilon, \delta)$ holds for any distribution $\mathcal{D}$ over the sample space $\mathcal{X}$, we can treat this case as a uniform distribution with finite support $S=\left\{a_1,...,a_n\right\}$ (picked by the adversary). The learner picks a set $T\subseteq S$ of $n/2$ samples (chosen uniformly at random), and chooses any consistent hypothesis $h$ (relative to $T$).

There are two issues which prevent us from directly using the known bounds on $err(h)$.

The first is that we are only interested in the error on the set $S\setminus T$, i.e. the training and test samples are not independent. This will add an extra $2$ factor to the bounds on $err(h)$, since:

$err(h)=\Pr_{x\sim\mathcal{D}}\left(h(x)\neq f^*(x)\right)= \Pr\left(h(x)\neq f^*(x) | x\in T\right)\Pr(x\in T)+\Pr\left(h(x)\neq f^*(x) | x\notin T\right)\Pr(x\notin T)$.

In this case we have $\Pr(x\in T)=\Pr(x\notin T)=\frac{1}{2}$, and $\Pr\left(h(x)\neq f^*(x) | x\in T\right)=0$ ($h$ is consistent with $T$). So we get $err(h)=\frac{1}{2}\Pr\left(h(x)\neq f^*(x) | x\notin T\right)$, or equivalently $\Pr\left(h(x)\neq f^*(x) | x\notin T\right)=2err(h)$, where the left hand side is the probability that we wish to bound.

The second issue is caused by the fact that we don't allow repetitions while picking $T$ (the usual model treats each training sample as chosen independently from the distribution $\mathcal{D}$). To avoid this issue, the learner could choose $T$ by taking $m$ independent samples form $\mathcal{D}$, such that with high probability we see at least $\frac{|S|}{2}$ samples. This can be easily done by picking $m\approx |S|$, and conditioning on the event that we saw at least half of $S$, we can use the regular bounds on $err(h)$ for sample size $\ge|S|/2$.