Delphi.science

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

Source: arxiv.org/abs/2611.10551

Jianhang Ai, Yiming Chen, Ondřej Kuželka, Yuyi Wang

arXivarxiv/2611.10551Nov 7, 2026math.STscore 0

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…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

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}'