Entropy, Combinatorial Dimensions and Random Averages
Abstract
In this article we introduce a new combinatorial parameter which generalizes the VC dimension and the fat-shattering dimension, and extends beyond the function-class setup. Using this parameter we establish entropy bounds for subsets of the n -dimensional unit cube, and in particular, we present new bounds on the empirical covering numbers and gaussian averages associated with classes of functions in terms of the fat-shattering dimension.
Cite
Text
Mendelson and Vershynin. "Entropy, Combinatorial Dimensions and Random Averages." Annual Conference on Computational Learning Theory, 2002. doi:10.1007/3-540-45435-7_2Markdown
[Mendelson and Vershynin. "Entropy, Combinatorial Dimensions and Random Averages." Annual Conference on Computational Learning Theory, 2002.](https://mlanthology.org/colt/2002/mendelson2002colt-entropy/) doi:10.1007/3-540-45435-7_2BibTeX
@inproceedings{mendelson2002colt-entropy,
title = {{Entropy, Combinatorial Dimensions and Random Averages}},
author = {Mendelson, Shahar and Vershynin, Roman},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2002},
pages = {14-28},
doi = {10.1007/3-540-45435-7_2},
url = {https://mlanthology.org/colt/2002/mendelson2002colt-entropy/}
}