Robust Sparse Mean Estimation via Sum of Squares

Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Ankit Pensia, Thanasis Pittas
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:4703-4763, 2022.

Abstract

We study the problem of high-dimensional sparse mean estimation in the presence of an ϵ-fraction of adversarial outliers. Prior work obtained sample and computationally efficient algorithms for this task for identity-covariance subgaussian distributions. In this work, we develop the first efficient algorithms for robust sparse mean estimation without a priori knowledge of the covariance. For distributions on Rd with ‘certifiably bounded’ t-th moments and sufficiently light tails, our algorithm achieves error of O(ϵ1−1/t) with sample complexity m=(klog(d))O(t)/ϵ2−2/t. For the special case of the Gaussian distribution, our algorithm achieves near-optimal error of ˜O(ϵ) with sample complexity m=O(k4polylog(d))/ϵ2. Our algorithms follow the Sum-of-Squares based proofs to algorithms approach. We complement our upper bounds with Statistical Query and low-degree polynomial testing lower bounds, providing evidence that the sample-time-error tradeoffs achieved by our algorithms are qualitatively best possible.

Cite this Paper

BibTeX
@InProceedings{pmlr-v178-diakonikolas22e, title = {Robust Sparse Mean Estimation via Sum of Squares}, author = {Diakonikolas, Ilias and Kane, Daniel M. and Karmalkar, Sushrut and Pensia, Ankit and Pittas, Thanasis}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {4703--4763}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/diakonikolas22e/diakonikolas22e.pdf}, url = {https://proceedings.mlr.press/v178/diakonikolas22e.html}, abstract = {We study the problem of high-dimensional sparse mean estimation in the presence of an $\epsilon$-fraction of adversarial outliers. Prior work obtained sample and computationally efficient algorithms for this task for identity-covariance subgaussian distributions. In this work, we develop the first efficient algorithms for robust sparse mean estimation without a priori knowledge of the covariance. For distributions on $\mathbb{R}^d$ with ‘certifiably bounded’ $t$-th moments and sufficiently light tails, our algorithm achieves error of $O(\epsilon^{1-1/t})$ with sample complexity $m = (k\log(d))^{O(t)}/\epsilon^{2-2/t}$. For the special case of the Gaussian distribution, our algorithm achieves near-optimal error of $\tilde O(\epsilon)$ with sample complexity $m = O(k^4 \mathrm{polylog}(d))/\epsilon^2$. Our algorithms follow the Sum-of-Squares based proofs to algorithms approach. We complement our upper bounds with Statistical Query and low-degree polynomial testing lower bounds, providing evidence that the sample-time-error tradeoffs achieved by our algorithms are qualitatively best possible.} }
Endnote
%0 Conference Paper %T Robust Sparse Mean Estimation via Sum of Squares %A Ilias Diakonikolas %A Daniel M. Kane %A Sushrut Karmalkar %A Ankit Pensia %A Thanasis Pittas %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-diakonikolas22e %I PMLR %P 4703--4763 %U https://proceedings.mlr.press/v178/diakonikolas22e.html %V 178 %X We study the problem of high-dimensional sparse mean estimation in the presence of an $\epsilon$-fraction of adversarial outliers. Prior work obtained sample and computationally efficient algorithms for this task for identity-covariance subgaussian distributions. In this work, we develop the first efficient algorithms for robust sparse mean estimation without a priori knowledge of the covariance. For distributions on $\mathbb{R}^d$ with ‘certifiably bounded’ $t$-th moments and sufficiently light tails, our algorithm achieves error of $O(\epsilon^{1-1/t})$ with sample complexity $m = (k\log(d))^{O(t)}/\epsilon^{2-2/t}$. For the special case of the Gaussian distribution, our algorithm achieves near-optimal error of $\tilde O(\epsilon)$ with sample complexity $m = O(k^4 \mathrm{polylog}(d))/\epsilon^2$. Our algorithms follow the Sum-of-Squares based proofs to algorithms approach. We complement our upper bounds with Statistical Query and low-degree polynomial testing lower bounds, providing evidence that the sample-time-error tradeoffs achieved by our algorithms are qualitatively best possible.
APA
Diakonikolas, I., Kane, D.M., Karmalkar, S., Pensia, A. & Pittas, T.. (2022). Robust Sparse Mean Estimation via Sum of Squares. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:4703-4763 Available from https://proceedings.mlr.press/v178/diakonikolas22e.html.

Related Material