提出新方法，让私密数据查询相对误差更小。
PREM: Privately Answering Statistical Queries with Relative Error
- 用乘法权重更新框架实现相对误差保障。
- 查询误差为1±ζ倍，附加误差仅与对数相关。
- 适合对精度要求高的隐私数据分析场景。
我们提出PREM（私有相对误差乘法权重更新）框架，用于生成满足(ε, δ)差分隐私的合成数据，并对统计查询提供相对误差保证。给定数据域𝒳、查询族ℱ（𝑓: 𝒳 → {0,1}）及ζ>0，该框架在输入数据集𝐷∈𝒳ⁿ后输出合成数据集𝒟̂∈𝒳ⁿ，使得ℱ中所有查询在𝐷上的真实值∑_{x∈𝐷}𝑓(x)与𝒟̂上对应值的相对误差控制在1±ζ范围内，附加误差为log|ℱ|、log|𝒳|、log𝑛、log(1/δ)、1/ε、1/ζ的多项式级别。相比之下，任何(ε, δ)-DP机制的最坏情况附加误差至少与𝑛、|ℱ|、|𝒳|之一呈多项式关系。本文还给出了近乎匹配的下界证明。
原文摘要 · Abstract (English)
We introduce $\mathsf{PREM}$ (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} \to \{0, 1\}$, and $ζ> 0$, our framework yields a mechanism that on input dataset $D \in {\cal X}^n$ outputs a synthetic dataset $\widehat{D} \in {\cal X}^n$ such that all statistical queries in ${\cal F}$ on $D$, namely $\sum_{x \in D} f(x)$ for $f \in {\cal F}$, are within a $1 \pm ζ$ multiplicative factor of the corresponding value on $\widehat{D}$ up to an additive error that is polynomial in $\log |{\cal F}|$, $\log |{\cal X}|$, $\log n$, $\log(1/δ)$, $1/\varepsilon$, and $1/ζ$. 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。