We study the problem of high-dimensional robust mean estimation in an online
setting. Specifically, we consider a scenario where $n$ sensors are measuring
some common, ongoing phenomenon. At each time step $t=1,2,\ldots,T$, the
$i^{th}$ sensor reports its readings $x^{(i)}_t$ for that time step. The
algorithm must then commit to its estimate $\mu_t$ for the true mean value of
the process at time $t$. We assume that most of the sensors observe independent
samples from some common distribution $X$, but an $\epsilon$-fraction of them
may instead behave maliciously. The algorithm wishes to compute a good
approximation $\mu$ to the true mean $\mu^\ast := \mathbf{E}[X]$. We note that
if the algorithm is allowed to wait until time $T$ to report its estimate, this
reduces to the well-studied problem of robust mean estimation. However, the
requirement that our algorithm produces partial estimates as the data is coming
in substantially complicates the situation.
We prove two main results about online robust mean estimation in this model.
First, if the uncorrupted samples satisfy the standard condition of
$(\epsilon,\delta)$-stability, we give an efficient online algorithm that
outputs estimates $\mu_t$, $t \in [T],$ such that with high probability it
holds that $\|\mu-\mu^\ast\|_2 = O(\delta \log(T))$, where $\mu = (\mu_t)_{t
\in [T]}$. We note that this error bound is nearly competitive with the best
offline algorithms, which would achieve $\ell_2$-error of $O(\delta)$. Our
second main result shows that with additional assumptions on the input (most
notably that $X$ is a product distribution) there are inefficient algorithms
whose error does not depend on $T$ at all.

在线高维健壮均值估计问题的研究，讨论传感器在在线环境下的独立采样和恶意行为，给出了一个高效算法以及附加假设下的低效算法。