A bounded-noise mechanism for differential privacy

Understand

We present an asymptotically optimal $(\epsilon,\delta)$ differentially private mechanism for answering multiple, adaptively asked, $\Delta$-sensitive queries, settling the conjecture of Steinke and Ullman [2020].

• Our algorithm has a significant advantage that it adds independent bounded noise to each query, thus providing an absolute error bound.
• Additionally, we apply our algorithm in adaptive data analysis, obtaining an improved guarantee for answering multiple queries regarding some underlying distribution using a finite sample.
• Numerical computations show that the bounded-noise mechanism outperforms the Gaussian mechanism in many standard settings.