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.

本文针对高维下平均数估计的稳健模型、对抗性污染和相应算法进行研究，提出了一种基于当前猜测值参数化的 SDP 族的自然算法，并经证明该算法在次线性时间内逼近真实平均数并达到了理论误差的信息论最优解，同时认为该算法还能进一步实现高维稳健学习问题的次线性时间算法。