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

Understand

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.