Free Gap Information from the Differentially Private Sparse Vector and Noisy Max Mechanisms
This work provides incremental improvements to differential privacy algorithms, benefiting practitioners by enhancing efficiency and accuracy in privacy-preserving data analysis.
The paper shows that the Noisy Max and Sparse Vector mechanisms in differential privacy can release extra information without additional privacy cost, such as the noisy gap between top queries, improving accuracy by up to 50% for some counting queries, and adaptively controlling privacy budgets to process more queries.
Noisy Max and Sparse Vector are selection algorithms for differential privacy and serve as building blocks for more complex algorithms. In this paper we show that both algorithms can release additional information for free (i.e., at no additional privacy cost). Noisy Max is used to return the approximate maximizer among a set of queries. We show that it can also release for free the noisy gap between the approximate maximizer and runner-up. This free information can improve the accuracy of certain subsequent counting queries by up to 50%. Sparse Vector is used to return a set of queries that are approximately larger than a fixed threshold. We show that it can adaptively control its privacy budget (use less budget for queries that are likely to be much larger than the threshold) in order to increase the amount of queries it can process. These results follow from a careful privacy analysis.