Concentration Inequalities for Random Sets
From MaRDI portal
Abstract: In a large, possibly infinite population, each subject is colored red with probability , independently of the others. Then, a finite sub-population is selected, possibly as a function of the coloring. The imbalance in the sub-population is defined as the difference between the number of reds in it and p times its size. This paper presents high-probability upper bounds (tail-bounds) on this imbalance. To present the upper bounds we define the *UI dimension* --- a new measure for the richness of a set-family. We present three simple rules for upper-bounding the UI dimension of a set-family. Our upper bounds on the imbalance in a sub-population depend only on the size of the sub-population and on the UI dimension of its support. We relate our results to known concepts from machine learning, particularly the VC dimension and Rademacher complexity.
This page was built for publication: Concentration Inequalities for Random Sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6281301)
