Free Gap Information from the Differentially Private Sparse Vector and Noisy Max Mechanisms
arXiv:1904.12773
Abstract
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.
arXiv comment16 pages
References in corpus (10)
- Deep Learning with Differential Privacy
- Renyi Differential Privacy
- Scalable Private Learning with PATE
- A simple and practical algorithm for differentially private data release
- Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12
- Proving Differential Privacy via Probabilistic Couplings
- LightDP: Towards Automating Differential Privacy Proofs
- Proving Differential Privacy with Shadow Execution
- Accuracy First: Selecting a Differential Privacy Level for Accuracy-Constrained ERM
- The Large Margin Mechanism for Differentially Private Maximization