Private selection methods using dataset sensitive calibrations improve privacy guarantees
Local Sensitivity in Exponential Selection: Failure Modes and Valid Calibrations
Data Structures and AlgorithmsCryptography and Security
Summary
Selecting the best choice from a set while protecting individual data is important in privacy. This paper studies how adjusting privacy settings based on the specific dataset, rather than worst-case assumptions, can improve selection methods. The authors propose several ways to safely use dataset-specific sensitivity in the exponential mechanism, a common private selection method. They also provide guarantees on how well these methods protect privacy and perform selection effectively.
What this means in practice
- •For data privacy engineers: Configure private selection algorithms to use dataset-specific sensitivity calibrations for improved privacy-utility tradeoffs in data analysis tools.
- •For machine learning model trainers: Implement private candidate selection with adaptive privacy parameters to better preserve accuracy while meeting privacy requirements during model parameter tuning.
Authors
Dung Nguyen, Anil Vullikanti
Abstract
Selection is a task that chooses one element from a finite public candidate range to maximize a data-dependent score. In differential privacy (DP), the exponential mechanism (EM) samples a candidate at a temperature calibrated to the global sensitivity. In this paper, we study when dataset-dependent sensitivity can safely replace global sensitivity in private selection. We propose three valid approaches. First, a private, high-probability upper bound on local sensitivity yields approximate DP, and the method extends to finite higher-order sensitivity hierarchies. Second, our Propose-Test-Release (PTR) variant privately searches a finite public grid for a temperature scale rather than fixing it in advance. Third, smooth sensitivity supports several designs. A candidate-independent smooth geometric construction produces a sensitivity envelope that is admissible under the local dampening framework, which privacy is guaranteed for any admissible envelope. Additionally, a separate logarithmic transformation utilizes smooth sensitivity to produce a smoothed candidate score function with advantages: having controlled global sensitivity, and preserving the maximizers of the original utility score, i.e., candidates maximizing the utility. Both of the designs yield range-independent pure DP. Besides that, we also give two approximate DP private selectors using smooth sensitivity: a direct EM with smooth sensitivity calibrated to the candidate range and privacy parameters that matches a theoretical lower bound up to some constant factor, and one using a privatized smooth upper scale by analyzing the logarithmic transform of the smoothness. For every proposed mechanism, we derive a high-probability regret bound under its stated conditions.