# Differentially Private Selection using Smooth Sensitivity

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 53 references that are in the map.
- First posted on arXiv 10 Apr 2025.

## Builds on (most cited first, 10 of 10)

- [Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation](https://mlsanity.com/paper/1906.02830/) (2019)
- [Practical Differentially Private Top-k Selection with Pay-what-you-get Composition](https://mlsanity.com/paper/1905.04273/) (2019)
- [Permute-and-Flip: A new mechanism for differentially private selection](https://mlsanity.com/paper/2010.12603/) (2020)
- [Differentially Private Random Decision Forests using Smooth Sensitivity](https://mlsanity.com/paper/1606.03572/) (2016)
- [The Permute-and-Flip Mechanism is Identical to Report-Noisy-Max with Exponential Noise](https://mlsanity.com/paper/2105.07260/) (2021)
- [Principled Evaluation of Differentially Private Algorithms using DPBench](https://mlsanity.com/paper/1512.04817/) (2015)
- [Differentially Private Deep Learning with Smooth Sensitivity](https://mlsanity.com/paper/2003.00505/) (2020)
- [Free Gap Estimates from the Exponential Mechanism, Sparse Vector, Noisy Max and Related Algorithms](https://mlsanity.com/paper/2012.01592/) (2020)
- [Local Dampening: Differential Privacy for Non-numeric Queries via Local Sensitivity](https://mlsanity.com/paper/2012.04117/) (2020)
- [Differentially Private Selection using Smooth Sensitivity](https://mlsanity.com/paper/2410.10187/) (2024)

## Abstract (arXiv)

Differentially private selection mechanisms offer strong privacy guarantees for queries aiming to identify the top-scoring element r from a finite set R, based on a dataset-dependent utility function. While selection queries are fundamental in data science, few mechanisms effectively ensure their privacy. Furthermore, most approaches rely on global sensitivity to achieve differential privacy (DP), which can introduce excessive noise and impair downstream inferences. To address this limitation, we propose the Smooth Noisy Max (SNM) mechanism, which leverages smooth sensitivity to yield provably tighter (upper bounds on) expected errors compared to global sensitivity-based methods. Empirical results demonstrate that SNM is more accurate than state-of-the-art differentially private selection methods in three applications: percentile selection, greedy decision trees, and random forests.