Order-Explicit Linearization of High-Dimensional $U$-Statistics

Understand

We give an order-explicit large deviation bound for the difference between a high-dimensional $U$-statistic and its H\'{a}jek projection.

• In particular, we show that any $U$-statistic of order $b$ on $n$ observations, with a $d$-dimensional kernel whose coordinates have $\psi_1$-Orlicz norm at most $\phi$, has a maximum deviation from its H\'{a}jek projection of order $O_p(\phi b n^{-1}\log^2(dn))$.
• The proof relies on the development of novel order-explicit moment inequalities for higher-order Hoeffding components.
• We show that this rate is unimprovable, up to the polynomial factor on the logarithmic term.