Abstract
Higher-order U-statistics appear throughout statistics, machine learning, and computer science, yet their exact computation can be expensive and their computational complexity has received limited systematic study. We develop a decomposition of an order-m U-statistic into a linear combination of V-statistics of orders at most m. We connect exact V-statistic computation to Einstein summation and use the treewidth of a graph associated with the kernel to obtain an optimistic estimate of computational complexity. Together, these results yield a faster algorithm for exact computation of general higher-order U-statistics and a more systematic characterization of its runtime. We provide the open-source u-stats package in Python and R, and demonstrate its performance against existing benchmarks in three statistical examples. The work aims to encourage further algorithmic development and make higher-order U-statistics easier to use in practice.
Links
๐ Journal ๐ arXiv ๐ป Software-Python ๐ป Software-R ๐ป Software-HOIF ๐ป Reproducibility Code ๐ผ Poster ๐ Slides
Xingyu Chen, Lin Liu, Ruiqi Zhang. On computing and the complexity of computing higher-order U-statistics, exactly. Statistics and Computing, 36(5), Article 223 (2026). Accepted before the journal’s transition to fully open access (fully OA).