Wael Alghamdi, Harvard University, United States; Shahab Asoodeh, McMaster University, Canada; Flavio P. Calmon, Harvard University, United States; Oliver Kosut, Lalitha Sankar, Arizona State University, United States
Session:
Differential Privacy
Track:
16: Privacy and Fairness
Location:
Omega
Presentation Time:
Fri, 12 Jul, 09:45 - 10:05
Session Chair:
Asaf Cohen, Ben-Gorion University of the Negev
Abstract
We formulate a fundamental limit in differential privacy under growing composition. We introduce the universal composition curve: the best privacy guarantee under repeated composition of a given privacy mechanism given only the sensitivity of the query. We define privacy capacity as the slowest growth rate of this universal composition curve among all privacy mechanisms. We show that, in the limit of large compositions, privacy capacity "single-letterizes" as a minimax KL-divergence term. Our privacy capacity formula extends previous literature results that connect differential privacy and KL-divergence via concentration theorems.