Quadratic Upper Bound for Recursive Teaching Dimension of Finite VC Classes

[edit]

Lunjia Hu, Ruihan Wu, Tianhong Li, Liwei Wang ;
Proceedings of the 2017 Conference on Learning Theory, PMLR 65:1147-1156, 2017.

Abstract

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⊆{0,1}^n$ , 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⊆{0,1}^n$ with $\mathrm{VCD}(\mathcal C) = d$, Simon and Zilles (2015) posed an open problem $\mathrm{RTD}(\mathcal C) = O(d)$, i.e., is RTD linearly upper bounded by VCD? Previously, the best known result is an exponential upper bound $\mathrm{RTD}(\mathcal C) = O(d\cdot2^d)$, due to Chen et al. (2016). In this paper, we show a quadratic upper bound: $\mathrm{RTD}(\mathcal C) = O(d^2)$, much closer to an answer to the open problem. We also discuss the challenges in fully solving the problem.

Related Material