Free gap estimates from the exponential mechanism, sparse vector, noisy max and related algorithms

Zeyu Ding, Yuxin Wang, Yingtai Xiao, Guanhong Wang, Danfeng Zhang, Daniel Kifer

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

Private selection algorithms, such as the exponential mechanism, noisy max and sparse vector, are used to select items (such as queries with large answers) from a set of candidates, while controlling privacy leakage in the underlying data. Such algorithms serve as building blocks for more complex differentially private algorithms. In this paper we show that these algorithms can release additional information related to the gaps between the selected items and the other candidates for free (i.e., at no additional privacy cost). This free gap information can improve the accuracy of certain follow-up counting queries by up to 66%. We obtain these results from a careful privacy analysis of these algorithms. Based on this analysis, we further propose novel hybrid algorithms that can dynamically save additional privacy budget.

Original languageEnglish (US)
Pages (from-to)23-48
Number of pages26
JournalVLDB Journal
Volume32
Issue number1
DOIs
StatePublished - Jan 2023

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Free gap estimates from the exponential mechanism, sparse vector, noisy max and related algorithms'. Together they form a unique fingerprint.

Cite this