提出非凸块-Lp估计，实现更优的鲁棒性，逼近理想最优解。
Median-of-Means as an Extremal Convex Estimator and a Nonconvex Route to the Trimmed Oracle
- 引入p∈(0,1)的非凸块-Lp估计方法，提升抗重尾与对抗污染能力。
- 在有限样本下，全局极小值的鲁棒性界随p减小逼近理想最优常数1/(1−ε)。
- 算法具有良性优化景观，适合高维鲁棒均值估计与稀疏回归任务。
本文从确定性优化视角重新审视中位数-均值估计，提出一类用于处理重尾和对抗性污染数据的块-Lp估计器。在至少存在1−ε比例良好块的块污染模型下，证明任意凸块M-估计器的最坏情况鲁棒性常数至少为1/(1−2ε)，该界与经典中位数-均值结果一致，表明凸类无法达到理想的修剪块最优常数1/(1−ε)。随后引入p∈(0,1)的非凸块-Lp族，并推导出所有全局最小值的有限样本确定性鲁棒界。随着p从1减小至0，这些界连续逼近修剪块最优常数。在足够小的p下，全局最小值与理想最优解一致（在温和分离条件下）。同时证明块-Lp目标函数具有良性优化景观：所有局部极小值均接近真实值，且无劣质吸引域。结合块级浓度不等式，可在仅存在二阶矩2+δ的条件下获得次高斯偏差界，并拓展至高维鲁棒均值估计与稀疏回归。
原文摘要 · Abstract (English)
We revisit median-of-means estimation from a deterministic optimization viewpoint and develop a family of block-Lp estimators for robust learning with heavy-tailed and adversarially corrupted data. In a block contamination model with at least a fraction 1 minus epsilon of good blocks, we first show that every convex block M-estimator has worst-case robustness constant at least 1 divided by 1 minus 2 epsilon. This matches the classical median-of-means bound and proves that the trimmed-block oracle constant 1 divided by 1 minus epsilon cannot be attained within the convex class. We then introduce a nonconvex block-Lp family for p between 0 and 1 and derive finite-sample deterministic robustness bounds for all global minimizers. As p decreases from 1 toward 0, these bounds continuously approach the trimmed-block oracle constant. For sufficiently small p, the global minimizers coincide with those of the oracle under a mild separation condition. We also show that the block-Lp objectives have a benign landscape, with all local minima remaining close to the truth and no bad basins. Combining these results with block-level concentration yields sub-Gaussian deviation bounds under finite 2 plus delta moments and high-dimensional extensions to robust mean estimation and sparse regression.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。