2021/10/10 by Idan Attias, Attias, Idan, Aryeh Kontorovich +1 · 2 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Algebra and Logic #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA) #Fuzzy Systems and Optimization #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Multi-Criteria Decision Making
paper · pdf · doi:10.48550/arxiv.2110.04763
openalex publication_date 2021/10/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.