On the Recursive Teaching Dimension of VC Classes
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 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(d2 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≥1 with VCD(C k ) = 3k and RTD(C k ) = 5k,
The paper is the first to provide an upper bound on the recursive teaching dimension (a complexity parameter in co-operative teacher/learner settings) in terms of the VC-dimension that does not depend on the size of the concept class. The upper bound is exponential in the VC-dimension. Further, the paper is the first to show that there are concept classes whose recursive teaching dimension exceeds their VC-dimension by more than a factor of 3/2 (namely, they provide classes that exhibit a factor of 5/3). 
The paper is very insightful - the authors quite nicely explain the approach they took for proving their results. The questions addressed, while interesting only for a fairly small subcommunity of the machine learning community, are really important in that subcommunity, and the authors have achieved a substantial breakthrough on an open problem posed in COLT 2015. I quite liked the idea to formulate the problem of finding a concept class with RTD > 3/2 VCD as a SAT problem. In my eyes, the results should definitely be published, and they are important enough to deserve publication in a leading venue like NIPS.  The paper is generally well written and easy to read, but there are a few minor (easy to fix issues (mostly just typos etc). The two things I'd like the authors to fix, since they are rather  misleading, are the following: (1) They keep talking about proving a "lower bound" on RTD in terms of VCD, and even in the abstract they say "RTD(C)\ge (5/3)VCD(C) in general". While I know what they want to say, what they do say is actually incorrect. There are classes of RTD 1 that have arbitrarily large VCD, so there is no lower bound on RTD in terms of VCD, and certainly (5/3)VCD(C) is not a lower bound. But 5/3 is a lower bound on the worst-case factor by which RTD may exceed VCD. The authors need to go through the whole paper and fix this everywhere (I spotted it here: last para of abstract, heading of section 3, first sentence of section 3, line 1 on page 7, line 2 on page 7, but I may have overlooked other places). (2) After Definition 1, the authors say that "RTD(C) measures the worst-case number of labeled examples needed to learn any target concept in C, if the teacher and the learner agree a priori on a specific order of the concepts". While this is not incorrect, is is rather misleading, since no such a priori agreement is needed. If teacher and learner do not agree on an order, they can still use a well-defined process to uniquely derive teaching sets, and the largest teaching set will have a size equal to RTD(C): first, one determines ALL concepts in C that have the smallest teaching dimension in C, and assigns teaching sets accordingly. Then one removes ALL those concepts from the class and proceeds recursively.  Hence, it would create the wrong impression to say that RTD corresponds to some order that the two parties have to agree on a priori. I'd like to urge the authors to modify the writing in this point.  Everything else is just typos and the like: line 9: at most d2^{d+1} -- > in O(d2^{d+1}) line 11: is -- > was line 16: is -- > was line 22: resultS line 83: largest _known_ multiplicative ... line 84: is -- > was lines 116 and 118: I believe it should be VCD(C) = 2 in both cases (not 3) formula display after line 134: VCD should be TS_min same after line 141 line 181: delete "that" at the end of the line line 206: insert a "times" symbol before the last C_0