# Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 May 2013.

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

- [Deep Learning with Label Differential Privacy](https://mlsanity.com/paper/2102.06062/) (2021)
- [No Free Lunch Theorem for Security and Utility in Federated Learning](https://mlsanity.com/paper/2203.05816/) (2022)
- [Optimizing Privacy, Utility and Efficiency in Constrained Multi-Objective Federated Learning](https://mlsanity.com/paper/2305.00312/) (2023)
- [FedXGBoost: Privacy-Preserving XGBoost for Federated Learning](https://mlsanity.com/paper/2106.10662/) (2021)
- [Robust Federated Learning via Over-The-Air Computation](https://mlsanity.com/paper/2111.01221/) (2021)
- [Nonparametric extensions of randomized response for private confidence sets](https://mlsanity.com/paper/2202.08728/) (2022)
- [Mean Estimation Under Heterogeneous Privacy: Some Privacy Can Be Free](https://mlsanity.com/paper/2305.09668/) (2023)
- [Theoretically Principled Federated Learning for Balancing Privacy and Utility](https://mlsanity.com/paper/2305.15148/) (2023)
- [A Meta-learning Framework for Tuning Parameters of Protection Mechanisms in Trustworthy Federated Learning](https://mlsanity.com/paper/2305.18400/) (2023)
- [Mean Estimation Under Heterogeneous Privacy Demands](https://mlsanity.com/paper/2310.13137/) (2023)
- [Over-The-Air Federated Learning under Byzantine Attacks](https://mlsanity.com/paper/2205.02949/) (2022)
- [Algorithms with More Granular Differential Privacy Guarantees](https://mlsanity.com/paper/2209.04053/) (2022)
- [Federated Learning Resilient to Byzantine Attacks and Data Heterogeneity](https://mlsanity.com/paper/2403.13374/) (2024)
- [Private Estimation when Data and Privacy Demands are Correlated](https://mlsanity.com/paper/2407.11274/) (2024)
- [Differentially Private Synthetic Data Using KD-Trees](https://mlsanity.com/paper/2306.13211/) (2023)
- [Bridging Privacy and Robustness for Trustworthy Machine Learning](https://mlsanity.com/paper/2403.16591/) (2024)
- [Locally differentially private estimation of nonlinear functionals of discrete distributions](https://mlsanity.com/paper/2107.03940/) (2021)
- [A Unified Learn-to-Distort-Data Framework for Privacy-Utility Trade-off in Trustworthy Federated Learning](https://mlsanity.com/paper/2407.04751/) (2024)
- [A Van Trees Lower Bound for Fully Interactive Differentially Private Federated Learning](https://mlsanity.com/paper/2605.19813/) (2026)

## Abstract (arXiv)

We provide a detailed study of the estimation of probability distributions---discrete and continuous---in a stringent setting in which data is kept private even from the statistician. We give sharp minimax rates of convergence for estimation in these locally private settings, exhibiting fundamental tradeoffs between privacy and convergence rate, as well as providing tools to allow movement along the privacy-statistical efficiency continuum. One of the consequences of our results is that Warner's classical work on randomized response is an optimal way to perform survey sampling while maintaining privacy of the respondents.