PREM: Privately Answering Statistical Queries with Relative Error

We introduce PREM (Private Relative Error Multiplicative weight update) a new (ε, δ)-DP mechanism for privately generating synthetic data that achieves a relative error guarantee for linear queries. Namely, for a domain X, a family F of queries f : X → {0, 1}, and ζ > 0, the mechanism on input dataset D ∈ X^n outputs a synthetic dataset D ̃ ∈ X^n such that all linear queries in F on D, namely sum_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/ζ. This is in contrast to the standard additive-error only setting considered in the literature, which is known to require polynomial error in at least one of n, |F|, or |X |. We complement the algorithm with nearly matching lower bounds.