Paper Info
Title
Open Problem: Recursive Teaching Dimension Versus VC Dimension
Abstract
The Recursive Teaching Dimension (RTD) of a concept class \mathcalC is a complexity parameter referring to the worst-case number of labelled examples needed to learn any target concept in \mathcalC from a teacher following the recursive teaching model. It is the first teaching complexity notion for which interesting relationships to the VC dimension (VCD) have been established. In particular, for finite maximum classes of a given VCD d, the RTD equals d. To date, there is no concept class known for which the ratio of RTD over VCD exceeds 3/2. However, the only known upper bound on RTD in terms of VCD is exponential in the VCD and depends on the size of the concept class. We pose the following question: is the RTD upper-bounded by a function that grows only linearly in the VCD? Answering this question would further our understanding of the relationships between the complexity of teaching and the complexity of learning from randomly chosen examples. In addition, the answer to this question, whether positive or negative, is known to have implications on the study of the long-standing open sample compression conjecture, which claims that every concept class of VCD d has a sample compression scheme in which samples for concepts in the class are compressed to subsets of size no larger than d.
Year
Venue
Field
2015
COLT
Discrete mathematics,VC dimension,Open problem,Teaching dimension,Exponential function,Concept class,Upper and lower bounds,Artificial intelligence,Conjecture,Recursion,Mathematics,Machine learning
DocType
Citations 
PageRank 
Conference
4
0.45
References 
Authors
6
2
Name
Order
Citations
PageRank
Hans-Ulrich Simon1567104.52
sandra zilles242747.94