A Quasi-Polynomial Time Mean Estimator Under Mean-Shift Contamination with Unknown Covariance

Ilias Diakonikolas, Jingyi Gao, Giannis Iakovidis, Daniel M. Kane, Sihan Liu, Thanasis Pittas
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1902-1937, 2026.

Abstract

We study the algorithmic problem of robust Gaussian mean estimation in the mean-shift contamination model with unknown covariance. Specifically, we are allowed to draw samples from a statistical mixture of an unknown target Gaussian $\mathcal{N}(\mu, \Sigma)$ (with weight at least $1-\alpha$), and arbitrary unknown mean-shifts of it, i.e., ${\mathcal{N}(\mu_i, \Sigma)}_i$, and the goal is to estimate $\mu$ up to any desired accuracy $\epsilon$ in $\ell_2$-norm. In the special case where $\Sigma$ is known to be the identity, prior work gave an algorithm with a near-optimal sample complexity of $\mathrm{poly}(d,2^{\epsilon^{-2}})$ and sample-polynomial time. In this work, we provide a quasi-polynomial time algorithm with sample complexity $2^{\mathrm{poly}(\log d/\epsilon)}$ in the more general unknown covariance case, markedly improving upon the only previously known estimator for this setting that incurs exponential runtime.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-diakonikolas26c, title = {A Quasi-Polynomial Time Mean Estimator Under Mean-Shift Contamination with Unknown Covariance}, author = {Diakonikolas, Ilias and Gao, Jingyi and Iakovidis, Giannis and Kane, Daniel M. and Liu, Sihan and Pittas, Thanasis}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {1902--1937}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/diakonikolas26c/diakonikolas26c.pdf}, url = {https://proceedings.mlr.press/v336/diakonikolas26c.html}, abstract = {We study the algorithmic problem of robust Gaussian mean estimation in the mean-shift contamination model with unknown covariance. Specifically, we are allowed to draw samples from a statistical mixture of an unknown target Gaussian $\mathcal{N}(\mu, \Sigma)$ (with weight at least $1-\alpha$), and arbitrary unknown mean-shifts of it, i.e., ${\mathcal{N}(\mu_i, \Sigma)}_i$, and the goal is to estimate $\mu$ up to any desired accuracy $\epsilon$ in $\ell_2$-norm. In the special case where $\Sigma$ is known to be the identity, prior work gave an algorithm with a near-optimal sample complexity of $\mathrm{poly}(d,2^{\epsilon^{-2}})$ and sample-polynomial time. In this work, we provide a quasi-polynomial time algorithm with sample complexity $2^{\mathrm{poly}(\log d/\epsilon)}$ in the more general unknown covariance case, markedly improving upon the only previously known estimator for this setting that incurs exponential runtime.} }
Endnote
%0 Conference Paper %T A Quasi-Polynomial Time Mean Estimator Under Mean-Shift Contamination with Unknown Covariance %A Ilias Diakonikolas %A Jingyi Gao %A Giannis Iakovidis %A Daniel M. Kane %A Sihan Liu %A Thanasis Pittas %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-diakonikolas26c %I PMLR %P 1902--1937 %U https://proceedings.mlr.press/v336/diakonikolas26c.html %V 336 %X We study the algorithmic problem of robust Gaussian mean estimation in the mean-shift contamination model with unknown covariance. Specifically, we are allowed to draw samples from a statistical mixture of an unknown target Gaussian $\mathcal{N}(\mu, \Sigma)$ (with weight at least $1-\alpha$), and arbitrary unknown mean-shifts of it, i.e., ${\mathcal{N}(\mu_i, \Sigma)}_i$, and the goal is to estimate $\mu$ up to any desired accuracy $\epsilon$ in $\ell_2$-norm. In the special case where $\Sigma$ is known to be the identity, prior work gave an algorithm with a near-optimal sample complexity of $\mathrm{poly}(d,2^{\epsilon^{-2}})$ and sample-polynomial time. In this work, we provide a quasi-polynomial time algorithm with sample complexity $2^{\mathrm{poly}(\log d/\epsilon)}$ in the more general unknown covariance case, markedly improving upon the only previously known estimator for this setting that incurs exponential runtime.
APA
Diakonikolas, I., Gao, J., Iakovidis, G., Kane, D.M., Liu, S. & Pittas, T.. (2026). A Quasi-Polynomial Time Mean Estimator Under Mean-Shift Contamination with Unknown Covariance. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:1902-1937 Available from https://proceedings.mlr.press/v336/diakonikolas26c.html.

Related Material