Differentially Private Selection using Smooth Sensitivity

• URL: http://arxiv.org/abs/2504.08086v1
• Date: Thu, 10 Apr 2025 19:31:34 GMT
• Title: Differentially Private Selection using Smooth Sensitivity
• Authors: Iago Chaves, Victor Farias, Amanda Perez, Diego Parente, Javam Machado,
• Abstract summary: Differentially private selection mechanisms offer strong privacy guarantees for queries aiming to identify the top-scoring element r from a finite set R.<n>We propose the Smooth Noisy Max (SNM) mechanism, which leverages smooth sensitivity to yield provably tighter expected errors compared to global sensitivity-based methods.<n> Empirical results demonstrate that SNM is more accurate than state-of-the-art differentially private selection methods in three applications.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• From Randomized Response to Randomized Index: Answering Subset Counting Queries with Local Differential Privacy [27.59934932590226]
  Local Differential Privacy (LDP) is the predominant privacy model for safeguarding individual data privacy. We propose an alternative approach -- instead of perturbing values, we apply randomization to indexes of values. Inspired by the deniability of randomized indexes, we present CRIAD for answering subset counting queries on set-value data.
  arXiv  Detail & Related papers  (2025-04-24T13:08:11Z)
• Private Selection with Heterogeneous Sensitivities [2.0936724675062406]
  Differentially private (DP) selection involves choosing a high-scoring candidate from a finite candidate pool.<n>This problem arises naturally in a variety of contexts including model selection, hypothesis testing, and within many DP algorithms.<n>To address this, algorithms like the Generalised Exponential Mechanism (GEM) leverage variability in candidate sensitivities.
  arXiv  Detail & Related papers  (2025-01-09T15:25:07Z)
• Differentially Private Random Feature Model [52.468511541184895]
  We produce a differentially private random feature model for privacy-preserving kernel machines.<n>We show that our method preserves privacy and derive a generalization error bound for the method.
  arXiv  Detail & Related papers  (2024-12-06T05:31:08Z)
• TernaryVote: Differentially Private, Communication Efficient, and Byzantine Resilient Distributed Optimization on Heterogeneous Data [50.797729676285876]
  We propose TernaryVote, which combines a ternary compressor and the majority vote mechanism to realize differential privacy, gradient compression, and Byzantine resilience simultaneously. We theoretically quantify the privacy guarantee through the lens of the emerging f-differential privacy (DP) and the Byzantine resilience of the proposed algorithm.
  arXiv  Detail & Related papers  (2024-02-16T16:41:14Z)
• On the Privacy of Selection Mechanisms with Gaussian Noise [44.577599546904736]
  We revisit the analysis of Report Noisy Max and Above Threshold with Gaussian noise. We find that it is possible to provide pure ex-ante DP bounds for Report Noisy Max and pure ex-post DP bounds for Above Threshold.
  arXiv  Detail & Related papers  (2024-02-09T02:11:25Z)
• Causal Inference with Differentially Private (Clustered) Outcomes [16.166525280886578]
  Estimating causal effects from randomized experiments is only feasible if participants agree to reveal their responses. We suggest a new differential privacy mechanism, Cluster-DP, which leverages any given cluster structure. We show that, depending on an intuitive measure of cluster quality, we can improve the variance loss while maintaining our privacy guarantees.
  arXiv  Detail & Related papers  (2023-08-02T05:51:57Z)
• Breaking the Communication-Privacy-Accuracy Tradeoff with $f$-Differential Privacy [51.11280118806893]
  We consider a federated data analytics problem in which a server coordinates the collaborative data analysis of multiple users with privacy concerns and limited communication capability. We study the local differential privacy guarantees of discrete-valued mechanisms with finite output space through the lens of $f$-differential privacy (DP) More specifically, we advance the existing literature by deriving tight $f$-DP guarantees for a variety of discrete-valued mechanisms.
  arXiv  Detail & Related papers  (2023-02-19T16:58:53Z)
• Optimum Noise Mechanism for Differentially Private Queries in Discrete Finite Sets [3.5379819043314176]
  We introduce a novel framework for designing an optimal noise Mass Probability Function tailored to discrete and finite query sets. Our framework seeks to optimize the noise distribution under an arbitrary $(epsilon, delta)$ constraint, thereby enhancing the accuracy and utility of the response. Numerical experiments highlight the superior performance of our proposed optimal mechanisms compared to state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-11-23T05:24:34Z)
• Partial sensitivity analysis in differential privacy [58.730520380312676]
  We investigate the impact of each input feature on the individual's privacy loss. We experimentally evaluate our approach on queries over private databases. We also explore our findings in the context of neural network training on synthetic data.
  arXiv  Detail & Related papers  (2021-09-22T08:29:16Z)
• Smoothed Differential Privacy [55.415581832037084]
  Differential privacy (DP) is a widely-accepted and widely-applied notion of privacy based on worst-case analysis. In this paper, we propose a natural extension of DP following the worst average-case idea behind the celebrated smoothed analysis. We prove that any discrete mechanism with sampling procedures is more private than what DP predicts, while many continuous mechanisms with sampling procedures are still non-private under smoothed DP.
  arXiv  Detail & Related papers  (2021-07-04T06:55:45Z)
• Robustness Threats of Differential Privacy [70.818129585404]
  We experimentally demonstrate that networks, trained with differential privacy, in some settings might be even more vulnerable in comparison to non-private versions. We study how the main ingredients of differentially private neural networks training, such as gradient clipping and noise addition, affect the robustness of the model.
  arXiv  Detail & Related papers  (2020-12-14T18:59:24Z)
• Bounding, Concentrating, and Truncating: Unifying Privacy Loss Composition for Data Analytics [2.614355818010333]
  We provide strong privacy loss bounds when an analyst may select pure DP, bounded range (e.g. exponential mechanisms) or concentrated DP mechanisms in any order. We also provide optimal privacy loss bounds that apply when an analyst can select pure DP and bounded range mechanisms in a batch.
  arXiv  Detail & Related papers  (2020-04-15T17:33:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.