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]. We remove the \log \log |C| factor.

We also improve the lower bound on the worst-case ratio of RTD(C) to VCD(C). We present a family of classes \{ C_k \}_{k \ge 1} with VCD(C_k) = 3k and RTD(C_k)=5k, which implies that the ratio of RTD(C) to VCD(C) in the worst case can be as large as 5/3. Before our work, the largest ratio known was 3/2 as obtained by Kuhlmann [Kuh99]. Since then, no finite concept class C has been known to satisfy RTD(C) > (3/2) VCD(C).

In this note, we study the recursive teaching dimension(RTD) of concept classes of low VC-dimension. Recall that the VC-dimension of C \subseteq \{0,1\}^n, denoted by VCD(C), is the maximum size of a shattered subset of [n], where Y\subseteq [n] is shattered if for every binary string \vec{b} of length |Y|, there is a concept c\in C such that the projection of c on Y=\vec{b}. Our main result is that RTD(C)\le 2^{d+1}(d-2) + d + 4 where C is a concept class with VCD(C)=d.