# Exactly Minimax-Optimal Locally Differentially Private Sampling

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

## Key facts

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

## Builds on (most cited first, 30 of 39)

- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Wasserstein GAN](https://mlsanity.com/paper/1701.07875/) (2017)
- [Scalable Extraction of Training Data from (Production) Language Models](https://mlsanity.com/paper/2311.17035/) (2023)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Differentially Private Generative Adversarial Network](https://mlsanity.com/paper/1802.06739/) (2018)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [LDP-Fed: Federated Learning with Local Differential Privacy](https://mlsanity.com/paper/2006.03637/) (2020)
- [Protection Against Reconstruction and Its Applications in Private Federated Learning](https://mlsanity.com/paper/1812.00984/) (2018)
- [DP-CGAN: Differentially Private Synthetic Data and Label Generation](https://mlsanity.com/paper/2001.09700/) (2020)
- [Privacy Amplification by Iteration](https://mlsanity.com/paper/1808.06651/) (2018)
- [On Protecting the Data Privacy of Large Language Models (LLMs): A Survey](https://mlsanity.com/paper/2403.05156/) (2024)
- [Unveiling Security, Privacy, and Ethical Concerns of ChatGPT](https://mlsanity.com/paper/2307.14192/) (2023)
- [Optimal Algorithms for Mean Estimation under Local Differential Privacy](https://mlsanity.com/paper/2205.02466/) (2022)
- [PPGAN: Privacy-preserving Generative Adversarial Network](https://mlsanity.com/paper/1910.02007/) (2019)
- [Privacy Odometers and Filters: Pay-as-you-Go Composition](https://mlsanity.com/paper/1605.08294/) (2016)
- [Optimal Schemes for Discrete Distribution Estimation under Locally Differential Privacy](https://mlsanity.com/paper/1702.00610/) (2017)
- [On the Privacy-Robustness-Utility Trilemma in Distributed Learning](https://mlsanity.com/paper/2302.04787/) (2023)
- [Differentially Private Next-Token Prediction of Large Language Models](https://mlsanity.com/paper/2403.15638/) (2024)
- [Decentralized Wireless Federated Learning with Differential Privacy](https://mlsanity.com/paper/2109.09142/) (2021)
- [Discrete Distribution Estimation under User-level Local Differential Privacy](https://mlsanity.com/paper/2211.03757/) (2022)
- [Shake to Leak: Fine-tuning Diffusion Models Can Amplify the Generative Privacy Risk](https://mlsanity.com/paper/2403.09450/) (2024)
- [Regression with Label Differential Privacy](https://mlsanity.com/paper/2212.06074/) (2022)
- [Fast Optimal Locally Private Mean Estimation via Random Projections](https://mlsanity.com/paper/2306.04444/) (2023)
- [Federated Linear Contextual Bandits with User-level Differential Privacy](https://mlsanity.com/paper/2306.05275/) (2023)
- [Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints](https://mlsanity.com/paper/2301.03566/) (2023)
- [GeoPointGAN: Synthetic Spatial Data with Local Label Differential Privacy](https://mlsanity.com/paper/2205.08886/) (2022)
- [Exact Optimality of Communication-Privacy-Utility Tradeoffs in Distributed Mean Estimation](https://mlsanity.com/paper/2306.04924/) (2023)
- [Differentially Private Sampling from Distributions](https://mlsanity.com/paper/2211.08193/) (2022)

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

- [Locally Private Sampling with Public Data](https://mlsanity.com/paper/2411.08791/) (2024)
- [Locally Optimal Private Sampling: Beyond the Global Minimax](https://mlsanity.com/paper/2510.09485/) (2025)
- [Reveal-or-Obscure: A Differentially Private Sampling Algorithm for Discrete Distributions](https://mlsanity.com/paper/2504.14696/) (2025)
- [Privately Estimating Black-Box Statistics](https://mlsanity.com/paper/2510.00322/) (2025)
- [Differentially Private Sampling from Distributions via Wasserstein Projection](https://mlsanity.com/paper/2605.10015/) (2026)

## 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.