Converse and Achievability Bounds on the Error of Approximate Differential Privacy

Considerable effort has been devoted to designing additive noise mechanisms that achieve $(ϵ,\delta )$-differential privacy for queries with ${\ell }_2$ sensitivity ${\Delta }_2$ while minimizing the resulting error. Let ${\mathcal{V}}_M({\Delta }_2)$ denote the infimum of the mean squared error (MSE) over all $M$-dimensional additive noise distributions that are $(ϵ,\delta )$-differentially private for every such query. We establish converse and achievability bounds on this optimal MSE. The converse (impossibility) shows that no feasible additive noise can achieve an MSE below $A_M({\Delta }_2)$ by more than $\mathcal{O}({\Delta }_2^2{M}^{-2})$, while under a further condition on the noise shape, the achievability (possibility) shows that generalized gamma noise achieves an MSE of at most $A_M({\Delta }_2)+\mathcal{O}({\Delta }_2^2{M}^{-2})$, where equation* aligned A_M(\Delta_2)=M\Delta_2^2v_0-\Delta_2^2C(\epsilon,\delta)+\Delta_2^2J(\epsilon,\delta)M. aligned equation* Here, ${\Delta }_2^2{v}_0$ is the exactly calibrated Gaussian variance per coordinate, and $C(ϵ,\delta )$ and $J(ϵ,\delta )$ are explicit functions of the privacy parameters alone. We derive the converse through the duality of error minimization under privacy constraints. To establish achievability, we develop an efficient noise calibration procedure that attains this upper bound. Our procedure determines the two shape parameters of the generalized gamma noise in closed form, avoiding the numerical shape search used by existing approaches. Relaxing the mild assumption on shape parameters required by our construction leaves the converse unchanged and increases the achievable upper bound by only $\mathcal{O}({\Delta }_2^2{M}^{-1})$. Numerical evaluations support the theoretical results.