On Finite-sample Concentration of Median of Incomplete U-Statistics

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-textitrandomized-U-Statistics (MoRU) and median-of-textitincomplete-U-Statistics (MoIU) for estimating expectations of heavy-tailed pairwise kernels. In citetpmlr-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.