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

Deep learning models, such as wide neural networks, can be conceptualized as
nonlinear dynamical physical systems characterized by a multitude of
interacting degrees of freedom. Such systems in the infinite limit, tend to
exhibit simplified dynamics. This paper delves into gradient descent-based
learning algorithms, that display a linear structure in their parameter
dynamics, reminiscent of the neural tangent kernel. We establish this apparent
linearity arises due to weak correlations between the first and higher-order
derivatives of the hypothesis function, concerning the parameters, taken around
their initial values. This insight suggests that these weak correlations could
be the underlying reason for the observed linearization in such systems. As a
case in point, we showcase this weak correlations structure within neural
networks in the large width limit. Exploiting the relationship between
linearity and weak correlations, we derive a bound on deviations from linearity
observed during the training trajectory of stochastic gradient descent. To
facilitate our proof, we introduce a novel method to characterise the
asymptotic behavior of random tensors.

基于梯度下降的深度学习算法以及大型神经网络中的线性动力学和弱相关性的研究。