# Robust Estimation of Discrete Distributions under Local Differential Privacy

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 44 references that are in the map.
- First posted on arXiv 14 Feb 2022.

## Builds on (most cited first, 26 of 26)

- [Certified Robustness to Adversarial Examples with Differential Privacy](https://mlsanity.com/paper/1802.03471/) (2018)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Differential privacy and robust statistics in high dimensions](https://mlsanity.com/paper/2111.06578/) (2021)
- [Discrete Distribution Estimation under Local Privacy](https://mlsanity.com/paper/1602.07387/) (2016)
- [Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism](https://mlsanity.com/paper/2111.12981/) (2021)
- [Private and polynomial time algorithms for learning Gaussians and beyond](https://mlsanity.com/paper/2111.11320/) (2021)
- [Optimal Schemes for Discrete Distribution Estimation under Locally Differential Privacy](https://mlsanity.com/paper/1702.00610/) (2017)
- [Manipulation Attacks in Local Differential Privacy](https://mlsanity.com/paper/1909.09630/) (2019)
- [Local Privacy, Data Processing Inequalities, and Statistical Minimax Rates](https://mlsanity.com/paper/1302.3203/) (2013)
- [Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication](https://mlsanity.com/paper/1802.04705/) (2018)
- [Fisher information under local differential privacy](https://mlsanity.com/paper/2005.10783/) (2020)
- [Unified lower bounds for interactive high-dimensional estimation under information constraints](https://mlsanity.com/paper/2010.06562/) (2020)
- [Interactive Inference under Information Constraints](https://mlsanity.com/paper/2007.10976/) (2020)
- [On robustness and local differential privacy](https://mlsanity.com/paper/2201.00751/) (2022)
- [Learning Discrete Distributions from Untrusted Batches](https://mlsanity.com/paper/1711.08113/) (2017)
- [Local differential privacy: Elbow effect in optimal density estimation and adaptation over Besov ellipsoids](https://mlsanity.com/paper/1903.01927/) (2019)
- [Locally private non-asymptotic testing of discrete distributions is faster using interactive mechanisms](https://mlsanity.com/paper/2005.12601/) (2020)
- [Optimal Robust Learning of Discrete Distributions from Batches](https://mlsanity.com/paper/1911.08532/) (2019)
- [A unified view on differential privacy and robustness to adversarial examples](https://mlsanity.com/paper/1906.07982/) (2019)
- [Efficiently Learning Structured Distributions from Untrusted Batches](https://mlsanity.com/paper/1911.02035/) (2019)
- [Robust Testing and Estimation under Manipulation Attacks](https://mlsanity.com/paper/2104.10740/) (2021)
- [Estimating Sparse Discrete Distributions Under Local Privacy and Communication Constraints](https://mlsanity.com/paper/2011.00083/) (2020)
- [Minimax optimal goodness-of-fit testing for densities and multinomials under a local differential privacy constraint](https://mlsanity.com/paper/2002.04254/) (2020)

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

- [Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation](https://mlsanity.com/paper/2211.00724/) (2022)
- [On the Privacy-Robustness-Utility Trilemma in Distributed Learning](https://mlsanity.com/paper/2302.04787/) (2023)
- [A Unified Theoretical Analysis of Private and Robust Offline Alignment: from RLHF to DPO](https://mlsanity.com/paper/2505.15694/) (2025)
- [SquarechiPO: Differentially Private and Robust chi2-Preference Optimization in Offline Direct Alignment](https://mlsanity.com/paper/2505.21395/) (2025)
- [Rate-Optimal Rank Aggregation with Private Pairwise Rankings](https://mlsanity.com/paper/2402.16792/) (2024)

## Abstract (arXiv)

Although robust learning and local differential privacy are both widely studied fields of research, combining the two settings is just starting to be explored. We consider the problem of estimating a discrete distribution in total variation from n contaminated data batches under a local differential privacy constraint. A fraction 1-ε of the batches contain k i.i.d. samples drawn from a discrete distribution p over d elements. To protect the users' privacy, each of the samples is privatized using an α-locally differentially private mechanism. The remaining ε n  batches are an adversarial contamination. The minimax rate of estimation under contamination alone, with no privacy, is known to be ε/√k+√d/kn, up to a √log(1/ε) factor. Under the privacy constraint alone, the minimax rate of estimation is √d2/α2 kn. We show that combining the two constraints leads to a minimax estimation rate of ε√d/α2 k+√d2/α2 kn up to a √log(1/ε) factor, larger than the sum of the two separate rates. We provide a polynomial-time algorithm achieving this bound, as well as a matching information theoretic lower bound.