mlsanityData to 7 Oct 2026

Exactly Minimax-Optimal Locally Differentially Private Sampling

arXiv 2410.22699 ↗First posted 30 Oct 2024cs.LG cs.CRcited by 5

Not on the map. Why?

Abstract (arXiv)

The sampling problem under local differential privacy has recently been studied with potential applications to generative models, but a fundamental analysis of its privacy-utility trade-off (PUT) remains incomplete. In this work, we define the fundamental PUT of private sampling in the minimax sense, using the f-divergence between original and sampling distributions as the utility measure. We characterize the exact PUT for both finite and continuous data spaces under some mild conditions on the data distributions, and propose sampling mechanisms that are universally optimal for all f-divergences. Our numerical experiments demonstrate the superiority of our mechanisms over baselines, in terms of theoretical utilities for finite data space and of empirical utilities for continuous data space.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 39 of its 70 references that are in the map. First posted on arXiv 30 Oct 2024.

Builds on

39 of 70 references.

References · 39

  1. 2022Generative Adversarial Networkscited by 5,603
  2. 2021Convex optimizationcited by 2,479
  3. 2017Wasserstein GANcited by 635
  4. 2023Scalable Extraction of Training Data from (Production) Language Modelscited by 415
  5. 2013The Composition Theorem for Differential Privacycited by 290
  6. 2014RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Responsecited by 262
  7. 2018Differentially Private Generative Adversarial Networkcited by 235
  8. 2017Collecting Telemetry Data Privatelycited by 147
  9. 2020LDP-Fed: Federated Learning with Local Differential Privacycited by 129
  10. 2018Protection Against Reconstruction and Its Applications in Private Federated Learningcited by 127
  11. 2020DP-CGAN: Differentially Private Synthetic Data and Label Generationcited by 118
  12. 2018Privacy Amplification by Iterationcited by 97
27 more
  1. 2024On Protecting the Data Privacy of Large Language Models (LLMs): A Surveycited by 91
  2. 2023Unveiling Security, Privacy, and Ethical Concerns of ChatGPTcited by 53
  3. 2022Optimal Algorithms for Mean Estimation under Local Differential Privacycited by 36
  4. 2019PPGAN: Privacy-preserving Generative Adversarial Networkcited by 34
  5. 2016Privacy Odometers and Filters: Pay-as-you-Go Compositioncited by 32
  6. 2017Optimal Schemes for Discrete Distribution Estimation under Locally Differential Privacycited by 28
  7. 2023On the Privacy-Robustness-Utility Trilemma in Distributed Learningcited by 24
  8. 2024Differentially Private Next-Token Prediction of Large Language Modelscited by 21
  9. 2021Decentralized Wireless Federated Learning with Differential Privacycited by 18
  10. 2022Discrete Distribution Estimation under User-level Local Differential Privacycited by 17
  11. 2024Shake to Leak: Fine-tuning Diffusion Models Can Amplify the Generative Privacy Riskcited by 17
  12. 2022Regression with Label Differential Privacycited by 14
  13. 2023Fast Optimal Locally Private Mean Estimation via Random Projectionscited by 14
  14. 2023Federated Linear Contextual Bandits with User-level Differential Privacycited by 12
  15. 2023Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraintscited by 10
  16. 2022GeoPointGAN: Synthetic Spatial Data with Local Label Differential Privacycited by 9
  17. 2023Exact Optimality of Communication-Privacy-Utility Tradeoffs in Distributed Mean Estimationcited by 9
  18. 2022Differentially Private Sampling from Distributionscited by 8
  19. 2022Privacy-Aware Compression for Federated Learning Through Numerical Mechanism Designcited by 6
  20. 2023On Differentially Private Sampling from Gaussian and Product Distributionscited by 6
  21. 2024Rate Optimality and Phase Transition for User-Level Local Differential Privacycited by 6
  22. 2022Network change point localisation under local differential privacycited by 5
  23. 2022Local Differential Privacy Image Generation Using Flow-based Deep Generative Modelscited by 5
  24. 2023Online Local Differential Private Quantile Inference via Self-normalizationcited by 5
  25. 2024Metric Differential Privacy at the User-Level Via the Earth Mover's Distancecited by 5
  26. 2024On Computing Pairwise Statistics with Local Differential Privacycited by 3
  27. 2024PrivShape: Extracting Shapes in Time Series under User-Level Local Differential Privacycited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 3; 2026: 1.

5 papers.

  1. 2024Locally Private Sampling with Public Datacited by 3
  2. 2025Locally Optimal Private Sampling: Beyond the Global Minimaxcited by 2
  3. 2025Reveal-or-Obscure: A Differentially Private Sampling Algorithm for Discrete Distributionscited by 1
  4. 2025Privately Estimating Black-Box Statisticscited by 0
  5. 2026Differentially Private Sampling from Distributions via Wasserstein Projectioncited by 0