Lower Bounds for Greedy Teaching Set Constructions

A fundamental open problem in learning theory is to characterize the best-case teaching dimension operatornameTSmin of a concept class C with finite VC dimension d. Resolving this problem will, in particular, settle the conjectured upper bound on Recursive Teaching Dimension posed by [Simon and Zilles; COLT 2015]. Prior work used a natural greedy algorithm to construct teaching sets recursively, thereby proving upper bounds on operatornameTSmin, with the best known bound being O(d2) [Hu, Wu, Li, and Wang; COLT 2017]. In each iteration, this greedy algorithm chooses to add to the teaching set the k labeled points that restrict the concept class the most. In this work, we prove lower bounds on the performance of this greedy approach for small k. Specifically, we show that for k = 1, the algorithm does not improve upon the halving-based bound of O(log(|C|)). Furthermore, for k = 2, we complement the upper bound of Oleft(log(log(|C|))right) from [Moran, Shpilka, Wigderson, and Yuhudayoff; FOCS 2015] with a matching lower bound. Most consequentially, our lower bound extends up to k ≤ lceil c d rceil for small constant c>0: suggesting that studying higher-order interactions may be necessary to resolve the conjecture that operatornameTSmin = O(d).