Concentration Inequalities for U-Statistics: A Survey with Explicit Constants

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.

13 pages, 1 table. v3: major revision and substantial expansion of the 6-page v2, which was titled "A Note on Concentration Inequalities for U-Statistics". The exposition is restructured around a single convex-domination lemma. Simulation code is included as an ancillary file