CRMay 15, 2021
The Permute-and-Flip Mechanism is Identical to Report-Noisy-Max with Exponential Noise
Zeyu Ding, Daniel Kifer, Sayed M. Saghaian N. E., Thomas Steinke, Yuxin Wang, Yingtai Xiao, Danfeng Zhang
arXiv:2105.07260v334 citations
Originality Synthesis-oriented
AI Analysis
This clarifies a theoretical relationship in differential privacy for researchers, but it is incremental as it does not introduce new algorithms or performance improvements.
The paper demonstrates that the permute-and-flip mechanism, a differentially private selection algorithm, is equivalent to the report noisy max algorithm with exponential noise, resolving a theoretical connection between these methods.
The permute-and-flip mechanism is a recently proposed differentially private selection algorithm that was shown to outperform the exponential mechanism. In this paper, we show that permute-and-flip is equivalent to the well-known report noisy max algorithm with exponential noise.