Concentration inequalities for order statistics
By Stéphane Boucheron, Maud Thomas. 2012
85 citations recorded by the source corpus.
This note describes non-asymptotic variance and tail bounds for order statistics of samples of independent identically distributed random variables. When the sampling distribution belongs to a maximum domain of attraction, these bounds are checked to be asymptotically tight. When the sampling distribution has a non decreasing hazard rate, we derive an exponential Efron-Stein inequality for order statistics, that is an inequality connecting the logarithmic moment generating function of order statistics with exponential moments of Efron-Stein (jackknife) estimates of variance. This connection is used to derive variance and tail bounds for order statistics of Gaussian samples that are not within the scope of the Gaussian concentration inequality. Proofs are elementary and combine Renyi's representation of order statistics with the entropy approach to concentration of measure popularized by M. Ledoux.
Subfields: Statistics and Probability
View Paper: https://www.semanticscholar.org/paper/77809252cebfc7f67280e85d4cf40c740ea2e574
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Statistics and Probability
- Aaditya Ramdas
- Jeff Schneider
- Barnab'as P'oczos
- Steven R. Howard
- Kirthevasan Kandasamy
- Akshay Krishnamurthy
- Arthur Gretton
- Bharath K. Sriperumbudur
Citations in the corpus
- Parallelised Bayesian Optimisation via Thompson Sampling (2018, methodology): “[5] Stéphane Boucheron and Maud Thomas.”
- Sequential estimation of quantiles with applications to A/B testing and best-arm identification (2019, methodology): “The pioneering work of Darling and Robbins (1967a) introduced the idea of a confidence sequence, as far as we are aware, and gave a confidence sequence for the median. Their method exploits a standard connection between concentration of quantiles and concentration of the empirical CDF, as does our w”
- Asynchronous Parallel Bayesian Optimisation via Thompson Sampling (2017, methodology): “This is Theorem 2.5 in [4] but we include a simple proof for completeness.”