Quadratic Upper Bound for Recursive Teaching Dimension of Finite VC Classes

In this work we study the quantitative relation between the recursive teaching dimension (RTD) and the VC dimension (VCD) of concept classes of finite sizes. The RTD of a concept class mathcal C subseteq 0, 1n, introduced by Zilles et al. (2011), is a combinatorial complexity measure characterized by the worst-case number of examples necessary to identify a concept in mathcal C according to the recursive teaching model. For any finite concept class mathcal C subseteq 0,1n with VCD(mathcal C)=d, Simon & Zilles (2015) posed an open problem RTD(mathcal C) = O(d), i.e., is RTD linearly upper bounded by VCD? Previously, the best known result is an exponential upper bound RTD(mathcal C) = O(d · 2d), due to Chen et al. (2016). In this paper, we show a quadratic upper bound: RTD(mathcal C) = O(d2), much closer to an answer to the open problem. We also discuss the challenges in fully solving the problem.