2025/05/06 by Spencer Compton, Compton, Spencer, Chirag Pabbaraju +3
Computer Science · #Combinatorics (math.CO) #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Intelligent Tutoring Systems and Adaptive Learning #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Natural Language Processing Techniques
paper · pdf · doi:10.48550/arxiv.2505.03223
openalex publication_date 2025/05/06 · openalex created_date 2025/10/16 · openalex updated_date 2026/07/28
A fundamental open problem in learning theory is to characterize the best-case teaching dimension TSmin 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 TSmin, 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 O(log(log(|C|))) 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 TSmin = O(d).