通过相关高斯噪声降低稀疏直方图的隐私误差，提升数据可用性。
The Correlated Gaussian Sparse Histogram Mechanism
- 引入相关高斯噪声替代独立噪声，利用稀疏性约束减少扰动幅度。
- 在稀疏场景下可将阈值降低一半，使误差显著下降。
- 适用于实际中的离散高斯机制，适合注重隐私保护的数据发布。
本文研究在 $(\varepsilon, δ)$-差分隐私下发布稀疏直方图的问题。传统稳定直方图对非零条目独立添加拉普拉斯或高斯噪声，并移除低于阈值的噪声计数。新非零值在相邻直方图中被泄露的概率不超过 $δ$，通常阈值决定误差大小。本文考虑使用相关高斯噪声的变体。近期工作（Joseph and Yu, COLT '24；Lebeda, SOSA '25）已通过相关噪声降低隐私直方图误差，但无法直接应用于极稀疏场景。本文采用 Lebeda 技术，证明在有稀疏性约束时，对非零计数添加相关噪声可降低噪声幅度，从而允许将阈值降低至原来的一半。进一步扩展机制至无已知稀疏性边界的情况。同时表明，相关噪声对更实用的离散高斯机制亦有类似改进效果。
原文摘要 · Abstract (English)
We consider the problem of releasing a sparse histogram under $(\varepsilon, δ)$-differential privacy. The stability histogram independently adds noise from a Laplace or Gaussian distribution to the non-zero entries and removes those noisy counts below a threshold. Thereby, the introduction of new non-zero values between neighboring histograms is only revealed with probability at most $δ$, and typically, the value of the threshold dominates the error of the mechanism. We consider the variant of the stability histogram with Gaussian noise. Recent works ([Joseph and Yu, COLT '24] and [Lebeda, SOSA '25]) reduced the error for private histograms using correlated Gaussian noise. However, these techniques can not be directly applied in the very sparse setting. Instead, we adopt Lebeda's technique and show that adding correlated noise to the non-zero counts only allows us to reduce the magnitude of noise when we have a sparsity bound. This, in turn, allows us to use a lower threshold by up to a factor of $1/2$ compared to the non-correlated noise mechanism. We then extend our mechanism to a setting without a known bound on sparsity. Additionally, we show that correlated noise can give a similar improvement for the more practical discrete Gaussian mechanism.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。