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

arXiv: https://arxiv.org/abs/2405.07860 · HTML: https://mlsanity.com/paper/2405.07860/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- First posted on arXiv 13 May 2024.

## Abstract (arXiv)

We give an order-explicit large deviation bound for the difference between a high-dimensional U-statistic and its H'ajek projection. In particular, we show that any U-statistic of order b on n observations, with a d-dimensional kernel whose coordinates have psi1-Orlicz norm at most φ, has a maximum deviation from its H'ajek projection of order Op(φ b n-1log2(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. As corollaries, we obtain new Bernstein-type concentration and Gaussian approximation results for high-dimensional U-statistics. We apply these results to establish the consistency of a set of resampling-based simultaneous confidence intervals built around a class of nonparametric regression estimators constructed with subsampled kernels. This class encompasses several forms of random forest regression, including Generalized Random Forests.