On Mean Estimation for General Norms with Statistical Queries
[edit]
Proceedings of the ThirtySecond Conference on Learning Theory, PMLR 99:21582172, 2019.
Abstract
We study the problem of mean estimation for highdimensional distributions given access to a statistical query oracle. 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 $\varepsilon$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 \emph{symmetric} as well as for Schatten$p$ norms, answering two questions raised by Feldman, Guzmán, and Vempala (SODA 2017).
Related Material


