pipette
ESEspañol

Removing the floor from Hoeffding and Bernstein inequalities for finite-population U-statistics

Jianhang Ai, Yiming Chen, Ond\v{r}ej Ku\v{z}elka, Yuyi Wang

Preprint

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