Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



Revision #1 to TR16-065 | 27th October 2016 23:03

On the Recursive Teaching Dimension of VC Classes


Revision #1
Authors: Xi Chen, Yu Cheng, Bo Tang
Accepted on: 27th October 2016 23:03
Downloads: 288


The recursive teaching dimension (RTD) of a concept class $C \subseteq \{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 \subseteq \{0, 1\}^n$ with $VCD(C) = d$, we first show that $RTD(C)$ is at most $d 2^{d+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(d 2^d \log \log |C|)$, obtained by Moran et al. [MSWY15]. We remove the $\log \log |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 $\{ C_k \}_{k \ge 1}$ with $VCD(C_k) = 3k$ and $RTD(C_k)=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)$.


TR16-065 | 18th April 2016 23:47

A Note on Teaching for VC Classes

Authors: Xi Chen, Yu Cheng, Bo Tang
Publication: 19th April 2016 18:03
Downloads: 425


In this note, we study the recursive teaching dimension(RTD) of concept classes of low VC-dimension. Recall that the VC-dimension of $C \subseteq \{0,1\}^n$, denoted by $VCD(C)$, is the maximum size of a shattered subset of $[n]$, where $Y\subseteq [n]$ is shattered if for every binary string $\vec{b}$ of length $|Y|$, there is a concept $c\in C$ such that the projection of $c$ on $Y=\vec{b}$. Our main result is that $RTD(C)\le 2^{d+1}(d-2) + d + 4$ where $C$ is a concept class with $VCD(C)=d$.

ISSN 1433-8092 | Imprint