On Finite-sample Concentration of Median of Incomplete U-Statistics
Abstract
Median-of-means (MoM) is a powerful technique that theoretically enables near sub-Gaussian finite-sample rate for parameter estimation when the underlying data distribution is heavy-tailed (e.g., assumed to have only two first finite moments). A recent work has extrapolated this technique to median-of-\textit{randomized}-U-Statistics (MoRU) and median-of-\textit{incomplete}-U-Statistics (MoIU) for estimating expectations of heavy-tailed pairwise kernels. In \citet{pmlr-v97-clemencon19a}, a concentration rate that scales like O(n−1/2) with sample size has been proven for MoRU. However, despite the computational advantage of the latter, the analysis of finite-sample bound for MoIU remains a significant theoretical challenge. As noted by the authors, a straightforward application of McDiarmid's inequality yields a loose bound of order O(n−1/4). In this work, we prove a finite-sample concentration bound for the MoIU estimator that scales as O(n−1/2) with respect to the sample size using a delicate convex decomposition approach. Furthermore, we show that our proof can be seamlessly extended to geometric median in multivariate settings. Using a Serfling-type argument, we extrapolate our results into a regime where data pairs are selected without replacement across blocks, breaking the usual block-wise independence condition. Then, using a Bernstein-type treatment for U-Statistics, we tighten the dependency of our bounds on the margin τ from O(τ−3/2) achieved in the previous work to O(τ−1). Finally, we proved anti-concentration results that is applicable for all median estimators presented in this work to demonstrate that M≤ O(n) is an intrinsic restriction on block sizes.
Related
- Thermodynamic Concentration Inequalities: Controlling Uncertainty in Finite-Time and Small-Sample Thermodynamic Inference
- The maximum concentration of results in incomplete round-robin tournaments
- Uniqueness, Cramér-Rao Efficiency and Concentration Bounds for Quantum U-Statistics
- Tracy Widom law for sample covariance matrices under quadratic form concentration
- High-Dimensional Two-Sample Inference via Marginal Likelihood-Ratio Rank Statistics
BibTeX
@misc{hieu2026finitesample,
title = {{On Finite-sample Concentration of Median of Incomplete U-Statistics}},
author = {Nong Minh Hieu and Antoine Ledent},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.00661},
eprint = {2606.00661},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.00661},
}
RIS
TY - UNPB
TI - On Finite-sample Concentration of Median of Incomplete U-Statistics
AU - Nong Minh Hieu
AU - Antoine Ledent
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2606.00661
UR - https://arxiv.org/abs/2606.00661
AB - Median-of-means (MoM) is a powerful technique that theoretically enables near sub-Gaussian finite-sample rate for parameter estimation when the underlying data distribution is heavy-tailed (e.g., assumed to have only two first finite moments). A recent work has extrapolated this technique to median-of-\textit{randomized}-U-Statistics (MoRU) and median-of-\textit{incomplete}-U-Statistics (MoIU) for estimating expectations of heavy-tailed pairwise kernels. In \citet{pmlr-v97-clemencon19a}, a concentration rate that scales like O(n^−1/2) with sample size has been proven for MoRU. However, despite the computational advantage of the latter, the analysis of finite-sample bound for MoIU remains a significant theoretical challenge. As noted by the authors, a straightforward application of McDiarmid's inequality yields a loose bound of order O(n^−1/4). In this work, we prove a finite-sample concentration bound for the MoIU estimator that scales as O(n^−1/2) with respect to the sample size using a delicate convex decomposition approach. Furthermore, we show that our proof can be seamlessly extended to geometric median in multivariate settings. Using a Serfling-type argument, we extrapolate our results into a regime where data pairs are selected without replacement across blocks, breaking the usual block-wise independence condition. Then, using a Bernstein-type treatment for U-Statistics, we tighten the dependency of our bounds on the margin τ from O(τ^−3/2) achieved in the previous work to O(τ^−1). Finally, we proved anti-concentration results that is applicable for all median estimators presented in this work to demonstrate that M≤ O(n) is an intrinsic restriction on block sizes.
ER -