VC-dimension and distance chains in Fqd

Abstract

Given a domain $X$ and a collection $\mathcal{H}$ of functions $h:X\to \{0,1\}$, the Vapnik-Chervonenkis (VC) dimension of $\mathcal{H}$ measures its complexity in an appropriate sense. In particular, the fundamental theorem of statistical learning says that a hypothesis class with finite VC-dimension is PAC learnable. Recent work by Fitzpatrick, Wyman, the fourth and seventh named authors studied the VC-dimension of a natural family of functions ${\mathcal{H}}_t^{{}^{\prime }2}(E):{\mathbb{F}}_q^2\to \{0,1\}$, corresponding to indicator functions of circles centered at points in a subset $E\subseteq {\mathbb{F}}_q^2$. They showed that when $|E|$ is large enough, the VC-dimension of ${\mathcal{H}}_t^{{}^{\prime }2}(E)$ is the same as in the case that $E={\mathbb{F}}_q^2$. We study a related hypothesis class, ${\mathcal{H}}_t^d(E)$, corresponding to intersections of spheres in ${\mathbb{F}}_q^d$, and ask how large $E\subseteq {\mathbb{F}}_q^d$ needs to be to ensure the maximum possible VC-dimension. We resolve this problem in all dimensions, proving that whenever $|E|\ge C_d{q}^{d-1/(d-1)}$ for $d\ge 3$, the VC-dimension of ${\mathcal{H}}_t^d(E)$ is as large as possible. We get a slightly stronger result if $d=3$: this result holds as long as $|E|\ge C_3{q}^{7/3}$. Furthermore, when $d=2$ the result holds when $|E|\ge C_2{q}^{7/4}$.