Poster
On the Recursive Teaching Dimension of VC Classes
Peter Chen · Xi Chen · Yu Cheng · Bo Tang
Area 5+6+7+8 #104
Keywords: [ Information Theory ] [ Learning Theory ]
Abstract:
The recursive teaching dimension (RTD) of a concept class C⊆{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⊆{0,1}n with VCD(C)=d, we first show that RTD(C) is at most d2d+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(d2dloglog|C|), obtained by Moran et al. [MSWY15]. We remove the loglog|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 {Ck}k≥1 with VCD(Ck)=3k and RTD(Ck)=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).
Chat is not available.