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

01/04/2019
by   Yanglei Song, et al.
0

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) is 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, dimensionality, and order, are all 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 with statistical and computational guarantees.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset