PREM: Privately Answering Statistical Queries with Relative Error

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