2026-10-13T01:45:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8321 2024-03-06T09:42:08Z ddc:004 open_access

Learning Discrete Distributions from Untrusted Batches Qiao, Mingda Valiant, Gregory robust statistics information-theoretic optimality We consider the problem of learning a discrete distribution in the presence of an epsilon fraction of malicious data sources. Specifically, we consider the setting where there is some underlying distribution, p, and each data source provides a batch of >= k samples, with the guarantee that at least a (1 - epsilon) fraction of the sources draw their samples from a distribution with total variation distance at most \eta from p. We make no assumptions on the data provided by the remaining epsilon fraction of sources--this data can even be chosen as an adversarial function of the (1 - epsilon) fraction of "good" batches. We provide two algorithms: one with runtime exponential in the support size, n, but polynomial in k, 1/epsilon and 1/eta that takes O((n + k)/epsilon^2) batches and recovers p to error O(eta + epsilon/sqrt(k)). This recovery accuracy is information theoretically optimal, to constant factors, even given an infinite number of data sources. Our second algorithm applies to the eta = 0 setting and also achieves an O(epsilon/sqrt(k)) recover guarantee, though it runs in poly((nk)^k) time. This second algorithm, which approximates a certain tensor via a rank-1 tensor minimizing l_1 distance, is surprising in light of the hardness of many low-rank tensor approximation problems, and may be of independent interest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mingda Qiao and Gregory Valiant 2018 Is Part Of LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2018.47 urn:nbn:de:0030-drops-83215 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.47 eng https://creativecommons.org/licenses/by/3.0/legalcode