可擴展的差分隱私雜訊大號p大號pL_p- 敏感性與p>2p>2p>2?
眾所周知，要使結果 $ \mathbb{R}^d $ 值查詢 $ (\varepsilon,\delta) $ - 差分私有，您可以為其添加噪音。如果添加拉普拉斯雜訊，則需要通過 $ L_1 $ - 查詢的敏感性；如果添加高斯雜訊，則需要將其縮放 $ L_2 $ - 敏感性代替。
是否存在可以縮放的雜訊函式，例如， $ L_3 $ - 敏感性，或任何其他 $ L_p $ - 敏感性與 $ p>2 $ ? 如果不是，如何形式化和證明這個不可能的結果？
您可以在任意規範中測量您的靈敏度。指數機制，從分佈中採樣 $ \exp(-\epsilon |z-f(x)|_p / 2) $ 會給純DP。這是更通用的，K-norm 機制將允許您處理以除某些 p-norm 之外的規範測量的靈敏度。對於純 DP，這些 p 範數機制是最優的。特別是，當靈敏度測量在 $ \ell_2 $ 範數，最優機制會增加來自 Gamma 分佈的雜訊。
那麼高斯雜訊機制如何做得更好呢？它給你 $ (\epsilon, \delta) $ -DP而不是純DP。很自然地要問其他靈敏度測量的最佳近似 DP 機制是什麼。事實證明，對於近似 DP，正確的高斯機制總是最優的。你只需轉換你的 $ \ell_p $ 靈敏度綁定到 $ \ell_2 $ 靈敏度界限（通過找到最小的 $ \ell_2 $ 包含你的球 $ \ell_p $ 球）並在此基礎上添加高斯雜訊。同樣，在非 p 範數中測量的靈敏度也有類似的結果。
一些警告是有序的。上面的最佳值是您在歐幾里得距離中測量的誤差。某些結果僅在對數因子的範圍內是最佳的。當您關心其他規範中的錯誤時（例如 $ \ell_\infty $ )，還有其他更有趣的機制。
參考：上限 $ \ell_p $ 球很簡單。下限在 https://arxiv.org/abs/0907.3754>和<https://arxiv.org/abs/1212.0297中。CDP/RDP 的更簡單的下限在https://arxiv.org/abs/1911.08339中。