Theory of Computing
-------------------
Title     : Sharp Bounds for Population Recovery
Authors   : Anindya De, Ryan O'Donnell, and Rocco A. Servedio
Volume    : 16
Number    : 6
Pages     : 1-20
URL       : https://theoryofcomputing.org/articles/v016a006

Abstract
--------

The _population recovery problem_ is a basic problem in noisy
unsupervised learning that has attracted significant attention in
recent years (Dvir et al., ITCS'12), (Wigderson and Yehudayoff,
STOC'12), (Moitra and Saks, FOCS'13), (Batman et al., RANDOM'13),
(Lovett and Zhang, STOC'15), (De et al., FOCS'16). A number of
variants of this problem have been studied, often under assumptions on
the unknown distribution (such as that it has restricted support
size). In this article we study the sample complexity and algorithmic
complexity of the most general version of the problem, under both the
bit-flip noise and the erasure noise models. We give essentially
matching upper and lower sample complexity bounds for both noise
models, and efficient algorithms matching these sample complexity
bounds up to polynomial factors.