Permute-and-Flip: A new mechanism for differentially private selection
arXiv:2010.12603
Abstract
We consider the problem of differentially private selection. Given a finite set of candidate items and a quality score for each item, our goal is to design a differentially private mechanism that returns an item with a score that is as high as possible. The most commonly used mechanism for this task is the exponential mechanism. In this work, we propose a new mechanism for this task based on a careful analysis of the privacy constraints. The expected score of our mechanism is always at least as large as the exponential mechanism, and can offer improvements up to a factor of two. Our mechanism is simple to implement and runs in linear time.
References in corpus (5)
- A simple and practical algorithm for differentially private data release
- Extremal Mechanisms for Local Differential Privacy
- The Large Margin Mechanism for Differentially Private Maximization
- Benefits and Pitfalls of the Exponential Mechanism with Applications to Hilbert Spaces and Functional PCA
- The Price of Selection in Differential Privacy
Cited by in corpus (7)
- How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy
- Real-World Trajectory Sharing with Local Differential Privacy
- The Discrete Gaussian for Differential Privacy
- Leveraging Public Data for Practical Private Query Release
- DiPPS: Differentially Private Propensity Scores for Bias Correction
- Balance is key: Private median splits yield high-utility random trees
- Unleash the Power of Ellipsis: Accuracy-enhanced Sparse Vector Technique with Exponential Noise