Generating Private Synthetic Data with Genetic Algorithms
Terrance Liu Jingwu Tang Giuseppe Vietri Zhiwei Steven Wu
We study the problem of efficiently generating differentially private
synthetic data that approximate the statistical properties of an underlying
sensitive dataset. In recent years, there has been a growing line of work that
approaches this problem using first-order optimization techniques. However,
such techniques are restricted to optimizing differentiable objectives only,
severely limiting the types of analyses that can be conducted. For example,
first-order mechanisms have been primarily successful in approximating
statistical queries only in the form of marginals for discrete data domains. In
some cases, one can circumvent such issues by relaxing the task's objective to
maintain differentiability. However, even when possible, these approaches
impose a fundamental limitation in which modifications to the minimization
problem become additional sources of error. Therefore, we propose Private-GSD,
a private genetic algorithm based on zeroth-order optimization heuristics that
do not require modifying the original objective. As a result, it avoids the
aforementioned limitations of first-order optimization. We empirically evaluate
Private-GSD against baseline algorithms on data derived from the American
Community Survey across a variety of statistics--otherwise known as statistical
queries--both for discrete and real-valued attributes. We show that Private-GSD
outperforms the state-of-the-art methods on non-differential queries while
matching accuracy in approximating differentiable ones.