A Central Limit Theorem for Differentially Private Query Answering

Abstract

Perhaps the single most important use case for differential privacy is to privately answer numerical queries, which is usually achieved by adding noise to the answer vector. The central question, therefore, is to understand which noise distribution optimizes the privacy-accuracy trade-off, especially when the dimension of the answer vector is high. Accordingly, extensive literature has been dedicated to the question and the upper and lower bounds have been matched up to constant factors [BUV18, SU17]. In this paper, we take a novel approach to address this important optimality question. We first demonstrate an intriguing central limit theorem phenomenon in the high-dimensional regime. More precisely, we prove that a mechanism is approximately Gaussian Differentially Private [DRS21] if the added noise satisfies certain conditions. In particular, densities proportional to ${\mathrm{e}}^{-\Vert x{\Vert }_p^{\alpha }}$, where $\Vert x{\Vert }_p$ is the standard ${\ell }_p$-norm, satisfies the conditions. Taking this perspective, we make use of the Cramer--Rao inequality and show an "uncertainty principle"-style result: the product of the privacy parameter and the ${\ell }_2$-loss of the mechanism is lower bounded by the dimension. Furthermore, the Gaussian mechanism achieves the constant-sharp optimal privacy-accuracy trade-off among all such noises. Our findings are corroborated by numerical experiments.

References in corpus (5)

• LinkedIn's Audience Engagements API: A Privacy Preserving Data Analytics System at Scale
• The Cost of Privacy in Generalized Linear Models: Algorithms and Minimax Lower Bounds
• Optimal Differential Privacy Composition for Exponential Mechanisms and the Cost of Adaptivity
• A bounded-noise mechanism for differential privacy
• On Avoiding the Union Bound When Answering Multiple Differentially Private Queries

Cited by in corpus (2)

• Differentially Private Multivariate Statistics with an Application to Contingency Table Analysis
• Rejoinder: Gaussian Differential Privacy