PreprintCC BY 4.0arXiv
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.
Related
- Accumulated-Variance Functionals of Hidden Markov and Semi-Markov Processes: Finite-Sample Upper and Lower Bounds
- The upper bounds on occupancy fraction and variance fraction for linear regular uniform hypergraphs
- Variance lower bounds for geometric functionals of rotationally invariant log-concave random polytopes
- Explicit upper and lower bounds on certain functions related to ζ(s) for s>1
- Upper and lower bounds for heat kernels with very strong degeneracy
BibTeX
@misc{nikoo2026sharp,
title = {{Sharp upper and lower bounds on the variance of U-statistics}},
author = {Kiarash Nikoo and Liqian Zhang and Dennis Leung},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.01690},
eprint = {2611.01690},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.01690},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Sharp upper and lower bounds on the variance of U-statistics
AU - Kiarash Nikoo
AU - Liqian Zhang
AU - Dennis Leung
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.01690
UR - https://arxiv.org/abs/2611.01690
AB - 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.
ER -