On Mean Estimation for General Norms with Statistical Queries

Jerry Li, Aleksandar Nikolov, Ilya Razenshteyn, Erik Waingarten
Proceedings of the Thirty-Second Conference on Learning Theory, PMLR 99:2158-2172, 2019.

Abstract

We study the problem of mean estimation for high-dimensional distributions given access to a statistical query oracle. For a normed space X=(Rd,‖ 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 this Paper

BibTeX
@InProceedings{pmlr-v99-li19a, title = {On Mean Estimation for General Norms with Statistical Queries}, author = {Li, Jerry and Nikolov, Aleksandar and Razenshteyn, Ilya and Waingarten, Erik}, booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory}, pages = {2158--2172}, year = {2019}, editor = {Beygelzimer, Alina and Hsu, Daniel}, volume = {99}, series = {Proceedings of Machine Learning Research}, month = {25--28 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v99/li19a/li19a.pdf}, url = {https://proceedings.mlr.press/v99/li19a.html}, 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).} }
Endnote
%0 Conference Paper %T On Mean Estimation for General Norms with Statistical Queries %A Jerry Li %A Aleksandar Nikolov %A Ilya Razenshteyn %A Erik Waingarten %B Proceedings of the Thirty-Second Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2019 %E Alina Beygelzimer %E Daniel Hsu %F pmlr-v99-li19a %I PMLR %P 2158--2172 %U https://proceedings.mlr.press/v99/li19a.html %V 99 %X 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).
APA
Li, J., Nikolov, A., Razenshteyn, I. & Waingarten, E.. (2019). On Mean Estimation for General Norms with Statistical Queries. Proceedings of the Thirty-Second Conference on Learning Theory, in Proceedings of Machine Learning Research 99:2158-2172 Available from https://proceedings.mlr.press/v99/li19a.html.

Related Material