Removing the floor from Hoeffding and Bernstein inequalities for finite-population U-statistics
In the authors' words
Let be a uniformly sampled -element subset of a finite population of size , and let be the complete U-statistic of order built from a bounded kernel on the -subsets of . We prove a product inequality for the uniform distribution on and deduce from it the comparison , where is a single kernel value taken at a uniformly sampled -subset of . This yields Hoeffding, Bennett and Bernstein inequalities for with effective sample size in place of the available so far. The gain is negligible when is much larger than , but it approaches a factor of two in the exponent when is close to .
Main resultLimitation the authors admit
Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 8