# Locally Optimal Private Sampling: Beyond the Global Minimax

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 58 references that are in the map.
- First posted on arXiv 10 Oct 2025.

## Builds on (most cited first, 29 of 29)

- [Ditto: Fair and Robust Federated Learning Through Personalization](https://mlsanity.com/paper/2012.04221/) (2020)
- [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)
- [Personalized Federated Learning with First Order Model Optimization](https://mlsanity.com/paper/2012.08565/) (2020)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [DP-CGAN: Differentially Private Synthetic Data and Label Generation](https://mlsanity.com/paper/2001.09700/) (2020)
- [Learning with User-Level Privacy](https://mlsanity.com/paper/2102.11845/) (2021)
- [PPGAN: Privacy-preserving Generative Adversarial Network](https://mlsanity.com/paper/1910.02007/) (2019)
- [Differentially Private Next-Token Prediction of Large Language Models](https://mlsanity.com/paper/2403.15638/) (2024)
- [Discrete Distribution Estimation under User-level Local Differential Privacy](https://mlsanity.com/paper/2211.03757/) (2022)
- [Federated Linear Contextual Bandits with User-level Differential Privacy](https://mlsanity.com/paper/2306.05275/) (2023)
- [A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacy](https://mlsanity.com/paper/2405.13453/) (2024)
- [GeoPointGAN: Synthetic Spatial Data with Local Label Differential Privacy](https://mlsanity.com/paper/2205.08886/) (2022)
- [Instance-Optimal Private Density Estimation in the Wasserstein Distance](https://mlsanity.com/paper/2406.19566/) (2024)
- [Contraction of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2210.13386/) (2022)
- [Differentially Private Sampling from Distributions](https://mlsanity.com/paper/2211.08193/) (2022)
- [Instance-Optimal Differentially Private Estimation](https://mlsanity.com/paper/2210.15819/) (2022)
- [On Differentially Private Sampling from Gaussian and Product Distributions](https://mlsanity.com/paper/2306.12549/) (2023)
- [Rate Optimality and Phase Transition for User-Level Local Differential Privacy](https://mlsanity.com/paper/2405.11923/) (2024)
- [Local Differential Privacy Image Generation Using Flow-based Deep Generative Models](https://mlsanity.com/paper/2212.10688/) (2022)
- [Metric Differential Privacy at the User-Level Via the Earth Mover's Distance](https://mlsanity.com/paper/2405.02665/) (2024)
- [Exactly Minimax-Optimal Locally Differentially Private Sampling](https://mlsanity.com/paper/2410.22699/) (2024)
- [Adaptively Private Next-Token Prediction of Large Language Models](https://mlsanity.com/paper/2410.02016/) (2024)
- [Locally Private Sampling with Public Data](https://mlsanity.com/paper/2411.08791/) (2024)
- [PrivShape: Extracting Shapes in Time Series under User-Level Local Differential Privacy](https://mlsanity.com/paper/2404.03873/) (2024)
- [Differentially Private Multi-Sampling from Distributions](https://mlsanity.com/paper/2412.10512/) (2024)
- [Optimal Differentially Private Sampling of Unbounded Gaussians](https://mlsanity.com/paper/2503.01766/) (2025)
- [Reveal-or-Obscure: A Differentially Private Sampling Algorithm for Discrete Distributions](https://mlsanity.com/paper/2504.14696/) (2025)

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

- [Differentially Private Sampling from Distributions via Wasserstein Projection](https://mlsanity.com/paper/2605.10015/) (2026)
- [Auditing and Mitigating Privacy Leakage in Cloud-Edge Collaborative Decoding](https://mlsanity.com/paper/2608.29111/) (2026)

## Abstract (arXiv)

We study the problem of sampling from a distribution under local differential privacy (LDP). Given a private distribution P ∈ P, the goal is to generate a single sample from a distribution that remains close to P in f-divergence while satisfying the constraints of LDP. This task captures the fundamental challenge of producing realistic-looking data under strong privacy guarantees. While prior work by Park et al. (NeurIPS'24) focuses on global minimax-optimality across a class of distributions, we take a local perspective. Specifically, we examine the minimax risk in a neighborhood around a fixed distribution P0, and characterize its exact value, which depends on both P0 and the privacy level. Our main result shows that the local minimax risk is determined by the global minimax risk when the distribution class P is restricted to a neighborhood around P0. To establish this, we (1) extend previous work from pure LDP to the more general functional LDP framework, and (2) prove that the globally optimal functional LDP sampler yields the optimal local sampler when constrained to distributions near P0. Building on this, we also derive a simple closed-form expression for the locally minimax-optimal samplers which does not depend on the choice of f-divergence. We further argue that this local framework naturally models private sampling with public data, where the public data distribution is represented by P0. In this setting, we empirically compare our locally optimal sampler to existing global methods, and demonstrate that it consistently outperforms global minimax samplers.