


























The structure of locally differentially private (LDP) mechanisms can be understood through the geometry of the corresponding privacy polytope. While the extreme points of the \( (ε,0)\)-LDP polytope are well characterized (Kairouz \emph{et al.}, 2014; Holohan \emph{et al.}, 2017; Pensia \emph{et al.}, 2017), comparatively little is known for the \((ε,δ)\)-LDP polytope with \(δ>0\). Recent work (Elangovan and Jog, 2024) has shown that even in the special case \(ε=0\), the \( (0,δ) \)-LDP privacy polytope exhibits fundamentally different behaviour. In this work, we provide complete characterizations of the extreme points for the low-input-alphabet regime \(k=2\) and \(k=3\) and with arbitrary output alphabet size \(m \). We also identify new extreme mechanisms for larger input alphabet sizes $k$, of the star configuration type, as introduced by Elangovan and Jog (2024).
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。