NeurIPS 2020poster21 citations
Learning Structured Distributions From Untrusted Batches: Faster and Simpler
Sitan Chen, Jerry Li, Ankur Moitra
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.
BibTeX
@inproceedings{NEURIPS2020_305ddad0,
author = {Chen, Sitan and Li, Jerry and Moitra, Ankur},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Larochelle and M. Ranzato and R. Hadsell and M.F. Balcan and H. Lin},
pages = {4512--4523},
publisher = {Curran Associates, Inc.},
title = {Learning Structured Distributions From Untrusted Batches: Faster and Simpler},
url = {https://proceedings.neurips.cc/paper_files/paper/2020/file/305ddad049f65a2c241dbb6e6f746c54-Paper.pdf},
volume = {33},
year = {2020}
}