Outlier-robust moment-estimation via sum-of-squares
Outlier-robust moment-estimation via sum-of-squares
复制标题
通过平方和进行异常值稳健矩估计
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
David Steurer
中科院分区：
文献类型：
--
作者：
Pravesh Kothari;David Steurer
我们开发了高效算法，用于在存在对抗性异常值的情况下估计未知分布的低阶矩。在许多情况下，我们算法的保证相较于之前由迪亚科尼科拉斯等人、赖等人以及查里卡尔等人在近期工作中所获得的最佳结果有了显著提高。我们还表明，对于我们所考虑的分布类别，我们算法的保证与信息论下界相匹配。这些改进的保证使我们能够在存在异常值的情况下，为独立成分分析和学习高斯混合模型给出改进的算法。
我们的算法基于对以下概念上简单的优化问题的标准平方和松弛：在所有矩与未知分布以相同方式有界的分布中，找到在统计距离上与受对抗性破坏的样本的经验分布最接近的那个分布。
We develop efficient algorithms for estimating low-degree moments of unknown distributions in the presence of adversarial outliers. The guarantees of our algorithms improve in many cases significantly over the best previous ones, obtained in recent works of Diakonikolas et al, Lai et al, and Charikar et al. We also show that the guarantees of our algorithms match information-theoretic lower-bounds for the class of distributions we consider. These improved guarantees allow us to give improved algorithms for independent component analysis and learning mixtures of Gaussians in the presence of outliers.
Our algorithms are based on a standard sum-of-squares relaxation of the following conceptually-simple optimization problem: Among all distributions whose moments are bounded in the same way as for the unknown distribution, find the one that is closest in statistical distance to the empirical distribution of the adversarially-corrupted sample.
DOI：
10.1137/1.9781611975031.171
发表时间：
2017-04
期刊：
ArXiv
影响因子：
--
作者：
Ilias Diakonikolas;Gautam Kamath;D. Kane;Jerry Li;Ankur Moitra;Alistair Stewart
通讯作者：
Ilias Diakonikolas;Gautam Kamath;D. Kane;Jerry Li;Ankur Moitra;Alistair Stewart
DOI：
--
发表时间：
2017-03
期刊：
--
影响因子：
--
作者：
Ilias Diakonikolas;Gautam Kamath;D. Kane;Jerry Li;Ankur Moitra;Alistair Stewart
通讯作者：
Ilias Diakonikolas;Gautam Kamath;D. Kane;Jerry Li;Ankur Moitra;Alistair Stewart