Fat-Shattering Dimension of $k$-fold Aggregations
This work addresses theoretical gaps in learning theory for researchers, though it appears incremental as it builds on and corrects prior results.
The paper tackles the problem of estimating the fat-shattering dimension for aggregation rules of real-valued function classes, such as median, mean, and maximum, deriving bounds based on component classes and achieving optimal dependence on k for linear and affine functions.
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 a pointwise function of them, such as the median, mean, and maximum. The bound is 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.