TY - GEN

T1 - Noisy Population Recovery in Polynomial Time

AU - De, Anindya

AU - Saks, Michael

AU - Tang, Sijian

N1 - Publisher Copyright:
© 2016 IEEE.

PY - 2016/12/14

Y1 - 2016/12/14

N2 - In the noisy population recovery problem of Dvir et al. [6], the goal is to learn an unknown distribution f on binary strings of length n from noisy samples. A noisy sample with parameter μ ϵ [0,1] is generated by selecting a sample from f, and independently flipping each coordinate of the sample with probability (1-μ)/2. We assume an upper bound k on the size of the support of the distribution, and the goal is to estimate the probability of any string to within some given error ϵ. It is known that the algorithmic complexity and sample complexity of this problem are polynomially related to each other. We describe an algorithm that for each μ > 0, provides the desired estimate of the distribution in time bounded by a polynomial in k, n and 1/ϵ improving upon the previous best result of poly(klog log k, n, 1/ϵ) due to Lovett and Zhang [9]. Our proof combines ideas from [9] with a noise attenuated version of Möbius inversion. The latter crucially uses the robust local inverse construction of Moitra and Saks [11].

AB - In the noisy population recovery problem of Dvir et al. [6], the goal is to learn an unknown distribution f on binary strings of length n from noisy samples. A noisy sample with parameter μ ϵ [0,1] is generated by selecting a sample from f, and independently flipping each coordinate of the sample with probability (1-μ)/2. We assume an upper bound k on the size of the support of the distribution, and the goal is to estimate the probability of any string to within some given error ϵ. It is known that the algorithmic complexity and sample complexity of this problem are polynomially related to each other. We describe an algorithm that for each μ > 0, provides the desired estimate of the distribution in time bounded by a polynomial in k, n and 1/ϵ improving upon the previous best result of poly(klog log k, n, 1/ϵ) due to Lovett and Zhang [9]. Our proof combines ideas from [9] with a noise attenuated version of Möbius inversion. The latter crucially uses the robust local inverse construction of Moitra and Saks [11].

KW - Fourier transform

KW - Population recovery

KW - Reverse Bonami-Beckner inequality

UR - http://www.scopus.com/inward/record.url?scp=85009355176&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85009355176&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2016.77

DO - 10.1109/FOCS.2016.77

M3 - Conference contribution

AN - SCOPUS:85009355176

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 675

EP - 684

BT - Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016

PB - IEEE Computer Society

T2 - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016

Y2 - 9 October 2016 through 11 October 2016

ER -