提出新算法,可在强噪声下实现最优鲁棒均值估计。
Optimal Robust Estimation under Local and Global Corruptions: Stronger Adversary and Smaller Error
- 用切片Wasserstein度量建模更强局部扰动,突破旧方法限制。
- 在各向同性次高斯分布下达到信息论最优误差,且可多项式时间实现。
- 通用框架适用于未知污染形式的现实场景,适合鲁棒统计与机器学习研究者。
算法鲁棒统计传统上关注小部分样本被任意破坏的污染模型。本文研究一种结合两类噪声的新模型:(i) 少数任意异常值,如经典鲁棒统计;(ii) 局部扰动,即样本平均有界偏移。尽管两类噪声各自已充分理解,但联合模型带来新的算法挑战,目前仅部分结果可知。现有高效算法存在两方面局限:(i) 仅适用于弱局部扰动定义,(ii) 对各向同性次高斯分布的误差非最优。这一限制促使[NGS24, COLT'24]推测改进误差可能计算上困难。令人意外的是,我们证明在更强的局部扰动模型(采用切片Wasserstein度量而非标准Wasserstein度量)下,仍可在多项式时间内实现信息论最优误差。分析揭示,所有基于稳定性的鲁棒均值估计器可黑盒适配该联合模型。该泛化在实际中极具价值,因真实数据污染形式常未知。此外,我们还给出了联合模型下的分布学习与主成分分析的高效算法。
原文摘要 · Abstract (English)
Algorithmic robust statistics has traditionally focused on the contamination model where a small fraction of the samples are arbitrarily corrupted. We consider a recent contamination model that combines two kinds of corruptions: (i) small fraction of arbitrary outliers, as in classical robust statistics, and (ii) local perturbations, where samples may undergo bounded shifts on average. While each noise model is well understood individually, the combined contamination model poses new algorithmic challenges, with only partial results known. Existing efficient algorithms are limited in two ways: (i) they work only for a weak notion of local perturbations, and (ii) they obtain suboptimal error for isotropic subgaussian distributions (among others). The latter limitation led [NGS24, COLT'24] to hypothesize that improving the error might, in fact, be computationally hard. Perhaps surprisingly, we show that information theoretically optimal error can indeed be achieved in polynomial time, under an even \emph{stronger} local perturbation model (the sliced-Wasserstein metric as opposed to the Wasserstein metric). Notably, our analysis reveals that the entire family of stability-based robust mean estimators continues to work optimally in a black-box manner for the combined contamination model. This generalization is particularly useful in real-world scenarios where the specific form of data corruption is not known in advance. We also present efficient algorithms for distribution learning and principal component analysis in the combined contamination model.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。