Efficiently Learning Structured Distributions from Untrusted Batches

Explore the challenges and solutions in learning structured distributions from untrusted batches in this 25-minute conference talk presented at the Association for Computing Machinery (ACM). Dive into robust learning techniques and methods for handling crowdsourced data. Examine information-theoretic lower and upper bounds, and investigate a warmup result for robust L1 mean estimation. Learn about searching for moment-bounded subsets and solving polynomial systems. Delve into the intricacies of learning structured distributions, including problem statements and SOS relaxation. Discover the importance of sparsity in Haar basis and gain valuable insights into this complex topic. Conclude with a comprehensive understanding of efficiently learning structured distributions from untrusted sources.

ROBUST LEARNING
LEARNING FROM CROWDSOURCED DATA
INFORMATION-THEORETIC LOWER BOUND
UPPER BOUNDS
A WARMUP RESULT
ROBUST L1 MEAN ESTIMATION
SEARCHING FOR A MOMENT-BOUNDED SUBSET
A POLYNOMIAL SYSTEM
LEARNING STRUCTURED DISTRIBUTIONS
PROBLEM STATEMENT
THE SOS RELAXATION
SPARSITY IN HAAR BASIS
CONCLUSION