Incomplete U-statistics have been proposed to accelerate computation. They use only a subset of the subsamples required for kernel evaluations by complete U-statistics. This paper gives a finite sample bound in the style of Bernstein's inequality. Applied to complete U-statistics the resulting inequality improves over the bounds of both Hoeffding and Arcones. For randomly determined subsamples it is shown, that, as soon as the their number reaches the square of the sample-size, the same order bound is obtained as for the complete statistic.

翻译：推荐了不完整的 U- Statistic 来加速计算。 它们只使用完整的 U- Statistics 进行内核评价所需的子样子子集。 本文给出了一个以 Bernstein 不平等为风格的有限样本。 用于完成 U- Statistics, 由此产生的不平等在Hoffding 和 Arcones 的界限上都有改善。 随机确定的子样集显示, 当其数量到达样本大小的正方形时, 就会获得与完整统计数据相同的定序 。