Removing the floor from Hoeffding and Bernstein inequalities for finite-population U-statistics
Ai et al.
For a U-statistic of order \(k\) on a sample of size \(n\) drawn without replacement, Hoeffding, Bennett and Bernstein bounds hold with effective sample size \(n/k\) instead of \(\lfloor n/k \rfloor\).
Source published · In the Daily Brief of 11 November 2026
Filed under Probability, Learning theory
Take a uniformly random \(n\)-element subset \(C\) of a finite population \(D\) of size \(N\) and form the complete U-statistic \(U_C\) of order \(k\) from a bounded kernel. Classical concentration bounds for \(U_C\) go through Hoeffding’s blocking argument and so only see \(\lfloor n/k \rfloor\) independent blocks.
The authors prove a product inequality for the uniform distribution on \(n\)-subsets and deduce a comparison of moment generating functions: \[ \log \mathbb{E}\, e^{\theta (U_C - \mathbb{E} U_C)} \le \frac{n}{k} \log \mathbb{E}\, e^{\frac{k\theta}{n}(Y - \mathbb{E} Y)}, \] where \(Y\) is the kernel evaluated at one uniformly random \(k\)-subset. The standard Chernoff route then gives Hoeffding, Bennett and Bernstein inequalities with \(n/k\) in the exponent.
The gain is small when \(n \gg k\) but approaches a factor of two in the exponent when \(k\) is close to \(n\), a regime that matters for sampling-without-replacement estimators in learning theory.