Fat-Shattering Dimension of $k$-fold Aggregations

Idan Attias, Leonid (Aryeh) Kontorovich

Publication date: 10 October 2021

Abstract: We provide improved estimates on the fat-shattering dimension of the $k$-fold maximum of real-valued function classes. The latter consists of all ways of choosing $k$ functions, one from each of the $k$ classes, and computing their pointwise 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 point out and correct a number of erroneous claims in the literature.

This page was built for publication: Fat-Shattering Dimension of $k$-fold Aggregations