Abstract 

The recursive teaching dimension (RTD) of a concept class C 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 with VCD(C) = d, we first show that RTD(C) is at most 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 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 with VCD and RTD 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).