Noisy Population Recovery from Unknown Noise

Shachar Lovett, Jiapeng Zhang
Proceedings of the 2017 Conference on Learning Theory, PMLR 65:1417-1431, 2017.

Abstract

The noisy population recovery problem is a statistical inference problem, which is a special case of the problem of learning mixtures of product distributions. Given an unknown distribution on $n$-bit strings with support of size $k$, and given access only to noisy samples from it, where each bit is flipped independently with some unknown noise probability, estimate from a few samples the underlying parameters of the model. Previous work [De et al., FOCS 2016] designed polynomial time algorithms which work under the assumption that the noise parameters are known exactly. In this work, we remove this assumption, and show how to recover the underlying parameters, even when the noise is unknown, in quasi-polynomial time.

Cite this Paper

BibTeX
@InProceedings{pmlr-v65-lovett17a, title = {Noisy Population Recovery from Unknown Noise}, author = {Lovett, Shachar and Zhang, Jiapeng}, booktitle = {Proceedings of the 2017 Conference on Learning Theory}, pages = {1417--1431}, year = {2017}, editor = {Kale, Satyen and Shamir, Ohad}, volume = {65}, series = {Proceedings of Machine Learning Research}, month = {07--10 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v65/lovett17a/lovett17a.pdf}, url = {https://proceedings.mlr.press/v65/lovett17a.html}, abstract = { The noisy population recovery problem is a statistical inference problem, which is a special case of the problem of learning mixtures of product distributions. Given an unknown distribution on $n$-bit strings with support of size $k$, and given access only to noisy samples from it, where each bit is flipped independently with some unknown noise probability, estimate from a few samples the underlying parameters of the model. Previous work [De et al., FOCS 2016] designed polynomial time algorithms which work under the assumption that the noise parameters are known exactly. In this work, we remove this assumption, and show how to recover the underlying parameters, even when the noise is unknown, in quasi-polynomial time. } }
Endnote
%0 Conference Paper %T Noisy Population Recovery from Unknown Noise %A Shachar Lovett %A Jiapeng Zhang %B Proceedings of the 2017 Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2017 %E Satyen Kale %E Ohad Shamir %F pmlr-v65-lovett17a %I PMLR %P 1417--1431 %U https://proceedings.mlr.press/v65/lovett17a.html %V 65 %X The noisy population recovery problem is a statistical inference problem, which is a special case of the problem of learning mixtures of product distributions. Given an unknown distribution on $n$-bit strings with support of size $k$, and given access only to noisy samples from it, where each bit is flipped independently with some unknown noise probability, estimate from a few samples the underlying parameters of the model. Previous work [De et al., FOCS 2016] designed polynomial time algorithms which work under the assumption that the noise parameters are known exactly. In this work, we remove this assumption, and show how to recover the underlying parameters, even when the noise is unknown, in quasi-polynomial time.
APA
Lovett, S. & Zhang, J.. (2017). Noisy Population Recovery from Unknown Noise. Proceedings of the 2017 Conference on Learning Theory, in Proceedings of Machine Learning Research 65:1417-1431 Available from https://proceedings.mlr.press/v65/lovett17a.html.

Related Material