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

arXiv: https://arxiv.org/abs/2606.00661 · HTML: https://mlsanity.com/paper/2606.00661/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 44 references that are in the map.
- First posted on arXiv 30 May 2026.

## Builds on (most cited first, 8 of 8)

- [Sub-Gaussian estimators of the mean of a random vector](https://mlsanity.com/paper/1702.00482/) (2017)
- [Scaling-up Empirical Risk Minimization: Optimization of Incomplete U-statistics](https://mlsanity.com/paper/1501.02629/) (2015)
- [Randomized incomplete U-statistics in high dimensions](https://mlsanity.com/paper/1712.00771/) (2017)
- [Approximating high-dimensional infinite-order U-statistics: statistical and computational guarantees](https://mlsanity.com/paper/1901.01163/) (2019)
- [Generalization Analysis for Supervised Contrastive Representation Learning under Non-IID Settings](https://mlsanity.com/paper/2505.04937/) (2025)
- [Concentration Inequalities for Two-Sample Rank Processes with Application to Bipartite Ranking](https://mlsanity.com/paper/2104.02943/) (2021)
- [On Medians of (Randomized) Pairwise Means](https://mlsanity.com/paper/2211.00603/) (2022)
- [A Refined Generalization Analysis for Extreme Multi-class Supervised Contrastive Representation Learning](https://mlsanity.com/paper/2605.07596/) (2026)

## Abstract (arXiv)

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.