The paper tackles differentially private (DP) sampling from a distribution, addressing two limitations of prior work that used KL divergence: it ignores geometric structure and fails when distribution supports differ. They propose using Wasserstein distance (which measures the minimum "transport cost" to move probability mass between distributions) as the utility measure instead. They introduce the Wasserstein Projection Mechanism (WPM), a minimax optimal DP sampling method based on projecting onto the feasible distribution set under Wasserstein distance, and provide efficient approximation algorithms with convergence guarantees.
Main takeaways:
- Uses Wasserstein distance instead of KL divergence to measure utility of DP sampling, capturing geometric structure and handling different supports
- Proposes Wasserstein Projection Mechanism (WPM) as a minimax optimal DP sampling method
- Provides efficient approximation algorithms for computing WPM with convergence guarantees
- Addresses key limitations of density ratio-based measures like KL divergence in the DP sampling setting