Fat-Shattering Dimension of k-fold Aggregations
Idan Attias, Aryeh Kontorovich; 25(144):1−29, 2024.
Abstract
We provide estimates on the fat-shattering dimension of aggregation rules of real-valued function classes. The latter consists of all ways of choosing k functions, one from each of the k classes, and computing pointwise an "aggregate" function of these, such as the median, mean, and maximum. The bounds are stated in terms of the fat-shattering dimensions of the component classes. For linear and affine function classes, we provide a considerably sharper upper bound and a matching lower bound, achieving, in particular, an optimal dependence on k. Along the way, we improve several known results in addition to pointing out and correcting a number of erroneous claims in the literature.
[abs]
[pdf][bib]© JMLR 2024. (edit, beta) |