6b5617315c9ac918215fc7514bef514b-Supplemental.pdf

Furthermore, their guarantees only hold in the realizable setting, requiring thatf is itself a size-s decision tree (i.e.opts = 0). There has been extensive work in the learning theory literature on learning the concept class of decision trees [EH89, Blu92, KM93, OS07, GKK08, HKY18, CM19]. This follows by combining the boundsInf(T) logs (see e.g.