证明阶梯噪声机制在向量查询中最优，可最小化隐私损失代价。
Optimality of Staircase Mechanisms for Vector Queries under Differential Privacy
- 用凸重排理论将复杂优化问题简化为一维分布族。
- 任意维度和范数下，阶梯机制在所有加性机制中代价最低。
- 为隐私领域长期猜想提供几何解释，适合研究隐私机制设计者。
我们研究在 ε-差分隐私（DP）约束下，针对向量查询的最优加性机制设计问题。给定查询的敏感度及衡量效用损失的范数单调成本函数，我们探讨在所有满足 ε-差分隐私的加性机制中，哪种噪声分布能最小化期望成本。通过凸重排理论，我们证明该无限维优化问题可约简为一个一维紧致凸的径向对称分布族，其极端点即为阶梯分布。由此得出：对于任意维度、任意范数及任意范数单调成本函数，均存在一个 ε-差分隐私的阶梯机制，在所有加性机制中达到最优。该结果解决了 Geng、Kairouz、Oh 与 Viswanath 提出的猜想，并从几何角度解释了阶梯机制在差分隐私中作为极值解出现的原因。
原文摘要 · Abstract (English)
We study the optimal design of additive mechanisms for vector-valued queries under $ε$-differential privacy (DP). Given only the sensitivity of a query and a norm-monotone cost function measuring utility loss, we ask which noise distribution minimizes expected cost among all additive $ε$-DP mechanisms. Using convex rearrangement theory, we show that this infinite-dimensional optimization problem admits a reduction to a one-dimensional compact and convex family of radially symmetric distributions whose extreme points are the staircase distributions. As a consequence, we prove that for any dimension, any norm, and any norm-monotone cost function, there exists an $ε$-DP staircase mechanism that is optimal among all additive mechanisms. This result resolves a conjecture of Geng, Kairouz, Oh, and Viswanath, and provides a geometric explanation for the emergence of staircase mechanisms as extremal solutions in differential privacy.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。