提出新方法在异常值占比接近50%时仍能高效准确估计均值。
Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares
- 用平方和证明系统重构可识别性，聚焦分布重叠而非距离。
- 在ε∈[0,1/2)范围内实现最优误差率且运行时间多项式。
- 适合高维数据中抗极端异常值的统计估计场景。
我们重新研究高维分布中存在ε比例对抗性异常值时的均值估计问题。当ε不超过某个充分小的常数时，已有方法能高效达到最优误差率。但随着ε趋近于崩溃点1/2，此前所有算法要么误差率次优，要么运行时间指数级增长。本文对文献中经典的平方和规划进行新分析，证明该规划可在所有ε∈[0,1/2)范围内高效实现最优误差率。核心创新在于提出一种新可识别性证明，关注分布间的重叠而非统计距离，并将其嵌入平方和证明系统，从而通过平方和证明到算法的范式获得高效算法。
原文摘要 · Abstract (English)
We revisit the problem of estimating the mean of a high-dimensional distribution in the presence of an $\varepsilon$-fraction of adversarial outliers. When $\varepsilon$ is at most some sufficiently small constant, previous works can achieve optimal error rate efficiently \cite{diakonikolas2018robustly, kothari2018robust}. As $\varepsilon$ approaches the breakdown point $\frac{1}{2}$, all previous algorithms incur either sub-optimal error rates or exponential running time. In this paper we give a new analysis of the canonical sum-of-squares program introduced in \cite{kothari2018robust} and show that this program efficiently achieves optimal error rate for all $\varepsilon \in[0,\frac{1}{2})$. The key ingredient for our results is a new identifiability proof for robust mean estimation that focuses on the overlap between the distributions instead of their statistical distance as in previous works. We capture this proof within the sum-of-squares proof system, thus obtaining efficient algorithms using the sum-of-squares proofs to algorithms paradigm \cite{raghavendra2018high}.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。