# A Central Limit Theorem for Differentially Private Query Answering

arXiv: https://arxiv.org/abs/2103.08721 · HTML: https://mlsanity.com/paper/2103.08721/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 42 references that are in the map.
- First posted on arXiv 15 Mar 2021.

## Builds on (most cited first, 14 of 14)

- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising](https://mlsanity.com/paper/1805.06530/) (2018)
- [Fingerprinting Codes and the Price of Approximate Differential Privacy](https://mlsanity.com/paper/1311.3158/) (2013)
- [Between Pure and Approximate Differential Privacy](https://mlsanity.com/paper/1501.06095/) (2015)
- [Prochlo: Strong Privacy for Analytics in the Crowd](https://mlsanity.com/paper/1710.00901/) (2017)
- [The Power of Factorization Mechanisms in Local and Central Differential Privacy](https://mlsanity.com/paper/1911.08339/) (2019)
- [Differentially Private Algorithms for Learning Mixtures of Separated Gaussians](https://mlsanity.com/paper/1909.03951/) (2019)
- [LinkedIn's Audience Engagements API: A Privacy Preserving Data Analytics System at Scale](https://mlsanity.com/paper/2002.05839/) (2020)
- [Towards Practical Differential Privacy for SQL Queries](https://mlsanity.com/paper/1706.09479/) (2017)
- [The Cost of Privacy in Generalized Linear Models: Algorithms and Minimax Lower Bounds](https://mlsanity.com/paper/2011.03900/) (2020)
- [A bounded-noise mechanism for differential privacy](https://mlsanity.com/paper/2012.03817/) (2020)
- [On Avoiding the Union Bound When Answering Multiple Differentially Private Queries](https://mlsanity.com/paper/2012.09116/) (2020)
- [Optimal Differential Privacy Composition for Exponential Mechanisms and the Cost of Adaptivity](https://mlsanity.com/paper/1909.13830/) (2019)

## Built on by (most cited first, 7 of 7)

- [Unified Enhancement of Privacy Bounds for Mixture Mechanisms via f-Differential Privacy](https://mlsanity.com/paper/2310.19973/) (2023)
- [A Statistical Viewpoint on Differential Privacy: Hypothesis Testing, Representation and Blackwell's Theorem](https://mlsanity.com/paper/2409.09558/) (2024)
- [Gaussian Certified Unlearning in High Dimensions: A Hypothesis Testing Approach](https://mlsanity.com/paper/2510.13094/) (2025)
- [Mitigating Privacy-Utility Trade-off in Decentralized Federated Learning via f-Differential Privacy](https://mlsanity.com/paper/2510.19934/) (2025)
- [Rejoinder: Gaussian Differential Privacy](https://mlsanity.com/paper/2104.01987/) (2021)
- [Differential privacy for symmetric log-concave mechanisms](https://mlsanity.com/paper/2202.11393/) (2022)
- [Optimality of Staircase Mechanisms for Vector Queries under Differential Privacy](https://mlsanity.com/paper/2601.14597/) (2026)

## Abstract (arXiv)

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 e-|x|pα, where |x|p is the standard ℓ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 ℓ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.