# On computing and the complexity of computing higher-order U-statistics, exactly

arXiv: https://arxiv.org/abs/2508.12627 · HTML: https://mlsanity.com/paper/2508.12627/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 64 references that are in the map.
- First posted on arXiv 18 Aug 2025.

## Builds on (most cited first, 14 of 14)

- [Learning Relevant Features of Data with Multi-scale Tensor Networks](https://mlsanity.com/paper/1801.00315/) (2017)
- [Engression: Extrapolation through the Lens of Distributional Regression](https://mlsanity.com/paper/2307.00835/) (2023)
- [A simple measure of conditional dependence](https://mlsanity.com/paper/1910.12327/) (2019)
- [A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path](https://mlsanity.com/paper/2011.05365/) (2020)
- [Randomized incomplete U-statistics in high dimensions](https://mlsanity.com/paper/1712.00771/) (2017)
- [Estimating Learnability in the Sublinear Data Regime](https://mlsanity.com/paper/1805.01626/) (2018)
- [Fast convergence rates for dose-response estimation](https://mlsanity.com/paper/2207.11825/) (2022)
- [Doubly-robust inference and optimality in structure-agnostic models with smoothness](https://mlsanity.com/paper/2405.08525/) (2024)
- [Peregrine: A Pattern-Aware Graph Mining System](https://mlsanity.com/paper/2004.02369/) (2020)
- [Rank-transformed subsampling: inference for multiple data splitting and exchangeable p-values](https://mlsanity.com/paper/2301.02739/) (2023)
- [Testing mutual independence in high dimension via distance covariance](https://mlsanity.com/paper/1609.09380/) (2016)
- [Adaptive, Rate-Optimal Hypothesis Testing in Nonparametric IV Models](https://mlsanity.com/paper/2006.09587/) (2020)
- [U-Statistic Reduction: Higher-Order Accurate Risk Control and Statistical-Computational Trade-Off, with Application to Network Method-of-Moments](https://mlsanity.com/paper/2306.03793/) (2023)
- [Adaptive Testing for High-dimensional Data](https://mlsanity.com/paper/2303.08197/) (2023)

## Abstract (arXiv)

Higher-order U-statistics abound in fields such as statistics, machine learning, and computer science, but are known to be highly time-consuming to compute in practice. Despite their widespread appearance, a comprehensive study of their computational complexity is surprisingly lacking. This paper aims to fill this gap by presenting several results related to the computational aspect of U-statistics. First, we derive a useful decomposition from a m-th order U-statistic to a linear combination of V-statistics with orders not exceeding m, which are generally more feasible to compute. Second, we explore the connection between exactly computing V-statistics and Einstein summation, a tool often used in computational mathematics and quantum computing to accelerate tensor computations. Third, we provide an optimistic estimate of the time complexity for exactly computing U-statistics, based on the treewidth of a particular graph associated with the U-statistic kernel. The above ingredients lead to (1) a new, much more runtime-efficient algorithm to exactly compute general higher-order U-statistics, and (2) a more streamlined characterization of runtime complexity of computing U-statistics. We develop an accompanying open-source package called textttu-stats in both Python (https://github.com/zrq1706/U-Statistics-Python) and R (https://github.com/cxy0714/U-Statistics-R). We demonstrate through three examples in statistics that textttu-stats achieves impressive runtime performance compared to existing benchmarks. This paper also aspires to achieve two goals: (1) to capture the interest of researchers in both statistics and other related areas to further advance the algorithmic development of U-statistics and (2) to lift the burden of implementing higher-order U-statistics from practitioners.