Privacy and Utility Tradeoff in Approximate Differential Privacy
  We characterize the minimum noise amplitude and power for noise-adding
mechanisms in $(\epsilon, \delta)$-differential privacy for single real-valued
query function. We derive new lower bounds using the duality of linear
programming, and new upper bounds by proposing a new class of
$(\epsilon,\delta)$-differentially private mechanisms, the \emph{truncated
Laplacian} mechanisms. We show that the multiplicative gap of the lower bounds
and upper bounds goes to zero in various high privacy regimes, proving the
tightness of the lower and upper bounds and thus establishing the optimality of
the truncated Laplacian mechanism. In particular, our results close the
previous constant multiplicative gap in the discrete setting. Numeric
experiments show the improvement of the truncated Laplacian mechanism over the
optimal Gaussian mechanism in all privacy regimes.
