# Optimal Robust Learning of Discrete Distributions from Batches

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

## Key facts

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

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

- [Robust Estimation for Random Graphs](https://mlsanity.com/paper/2111.05320/) (2021)
- [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)
- [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)

## Abstract (arXiv)

Many applications, including natural language processing, sensor networks, collaborative filtering, and federated learning, call for estimating discrete distributions from data collected in batches, some of which may be untrustworthy, erroneous, faulty, or even adversarial. Previous estimators for this setting ran in exponential time, and for some regimes required a suboptimal number of batches. We provide the first polynomial-time estimator that is optimal in the number of batches and achieves essentially the best possible estimation accuracy.