2025/02/20 by Ghazi, Badih, Guzmán, Cristóbal, Kamath, Pritish +4
#FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · doi:10.48550/arxiv.2502.14809
We introduce PREM (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 \cal X, a family \cal F of queries f : \cal X → \0, 1\, and ζ> 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 ∑x ∈ D f(x) for f ∈ \cal F, are within a 1 ± ζ 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/ε, and 1/ζ. In contrast, any (ε, δ)-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.