Differentially Private Selection using Smooth Sensitivity

We propose the first mechanism for differentially private selection using the concept of ${\it smooth\ sensitivity}$, the Smooth Private Selection (SPS).

This page contains Python codes of our experiments on accuracy, rank error, and run time.

We pre-evaluated the value of $l$ for our mechanism in "beta_evaluation.ipynb".

In "Comparison with existing methods", we compared our SPS with two existing ${\it global\ sensitivity}$-based mechanisms (the exponential mechanism (EM) and the permute-and-flip (PF)). We also provide the results on Rank Error, which was calculated as $\mathrm{RE} = t - 1$, where $t$ denotes the true rank of the extracted data.

"Effects of gamma" provides an evaluation of suitable $\gamma$ for the SPS.

In Supplements.pdf, we provide the omitted proofs in the main paper.

Important Issue (2025/12)

Theorem 3 in the original paper is not rigorous; that is, the differential privacy guarantee is (expected to be) not necessarily $\left(\left( k + \frac{|\mathcal{R}|-1}{2} \cdot l \right) \cdot \epsilon\right)$. We revised Supplements.pdf accordingly. In the revised document, we state that differential privacy guarantee value is not more than $\left(\left( k + \frac{|\mathcal{R}|}{2} \cdot l \right) \cdot \epsilon\right)$. However, the true value should be truly less than that and indeed superior to that achieved by the mechanism with two-sided noise. Moreover, it should be even less than $\left(\left( k + \frac{|\mathcal{R}|-1}{2} \cdot l \right) \cdot \epsilon\right)$ when using an appropriate $(\alpha, \beta)$-admissible distribution. (Indeed, the accuracy results of SPS_(II) and SPS_(IV) in Fig. 1 can be higher than those in the original paper.)

Regarding this issue, we will revisit the discussion in our next paper (on this topic) and also propose a new mechanism that outperforms the SPS. → Enhanced SPS

Important Notes

This study is not specialized for any particular analysis purpose, but rather aims to enhance the basic theory and mechanisms regarding ${\it smooth\ sensitivity}$. In particular, this is the first study on private selection using ${smooth \ sensitivity}$, and we expect the research to widely expand in the future (cf. Future Directions below).
In our experiments, we took the case of employing genome statistics as a score function for one example, and showed that the proposed method (SPS) does have the potential to provide higher accuracy than existing ${\it global \ sensitivity}$-based methods. Certainly, depending on the score function and data characteristics, ${\it global\ sensitivity}$-based methods may be superior (cf. discussion in Section V); however, in terms of increasing the possibilities for better score functions and options for differentially private selection mechanisms, this study will have a significant impact.

Future Directions

・Developing an optimal method for determining the values of $k$ and $l$ that provide the highest accuracy for each analysis data. (This will also be important in constructing algorithms for numeric queries.)

・Conducting general theoretical analysis of our mechanism (including our methods for computing ${\it smooth\ sensitivity}$ and ${\it smooth\ upper\ bound}$ ) given the characteristics of the data, and clarifying conditions for SPS to outperform EM and PF.

・Exploring possible noise distributions with a density function other than $h(z) \propto \frac{1}{1+|z|^\gamma}$ (under $\epsilon$-differential privacy).
e.g.) For any $k \geq 2$ and $l > 0$, the distribution with density $h(z) \propto \frac{1}{|z|^k + l}$ should be $\left( \frac{l^{1/k}}{2 \cdot (k-1)^{\frac{k-1}{k}}} \cdot \epsilon, \ \frac{1}{2 (k-1)} \cdot \epsilon \right)$- ${\it admissible}$. (Detailed analyses on this distribution is provided in our paper in ACISP 2025.)
← Are there any cases where $\alpha$ and $\beta$ in the ${\it admissible}$ property cannot be represented as linear functions of $\epsilon$? / Given functions $\alpha$ and $\beta$, can we find an $(\alpha, \beta)$- ${\it admissible}$ distribution?

・Developing efficient algorithms for obtaining ${\it smooth\ sensitivity}$ (not ${\it smooth\ upper\ bound}$) for any $\beta$. (And exploring the bounds of $\beta$ where ${\it smooth\ sensitivity}$ can be obtained in an efficient manner.)

・Integrating our mechanism with the joint approach [Gillenwater et al., 2022] and the local dampening mechanism [Farias et al., 2023], while considering $(\epsilon,\delta)$-differential privacy.

・For datasets with a large $m$, there will be less advantage of our method because $\max_r S(x,r)$ (in the SPS) becomes closer to $GS_{u,\mathcal{R}}$. Using this study as a starting point, we intend to develop methods that are valuable even for large datasets.
← Is it possible to satisfy differential privacy while adding noise of different scales for each $r \in \mathcal{R}$? (In our mechanism, the noise part is expressed by the same formula for all $r$. Can we make it $r$-dependent to improve the accuracy?)

Note

For details of our methods and discussion, please see our paper entitled "Differentially Private Selection using Smooth Sensitivity" (https://doi.org/10.1109/IPCCC59868.2024.10850477) presented at IEEE IPCCC 2024.

Errata:
・Theorem 6 and its proof, $\frac{\epsilon}{2(\gamma - 1)}$ → $\min\left( \frac{\epsilon}{2(\gamma - 1)}, \ \frac{\epsilon}{2} \right)$.

Contact

Akito Yamamoto

Division of Medical Data Informatics, Human Genome Center,

the Institute of Medical Science, the University of Tokyo

a-ymmt@ims.u-tokyo.ac.jp