# Duff: A Dataset-Distance-Based Utility Function Family for the Exponential Mechanism

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Oct 2020.

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

- [Differentially Private Quantiles](https://mlsanity.com/paper/2102.08244/) (2021)
- [Easy Differentially Private Linear Regression](https://mlsanity.com/paper/2208.07353/) (2022)
- [DP-XGBoost: Private Machine Learning at Scale](https://mlsanity.com/paper/2110.12770/) (2021)
- [Differentially Private Top-k Selection via Canonical Lipschitz Mechanism](https://mlsanity.com/paper/2201.13376/) (2022)
- [Differentially Private Prototypes for Imbalanced Transfer Learning](https://mlsanity.com/paper/2406.08039/) (2024)
- [Tukey Depth Mechanisms for Practical Private Mean Estimation](https://mlsanity.com/paper/2502.18698/) (2025)

## Abstract (arXiv)

We propose and analyze a general-purpose dataset-distance-based utility function family, Duff, for differential privacy's exponential mechanism. Given a particular dataset and a statistic (e.g., median, mode), this function family assigns utility to a possible output o based on the number of individuals whose data would have to be added to or removed from the dataset in order for the statistic to take on value o. We show that the exponential mechanism based on Duff often offers provably higher fidelity to the statistic's true value compared to existing differential privacy mechanisms based on smooth sensitivity. In particular, Duff is an affirmative answer to the open question of whether it is possible to have a noise distribution whose variance is proportional to smooth sensitivity and whose tails decay at a faster-than-polynomial rate. We conclude our paper with an empirical evaluation of the practical advantages of Duff for the task of computing medians.