Removing the floor from Hoeffding and Bernstein inequalities for finite-population U-statistics
Source: arxiv.org/abs/2611.10551
Let $C$ be a uniformly sampled $n$-element subset of a finite population $D$ of size $N$, and let $U_C$ be the complete U-statistic of order $k$ built from a bounded kernel on the $k$-subsets of $D$. We prove a product inequality for the uniform distribution on $\binom{D}{n}$ and deduce from it the comparison $ \log \mathbb{E}\left[e^{θ(U_C-\mathbb{E}U_C)}\right] \le \frac{n}{k}\log \mathbb{E}\left[e^{\frac{kθ}{n}(Y-\mathbb{E}Y)}\right]$, where $Y$ is a single kernel value taken at a uniformly sampled $k$-subset of $D$. This yields Hoeffding, Bennett and Bernstein inequalities for $U_C$ with…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.10551
curl -X POST /api/v1/records/arxiv/2611.10551/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.10551/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'