Robust Sparse Estimation Tasks in High Dimensions
Robust Sparse Estimation Tasks in High Dimensions
复制标题
高维鲁棒稀疏估计任务
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Jerry Li
中科院分区：
文献类型：
--
作者：
Jerry Li
在本文中，我们开始研究稀疏估计任务是否可以在高维、在样本的 $\eps$ 部分被对抗性损坏的鲁棒设置中有效地执行。我们研究了两个经典稀疏估计问题的自然鲁棒版本，即尖峰协方差模型中的稀疏均值估计和稀疏 PCA。对于这两个问题，我们提供了第一个有效的算法，该算法在存在噪声的情况下提供非平凡的错误保证，仅使用与这些没有噪声的问题所需的数量相似的样本数量。特别是，我们的样本复杂度在环境维度 $d$ 中是次线性的。我们的工作还为这些问题（类似于无噪声的稀疏 PCA 的问题）提供了新的计算与统计差距的证据，这些问题仅在存在噪声的情况下出现。
In this paper we initiate the study of whether or not sparse estimation tasks can be performed efficiently in high dimensions, in the robust setting where an $\eps$-fraction of samples are corrupted adversarially. We study the natural robust version of two classical sparse estimation problems, namely, sparse mean estimation and sparse PCA in the spiked covariance model. For both of these problems, we provide the first efficient algorithms that provide non-trivial error guarantees in the presence of noise, using only a number of samples which is similar to the number required for these problems without noise. In particular, our sample complexities are sublinear in the ambient dimension $d$. Our work also suggests evidence for new computational-vs-statistical gaps for these problems (similar to those for sparse PCA without noise) which only arise in the presence of noise.
DOI：
--
发表时间：
2016-06
期刊：
--
影响因子：
--
作者：
Yu Cheng;Ilias Diakonikolas;D. Kane;Alistair Stewart
通讯作者：
Yu Cheng;Ilias Diakonikolas;D. Kane;Alistair Stewart
影响因子：
2.1
作者：
Witten, Daniela M.;Tibshirani, Robert;Hastie, Trevor
通讯作者：
Hastie, Trevor