First the basic definitions: Let $H$ be a family of sets, and let $P$ be a set of points. Then $H$ is said to shatter $P$ if $\{ h \cap P:~h \in H\}=2^P$, that is, if every subset of $P$ can be obtained by intersecting $P$ with an element of $H$. The Vapnik-Chervonenkis dimension of $H$ is the maximal cardinality of a point set $P$ that is shattered by $H$. See also https://en.wikipedia.org/wiki/VC_dimension.

Let $A$ be the family of axis-parallel boxes in the $d$-dimensional unit cube $[0,1]^d$ having one vertex at the origin. It is known that the VC dimension of $A$ is $d$. Let $B$ be the family of all axis-parallel boxes in $[0,1]^d$ (not necessarily anchored at the origin). The VC dimension of $B$ is known, it is $2d$.

Now the question: Let $C$ be the class of all axis-parallel boxes on the $d$-dimensional unit torus. You could also thing of $C$ as the class of all sets in $[0,1]^d$ which are the $d$-dimensional Cartesian product of elements of $D$, where $D$ is the collection of all subintervals and all complements of subintervals of $[0,1]^d$. Now, what is the VC dimension of $C$?

  • $\begingroup$ Do you have some bounds in general or for $d=2$? $\endgroup$ – domotorp Jan 29 '17 at 21:27
  • $\begingroup$ Well, obviously a lower bound is the dimension for "non-periodic" boxes (boxes contained in the proper cube, not in the torus), which is 2d. For an upper bound, I don't have any idea. Probably you could use the fact that a "periodic" box on the torus splits into $2^d$ "non-periodic" boxes, but I do not see how this should lead to a reasonable result. My guess would be that the solution could be something linear in $d$, maybe $4d$ or something similar. $\endgroup$ – Kurisuto Asutora Jan 31 '17 at 10:03

This answer doesn't provide the exact VC-dimension of $C$, but does provide an almost linear upper bound.

The observation that a periodic box is a union of at most $2^d$ boxes could be used get a bound of $(2d^2+o(d^2))2^d$ for the VC-dimension of non-periodic boxes (using the fact that boxes have VC-dimension $2d$). I will use a similar idea to obtain a much better bound (but still not linear in $d$, unfortunately).

Lemma. Suppose $H_1,\ldots,H_n$ are set systems on a set $X$, each of VC-dimension at most $k$. Suppose $H$ is one of the following two set systems:

  1. $H_1\vee\ldots\vee H_n:=\{S_1\cup\ldots\cup S_n:S_i\in H_i\}$, or
  2. $H_1\wedge\ldots\wedge H_n:=\{S_1\cap\ldots\cap S_n:S_i\in H_i\}$.

Then $H$ has VC-dimension at most $k(1+o(1))n\log_2(n)$ (where $o(1)$ depends only on $n$).

Proof. Let $\pi_i$ be the shatter function for $H_i$, i.e., $$ \pi_i(m)=\max\{|\{Y\cap S:S\in H_i\}|:Y\subseteq X,~|Y|=m\}. $$ Let $\pi$ be the shatter function for $H$. One can show $\pi(m)\leq\pi_1(m)\cdot\ldots\cdot\pi_n(m)$ for any $m$. By the Sauer-Shelah lemma, we have $\pi_i(m)\leq (em/k)^k$ for all $i$ and $m\geq k$. So $\pi(m)\leq (em/k)^{kn}$ for any $m\geq k$. In particular, if $m\geq k$ and $(em/k)^{kn}<2^m$, then $\pi(m)<2^m$, and so the VC-dimension of $H$ is less than $m$. So we just need to optimize $m$ satisfying these inequalities. The following works and is of the form stated in the lemma: $$ m:=kn\log_2(cn\log_2(cn)) $$ where $c=e+\log_2(e)$.

So if we use case $(1)$ and write a periodic box as a union of at most $2^d$ boxes, then we get $(2d^2+o(d^2))2^d$.

Instead, we can use case $(2)$ to get a better bound. In particular, for $i\leq d$, let $C_i$ be the set of periodic boxes of the form $I_1\times\ldots\times I_d$ such that $I_j=[0,1]$ for all $j\neq i$. Then the collection $C$ of all periodic boxes is precisely $C_1\wedge\ldots\wedge C_d$. Moreover, each $C_i$ has the same VC-dimension as the set of $1$-dimensional periodic boxes, which is $3$. So altogether, this yields:

Corollary. The VC-dimension of $C$ is at most $(3+o(1))d\log_2(d)$.

The precise VC-dimension of $C$ appears to still be an open problem. I only found one paper discussing it, which only conjectures that the VC-dimension is linear in $d$ (but gives no known bounds). One major defect in my argument as that geometry is only being used in dimension $1$, and then the rest is just abstract combinatorics. One would expect intersections of elements from the $C_i$'s to be much better behaved than intersections of arbitrary sets. Probably the bound in the lemma can be improved a little bit, but not to something linear.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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