提出不完整U统计量中位数的有限样本收敛界，达到最优速率。
On Finite-sample Concentration of Median of Incomplete U-Statistics
- 基于随机分块构造不完整U统计量中位数估计器。
- 证明其收敛速率达O(n⁻¹/²)，优于传统方法的O(n⁻¹⁴)。
- 适用于重尾分布估计，适合关注鲁棒统计与计算效率的研究者。
中位数-均值（MoM）是一种强大技术，可在数据分布重尾（仅存在两个有限一阶矩）时实现接近次高斯的有限样本估计率。近期工作将该技术推广至随机化U统计量中位数（MoRU）和不完整U统计量中位数（MoIU），用于估计重尾成对核的期望。在文献中，已证明MoRU的收敛率可达到O(n⁻¹/²)。然而，尽管MoIU具有计算优势，其有限样本界分析仍面临重大理论挑战。作者指出，直接应用McDiarmid不等式仅能获得O(n⁻¹⁴)的松散界。本文首次证明了MoIU估计器的有限样本集中性界为O(n⁻¹/²)。进一步，我们将结果推广至多种分块采样方案，包括跨块无放回采样的情形，突破了传统分块独立性假设。最后，采用相似技巧将证明扩展至向量值核的几何中位数集中性分析。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。