PREM: Privately Answering Statistical Queries with Relative Error

Abstract

We introduce $\mathsf{PREM}$ (Private Relative Error Multiplicative weight update), a new framework for generating synthetic data that achieves a relative error guarantee for statistical queries under $(\epsilon ,\hat{I}´)$ differential privacy (DP). Namely, for a domain $\mathcal{X}$, a family $\mathcal{F}$ of queries $f:\mathcal{X}\to \{0,1\}$, and $\hat{I}\P >0$, our framework yields a mechanism that on input dataset $D\in {\mathcal{X}}^n$ outputs a synthetic dataset $\hat{D}\in {\mathcal{X}}^n$ such that all statistical queries in $\mathcal{F}$ on $D$, namely ${\sum }_{x\in D}f(x)$ for $f\in \mathcal{F}$, are within a $1\pm \hat{I}\P$ multiplicative factor of the corresponding value on $\hat{D}$ up to an additive error that is polynomial in $\log |\mathcal{F}|$, $\log |\mathcal{X}|$, $\log n$, $\log (1/\hat{I}´)$, $1/\epsilon$, and $1/\hat{I}\P$. In contrast, any $(\epsilon ,\hat{I}´)$-DP mechanism is known to require worst-case additive error that is polynomial in at least one of $n,|\mathcal{F}|$, or $|\mathcal{X}|$. We complement our algorithm with nearly matching lower bounds.