Online Robust Mean Estimation
Daniel M. Kane, Ilias Diakonikolas, Hanshen Xiao, Sihan Liu · Society for Industrial and Applied Mathematics eBooks · 2024
This 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,. ., T, the ith sensor reports its readings for that time step. The algorithm must then commit to its estimate μ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 ɛ-fraction of them may instead behave maliciously. The algorithm wishes to compute a good approximation μ to the true mean μ* := 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.