mlsanityData to 7 Oct 2026

Minimax Optimal Procedures for Locally Private Estimation

arXiv 1604.02390 ↗First posted 8 Apr 2016math.ST cs.IT math.ITcited by 103

Not on the map. Why?

Abstract (arXiv)

Working under a model of privacy in which data remains private even from the statistician, we study the tradeoff between privacy guarantees and the risk of the resulting statistical estimators. We develop private versions of classical information-theoretic bounds, in particular those due to Le Cam, Fano, and Assouad. These inequalities allow for a precise characterization of statistical rates under local privacy constraints and the development of provably (minimax) optimal estimation procedures. We provide a treatment of several canonical families of problems: mean estimation and median estimation, generalized linear models, and nonparametric density estimation. For all of these families, we provide lower and upper bounds that match up to constant factors, and exhibit new (optimal) privacy-preserving mechanisms and computationally efficient estimators that achieve the bounds. Additionally, we present a variety of experimental results for estimation problems involving sensitive data, including salaries, censored blog posts and articles, and drug abuse; these experiments demonstrate the importance of deriving optimal procedures.

Key facts. Cited by 103 papers in the map (data through 7 Oct 2026). First posted on arXiv 8 Apr 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 14; 2022: 18; 2023: 17; 2024: 21; 2025: 16; 2026: 17.

103 papers.

Sort:

By area:

  1. 2021Deep Learning with Label Differential Privacycited by 113
  2. 2021Differentially Private Federated Learning on Heterogeneous Datacited by 74
  3. 2021Private Adaptive Gradient Methods for Convex Optimizationcited by 46
  4. 2021High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Datacited by 42
  5. 2022Optimal Algorithms for Mean Estimation under Local Differential Privacycited by 36
  6. 2021Generalized Linear Bandits with Local Differential Privacycited by 29
  7. 2021Lossless Compression of Efficient Private Local Randomizerscited by 27
  8. 2021Differentially private inference via noisy optimizationcited by 27
  9. 2022On the Impossible Safety of Large AI Modelscited by 27
  10. 2022DP-PCA: Statistically Optimal and Differentially Private PCAcited by 24
  11. 2021Shuffle Private Stochastic Convex Optimizationcited by 17
  12. 2024The Privacy Power of Correlated Noise in Decentralized Learningcited by 17
38 more
  1. 2023Fast Optimal Locally Private Mean Estimation via Random Projectionscited by 14
  2. 2021Privately Learning Mixtures of Axis-Aligned Gaussianscited by 13
  3. 2021Differential Privacy in Personalized Pricing with Nonparametric Demand Modelscited by 13
  4. 2021Locally Differentially Private Reinforcement Learning for Linear Mixture Markov Decision Processescited by 13
  5. 2021Faster Rates of Private Stochastic Convex Optimizationcited by 12
  6. 2022OpBoost: A Vertical Federated Tree Boosting Framework Based on Order-Preserving Desensitizationcited by 12
  7. 2023A Bias-Accuracy-Privacy Trilemma for Statistical Estimationcited by 12
  8. 2023Differentially Private Reward Estimation with Preference Feedbackcited by 12
  9. 2022Communication-constrained hypothesis testing: Optimality, robustness, and reverse data processing inequalitiescited by 11
  10. 2022XRand: Differentially Private Defense against Explanation-Guided Attackscited by 11
  11. 2023Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraintscited by 10
  12. 2024Optimal Differentially Private PCA and Estimation for Spiked Covariance Matricescited by 10
  13. 2023Exact Optimality of Communication-Privacy-Utility Tradeoffs in Distributed Mean Estimationcited by 9
  14. 2022Differentially Private Linear Bandits with Partial Distributed Feedbackcited by 8
  15. 2022Contraction of Locally Differentially Private Mechanismscited by 8
  16. 2023Mean Estimation with User-level Privacy under Data Heterogeneitycited by 8
  17. 2025Towards Trustworthy Federated Learning with Untrusted Participantscited by 8
  18. 2025A Unified Theoretical Analysis of Private and Robust Offline Alignment: from RLHF to DPOcited by 8
  19. 2022The Role of Interactivity in Structured Estimationcited by 7
  20. 2024Optimal Federated Learning for Nonparametric Regression with Heterogeneous Distributed Differential Privacy Constraintscited by 7
  21. 2024Contraction of Private Quantum Channels and Private Quantum Hypothesis Testingcited by 7
  22. 2021Distribution-Invariant Differential Privacycited by 6
  23. 2022Nonparametric extensions of randomized response for private confidence setscited by 6
  24. 2023Mean Estimation Under Heterogeneous Privacy: Some Privacy Can Be Freecited by 6
  25. 2023Mean Estimation Under Heterogeneous Privacy Demandscited by 6
  26. 2022Continual Mean Estimation Under User-Level Privacycited by 5
  27. 2023Private Federated Learning with Autotuned Compressioncited by 5
  28. 2024Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messagescited by 5
  29. 2024Federated Nonparametric Hypothesis Testing with Differential Privacy Constraints: Optimal Rates and Adaptive Testscited by 5
  30. 2022Shuffle Gaussian Mechanism for Differential Privacycited by 4
  31. 2023Improved Analysis of Sparse Linear Regression in Local Differential Privacy Modelcited by 4
  32. 2024Efficient Sparse Least Absolute Deviation Regression with Differential Privacycited by 4
  33. 2024Online Differentially Private Synthetic Data Generationcited by 4
  34. 2024Low-Cost Privacy-Preserving Decentralized Learningcited by 4
  35. 2024Differentially Private Clustered Federated Learningcited by 4
  36. 2024Correlated Privacy Mechanisms for Differentially Private Distributed Mean Estimationcited by 4
  37. 2023General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimationcited by 3
  38. 2023Privacy-Preserving Graph Embedding based on Local Differential Privacycited by 3

50 most cited of 103 All 103 (JSON)