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

Yanglei Song, Xiaohui Chen, Kengo Kato

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)4794-4848
Number of pages55
JournalElectronic Journal of Statistics
Issue number2
StatePublished - 2019


  • Bootstrap
  • Gaussian approximation
  • Incomplete U statistics
  • Infinite-order U-statistics
  • Random forests
  • Uncertainty quantification

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty


Dive into the research topics of 'Approximating high-dimensional infinite-order U-statistics: Statistical and computational guarantees'. Together they form a unique fingerprint.

Cite this