Noisy Population Recovery from Unknown Noise

[edit]

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.

Related Material