Skip to yearly menu bar Skip to main content


Poster

Faster Differentially Private Top-k Selection: A Joint Exponential Mechanism with Pruning

Hao WU · Hanwen Zhang

West Ballroom A-D #6305
[ ]
[ Paper [ Poster [ OpenReview
Thu 12 Dec 4:30 p.m. PST — 7:30 p.m. PST

Abstract: We study the differentially private top-k selection problem, aiming to identify a sequence of k items with approximately the highest scores from d items. Recent work by Gillenwater et al. (2022) employs a direct sampling approach from the vast collection of O(dk) possible length-k sequences, showing superior empirical accuracy compared to previous pure or approximate differentially private methods. Their algorithm has a time and space complexity of O~(dk). In this paper, we present an improved algorithm that achieves time and space complexity of O~(d+k2).Experimental results show that our algorithm runs orders of magnitude faster than their approach, while achieving similar empirical accuracy.

Chat is not available.