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

We study the problem of high-dimensional robust mean estimation in the
presence of a constant fraction of adversarial outliers. A recent line of work
has provided sophisticated polynomial-time algorithms for this problem with
dimension-independent error guarantees for a range of natural distribution
families.
In this work, we show that a natural non-convex formulation of the problem
can be solved directly by gradient descent. Our approach leverages a novel
structural lemma, roughly showing that any approximate stationary point of our
non-convex objective gives a near-optimal solution to the underlying robust
estimation task. Our work establishes an intriguing connection between
algorithmic high-dimensional robust statistics and non-convex optimization,
which may have broader applications to other robust estimation tasks.

研究高维度的强健均值估计问题，在存在恒定比例的对抗性离群值的情况下，我们显示出这个问题的自然非凸公式可以直接通过梯度下降来解决。

通过梯度下降实现高维度鲁棒均值估计

High-Dimensional Robust Mean Estimation via Gradient Descent

We study the problem of estimating a $p$-dimensional $s$-sparse vector in a
linear model with Gaussian design and additive noise. In the case where the
labels are contaminated by at most $o$ adversarial outliers, we prove that the
$\ell_1$-penalized Huber's $M$-estimator based on $n$ samples attains the
optimal rate of convergence $(s/n)^{1/2} + (o/n)$, up to a logarithmic factor.
For more general design matrices, our results highlight the importance of two
properties: the transfer principle and the incoherence property. These
properties with suitable constants are shown to yield the optimal rates, up to
log-factors, of robust estimation with adversarial contamination.

研究了在高斯设计和加性噪声的线性模型中，估计一个 p - 维 s - 稀疏向量的问题，证明当标签受到至多 o 个敌对异常数据的污染时，基于 n 个样本的 L1 惩罚 Huber's M - 估计量达到最优的收敛速率 (s /n)^ {1/2} +（o /n），更一般的设计矩阵结果强调了转移原则和无相干性质的重要性，并证明适当的常数加上这些属性可以实现最优的强鲁棒估计率，最高可达对数因子，具有敌对扰动。