Privately Answering Counting Queries with Generalized Gaussian Mechanisms

Abstract

We consider the problem of answering $k$ counting (i.e. sensitivity-1) queries about a database with $(\epsilon ,\delta )$-differential privacy. We give a mechanism such that if the true answers to the queries are the vector $d$, the mechanism outputs answers $\tilde{d}$ with the ${\ell }_{\infty }$-error guarantee: $$\mathcal{E}\left[||\tilde{d}-d|{|}_{\infty }\right]=O\left(\frac{\sqrt{k\log \log \log k\log (1/\delta )}}{\epsilon }\right).$$ This reduces the multiplicative gap between the best known upper and lower bounds on ${\ell }_{\infty }$-error from $O(\sqrt{\log \log k})$ to $O(\sqrt{\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 \textit{Generalized Gaussian}, i.e. with probability proportional to $\exp (-(||x|{|}_p/\sigma {)}^p)$, and output $\tilde{d}=d+x$. This family of mechanisms offers a tradeoff between ${\ell }_1$ and ${\ell }_{\infty }$-error guarantees and may be of independent interest. For $p=O(\log \log k)$, this mechanism already matches the previous best known ${\ell }_{\infty }$-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.