  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.
