Incomplete U-Statistics of Equireplicate Designs: Berry-Esseen Bound and Efficient Construction

2026-07-14 · Source: stat.ML updates on arXiv.org · Field: Science & Research — Mathematics & Computational Sciences, Artificial Intelligence & Machine Learning · Depth: Expert, medium

Summary

A novel perspective on U-statistics, grounded in hypergraph theory and combinatorial designs, addresses the high computational cost of U-statistics via incomplete U-statistics and their non-standard asymptotic behavior in degenerate cases. The authors derive a Berry–Esseen bound for all incomplete U-statistics of deterministic designs, establishing conditions for Gaussian limiting distributions even in degenerate cases and when the order diverges, bypassing the traditional Hoeffding decomposition. They also present efficient algorithms for constructing incomplete U-statistics of equireplicate designs, which can achieve minimum variance. The framework is applied to kernel-based tests like Maximum Mean Discrepancy (MMD) and Hilbert–Schmidt Independence Criterion (HSIC). A permutation-free MMD test on CIFAR-10 data showed substantial computational gains while maintaining power and type I error control.

Key takeaway

For research scientists developing or applying U-statistics for nonparametric inference or machine learning, this work provides a critical advancement. You can now establish Gaussian limiting distributions for incomplete U-statistics, even in degenerate cases, by leveraging hypergraph theory and efficient equireplicate design construction. This enables permutation-free kernel tests like MMD, offering substantial computational gains and improved statistical validity without sacrificing power or type I error control. Consider adopting these methods to enhance the efficiency and reliability of your statistical procedures.

Key insights

A hypergraph-theoretic approach enables Gaussian limiting distributions for incomplete U-statistics, even in degenerate cases.

Principles

• U-statistics' dependence structure can be characterized by the line graph of the design hypergraph.
• Asymptotic normality can be achieved for incomplete U-statistics under specific hypergraph degree and order conditions.
• Equireplicate designs can achieve minimum variance for incomplete U-statistics.

Method

Characterize U-statistic dependence via the line graph of the design hypergraph. Derive Berry-Esseen bounds using Stein's method. Construct incomplete U-statistics using efficient algorithms for equireplicate designs.

In practice

• Apply permutation-free MMD tests for computational gains in kernel-based testing.
• Use equireplicate designs to construct minimum variance incomplete U-statistics for k=2.
• Control maximum degree of design hypergraph for asymptotic normality.

Topics

• U-statistics
• Incomplete U-statistics
• Hypergraph Theory
• Berry-Esseen Bound
• Equireplicate Designs
• Kernel Methods

Code references

• CaesarXVII/IUstat_equireplicate_designs

Best for: AI Scientist, Research Scientist

Related on AIssential

• Testing Distributions Against Bounded Distinguishers — The paper introduces "identity testing with respect to fooling distance" for high-dimensional distribution comparison.
• History estimation in random recursive trees: Pointwise approach via iterated Jordan centralities — Estimating vertex arrival times in random recursive trees involves a tradeoff between overestimation and underestimation tail performance.
• Hypergraph Neural Stochastic Diffusion: An SDE Framework for Uncertainty Estimation — HyperNSD employs a stochastic differential equation framework to intrinsically quantify predictive uncertainty in hypergraphs by modeling representations as evolving stochastic processes.
• Computationally sufficient statistics for Ising models — Learning Ising models from limited statistics is feasible by approximating gradients with polynomials up to $O(\gamma)$ order.
• Lipschitzian SLLNs for random functions — New SLLNs for Lipschitz functions define conditions preventing previously observed statistical failures.
• Accelerating Constrained Sampling: A Large Deviations Approach — A specific skew-symmetric matrix design for SRNLD accelerates constrained sampling and reduces asymptotic variance.

See Counsel's argued verdicts on the open AI decisions leaders are weighing →

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by stat.ML updates on arXiv.org.