Loading [MathJax]/jax/output/CommonHTML/jax.js

On the Recursive Teaching Dimension of VC Classes

Part of Advances in Neural Information Processing Systems 29 (NIPS 2016)

Bibtex Metadata Paper Reviews Supplemental

Authors

Xi Chen, Xi Chen, Yu Cheng, Bo Tang

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}k1 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).