2020/10/04 by Ganesh, Arun, Zhao, Jiazheng · 2 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2010.01457
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 d with the ℓ_∞-error guarantee: E[||d - d||_∞] = O(\frac√(k log log log k log(1/δ))ε). 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 Generalized Gaussian, i.e. with probability proportional to exp(-(||x||p/σ)p), and output d = 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.