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

高阶U统计量在统计学、机器学习及计算机科学中广泛应用，但其精确计算在实践中往往面临严峻的计算瓶颈，尤其当样本量大、阶数高时，朴素算法的时间复杂度高达O(n^m)，难以实用。本文系统研究了高阶U统计量的精确计算复杂性，并提出一套兼具理论深度与工程可行性的新方法。首先，建立了一种将m阶U统计量分解为若干阶数不超过m的V统计量线性组合的通用代数结构，显著降低计算冗余；其次，揭示了V统计量精确计算与爱因斯坦求和（Einstein summation）之间的本质联系，将U/V统计量求值问题转化为张量收缩问题；进而，引入图论工具——特别是基于U统计量核函数构造的关联图及其树宽（treewidth），给出了计算复杂度的乐观上界估计，表明当核具有可分解结构时，时间复杂度可大幅低于O(n^m)。基于上述理论，设计出一种高效、通用的精确计算算法，并开源跨语言软件包u-stats（支持Python与R，兼容CPU/GPU）。在因果推断中的高阶影响函数（HOIF）估计、网络 motif 计数及距离协方差计算三个典型统计任务上的实验表明，u-stats相较现有基准工具实现数量级级别的加速。本工作不仅填补了U统计量计算复杂性研究的空白，也为统计软件生态提供了首个面向高阶U统计量的通用计算基础设施，有望推动其在实际研究与工业场景中的广泛应用。