Concentration inequalities for sampling without replacement

By Rémi Bardenet, Odalric-Ambrym Maillard. 2013

200 citations recorded by the source corpus.

Concentration inequalities quantify the deviation of a random variable from a fixed value. In spite of numerous applications, such as opinion surveys or ecological counting procedures , few concentration results are known for the setting of sampling without replacement from a finite population. Until now, the best general concentration inequality has been a Hoeffding inequality due to ?. In this paper, we first improve on the fundamental result of ?, and further extend it to obtain a Bernstein concentration bound for sampling without replacement. We then derive an empirical version of our bound that does not require the variance to be known to the user.

Subfields: Artificial Intelligence, Infectious Diseases, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Zhiwei Steven Wu
2. Seth Neel
3. Aaron Roth
4. Larry A. Wasserman
5. Sivaraman Balakrishnan
6. Aaditya Ramdas
7. Ilmun Kim
8. Ian Waudby-Smith

In Infectious Diseases

1. Ian Waudby-Smith
2. Aaditya Ramdas
3. Chulhee Yun
4. Suvrit Sra
5. Kwangjun Ahn

In Statistics and Probability

1. Sivaraman Balakrishnan
2. Larry A. Wasserman
3. Ilmun Kim
4. Aaditya Ramdas
5. Ian Waudby-Smith
6. Aaron Roth
7. Zhiwei Steven Wu
8. Chulhee Yun

Citations in the corpus

• Minimax optimality of permutation tests (2020, result): “Similar results can be found in Bercu et al. (2015) and Albert (2019) but in terms of constants, the bound below is much shaper than the previous ones.”
• How to Use Heuristics for Differential Privacy (2018, background): “By a Cherno ff bound for subsampled random variables (see e.g. Theorem 1.2 of [BM13]), for any By a union bound over Q , this means that with probability 1 − η , We now have all the ingredients to complete the bound: By a union bound and the results above, we know that the righthand side is less…”
• SGD with shuffling: optimal rates without component convexity and large epoch requirements (2020, methodology): “The scalar-valued version of Hoeffding-Serfling inequality [1] was also used in [17].”
• Estimating means of bounded random variables by betting (2020, methodology): “Serfling [1974] improved on this bound, which was then further refined by Bardenet and Maillard [2015].”