Back To Index Previous Article Next Article Full Text

Statistica Sinica 31 (2021), 1593-1618

DESIGN BASED INCOMPLETE U-STATISTICS

Xiangshun Kong and Wei Zheng

Beijing Institute of Technology and University of Tennessee

Abstract: U-statistics are widely used in fields such as economics, machine learning, and statistics. However, while they enjoy desirable statistical properties, they have an obvious drawback in that the computation becomes impractical as the data size n increases. Specifically, the number of combinations, say m, that a U-statistic of order d has to evaluate is O(nd) . Many efforts have been made to approximate the original U-statistic using a small subset of combinations since Blom (1976), who referred to such an approximation as an incomplete U-statistic. To the best of our knowledge, all existing methods require m to grow at least faster than n, albeit more slowly than nd, in order for the corresponding incomplete U-statistic to be asymptotically efficient in terms of the mean squared error. In this paper, we introduce a new type of incomplete U-statistic that can be asymptotically efficient, even when m grows more slowly than n. In some cases, m is only required to grow faster than vn. Our theoretical and empirical results both show significant improvements in the statistical efficiency of the new incomplete U-statistic.

Key words and phrases: Asymptotically efficient, BIBD, big data, design of experiment, subsampling.

Back To Index Previous Article Next Article Full Text