On the Recursive Teaching Dimension of VC Classes

The recursive teaching dimension (RTD) of a concept class $C \subseteq \{0, 1\} n$, introduced by Zilles et al. [ZLHZ11], is a complexity parameter measured by the worst-case number of labeled examples needed to learn any target concept of $C$ in the recursive teaching model. In this paper, we study the quantitative relation between RTD and the well-known learning complexity measure VC dimension (VCD), and improve the best known upper and (worst-case) lower bounds on the recursive teaching dimension with respect to the VC dimension. Given a concept class $C \subseteq \{0, 1\} n$ with $VCD(C) d$, we first show that $RTD(C)$ is at most $d 2 {d 1}$. This is the first upper bound for $RTD(C)$ that depends only on $VCD(C)$, independent of the size of the concept class $ C $ and its domain size $n$. Before our work, the best known upper bound for $RTD(C)$ is $O(d 2 d \log \log C)$, obtained by Moran et al. [MSWY15].