A Simple and Optimal Sublinear Algorithm for Mean Estimation

We study the sublinear mean estimation problem. Specifically, we aim to output a point minimizing the sum of squared Euclidean distances. We show that a multiplicative $(1+\varepsilon)$ approximation can be found with probability $1-\delta$ using $O(\varepsilon^{-1}\log \delta^{-1})$ many independent random samples. We also provide a matching lower bound.