# Privacy and Utility Tradeoff in Approximate Differential Privacy

arXiv: https://arxiv.org/abs/1810.00877 · HTML: https://mlsanity.com/paper/1810.00877/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Oct 2018.

## Built on by (most cited first, 3 of 3)

- [Polynomial Time and Private Learning of Unbounded Gaussian Mixture Models](https://mlsanity.com/paper/2303.04288/) (2023)
- [Echo of Neighbors: Privacy Amplification for Personalized Private Federated Learning with Shuffle Model](https://mlsanity.com/paper/2304.05516/) (2023)
- [Agnostic Private Density Estimation for GMMs via List Global Stability](https://mlsanity.com/paper/2407.04783/) (2024)

## Abstract (arXiv)

We characterize the minimum noise amplitude and power for noise-adding mechanisms in (ε, δ)-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 (ε,δ)-differentially private mechanisms, the 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.