Learning Structured Distributions from Untrusted Batches: Faster and Simpler
Abstract
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 μ is assumed to be structured, e.g. log-concave, monotone hazard rate, t-modal, etc. In this case, it is possible to achieve the same error with sample complexity sublinear in n, and they exhibited a quasi-polynomial time algorithm for doing so using Haar wavelets.
Cite
Text
Chen et al. "Learning Structured Distributions from Untrusted Batches: Faster and Simpler." Neural Information Processing Systems, 2020.Markdown
[Chen et al. "Learning Structured Distributions from Untrusted Batches: Faster and Simpler." Neural Information Processing Systems, 2020.](https://mlanthology.org/neurips/2020/chen2020neurips-learning/)BibTeX
@inproceedings{chen2020neurips-learning,
title = {{Learning Structured Distributions from Untrusted Batches: Faster and Simpler}},
author = {Chen, Sitan and Li, Jerry and Moitra, Ankur},
booktitle = {Neural Information Processing Systems},
year = {2020},
url = {https://mlanthology.org/neurips/2020/chen2020neurips-learning/}
}