Permute-and-Flip: A New Mechanism for Differentially Private Selection
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.
Cite
Text
McKenna and Sheldon. "Permute-and-Flip: A New Mechanism for Differentially Private Selection." Neural Information Processing Systems, 2020.Markdown
[McKenna and Sheldon. "Permute-and-Flip: A New Mechanism for Differentially Private Selection." Neural Information Processing Systems, 2020.](https://mlanthology.org/neurips/2020/mckenna2020neurips-permuteandflip/)BibTeX
@inproceedings{mckenna2020neurips-permuteandflip,
title = {{Permute-and-Flip: A New Mechanism for Differentially Private Selection}},
author = {McKenna, Ryan and Sheldon, Daniel R.},
booktitle = {Neural Information Processing Systems},
year = {2020},
url = {https://mlanthology.org/neurips/2020/mckenna2020neurips-permuteandflip/}
}