The VC dimension when the samples are fixed

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?

• maybe i don't understand your setting, but we have (for finite VC dimension), a bound on the error in terms of the number of samples, which holds for any distribution $\mathcal{D}$. Isn't your case simply taking a distribution with finite support $S\subseteq \mathcal{X}$ (sample space), and asking what is the error when the number of samples is greater than $|S|/2$? Commented Jul 19, 2016 at 20:30
• @Ariel in the original setting, the training samples and the test samples are independent. In the halving procedure, the two halves are dependent. As an example, suppose there is a total of 1000 samples, one of the samples is X and the other 999 samples are Y. If you treat it as a finite support distribution, there is a chance of 0.001 that X will be in the train set and an independent chance of 0.001 that X will be in the test set, so there is positive chance to see X in both sets. In the halving procedure, there is 0 chance to see X twice. Commented Jul 20, 2016 at 13:34
• Suppose you're in the realizable model, i.e. you want to learn some $f^*\in \mathcal{H}\subseteq 2^\mathcal{X}$ where $VCdim(\mathcal{H})=d$. Let $T$ be your training set obtained in the halving procedure, then you wish to bound $\Pr\left(h(x)\neq f^*(x) | x\notin T\right)$, where $h$ is the hypothesis which minimizes the empirical error. But $\Pr\left(h(x)\neq f^*(x) | x\notin T\right) = 2\Pr_{x\sim \mathcal{D}}\left(h(x)\neq f^*(x)\right)=2err(h)$, so you can still use the usual bound (with the extra $2$ factor). Commented Jul 20, 2016 at 20:13
• @Ariel I did not understand the last inequality in your comment. Can you please expand? (maybe as an answer) Commented Jul 30, 2016 at 21:38

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$.

• Thank you! This answer may have interesting implications in computational economics and auction theory. If you are interested, you are welcome to contact me (see my profile). Commented Jul 31, 2016 at 16:09