Abstract

We study the (nearly) optimal mechanisms in $(\epsilon,\delta)$ -approximate differential privacy for integer-valued query functions and vector-valued (histogram-like) query functions under a utility-maximization/cost-minimization framework. We characterize the tradeoff between $\epsilon$ and $\delta$ in utility and privacy analysis for histogram-like query functions ( $\ell^{1}$ sensitivity), and show that the $(\epsilon,\delta)$ -differential privacy is a framework not much more general than the $(\epsilon,0)$ -differential privacy and $(0,\delta)$ -differential privacy in the context of $\ell^{1}$ and $\ell^{2}$ cost functions, i.e., minimum expected noise magnitude and noise power. In the same context of $\ell^{1}$ and $\ell^{2}$ cost functions, we show the near-optimality of uniform noise mechanism and discrete Laplacian mechanism in the high privacy regime (as $(\epsilon,\delta)\to(0,0)$ ). We conclude that in $(\epsilon,\delta)$ -differential privacy, the optimal noise magnitude and noise power are $\Theta(\min(\frac{1}{\epsilon},\frac{1}{\delta}))$ and $\Theta(\min(\frac{1}{\epsilon^{2}},\frac{1}{\delta^{2}}))$ , respectively, in the high privacy regime.