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

Abstract

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.

References in corpus (5)

• Gaussian approximations and multiplier bootstrap for maxima of sums of high-dimensional random vectors
• Quantifying Uncertainty in Random Forests via Confidence Intervals and Hypothesis Tests
• Gaussian and bootstrap approximations for high-dimensional U-statistics and their applications
• On local $U$-statistic processes and the estimation of densities of functions of several sample variables
• Jackknife multiplier bootstrap: finite sample approximations to the $U$-process supremum with applications

Cited by in corpus (4)

• Central limit theorems for high dimensional dependent data
• Asymptotic Distributions and Rates of Convergence for Random Forests via Generalized U-statistics
• High-dimensional Central Limit Theorems by Stein's Method
• Stratified incomplete local simplex tests for curvature of nonparametric multiple regression