pipette
ENEnglish

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

En palabras de los autores

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 .

Resultado principalLimitación que admiten los autores

Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 8