Learning Structured Distributions From Untrusted Batches: Faster and Simpler

Understand

We revisit the problem of learning from untrusted batches introduced by Qiao and Valiant [QV17].

• Recently, Jain and Orlitsky [JO19] gave a simple semidefinite programming approach based on the cut-norm that achieves essentially information-theoretically optimal error in polynomial time.
• Concurrently, Chen et al.
• [CLM19] considered a variant of the problem where $\mu$ is assumed to be structured, e.g.