  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(n^d)$. 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 $n^d$, 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 $\sqrt{n}$. Our theoretical and empirical results both show
significant improvements in the statistical efficiency of the new incomplete
U-statistic.
