论文标题
强大而重尾的平均估计使遗憾最小化变得简单
Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization
论文作者
论文摘要
我们研究了当样品被对抗损坏或分布重尾时，估计高维度分布的平均值的问题。强大统计数据的最新发展已经确立了两种设置的有效且（接近）的最佳程序。但是，两侧开发的算法往往是复杂的，并且不会直接转移到其他方面，其中许多具有临时或复杂的分析。 在本文中，我们提供了一个元问题和二元定理，该定理导致对高度强大而重尾平均估计的新统一观点。我们表明，由于dong，Hopkins和Li（Neurips '19），可以通过最近有关强大估计的过滤算法或量子熵评分方案（QUE）来解决元问题。通过利用我们的二元定理，这些结果转化为可靠和重尾设置的简单有效算法。此外，基于QUE的过程具有运行时，它匹配这两个方面最快的已知算法。 我们对过滤器的分析是通过乘法权重更新方法的经典遗憾结合。这种连接使我们能够避免以前的工作中的技术并发症，并在基于梯度的算法对Cheng，Diakonikolas，GE和Soltanolkotabi（ICML '20）进行稳健平均估计的运行时分析进行改进。
We study the problem of estimating the mean of a distribution in high dimensions when either the samples are adversarially corrupted or the distribution is heavy-tailed. Recent developments in robust statistics have established efficient and (near) optimal procedures for both settings. However, the algorithms developed on each side tend to be sophisticated and do not directly transfer to the other, with many of them having ad-hoc or complicated analyses. In this paper, we provide a meta-problem and a duality theorem that lead to a new unified view on robust and heavy-tailed mean estimation in high dimensions. We show that the meta-problem can be solved either by a variant of the Filter algorithm from the recent literature on robust estimation or by the quantum entropy scoring scheme (QUE), due to Dong, Hopkins and Li (NeurIPS '19). By leveraging our duality theorem, these results translate into simple and efficient algorithms for both robust and heavy-tailed settings. Furthermore, the QUE-based procedure has run-time that matches the fastest known algorithms on both fronts. Our analysis of Filter is through the classic regret bound of the multiplicative weights update method. This connection allows us to avoid the technical complications in previous works and improve upon the run-time analysis of a gradient-descent-based algorithm for robust mean estimation by Cheng, Diakonikolas, Ge and Soltanolkotabi (ICML '20).
