Privately Answering Counting Queries with Generalized Gaussian Mechanisms

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.