# Fat-Shattering Dimension of k-fold Aggregations

arXiv: https://arxiv.org/abs/2110.04763 · HTML: https://mlsanity.com/paper/2110.04763/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 46 references that are in the map.
- First posted on arXiv 10 Oct 2021.

## Builds on (most cited first, 6 of 6)

- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Improved Generalization Bounds for Adversarially Robust Learning](https://mlsanity.com/paper/1810.02180/) (2018)
- [Closure Properties for Private Classification and Online Prediction](https://mlsanity.com/paper/2003.04509/) (2020)
- [Robust k-means Clustering for Distributions with Two Moments](https://mlsanity.com/paper/2002.02339/) (2020)
- [Efficient Classification for Metric Data](https://mlsanity.com/paper/1306.2547/) (2013)
- [Near-tight closure bounds for Littlestone and threshold dimensions](https://mlsanity.com/paper/2007.03668/) (2020)

## Built on by (most cited first, 5 of 5)

- [Coverage Improvement and Fast Convergence of On-policy Preference Learning](https://mlsanity.com/paper/2601.08421/) (2026)
- [Learning With Multi-Group Guarantees For Clusterable Subpopulations](https://mlsanity.com/paper/2410.14588/) (2024)
- [Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale](https://mlsanity.com/paper/2605.13684/) (2026)
- [Transductive and Learning-Augmented Online Regression](https://mlsanity.com/paper/2510.03917/) (2025)
- [The Interplay Between Interpolation and Aggregation in Regression: Optimal Sample Complexity](https://mlsanity.com/paper/2605.29819/) (2026)

## Abstract (arXiv)

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.