mlsanityData to 14 Oct 2026

On the Statistical Complexity of Estimation and Testing under Privacy Constraints

arXiv 2210.02215 ↗First posted 5 Oct 2022cs.LG cs.CRcited by 6

Not on the map. Why?

Abstract (arXiv)

The challenge of producing accurate statistics while respecting the privacy of the individuals in a sample is an important area of research. We study minimax lower bounds for classes of differentially private estimators. In particular, we show how to characterize the power of a statistical test under differential privacy in a plug-and-play fashion by solving an appropriate transport problem. With specific coupling constructions, this observation allows us to derive Le Cam-type and Fano-type inequalities not only for regular definitions of differential privacy but also for those based on Renyi divergence. We then proceed to illustrate our results on three simple, fully worked out examples. In particular, we show that the problem class has a huge importance on the provable degradation of utility due to privacy. In certain scenarios, we show that maintaining privacy results in a noticeable reduction in performance only when the level of privacy protection is very high. Conversely, for other problems, even a modest level of privacy protection can lead to a significant decrease in performance. Finally, we demonstrate that the DP-SGLD algorithm, a private convex solver, can be employed for maximum likelihood estimation with a high degree of confidence, as it provides near-optimal results with respect to both the size of the sample and the level of privacy protection. This algorithm is applicable to a broad range of parametric estimation procedures, including exponential families.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 31 of its 94 references that are in the map. First posted on arXiv 5 Oct 2022.

Builds on

31 of 94 references.

References · 31

  1. 2016Deep Learning with Differential Privacycited by 2,728
  2. 2017Renyi Differential Privacycited by 650
  3. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 346
  4. 2013The Composition Theorem for Differential Privacycited by 297
  5. 2014RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Responsecited by 272
  6. 2017Collecting Telemetry Data Privatelycited by 149
  7. 2016Concentrated Differential Privacycited by 144
  8. 2017Finite Sample Differentially Private Confidence Intervalscited by 104
  9. 2020CoinPress: Practical Private Mean and Covariance Estimationcited by 74
  10. 2021Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descentcited by 73
  11. 2019Private Hypothesis Selectioncited by 60
  12. 2020Differentially Private Assouad, Fano, and Le Camcited by 55
19 more
  1. 2019Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimationcited by 52
  2. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  3. 2020Local Differential Privacy and Its Applications: A Comprehensive Surveycited by 41
  4. 2019An Introductory Guide to Fano's Inequality with Applications in Statistical Estimationcited by 31
  5. 2013Local Privacy, Data Processing Inequalities, and Statistical Minimax Ratescited by 26
  6. 2017Differentially Private Testing of Identity and Closeness of Discrete Distributionscited by 25
  7. 2021Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Banditscited by 25
  8. 2020Near Instance-Optimality in Differential Privacycited by 23
  9. 2020Fisher information under local differential privacycited by 22
  10. 2020Unified lower bounds for interactive high-dimensional estimation under information constraintscited by 22
  11. 2020Differentially Private Confidence Intervalscited by 20
  12. 2022Differential Privacy Guarantees for Stochastic Gradient Langevin Dynamicscited by 19
  13. 2019Local Differential Privacy: a tutorialcited by 13
  14. 2021Inference under Information Constraints III: Local Privacy Constraintscited by 13
  15. 2021Optimal Rates for Nonparametric Density Estimation under Communication Constraintscited by 9
  16. 2021Information-constrained optimization: can adaptive processing of gradients help?cited by 8
  17. 2021Differentially Private Densest Subgraphcited by 6
  18. 2022Private Quantiles Estimation in the Presence of Atomscited by 5
  19. 2022Archimedes Meets Privacy: On Privately Estimating Quantiles in High Dimensions Under Minimal Assumptionscited by 5

Built on by

Cited by year

Citing papers per year: 2023: 4; 2024: 2.

6 papers.

  1. 2023Concentrated Differential Privacy for Banditscited by 10
  2. 2024Optimal Federated Learning for Nonparametric Regression with Heterogeneous Distributed Differential Privacy Constraintscited by 10
  3. 2023Private Statistical Estimation of Many Quantilescited by 3
  4. 2023About the Cost of Central Privacy in Density Estimationcited by 2
  5. 2023Sparsity in neural networks can improve their privacycited by 1
  6. 2024Optimal Federated Learning for Functional Mean Estimation under Heterogeneous Privacy Constraintscited by 1