Extreme Points of the $(0,δ)$-LDP Polytope with Small Input Size and Arbitrary Output Sizes
2026-06-08 • Information Theory
Information Theory
AI summaryⓘ
The authors study privacy methods called locally differentially private (LDP) mechanisms, focusing on a version that allows a small chance of error (labeled by parameters (ε, δ)). Previous work has explained the structure when δ is zero, but not much is known when δ is positive. The authors fully describe the key building blocks (extreme points) of these privacy methods for small input sizes (2 and 3), regardless of output size. They also find new types of privacy methods for larger input sizes, expanding understanding of how these mechanisms work.
locally differentially private (LDP)privacy polytopeextreme points(ε, δ)-LDPinput alphabet sizeoutput alphabet sizestar configurationdifferential privacymechanism designprivacy guarantees
Authors
Supriya Rawat, Myna Vajha, Gowtham R. Kurri, Anand Sarwate
Abstract
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).