Differentially Private Selection Using Smooth Sensitivity

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 datasetdependent 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.

selection requires addressing significant technical obstacles. For instance, the most intuitive way to adapt existing algorithms (e.g., exponential mechanism) is replacing the global sensitivity by the smooth one. However, our Theorem 7.2 shows this does not result in a differentially private algorithm. We also provide utility guarantees showing SNM is never worse than existing methods under mild conditions. In summary, the contributions of this work are: i) We prove that the concept of smooth sensitivity cannot be utilized along with the exponential mechanism. Therefore, we extend the smooth sensitivity, originally defined for numerical data, to the data selection setting; ii) We propose the Smooth Noisy Max (SNM), a differentially private data selection algorithm that applies our extended notion of smooth sensitivity; iii) We provide differential privacy guarantees for Smooth Noisy Max, along with theoretically rigorous utility guarantees showing that Smooth Noisy Max is never worse than its competitors under mild conditions; iv) We conducted an empirical comparison 1 of Smooth Noisy Max with competing methods across three applications: percentile selection, greedy decision trees, and random forests. Our findings indicate that SNM consistently outperforms state-of-the-art methods in terms of accuracy and expected error. This paper is structured as follows: Section 2 provides basic definitions regarding DP. Section 3 reviews the prior art on private selection. Section 4 presents the Smooth Noisy Max algorithm. Section 5 applies Smooth Noisy Max to percentile selection. Section 6 explores a private decision tree approach. Section 7 discusses a novel random forest algorithm using Smooth Noisy Max. Finally, Section 8 concludes the paper with future directions.

Let database x be a set of records drawn from a universe X, and f a query over x. In differential privacy, the goal is to ensure that the outcome of a computation/algorithm, denoted by A, does not reveal much sensitive information about any individual in a database. At the same time, the algorithm A ensures data processing without disclosing individual information, even if an adversary has almost complete knowledge of all other individuals in the database. Differential privacy uses a randomized algorithm, i.e., a mechanism that adds controlled noise to the data, and it is based on a privacy budget parameter, typically denoted as ε, representing the desired level of privacy protection. We formalize the database as a multiset of records of X. Therefore, the distance between two databases can be determined by counting the records that differ between them. More specifically, this distance is quantified using the symmetric difference of two sets, denoted as d(x, y) = |x ⊕ y|.

Definition 2.1 ((ε, δ)-Differential privacy [15]). A randomized algorithm A satisfies (ε, δ)-differential privacy if, for