The Optimal Mechanism in Differential Privacy: Multidimensional Setting
This work addresses the challenge of improving privacy-utility trade-offs in differential privacy for multidimensional data, offering a theoretical advance with potential applications in data analysis, though it is incremental as it builds on existing mechanisms.
The paper tackles the problem of designing an optimal differentially private mechanism for two-dimensional real-valued queries under an ℓ¹ cost function, deriving a correlated multidimensional staircase-shaped noise distribution and showing that it outperforms the Laplacian mechanism, especially in the low privacy regime where the optimal cost scales as Θ(e^{-ε/3}) compared to 2Δ/ε for Laplacian.
We derive the optimal $ε$-differentially private mechanism for a general two-dimensional real-valued (histogram-like) query function under a utility-maximization (or cost-minimization) framework for the $\ell^1$ cost function. We show that the optimal noise probability distribution has a correlated multidimensional staircase-shaped probability density function. Compared with the Laplacian mechanism, we show that in the high privacy regime (as $ε\to 0$), the Laplacian mechanism is approximately optimal; and in the low privacy regime (as $ε\to +\infty$), the optimal cost is $Θ(e^{-\fracε{3}})$, while the cost of the Laplacian mechanism is $\frac{2Δ}ε$, where $Δ$ is the sensitivity of the query function. We conclude that the gain is more pronounced in the low privacy regime. We conjecture that the optimality of the staircase mechanism holds for vector-valued (histogram-like) query functions with arbitrary dimension, and holds for many other classes of cost functions as well.