We study the algorithmic problem of sparse mean estimation in the presence of
adversarial outliers. Specifically, the algorithm observes a \emph{corrupted}
set of samples from $\mathcal{N}(\mu,\mathbf{I}_d)$, where the unknown mean
$\mu \in \mathbb{R}^d$ is constrained to be $k$-sparse. A series of prior works
has developed efficient algorithms for robust sparse mean estimation with
sample complexity $\mathrm{poly}(k,\log d, 1/\epsilon)$ and runtime $d^2
\mathrm{poly}(k,\log d,1/\epsilon)$, where $\epsilon$ is the fraction of
contamination. In particular, the fastest runtime of existing algorithms is
quadratic ($\Omega(d^2)$), which can be prohibitive in high dimensions. This
quadratic barrier in the runtime stems from the reliance of these algorithms on
the sample covariance matrix, which is of size $d^2$. Our main contribution is
an algorithm for robust sparse mean estimation which runs in
\emph{subquadratic} time using $\mathrm{poly}(k,\log d,1/\epsilon)$ samples. We
also provide analogous results for robust sparse PCA. Our results build on
algorithmic advances in detecting weak correlations, a generalized version of
the light-bulb problem by Valiant.

稀疏均值估计算法在存在对抗性异常值的情况下的研究，提出了一种在次二次时间内运行的鲁棒稀疏均值估计算法，并在检测弱相关性方面取得了算法进展。

稳健稀疏均值估计的次二次时间算法

A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation

In this paper, we study the problem of robust sparse mean estimation, where
the goal is to estimate a $k$-sparse mean from a collection of partially
corrupted samples drawn from a heavy-tailed distribution. Existing estimators
face two critical challenges in this setting. First, they are limited by a
conjectured computational-statistical tradeoff, implying that any
computationally efficient algorithm needs $\tilde\Omega(k^2)$ samples, while
its statistically-optimal counterpart only requires $\tilde O(k)$ samples.
Second, the existing estimators fall short of practical use as they scale
poorly with the ambient dimension. This paper presents a simple mean estimator
that overcomes both challenges under moderate conditions: it runs in
near-linear time and memory (both with respect to the ambient dimension) while
requiring only $\tilde O(k)$ samples to recover the true mean. At the core of
our method lies an incremental learning phenomenon: we introduce a simple
nonconvex framework that can incrementally learn the top-$k$ nonzero elements
of the mean while keeping the zero elements arbitrarily small. Unlike existing
estimators, our method does not need any prior knowledge of the sparsity level
$k$. We prove the optimality of our estimator by providing a matching
information-theoretic lower bound. Finally, we conduct a series of simulations
to corroborate our theoretical findings. Our code is available at
this https URL

本文提出了一种简单的平均值估计方法，可以在 moderate 条件下克服现有估计器面临的计算和统计问题，并基于增量学习现象推导出匹配信息理论下界。