# Approximating high-dimensional infinite-order U-statistics: statistical and computational guarantees

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jan 2019.

## Built on by (most cited first, 6 of 6)

- [On Variance Estimation of Random Forests with Infinite-Order U-statistics](https://mlsanity.com/paper/2202.09008/) (2022)
- [On Differentially Private U Statistics](https://mlsanity.com/paper/2407.04945/) (2024)
- [Uncertainty Quantification of Data Shapley via Statistical Inference](https://mlsanity.com/paper/2407.19373/) (2024)
- [Jackknife Variance Estimation for H'ajek-Dominated Generalized U-Statistics](https://mlsanity.com/paper/2509.12356/) (2025)
- [Empirical Likelihood for Random Forests and Ensembles](https://mlsanity.com/paper/2511.13934/) (2025)
- [On Finite-sample Concentration of Median of Incomplete U-Statistics](https://mlsanity.com/paper/2606.00661/) (2026)

## Abstract (arXiv)

We study the problem of distributional approximations to high-dimensional non-degenerate U-statistics with random kernels of diverging orders. Infinite-order U-statistics (IOUS) are a useful tool for constructing simultaneous prediction intervals that quantify the uncertainty of ensemble methods such as subbagging and random forests. A major obstacle in using the IOUS is their computational intractability when the sample size and/or order are large. In this article, we derive non-asymptotic Gaussian approximation error bounds for an incomplete version of the IOUS with a random kernel. We also study data-driven inferential methods for the incomplete IOUS via bootstraps and develop their statistical and computational guarantees.