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

2025/08/18 by Xingyu Chen, Ruiqi Zhang, Chen, Xingyu +3
Computer Science · Mathematics · #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #Computation (stat.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Methodology (stat.ME) #Numerical Analysis (math.NA) #Rough Sets and Fuzzy Logic

paper · pdf · doi:10.48550/arxiv.2508.12627

openalex publication_date 2025/08/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 u-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 u-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.

Citations

• Counting Cycles with AI: Counting Cycles with AI: Computationally Efficient Equivalent Forms with Applications
• Doubly-robust inference and optimality in structure-agnostic models with smoothness
• Higher-Order Graphon Theory: Fluctuations, Degeneracies, and Inference
• Engression: Extrapolation through the Lens of Distributional Regression
• U-Statistic Reduction: Higher-Order Accurate Risk Control and Statistical-Computational Trade-Off, with Application to Network Method-of-Moments
• Adaptive Testing for High-dimensional Data
• Fast convergence rates for dose-response estimation
• A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path
• Adaptive, Rate-Optimal Hypothesis Testing in Nonparametric IV Models
• Minimax Optimal Conditional Independence Testing
• A simple measure of conditional dependence
• A new coefficient of correlation
• Estimating Learnability in the Sublinear Data Regime
• Randomized incomplete U-statistics in high dimensions
• Testing mutual independence in high dimension via distance covariance
• The Treewidth of Line Graphs
• An Efficient Algorithm for Computing Interventional Distributions in Latent Variable Causal Models
• Measuring and testing dependence by correlation of distances
• Ranking and empirical minimization of U-statistics
• Simulating Quantum Computation by Contracting Tensor Networks

Related

• The Tensor Track VII: From Quantum Gravity to Artificial Intelligence
• A Fast Convoluted Story: Scaling Probabilistic Inference for Integer Arithmetic
• A Tensor Train Approach for Deterministic Arithmetic Operations on Discrete Representations of Probability Distributions
• Tensor cumulants for statistical inference on invariant distributions
• Report on "Geometry and representation theory of tensors for computer science, statistics and other areas."