Learning Discrete Distributions from Untrusted Batches

By Mingda Qiao, Gregory Valiant. 2017

37 citations recorded by the source corpus.

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 $\ge 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 $\mathrm{poly}((nk)^k)$ time. This second algorithm, which approximates a certain tensor via a rank-1 tensor minimizing $\ell_1$ distance, is surprising in light of the hardness of many low-rank tensor approximation problems, and may be of independent interest.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Radiology, Nuclear Medicine and Imaging, Probabilistic & Bayesian Methods, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Radiology, Nuclear Medicine and Imaging

In Probabilistic & Bayesian Methods

In Statistical Learning Theory

Citations in the corpus

Backdoor Attacks on Federated Meta-Learning (2020, methodology): “Several defense mechanisms have been proposed: [14] and [15] estimated the distribution of the training data to suppress the influence of outliers assuming that training datasets of different users are i.”
A Little Is Enough: Circumventing Defenses For Distributed Learning (2019, background): “A few defenses aimed at detecting backdoors were proposed [26, 22, 6, 27], but those defenses assume a single-server training in which the backdoor is injected in the training set for which the server has access to, so that by clustering or other techniques the backdoor samples can be found and remo”
Sever: A Robust Meta-Algorithm for Stochastic Optimization (2018, background): “…tradeoﬀs [DKS17c, DKK + 18], establishing connections to PAC learning [DKS17a], tolerating more noise by outputting a list of hypotheses [CSV17, MV17, DKS17b], robust estimation of discrete structures [Ste17, QV17, SCV18], and robust estimation via sum-of-squares [KS17b, HL17, KS17a].”
On the Sample Complexity of Adversarial Multi-Source PAC Learning (2020, background): “Qiao & Valiant (2018), as well as the follow-up works of Chen et al. (2019); Jain & Orlitsky (2019), aim at estimating discrete distributions from multiple batches of data, some of which have been adversarially corrupted.”
Robust Learning from Untrusted Sources (2019, background): “The work closest in spirit to ours is the one of (Qiao & Valiant, 2018), who provide efﬁcient algorithms for learning from batches of data, an (cid:15) -fraction of which can be malicious.”