Algorithmically Effective Differentially Private Synthetic Data

2023/02/11 by Yiyun He, He, Yiyun, Roman Vershynin +3 · 1 citation
Computer Science · #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Privacy-Preserving Technologies in Data #Probability (math.PR) #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.2302.05552

openalex publication_date 2023/02/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a highly effective algorithmic approach for generating ε-differentially private synthetic data in a bounded metric space with near-optimal utility guarantees under the 1-Wasserstein distance. In particular, for a dataset X in the hypercube [0,1]^d, our algorithm generates synthetic dataset Y such that the expected 1-Wasserstein distance between the empirical measure of X and Y is O((ε n)^-1/d) for d≥ 2, and is O(log²(ε n)(ε n)^-1) for d=1. The accuracy guarantee is optimal up to a constant factor for d≥ 2, and up to a logarithmic factor for d=1. Our algorithm has a fast running time of O(ε dn) for all d≥ 1 and demonstrates improved accuracy compared to the method in (Boedihardjo et al., 2022) for d≥ 2.

Cited by

• Differentially Private Wasserstein Barycenters

Related

• Differentially Private Low-dimensional Synthetic Data from High-dimensional Datasets
• Private measures, random walks, and synthetic data
• Differentially Private Wasserstein Barycenters
• Learning with Differentially Private (Sliced) Wasserstein Gradients
• Private Evolution Converges