Optimal Multidimensional Differentially Private Mechanisms in the Large-Composition Regime
Wael Alghamdi, Shahab Asoodeh, Flávio P. Calmon, Juan Felipe Gomez, Oliver Kosut, Lalitha Sankar · 2023
We construct vector differentially-private (DP) mechanisms that are asymptotically optimal in the limit of the number of compositions growing without bound. First, we derive via the central limit theorem a reduction from DP to a KL-divergence minimization problem. Second, we formulate the general theory of spherically-symmetric DP mechanisms in the large-composition regime. Specifically, we show that additive, continuous, spherically-symmetric DP mechanisms are optimal if one considers a spherically-symmetric cost (e.g., bounded noise variance) and an ℓ2sensitivity metric. We then formulate a finite-dimensional problem that produces noise distributions that can get arbitrarily close to optimal among monotone mechanisms. Finally, we demonstrate numerically that our proposed mechanism achieves better DP parameters than the vector Gaussian mechanism for the same variance constraint.