Online Robust Mean Estimation
Daniel M. Kane Ilias Diakonikolas Hanshen Xiao Sihan Liu
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.