# Randomized incomplete U-statistics in high dimensions

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Dec 2017.

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

- [Deeply-Debiased Off-Policy Interval Estimation](https://mlsanity.com/paper/2105.04646/) (2021)
- [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)
- [Higher-order accurate two-sample network inference and network hashing](https://mlsanity.com/paper/2208.07573/) (2022)
- [Jackknife Variance Estimation for H'ajek-Dominated Generalized U-Statistics](https://mlsanity.com/paper/2509.12356/) (2025)
- [Riemann-Lebesgue Forest for Regression](https://mlsanity.com/paper/2402.04550/) (2024)
- [Global Censored Quantile Random Forest](https://mlsanity.com/paper/2410.12209/) (2024)
- [Conditional Dependence via U-Statistics Pruning](https://mlsanity.com/paper/2410.15888/) (2024)
- [On computing and the complexity of computing higher-order U-statistics, exactly](https://mlsanity.com/paper/2508.12627/) (2025)
- [Learning U-Statistics with Active Inference](https://mlsanity.com/paper/2605.11638/) (2026)
- [On Finite-sample Concentration of Median of Incomplete U-Statistics](https://mlsanity.com/paper/2606.00661/) (2026)
- [Calibrated Derivative-Process Sensitivity for Gaussian-Process Variable Selection](https://mlsanity.com/paper/2609.33549/) (2026)

## Abstract (arXiv)

This paper studies inference for the mean vector of a high-dimensional U-statistic. In the era of Big Data, the dimension d of the U-statistic and the sample size n of the observations tend to be both large, and the computation of the U-statistic is prohibitively demanding. Data-dependent inferential procedures such as the empirical bootstrap for U-statistics is even more computationally expensive. To overcome such computational bottleneck, incomplete U-statistics obtained by sampling fewer terms of the U-statistic are attractive alternatives. In this paper, we introduce randomized incomplete U-statistics with sparse weights whose computational cost can be made independent of the order of the U-statistic. We derive non-asymptotic Gaussian approximation error bounds for the randomized incomplete U-statistics in high dimensions, namely in cases where the dimension d is possibly much larger than the sample size n, for both non-degenerate and degenerate kernels. In addition, we propose generic bootstrap methods for the incomplete U-statistics that are computationally much less-demanding than existing bootstrap methods, and establish finite sample validity of the proposed bootstrap methods. Our methods are illustrated on the application to nonparametric testing for the pairwise independence of a high-dimensional random vector under weaker assumptions than those appearing in the literature.