Concentration inequalities for sampling without replacement

Bardenet, Remi; Maillard, Odalric-Ambrym

Document type :

Article dans une revue scientifique

DOI :

10.3150/14-BEJ605

Title :

Concentration inequalities for sampling without replacement

Author(s) :

Bardenet, Remi [Auteur]

University of Oxford
Maillard, Odalric-Ambrym [Auteur]

Department of Electrical Engineering - Technion [Haïfa] [EE-Technion]
Machine Learning and Optimisation [TAO]

Journal title :

Bernoulli

Pages :

1361-1385

Publisher :

Bernoulli Society for Mathematical Statistics and Probability

Publication date :

2015

ISSN :

1350-7265

English keyword(s) :

Sampling without replacement
Concentration bounds

HAL domain(s) :

Mathématiques [math]/Statistiques [math.ST]

English abstract : [en]

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 ...
Show more >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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Files

https://hal.archives-ouvertes.fr/hal-01216652/document
Open access
Access the document

https://doi.org/10.3150/14-bej605
Open access
Access the document

https://hal.archives-ouvertes.fr/hal-01216652/document
Open access
Access the document

https://doi.org/10.3150/14-bej605
Open access
Access the document

https://doi.org/10.3150/14-bej605
Open access
Access the document

https://doi.org/10.3150/14-bej605
Open access
Access the document

https://doi.org/10.3150/14-bej605
Open access
Access the document

Concentration inequalities for sampling ... BibTeX CSV Excel RIS

Files

Concentration inequalities for sampling ...

BibTeX

CSV

Excel

RIS