WorksMathematics
Sharp upper and lower bounds on the variance of U-statistics
Abstract
For a U-statistic with a symmetric kernel of any rank, we offer new upper and lower bounds on its variance, which are uniformly sharper than those established in the classical paper by Hoeffding (1948, Theorem 5.2). Our new bounds have strong optimality properties and can tightly describe how the variance scales with the degree of the kernel. As an application, we leverage our new upper bound to improve an existing Berry-Esseen theorem for the normal approximation of incomplete U-statistics based on Bernoulli sampling, in a computationally frugal regime where the computational budget is much smaller than the available sample size.
Introduction
Let be independent and identically distributed sample points taking values in a measurable space , and be a measurable real-valued function symmetric in its arguments, i.e. for any permutation of the indices . For , in his seminal paper, Hoeffding [2] introduced the U-statistic
that averages the evaluations of the kernel function over all possible subsets of distinct sample points. Throughout, for any natural number , we will adopt the shorthand ; moreover, given a function in arguments in and another natural number , we will use , , and as respective shorthands for , and . We will assume that , so that is not always trivially equal to its expectation .
The structure of the variance of is well understood. For any , let
be the centered conditional expectation of by fixing of its arguments, and
be the recursively defined canonical projection function of . Define the second moment quantities
for every . The two exact variance formulas
are standard results in the U-statistic literature ([4 Chapter 1]. We also remark that by definition.
Nevertheless, instead of the exact forms in (5) and (6), it is sometimes more instructive to work with bounds on , particularly when one demands a more transparent understanding of how scales with the kernel degree . In this article, we will contribute new bounds on that are sharp, which we believe will be useful for future research on the theory of U-statistics, an area that has proven to be fertile even after nearly 8 decades since the work by Hoeffding [2].
Main results
Hoeffding [2] (Theorem 5.2) established that, if the kernel is of rank at least , then
for the constant
The rank of a kernel (or of the corresponding U-statistic) is defined to be the smallest integer such that and ; it is well-defined, because it must be true that as an easy consequence of Jensen’s inequality. Alternatively, for any , using the well-known identities that
and
the rank can be equivalently defined as the smallest such that and .2 In the literature, a kernel of rank 1 is said to be non-degenerate, and a kernel of rank is said to be completely degenerate.
Rather surprisingly, in this article we illustrate that the classical inequalities in (7) are actually suboptimal. Our main contributions are the following upper and lower bounds on that are uniformly sharper than (7), which are proven in Appendix A.
Theorem 1 (Sharper variance bounds on U-statistics). Suppose is a -statistic defined as in (1) of rank at least and . Then
for the constant
Moreover, these two properties hold:
(i) It is true that
and each inequality in (13) becomes an equality if and only if .
(ii) Each inequality in (11) is an equality if and only if .
We assume in Theorem 1 to exclude the mathematically uninteresting case , in which the variance upper bounds in both (7) and (11) trivially become equalities as and . Property (i) in Theorem 1 says that our bounds in (11) are strictly sharper than those in (7) by having better constants, except when the kernel is non-degenerate or completely degenerate; it is established through a neat argument that expresses both and in terms of the same hypergeometric random variable and exploits its binomial moments; see (A.11) and (A.12).
To further illustrate the optimality of our result, property (ii) in Theorem 1 says that both inequalities in (11) can be attained when is the only non-vanishing quantity among all of , that is, when is entirely comprised of the -th component in its canonical decomposition [4 p.24] and therefore, upon centering by its mean , has the form
An example of a kernel that can give rise to (14) is as follows. Let be a (measurable) function such that and , and define the mean-zero kernel
For instance, if is a set such that and , then and . In Appendix § 7, we will show that a U-statistic based on the kernel above satisfies (14).
To the best of our knowledge, Theorem 1 is new. That being said, a prototype of our upper bound on in (11) has been hinted by Peng et al. [6], who set out to improve upon the Berry-Esseen theorem for a non-degenerate stated in Chen et al. [1]. In this latter line of work, a key step is to bound the variance of the Hájek projection remainder of
which is itself a U-statistic constructed with the kernel and is of rank at least 2. Peng et al. [6] applied a bound qualitatively comparable to our upper bound in (11) to get
On the contrary, Chen et al. [1] have effectively applied Hoeffding [2]’s upper bound in (7) at on , and their subsequent arguments [1 p.284-286], which show the inequality
will further lead to the bound , which is fundamentally looser than (16) with respect to order in . As a result, among other things, the Berry-Esseen bound for in Peng et al. [6] is superior to the one in Chen et al. [1] by exhibiting a tighter dependence on the degree . The proof of our upper bound in (11) essentially sharpens Peng et al. [6]’s arguments and generalizes them for a U-statistic of any arbitrary rank. In § 3, we will further leverage this new upper bound to improve an existing Berry-Esseen theorem for incomplete U-statistics with Bernoulli sampling.
We have also developed the proposition below (proven in Appendix § 8) to illustrate some properties of the constant , particularly how it scales with the kernel degree :
Proposition 1 (Further properties of the constant ). The following inequalities are true:
(i) For any ,
(ii) Suppose . For any ,
where denotes the falling factorial .
Proposition 1(i) should intuitively make sense to the reader once we rewrite the constant as
it suggests that for a fixed , is of the order . To understand Proposition 1(ii), first note that it is always true that , which simply rephrases the first inequality in (13). Therefore, (19) can be understood as a “reverse” of the latter inequality via adjustment by the factor . However, when is held fixed and , the factor is very close to 1, which suggests that is approximately larger than by a factor of . Indeed, it is no coincidence that only an upper bound of the order can be established for as in (17) by Chen et al. [1], which is looser than the tighter bound of the order suggested by (18) at .
Application to Berry-Esseen theorems for incomplete U-statistics with a small Bernoulli sampling budget
Let , and for a positive integer , define . Suppose are independent and identically distributed Bernoulli random variables such that , and that they are also independent of all the sample points . Let be the count of how many of these Bernoulli random variables realize as a “1”. For a kernel with a large degree , instead of in (1) which sums over all kernel evaluations, to achieve computational savings one can construct the incomplete U-statistic with Bernoulli sampling
where we have used the shorthand for any ; by convention, is set to be zero when . Because only approximately a fraction of all the Bernoulli samplers in (21) will be “switched on”, sums over many fewer kernel evaluations than , particularly when the computational budget is small.
The normal convergence behavior of has been well-studied. In particular, if is the rank of the kernel , it has been established that, for a fixed ,
converges in distribution to the standard normal as with ; (22)
see Leung [5] which has its roots in Janson [3]. Note that the asymptotic regime here suggests a computationally frugal situation where could be much less than . Leung [5] also developed a Berry-Esseen theorem to gauge the normal approximating accuracy in terms of Kolmogorov distance for the weak convergence in (22). Turns out, the said Berry-Esseen theorem can be further improved with our new upper bound on in (11). Below, we will first state the improved theorem, and then explain how it has improved upon its predecessor Leung [5]; we will use to denote the standard normal distribution function.
Corollary 1 (Improved Berry-Esseen theorem for the normal convergence in (22)). Let be constructed as in (21) with a symmetric kernel of rank on . Suppose that
and hold. Then, there exists an absolute constant such that
As is customary in the literature on Berry-Esseen theorems for U-statistics, we have made the mean zero assumption in (22) only to avoid cluttering the notation in our bound (23); obviously, one could present the theorem in terms of the centered kernel without making this assumption. Moreover, similarly to Leung [5], a version of the result with the milder finite third moment assumption can also be stated, but we have opted to only present the notationally cleaner result (23) under the finite fourth moment assumption for the purpose of illustration.
The original Berry-Esseen bound in Leung [5] is essentially the same as (23) except that the quantity was in the place of ; indeed, as explained in Appendix § 9, the proof of Corollary 1 is only a minor modification of that of Leung [5] by making use of the new upper bound in (11). As such, when , our Berry-Esseen bound (23) is now tighter, not only because is smaller than as per property (i) in Theorem 1, but also because it is smaller than it by approximately a factor of order for a fixed as , as per (19). The latter is an important attribute for modern applications of incomplete U-statistics such as uncertainty inference in random forests, where the degree corresponds to the subsample size for growing each tree, which is typically quite large; we refer the readers to Leung [5] which contains more related discussion.
Acknowledgments
This research is partially funded by the Manchester-Melbourne-Toronto Research Fund. Dennis Leung would also like to thank Dr. Yuta Koike for some helpful discussion during the early stage of this project.
Declaration of generative AI and AI-assisted technologies in the manuscript preparation process.
During the preparation of this work, the first author (K.N.) used Claude (Anthropic) to assist in refining and verifying certain mathematical arguments and calculations, while the last author (D.L.) used Codex (OpenAI) to assist with some final edits. The authors independently verified all mathematical statements and proofs, and take full responsibility for the content of the published article.
Proof of Theorem 1
From (6), we can first write the variance of as
where (A.1) is true because
as the rank of is at least , and (A.2) is true because
which can be seen by taking in (9) and using (A.3).
Under , for any , which implies
In light of (A.5), one can deduce from (A.1) that
where the last equality in (A.6) comes from (9), (A.3) and (A.4). On the other hand, from (A.2), one can immediately see that
Not only do the inequalities (A.6) and (A.7) together imply (11), but it is also easy to see that each of them precisely becomes an equality if and only if , which proves the property (ii).
It remains to show property (i). To that end, we will exploit expressions of and in terms of hypergeometric random variables, as well as an elementary result on the binomial moments of hypergeometric distributions [8 Eq. (93]: If is a Hypergeometric random variable, i.e. it is the number of successes in draws without replacement, out of a finite population of size containing successes, then
We will first prove
as well as the fact that
From the definition of in (8) and , we can first write
On the other hand, using the definition of in (12) and formula (A.8), we have
Since by definition, it is always true that ; therefore, it is always true that
which proves (A.9) by comparing the rightmost expectations in (A.11) and (A.12). Moreover, it is easy to see that (A.13) becomes an equality when , so the “if” part of (A.10) is proved. When , on the event which has a strictly positive probability, (A.13) becomes a strict inequality because , which proves the “only if” part of (A.10) by comparing (A.11) and (A.12) again.
Next, we will prove , which is equivalent to
as well as the fact that
in an analogous manner. The rightmost expression of in (A.12) readily gives
Since it is always true that on the event , we have
which proves (A.14) by comparing the expectations in (A.11) and (A.16). Moreover, it is easy to see that (A.17) becomes an equality when , so the “if” part of (A.15) is proved. When , on the event which has a strictly positive probability, we have , so (A.17) becomes a strict inequality, which proves the “only if” part of (A.15) by comparing (A.11) and (A.16) again.
Collecting (A.9), (A.10), (A.14) and (A.15) proves the property (i), and we are done.
Proof that the kernel in (15) satisfies (14)
In this section, all the special functions in (2) and (3) and moment quantities in (4) mentioned are defined with respect to the specific kernel . Note that because
as per their recursive definitions in (3), because it is easy to see that for the kernel and any . To show that , because of (B.1), one first notes that , and so . Further, by exploiting independence, via direct calculations it must be true that
In light of the generic formula for in (9), the above display is only true when all the vanish.
Proof of Proposition 1
We first prove (i). The upper bound in (18) follows from (20) since when . Moreover, since any is at most in (20), we have , and the lower bound in (18) follows. Now we prove (ii). It suffices to show
because the term on the right hand side of (C.1) is the term at of the sum defining in (8). Since , we have
and our proof of (C.1) is done.
Proof of Corollary 1
The proof is almost word for word the same as the proof of Leung [5]; one simply has to replace all the occurrences of in the proof of Leung [5] with . For the interested reader who will explore the fine details in Leung [5], we briefly explain why such simple replacements suffice below.
The proof of Leung [5] relies on a technical result stated in Leung [5], whose proof in Leung [5] in turn uses that , which is simply Hoeffding [2]’s upper bound in (7) under (22). Obviously, by our new upper bound in (11), it is also true that , so can be supplanted. Another place where shows up in the original proof of Leung [5] is at Leung [5], where the inequality is employed. However, it is certainly also true that , so can be supplanted there as well.
References
- [1]Chen, L.H.Y., Goldstein, L., Shao, Q.M., 2011. Normal Approximation by Stein’s Method. Probability and its Applications, Springer, Heidelberg. doi:10.1007/978-3-642-15007-4.DOI
- [2]Hoeffding, W., 1948. A class of statistics with asymptotically normal distribution. The Annals of Mathematical Statistics 19, 293–325. doi:10.1214/aoms/1177730196.
- [3]Janson, S., 1984. The asymptotic distributions of incomplete u-statistics. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 66, 495–505.DOI
- [4]Koroljuk, V.S., Borovskich, Y.V., 1994. Theory of U-statistics. volume 273 of Mathematics and its Applications. Kluwer Academic Publishers Group, Dordrecht. Translated from the 1989 Russian original by P. V. Malyshev and D. V. Malyshev and revised by the authors.
- [5]Leung, D., 2026. Berry–Esseen theorems for the asymptotic normality of incomplete U-statistics with Bernoulli sampling. Electronic Journal of Probability 31, Article no. 17, 1–52. doi:10.1214/26-EJP1473.DOI
- [6]Peng, W., Coleman, T., Mentch, L., 2022. Rates of convergence for random forests via generalized U-statistics. Electronic Journal of Statistics 16, 232–292. doi:10.1214/21-EJS1958.DOI
- [7]Pitman, J., 1993. Probability. Springer Texts in Statistics, Springer-Verlag, New York. doi:10.1007/978-1-4612-4374-8.DOI
- [8]Pitman, J., 2001. Random mappings, forests, and subsets associated with abel-cayley-hurwitz multinomial expansions. Séminaire Lotharingien de Combinatoire [electronic only] 46, B46h–45.