Lower Bounds for Greedy Teaching Set Constructions

Spencer Compton, Chirag Pabbaraju, Nikita Zhivotovskiy

A fundamental open problem in learning theory is to characterize the best-case teaching dimension ${\mathrm{TS}}_{\min }$ of a concept class $\mathcal{C}$ with finite VC dimensi…