On the Extreme Points of the (0, δ) - Differential Privacy Polytope
Karan Elangovan, Varun Jog · 2024
The extreme points of the$(\epsilon, 0)$-differential privacy polytope have been studied in prior work [9]–[11]. No such results exist for the$(\epsilon, \delta)$-differential privacy polytope for$\delta > 0$. In this work, we highlight the challenges involved in this setting by studying the special case of the$(0, \delta)$-differential privacy polytope with input$[k]$and output$[m]$. We characterise all extreme points for arbitrary$k$and$m\leq 3$. We show that such a characterisation is elusive for$m\geq 4$by demonstrating examples of extreme channels that defy some natural conjectures.