A bounded-noise mechanism for differential privacy
share
Answering multiple counting queries is one of the best-studied problems in differential privacy. Its goal is to output an approximation of the average 1/n∑_i=1^n x⃗^(i) of vectors x⃗^(i)∈ [0,1]^k, while preserving the privacy with respect to any x⃗^(i). We present an (ϵ,δ)-private mechanism with optimal ℓ_∞ error for most values of δ. This result settles the conjecture of Steinke and Ullman [2020] for the these values of δ. Our algorithm adds independent noise of bounded magnitude to each of the k coordinates, while prior solutions relied on unbounded noise such as the Laplace and Gaussian mechanisms.
READ FULL TEXT