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

Xingyu Chen, Ruiqi Zhang, Lin Liu

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 t…