Free Gap Estimates from the Exponential Mechanism, Sparse Vector, Noisy Max and Related Algorithms

Zeyu Ding, Yuxin Wang, Yingtai Xiao +3

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…