# Efficiently Learning Structured Distributions from Untrusted Batches

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

## Key facts

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

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

- [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)
- [Testing Closeness of Multivariate Distributions via Ramsey Theory](https://mlsanity.com/paper/2311.13154/) (2023)
- [Robust Estimation of Discrete Distributions under Local Differential Privacy](https://mlsanity.com/paper/2202.06825/) (2022)
- [Robust estimation algorithms don't need to know the corruption level](https://mlsanity.com/paper/2202.05453/) (2022)
- [Robust Voting Rules from Algorithmic Robust Statistics](https://mlsanity.com/paper/2112.06380/) (2021)
- [FLEA: Provably Robust Fair Multisource Learning from Unreliable Training Data](https://mlsanity.com/paper/2106.11732/) (2021)
- [Density estimation for Hellinger via minimum-distance estimators: mixtures of Gaussians, log-concave, and more](https://mlsanity.com/paper/2606.11469/) (2026)

## Abstract (arXiv)

We study the problem, introduced by Qiao and Valiant, of learning from untrusted batches. Here, we assume m users, all of whom have samples from some underlying distribution p over 1, ldots, n. Each user sends a batch of k i.i.d. samples from this distribution; however an ε-fraction of users are untrustworthy and can send adversarially chosen responses. The goal is then to learn p in total variation distance. When k = 1 this is the standard robust univariate density estimation setting and it is well-understood that Omega (ε) error is unavoidable. Suprisingly, Qiao and Valiant gave an estimator which improves upon this rate when k is large. Unfortunately, their algorithms run in time exponential in either n or k. We first give a sequence of polynomial time algorithms whose estimation error approaches the information-theoretically optimal bound for this problem. Our approach is based on recent algorithms derived from the sum-of-squares hierarchy, in the context of high-dimensional robust estimation. We show that algorithms for learning from untrusted batches can also be cast in this framework, but by working with a more complicated set of test functions. It turns out this abstraction is quite powerful and can be generalized to incorporate additional problem specific constraints. Our second and main result is to show that this technology can be leveraged to build in prior knowledge about the shape of the distribution. Crucially, this allows us to reduce the sample complexity of learning from untrusted batches to polylogarithmic in n for most natural classes of distributions, which is important in many applications. To do so, we demonstrate that these sum-of-squares algorithms for robust mean estimation can be made to handle complex combinatorial constraints (e.g. those arising from VC theory), which may be of independent technical interest.