提出高效私密的边缘查询重建方法，降低隐私预算消耗。
Efficient and Private Marginal Reconstruction with Local Non-Negativity
- 基于残差基的高效伪逆机制，实现快速重建
- 引入局部非负约束，减少重建误差
- 适用于高维数据的私密查询回答系统
差分隐私是主流的可量化隐私保护标准，已广泛应用于影响数百万人的系统。许多差分隐私的查询发布与合成数据算法中，需通过其他已私密测量的查询结果来重构目标查询答案。重建是此类机制的关键子问题，有助于节省隐私预算、降低重建误差，并支持高维数据扩展。本文提出一种原理严谨且高效的后处理方法 ReM（Residuals-to-Marginals），用于重构边缘查询答案。该方法基于近期关于边缘查询高效发布的成果，利用可高效伪逆的残差查询基。进一步提出 GReM-LNN（Gaussian Residuals-to-Marginals with Local Non-negativity），在满足一致性与非负性约束的高斯噪声下进行重建，通常可降低重建误差。我们通过实证表明，ReM 和 GReM-LNN 可有效提升现有私密查询回答机制的性能。
原文摘要 · Abstract (English)
Differential privacy is the dominant standard for formal and quantifiable privacy and has been used in major deployments that impact millions of people. Many differentially private algorithms for query release and synthetic data contain steps that reconstruct answers to queries from answers to other queries that have been measured privately. Reconstruction is an important subproblem for such mechanisms to economize the privacy budget, minimize error on reconstructed answers, and allow for scalability to high-dimensional datasets. In this paper, we introduce a principled and efficient postprocessing method ReM (Residuals-to-Marginals) for reconstructing answers to marginal queries. Our method builds on recent work on efficient mechanisms for marginal query release, based on making measurements using a residual query basis that admits efficient pseudoinversion, which is an important primitive used in reconstruction. An extension GReM-LNN (Gaussian Residuals-to-Marginals with Local Non-negativity) reconstructs marginals under Gaussian noise satisfying consistency and non-negativity, which often reduces error on reconstructed answers. We demonstrate the utility of ReM and GReM-LNN by applying them to improve existing private query answering mechanisms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。