  We study the problem of mean estimation for high-dimensional distributions,
assuming access to a statistical query oracle for the distribution. For a
normed space $X = (\mathbb{R}^d, \|\cdot\|_X)$ and a distribution supported on
vectors $x \in \mathbb{R}^d$ with $\|x\|_{X} \leq 1$, the task is to output an
estimate $\hat{\mu} \in \mathbb{R}^d$ which is $\epsilon$-close in the distance
induced by $\|\cdot\|_X$ to the true mean of the distribution. We obtain sharp
upper and lower bounds for the statistical query complexity of this problem
when the the underlying norm is symmetric as well as for Schatten-$p$ norms,
answering two questions raised by Feldman, Guzm\'{a}n, and Vempala (SODA 2017).

Data Structures and Algorithms