# PREM: Privately Answering Statistical Queries with Relative Error

arXiv: https://arxiv.org/abs/2502.14809 · HTML: https://mlsanity.com/paper/2502.14809/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Feb 2025.

## Built on by (most cited first, 2 of 2)

- [Privately Learning Decision Lists and a Differentially Private Winnow](https://mlsanity.com/paper/2602.07370/) (2026)
- [Fixed-Parameter Tractability of Private Synthetic Data Generation](https://mlsanity.com/paper/2606.11283/) (2026)

## Abstract (arXiv)

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.