PREM: Privately Answering Statistical Queries with Relative Error

摘要

We introduce 𝖯𝖱𝖤𝖬 (Private Relative Error Multiplicative weight update), a new framework for generating synthetic data that achieves a relative error guarantee for statistical queries under (ε, δ)-differential privacy (DP). Namely, for a domain X, a family F of queries f : X→{0, 1}, and ζ > 0, our framework yields a mechanism that on input dataset D ∈ X^n outputs a synthetic dataset D∈ X^n such that all statistical queries in F on D, namely ∑_x ∈ D f(x) for f ∈ F, are within a 1 ±ζ multiplicative factor of the corresponding value on D up to an additive error that is polynomial in log | F|, log | X|, log n, log(1/δ), 1/ε, and 1/ζ. In contrast, any (ε, δ)-DP mechanism is known to require worst-case additive error that is polynomial in at least one of n, | F|, or | X|. We complement our algorithm with nearly matching lower bounds.