High-Dimensional Robust Mean Estimation in Nearly-Linear Time
High-Dimensional Robust Mean Estimation in Nearly-Linear Time
复制标题
DOI：
10.1137/1.9781611975482.171
复制
发表时间：
2018-11
期刊：
影响因子：
--
通讯作者：
Yu Cheng;Ilias Diakonikolas;Rong Ge
中科院分区：
文献类型：
--
作者：
Yu Cheng;Ilias Diakonikolas;Rong Ge
我们研究了一个稳健模型中的高维均值估计的基本问题，该模型的样本中含有一定比例的逆污染样本。最近的工作给出了几类结构分布族的第一个多项式时间算法，该算法具有与维度无关的误差保证。在这项工作中，我们给出了高维稳健均值估计的第一个近线性时间算法。具体地说，我们关注具有(I)已知协方差和亚高斯尾部，以及(Ii)未知有界协方差的分布。给出$\mathbb{R}^d$上的$N$样本，其中的$\epsilon$-部分可能被任意破坏，我们的算法在时间上运行，并且逼近信息内的真实平均值--理论上最优误差，直到常数因子。以前的健壮算法具有相当的误差保证，对于$\epsilon=\omega(1)$，其运行时间为$\tide{\omega}(N d^2)$。我们的算法依赖于一个自然的SDP族，这个族由我们目前对未知平均值$\MU^\STAR$的猜测$\nu$来参数化。我们给出了一个双赢分析，建立了以下结论：要么是原始SDP的近最优解产生了一个很好的候选者$\MU^\STAR$--独立于我们目前的猜测$\nU$--要么是对偶SDP产生了一个新的猜想$\nU‘$，它与$\MU^\STAR$的距离是一个常量因子。我们利用相应SDP的特殊结构来证明它们在近线性时间内是近似可解的。我们的方法是非常通用的，我们相信它也可以用于获得其他高维鲁棒学习问题的近线性时间算法。
We study the fundamental problem of high-dimensional mean estimation in a robust model where a constant fraction of the samples are adversarially corrupted. Recent work gave the first polynomial time algorithms for this problem with dimension-independent error guarantees for several families of structured distributions. In this work, we give the first nearly-linear time algorithms for high-dimensional robust mean estimation. Specifically, we focus on distributions with (i) known covariance and sub-gaussian tails, and (ii) unknown bounded covariance. Given $N$ samples on $\mathbb{R}^d$, an $\epsilon$-fraction of which may be arbitrarily corrupted, our algorithms run in time $\tilde{O}(Nd) / \mathrm{poly}(\epsilon)$ and approximate the true mean within the information-theoretically optimal error, up to constant factors. Previous robust algorithms with comparable error guarantees have running times $\tilde{\Omega}(N d^2)$, for $\epsilon = \Omega(1)$. Our algorithms rely on a natural family of SDPs parameterized by our current guess $\nu$ for the unknown mean $\mu^\star$. We give a win-win analysis establishing the following: either a near-optimal solution to the primal SDP yields a good candidate for $\mu^\star$ -- independent of our current guess $\nu$ -- or the dual SDP yields a new guess $\nu'$ whose distance from $\mu^\star$ is smaller by a constant factor. We exploit the special structure of the corresponding SDPs to show that they are approximately solvable in nearly-linear time. Our approach is quite general, and we believe it can also be applied to obtain nearly-linear time algorithms for other high-dimensional robust learning problems.