Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation
Not on the map. Why?
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.
Key facts. Cited by 19 papers in the map (data through 7 Oct 2026). First posted on arXiv 26 May 2013.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 4; 2022: 4; 2023: 6; 2024: 4; 2025: 0; 2026: 1.
19 papers.
Sort:
- 2021Deep Learning with Label Differential Privacycited by 113
- 2022No Free Lunch Theorem for Security and Utility in Federated Learningcited by 39
- 2023Optimizing Privacy, Utility and Efficiency in Constrained Multi-Objective Federated Learningcited by 12
- 2021FedXGBoost: Privacy-Preserving XGBoost for Federated Learningcited by 9
- 2022Nonparametric extensions of randomized response for private confidence setscited by 6
- 2023Mean Estimation Under Heterogeneous Privacy: Some Privacy Can Be Freecited by 6
- 2023Theoretically Principled Federated Learning for Balancing Privacy and Utilitycited by 6
- 2023A Meta-learning Framework for Tuning Parameters of Protection Mechanisms in Trustworthy Federated Learningcited by 6
- 2023Mean Estimation Under Heterogeneous Privacy Demandscited by 6
- 2021Robust Federated Learning via Over-The-Air Computationcited by 5
- 2022Over-The-Air Federated Learning under Byzantine Attackscited by 4
- 2022Algorithms with More Granular Differential Privacy Guaranteescited by 4
7 more
- 2024Federated Learning Resilient to Byzantine Attacks and Data Heterogeneitycited by 4
- 2024Private Estimation when Data and Privacy Demands are Correlatedcited by 2
- 2023Differentially Private Synthetic Data Using KD-Treescited by 1
- 2024Bridging Privacy and Robustness for Trustworthy Machine Learningcited by 1
- 2021Locally differentially private estimation of nonlinear functionals of discrete distributionscited by 0
- 2024A Unified Learn-to-Distort-Data Framework for Privacy-Utility Trade-off in Trustworthy Federated Learningcited by 0
- 2026A Van Trees Lower Bound for Fully Interactive Differentially Private Federated Learningcited by 0
- 2026A Van Trees Lower Bound for Fully Interactive Differentially Private Federated Learning19 May 2026
- 2024Private Estimation when Data and Privacy Demands are Correlated15 Jul 2024
- 2024A Unified Learn-to-Distort-Data Framework for Privacy-Utility Trade-off in Trustworthy Federated Learning5 Jul 2024
- 2024Bridging Privacy and Robustness for Trustworthy Machine Learning25 Mar 2024
- 2024Federated Learning Resilient to Byzantine Attacks and Data Heterogeneity20 Mar 2024
- 2023Mean Estimation Under Heterogeneous Privacy Demands19 Oct 2023
- 2023Differentially Private Synthetic Data Using KD-Trees19 Jun 2023
- 2023A Meta-learning Framework for Tuning Parameters of Protection Mechanisms in Trustworthy Federated Learning28 May 2023
- 2023Theoretically Principled Federated Learning for Balancing Privacy and Utility24 May 2023
- 2023Optimizing Privacy, Utility and Efficiency in Constrained Multi-Objective Federated Learning29 Apr 2023
- 2023Mean Estimation Under Heterogeneous Privacy: Some Privacy Can Be Free27 Apr 2023
- 2022Algorithms with More Granular Differential Privacy Guarantees8 Sep 2022
7 more
- 2022Over-The-Air Federated Learning under Byzantine Attacks5 May 2022
- 2022No Free Lunch Theorem for Security and Utility in Federated Learning11 Mar 2022
- 2022Nonparametric extensions of randomized response for private confidence sets17 Feb 2022
- 2021Robust Federated Learning via Over-The-Air Computation1 Nov 2021
- 2021Locally differentially private estimation of nonlinear functionals of discrete distributions8 Jul 2021
- 2021FedXGBoost: Privacy-Preserving XGBoost for Federated Learning20 Jun 2021
- 2021Deep Learning with Label Differential Privacy11 Feb 2021
- 2021Deep Learning with Label Differential Privacycited by 113
- 2022No Free Lunch Theorem for Security and Utility in Federated Learningcited by 39
- 2023Optimizing Privacy, Utility and Efficiency in Constrained Multi-Objective Federated Learningcited by 12
- 2021FedXGBoost: Privacy-Preserving XGBoost for Federated Learningcited by 9
- 2022Nonparametric extensions of randomized response for private confidence setscited by 6
- 2023Mean Estimation Under Heterogeneous Privacy: Some Privacy Can Be Freecited by 6
- 2023Theoretically Principled Federated Learning for Balancing Privacy and Utilitycited by 6
- 2023A Meta-learning Framework for Tuning Parameters of Protection Mechanisms in Trustworthy Federated Learningcited by 6
- 2023Mean Estimation Under Heterogeneous Privacy Demandscited by 6
- 2021Robust Federated Learning via Over-The-Air Computationcited by 5
- 2022Over-The-Air Federated Learning under Byzantine Attackscited by 4
- 2022Algorithms with More Granular Differential Privacy Guaranteescited by 4
12 most cited of 19 All 19 (JSON)
- 2026A Van Trees Lower Bound for Fully Interactive Differentially Private Federated Learning19 May 2026
- 2024Private Estimation when Data and Privacy Demands are Correlated15 Jul 2024
- 2024A Unified Learn-to-Distort-Data Framework for Privacy-Utility Trade-off in Trustworthy Federated Learning5 Jul 2024
- 2024Bridging Privacy and Robustness for Trustworthy Machine Learning25 Mar 2024
- 2024Federated Learning Resilient to Byzantine Attacks and Data Heterogeneity20 Mar 2024
- 2023Mean Estimation Under Heterogeneous Privacy Demands19 Oct 2023
- 2023Differentially Private Synthetic Data Using KD-Trees19 Jun 2023
- 2023A Meta-learning Framework for Tuning Parameters of Protection Mechanisms in Trustworthy Federated Learning28 May 2023
- 2023Theoretically Principled Federated Learning for Balancing Privacy and Utility24 May 2023
- 2023Optimizing Privacy, Utility and Efficiency in Constrained Multi-Objective Federated Learning29 Apr 2023
- 2023Mean Estimation Under Heterogeneous Privacy: Some Privacy Can Be Free27 Apr 2023
- 2022Algorithms with More Granular Differential Privacy Guarantees8 Sep 2022
12 newest of 19 All 19 (JSON)