Let $\mathcal{X}$ be a finite domain and $k$ a number such that $k\leq|\mathcal{X}|$. Consider the hypothesis class


that is, the class of hypotheses $h:\mathcal{X}\to\{0,1\}$ that assign label $1$ to exactly $k$ elements of $\mathcal{X}$.

Question: What is the VC-dimension of $\mathcal{H}$?

(Note that this is Exercise 6.2 (1) in the book "Understanding Machine Learning: From Theory to Algorithms" from Shalev-Shwartz & Ben-David.)

The claim is that $\mathrm{VCdim}(\mathcal{H})=\min\{k,|\mathcal{X}|-k\}$. The solution that was provided to me proceeds as follows:

  1. Show that $\mathrm{VCdim}(\mathcal{H})\leq\min\{k,|\mathcal{X}|-k\}$.
  2. Show that $\mathrm{VCdim}(\mathcal{H})\geq\min\{k,|\mathcal{X}|-k\}$.

I'm already struggling with the first part. Let $C\subseteq\mathcal{X}$ be a set of size $k+1$. Then, $C$ is not shattered by $\mathcal{H}$ as there is no $h\in\mathcal{H}$ satisfying $h(\mathbf{x})=1$ for all $\mathbf{x}\in C$ $\Rightarrow\;\mathrm{VCdim}(\mathcal{H})\leq k$. On the other hand, if $C\subseteq\mathcal{X}$ is of size $|\mathcal{X}|-k+1$, then $C$ is not shattered by $\mathcal{H}$ as there is no $h\in\mathcal{H}$ satisfying $h(\mathbf{x})=0$ for all $\mathbf{x}\in C$. Hence, $\mathrm{VCdim}(\mathcal{H})\leq\min\{k,|\mathcal{X}|-k\}$.

I don't see why the second step in this line of reasoning is true. For example, consider some domain of cardinality $|\mathcal{X}|=4$ and let $k=3$. Then, $|\mathcal{X}|-k+1=2$. So when I pick any $2$ instances from $\mathcal{X}$ so that $C=\{\mathbf{x}_1,\mathbf{x}_2\}$, why is there no $h\in\mathcal{H}$ satisfying $h(\mathbf{x}_1)=h(\mathbf{x}_2)=0$? In my opinion, as $2<k=3$, this is actually the only possible labeling.

I am convinced the general claim is correct but I believe the proof of the upper bound in the form above is incomplete. Or did I completely misunderstand the problem setting?


1 Answer 1


In your example, there is no such $h$. Every $h$ assigns 1 to three elements of the four, so can only assign 0 to one element.

  • $\begingroup$ This is the obvious part to me. If $C\subseteq\mathcal{X}$ is of size $k+1$, then there must be at least one element that is labeled as 0 $\Rightarrow\,\mathrm{VCdim}(\mathcal{H})\leq k$. Next step is to show that also $\mathrm{VCdim}(\mathcal{H})\leq |\mathcal{X}|-k$. So in the proof that I found it is argued that if $C\subseteq\mathcal{X}$ is of size $|\mathcal{X}|-k+1$ that no $h\in\mathcal{H}$ exists that assigns label $0$ to every $\mathbf{x}\in C$. This is what my example is about. It shows there is such $h$ (maybe it is just a typo in the proof that I found, I don't know). $\endgroup$
    – VK88
    Jan 17, 2023 at 8:44
  • $\begingroup$ @VK88 my answer is addressing the $|\mathcal{X}|-k$ case. There is no such $h\in \mathcal{H}$. Perhaps being more concrete will help: in your example, you wanted $h(x_1)=h(x_2)=0$; what values do you propose for $h(x_3)$ and $h(x_4)$? Remember you had $|\mathcal{X}|=4$ and $k=3$. $\endgroup$
    – Ben Reiniger
    Jan 17, 2023 at 12:13
  • $\begingroup$ In case $|\mathcal{X}|=4$ and $k=3$, any set $C\subseteq\mathcal{X}$ of size $|\mathcal{X}|-k+1$ has only two elements $x_1$ and $x_2$. Hence, the labeling $h(x_1)=h(x_2)=1$ is not possible by any $h\in\mathcal{H}$, which is why $C$ is not shattered. But this is in contrast to the claim in the proof that I found that says there is no $h\in\mathcal{H}$ satisfying $h(x_1)=h(x_2)=0$. The latter is in my opinion the only labeling that is possible for this two element set. But maybe this is just a typo and they meant $=1$ instead $=0$. $\endgroup$
    – VK88
    Jan 17, 2023 at 20:22
  • $\begingroup$ @VK88 I think $h(x_1)=h(x_2)=1$ is possible, with $h(x_3)=1$ and $h(x_4)=0$. But $h(x_1)=h(x_2)=0$ is not possible. ? $\endgroup$
    – Ben Reiniger
    Jan 17, 2023 at 21:10
  • 1
    $\begingroup$ Oh, the penny has dropped! Of course, $h:\mathcal{X}\to\{0,1\}$ not $C\to\{0,1\}$. I've confused $\mathcal{H}$ with $\mathcal{H}_C$, where the latter is the restriction of $\mathcal{H}$ to $C$. The definition of shattering I'm aware of is "A class $\mathcal{H}$ shatters a finite set $C\subset\mathcal{X}$ if the restriction of $\mathcal{H}$ to $C$ is the set of all functions from $C$ to $\{0,1\}$ (book of Shalev-Schwartz & Ben-David). But the line of reasoning in my original post refers directly to $\mathcal{H}$ instead of $\mathcal{H}_C$. Thanks a lot for helping me out! $\endgroup$
    – VK88
    Jan 18, 2023 at 22:07

Your Answer

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

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