Abstract:This survey gives a self-contained treatment of concentration inequalities for U-statistics. Using Hoeffding's blocking argument, which reduces a U-statistic to an average over sums of independent random variables, we derive Hoeffding-, Bennett-, and Bernstein-type tail bounds with explicit constants, together with their extensions to unbounded sub-Gaussian and sub-exponential kernels and to two-sample and incomplete U-statistics. The reduction is stated once, as a convex-domination lemma, from which all the tail bounds follow as corollaries. While these results are classical -- the blocking argument goes back to Hoeffding (1963) and Bernstein-type bounds appear in Arcones (1995) -- complete elementary derivations with explicit constants are scattered or omitted in the literature, and collecting them is the purpose of this survey. We close with an overview of sharper bounds available under degeneracy assumptions and of robust median-of-means alternatives for heavy-tailed kernels, and with a numerical illustration that quantifies how conservative the explicit bounds are and decomposes the observed gap into interpretable factors.
From: Yannik Pitcan [view email]
[v1]
Sun, 17 Dec 2017 19:25:20 UTC (6 KB)
[v2]
Thu, 14 Mar 2019 22:42:57 UTC (6 KB)
[v3]
Mon, 10 Aug 2026 06:46:40 UTC (16 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。