FR1.R8.2

On the Extreme Points of the (0, δ)-Differential Privacy Polytope

Karan Elangovan, Varun Jog, University of Cambridge, United Kingdom

Session:
Differential Privacy

Track:
16: Privacy and Fairness

Location:
Omega

Presentation Time:
Fri, 12 Jul, 10:05 - 10:25

Session Chair:
Asaf Cohen, Ben-Gorion University of the Negev
Abstract
The extreme points of the (ε, 0)-differential privacy polytope have been studied in prior work [9]–[11]. No such results exist for the (ε,δ)-differential privacy polytope for δ > 0. In this work, we highlight the challenges involved in this setting by studying the special case of the (0,δ)-differential privacy polytope with input [k] and output [m]. We characterise all extreme points for arbitrary k and m ≤ 3. We show that such a characterisation is elusive for m ≥ 4 by demonstrating examples of extreme channels that defy some natural conjectures.
Resources