# Privately Answering Counting Queries with Generalized Gaussian Mechanisms

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Oct 2020.

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

- [Differentially Private Multi-Sampling from Distributions](https://mlsanity.com/paper/2412.10512/) (2024)
- [Beyond Laplace and Gaussian: Exploring the Generalized Gaussian Mechanism for Private Machine Learning](https://mlsanity.com/paper/2506.12553/) (2025)
- [Privately Estimating Black-Box Statistics](https://mlsanity.com/paper/2510.00322/) (2025)
- [Predicting adaptively chosen observables in quantum systems](https://mlsanity.com/paper/2410.15501/) (2024)

## Abstract (arXiv)

We consider the problem of answering k counting (i.e. sensitivity-1) queries about a database with (ε, δ)-differential privacy. We give a mechanism such that if the true answers to the queries are the vector d, the mechanism outputs answers tilded with the ℓ_∞-error guarantee: Eleft[||tilded - d||_∞right] = Oleft(frac√k log log log k log(1/δ)εright). This reduces the multiplicative gap between the best known upper and lower bounds on ℓ_∞-error from O(√log log k) to O(√log log log k). Our main technical contribution is an analysis of the family of mechanisms of the following form for answering counting queries: Sample x from a textitGeneralized Gaussian, i.e. with probability proportional to exp(-(||x||p/σ)p), and output tilded = d + x. This family of mechanisms offers a tradeoff between ℓ1 and ℓ_∞-error guarantees and may be of independent interest. For p = O(log log k), this mechanism already matches the previous best known ℓ_∞-error bound. We arrive at our main result by composing this mechanism for p = O(log log log k) with the sparse vector mechanism, generalizing a technique of Steinke and Ullman.