Approximate Differential Privacy of the $\ell_2$ Mechanism

We study the $\ell_2$ mechanism for computing a $d$-dimensional statistic with bounded $\ell_2$ sensitivity under approximate differential privacy. Across a range of privacy parameters, we find that the $\ell_2$ mechanism obtains error approaching that of the Laplace mechanism as $d \to 1$ and approaching that of the Gaussian mechanism as $d \to \infty$; however, it dominates both in between.

For a certain kind of statistic, we provide a new algorithm that computes the statistic with a quantitative privacy guarantee, with lower error than previous such algorithms.