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. Then, we extrapolate our results into different block sampling schemes including the regime where data pairs are selected without replacement across blocks, breaking the usual block-wise independence condition. Finally, we use similar techniques to extend our proofs to the concentration of geometric median for vector-valued kernels.
From: Minh Hieu Nong [view email]
[v1]
Sat, 30 May 2026 10:22:15 UTC (8 KB)
[v2]
Thu, 20 Aug 2026 20:06:56 UTC (30 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。