Exactly Minimax-Optimal Locally Differentially Private Sampling
This provides foundational analysis for private sampling with applications to generative models, though it is incremental in extending existing privacy frameworks.
The paper tackles the fundamental privacy-utility trade-off in locally differentially private sampling by defining it in a minimax sense and characterizing exact trade-offs for finite and continuous data spaces, proposing universally optimal sampling mechanisms that outperform baselines in experiments.
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.