On Mean Estimation for General Norms with Statistical Queries
Abstract
We study the problem of mean estimation for high-dimensional 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).
Cite
Text
Li et al. "On Mean Estimation for General Norms with Statistical Queries." Conference on Learning Theory, 2019.Markdown
[Li et al. "On Mean Estimation for General Norms with Statistical Queries." Conference on Learning Theory, 2019.](https://mlanthology.org/colt/2019/li2019colt-mean/)BibTeX
@inproceedings{li2019colt-mean,
title = {{On Mean Estimation for General Norms with Statistical Queries}},
author = {Li, Jerry and Nikolov, Aleksandar and Razenshteyn, Ilya and Waingarten, Erik},
booktitle = {Conference on Learning Theory},
year = {2019},
pages = {2158-2172},
volume = {99},
url = {https://mlanthology.org/colt/2019/li2019colt-mean/}
}