Exponential Randomized Response: Boosting Utility in Differentially Private Selection
This work addresses the challenge of improving utility in differentially private selection algorithms for data analysts, though it is incremental as it builds on prior mechanisms.
The paper tackles the problem of differentially private selection by introducing a new mechanism that can provide utility improvements significantly larger than a factor of two over existing methods like the exponential mechanism and permute-and-flip in common scenarios, though it may have lower utility in niche cases.
A differentially private selection algorithm outputs from a finite set the item that approximately maximizes a data-dependent quality function. The most widely adopted mechanisms tackling this task are the pioneering exponential mechanism and permute-and-flip, which can offer utility improvements of up to a factor of two over the exponential mechanism. This work introduces a new differentially private mechanism for private selection and conducts theoretical and empirical comparisons with the above mechanisms. For reasonably common scenarios, our mechanism can provide utility improvements of factors significantly larger than two over the exponential and permute-and-flip mechanisms. Because the utility can deteriorate in niche scenarios, we recommend our mechanism to analysts who can tolerate lower utility for some datasets.