Concentration inequalities for sampling without replacement
From MaRDI portal
Abstract: 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 Serfling [Ann. Statist. 2 (1974) 39-48]. In this paper, we first improve on the fundamental result of Serfling [Ann. Statist. 2 (1974) 39-48], 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.
Recommendations
- Concentration inequalities for samples without replacement
- Hoeffding-Serfling inequality for U-statistics without replacement
- Hoeffding and Bernstein inequalities for U-statistics without replacement
- A bound on the moment generating function of a sum of dependent variables with an application to simple random sampling without replacement
- Concentration inequalities on the multislice and for sampling without replacement
Cites work
- A Generalization of Sampling Without Replacement From a Finite Universe
- Centering Sequences with Bounded Differences
- Concentration inequalities for functions of independent variables
- Concentration inequalities. A nonasymptotic theory of independence
- Exploration and exploitation of scratch games
- Exploration-exploitation tradeoff using variance estimates in multi-armed bandits
- scientific article; zbMATH DE number 2034517 (Why is no real title available?)
- scientific article; zbMATH DE number 3242901 (Why is no real title available?)
- ON ESTIMATING THE SIZE OF MOBILE POPULATIONS FROM RECAPTURE DATA
- Probability Inequalities for Sums of Bounded Random Variables
- Probability inequalities for the sum in sampling without replacement
- Stochastic dual coordinate ascent methods for regularized loss minimization
Cited in
(26)- Weighted sampling without replacement
- Exponential inequality for chaos based on sampling without replacement
- Concentration inequalities on the multislice and for sampling without replacement
- Bernstein-type exponential inequalities in survey sampling: conditional Poisson sampling schemes
- Samples without replacement: one property of distribution of range
- Hoeffding and Bernstein inequalities for U-statistics without replacement
- Large-deviation bounds for sampling without replacement
- An inequality for random replacement sampling plans
- Two models of double descent for weak features
- Stochastic Cutting Planes for Data-Driven Optimization
- Distribution-free, size adaptive submatrix detection with acceleration
- The distribution of sandpile groups of random regular graphs
- Learning optimized risk scores
- Concentration inequalities for samples without replacement
- Rate of convergence of the asymptotic normality of sample quantiles from a finite population
- Hoeffding-Serfling inequality for U-statistics without replacement
- Algorithms for maximum social welfare of online random trading
- Extended Glivenko—Cantelli theorem for simple random sampling without replacement from a finite population
- Hoeffding and Bernstein inequalities for weighted sums of exchangeable random variables
- Transport dependency: optimal transport based dependency measures
- Near-optimal algorithms for stochastic online bin packing
- Asymptotic optimality of degree-greedy discovering of independent sets in configuration model graphs
- Intervention efficient algorithms for approximate learning of causal graphs
- Adversarial laws of large numbers and optimal regret in online classification
- Elementary tail bounds on the hypergeometric distribution
- Quantile-based Loss Filtering for Outlier-Robust Stochastic Gradient Descent
This page was built for publication: Concentration inequalities for sampling without replacement
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2515502)
