# Learning Discrete Distributions from Untrusted Batches

arXiv: https://arxiv.org/abs/1711.08113 · HTML: https://mlsanity.com/paper/1711.08113/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Nov 2017.

## Built on by (most cited first, 14 of 14)

- [Byzantine-Robust Online and Offline Distributed Reinforcement Learning](https://mlsanity.com/paper/2206.00165/) (2022)
- [Robust Estimation for Random Graphs](https://mlsanity.com/paper/2111.05320/) (2021)
- [Incentivizing Honesty among Competitors in Collaborative Learning and Optimization](https://mlsanity.com/paper/2305.16272/) (2023)
- [Robust Testing and Estimation under Manipulation Attacks](https://mlsanity.com/paper/2104.10740/) (2021)
- [Robust Estimation of Discrete Distributions under Local Differential Privacy](https://mlsanity.com/paper/2202.06825/) (2022)
- [Efficient List-Decodable Regression using Batches](https://mlsanity.com/paper/2211.12743/) (2022)
- [Robust estimation algorithms don't need to know the corruption level](https://mlsanity.com/paper/2202.05453/) (2022)
- [Linear Regression using Heterogeneous Data Batches](https://mlsanity.com/paper/2309.01973/) (2023)
- [Testing with Non-identically Distributed Samples](https://mlsanity.com/paper/2311.11194/) (2023)
- [Robust Federated Personalised Mean Estimation for the Gaussian Mixture Model](https://mlsanity.com/paper/2504.19955/) (2025)
- [When More Data Doesn't Help: Limits of Adaptation in Multitask Learning](https://mlsanity.com/paper/2601.20774/) (2026)
- [FLEA: Provably Robust Fair Multisource Learning from Unreliable Training Data](https://mlsanity.com/paper/2106.11732/) (2021)
- [Batch List-Decodable Linear Regression via Higher Moments](https://mlsanity.com/paper/2503.09802/) (2025)
- [GeoERM: Geometry-Aware Multi-Task Representation Learning on Riemannian Manifolds](https://mlsanity.com/paper/2505.02972/) (2025)

## Abstract (arXiv)

We consider the problem of learning a discrete distribution in the presence of an ε 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-ε) fraction of the sources draw their samples from a distribution with total variation distance at most η from p. We make no assumptions on the data provided by the remaining ε fraction of sources--this data can even be chosen as an adversarial function of the (1-ε) fraction of "good" batches. We provide two algorithms: one with runtime exponential in the support size, n, but polynomial in k, 1/ε and 1/η that takes O((n+k)/ε2) batches and recovers p to error O(η+ε/√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 η = 0 setting and also achieves an O(ε/√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 ℓ1 distance, is surprising in light of the hardness of many low-rank tensor approximation problems, and may be of independent interest.