Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Let $\chi$ be an instance space and $H \in \{0, 1\}^\chi$ a class with finite VC-dimension. For each $x \in X$ we consider $z_x\colon H \rightarrow \{0, 1\}$ s.t. $z_x(h) = h(x), \forall h \in H$.
Let $Z = \{z_x:H\rightarrow\{0,1\}\mid x\in\chi\}$. Is $\mathit{VCdim}(Z)<2^{\mathit{VCdim}(H)+1}$?
The only thing that comes to mind when seeing this is the Sauer lemma, but that's related to the growth function and I don't see how to apply it here. Anyone got any idea on how to approach this?
This is a classical result of Assouad (Densité et dimension) about dual VC dimension.
Let $A$ be a binary matrix. The VC dimension of $A$ is the maximal size of a set $S$ of columns which are shattered, that is, all possible rows appear when we restrict $A$ to the columns in $S$. The dual VC dimension of $A$ is the VC dimension of $A^T$, the transpose of $A$.
Suppose that $A^T$ has VC dimension $2^{d+1}$. Then there is a set $S$ of $2^{d+1}$ rows of $A$ such that when we restrict $A$ to this set of rows, we see all possible columns. If we number the rows using binary numbers of length $d+1$, then in particular we see the following columns: for each $i$, there is a column which contains the $i$'th bit of the row index. For example, if $d=1$ then we see the following columns: $$ \begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{matrix} $$ Therefore the VC dimension of $A$ is at least $d+1$.
If we take $d = \mathrm{VC}(A)$, then we deduce $\mathrm{VC}(A^T) < 2^{\mathrm{VC}(A)+1}$.
