Abstract: The population recovery problem is a basic problem in noisy unsupervised learning that has attracted significant research attention in recent years [WY12,DRWY12, MS13, BIMP13, LZ15,DST16]. A number of different variants of this problem have been studied, often under assumptions on the unknown distribution (such as that it has restricted support size). In this work we study the sample complexity and algorithmic complexity of the most general version of the problem, under both bit-flip noise and erasure noise model. 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.
Recommendations
Cites work
- Analysis of Boolean Functions
- Coppersmith-Rivlin type inequalities and the order of vanishing of polynomials at 1
- Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions
- Littlewood-Type Problems on [0,1]
- Littlewood-type problems on subarcs of the unit circle
- Optimal mean-based algorithms for trace reconstruction
- Population recovery and partial identification
- Recurrence times for the Ehrenfest model
- Restriction access
Cited in
(3)
This page was built for publication: Sharp bounds for population recovery
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5140840)
