Privacy Odometers and Filters: Pay-as-you-Go Composition

By Ryan M. Rogers, Salil P. Vadhan, Aaron Roth, Jonathan Ullman. 2016

134 citations recorded by the source corpus.

In this paper we initiate the study of adaptive composition in differential privacy when the length of the composition, and the privacy parameters themselves can be chosen adaptively, as a function of the outcome of previously run analyses. This case is much more delicate than the setting covered by existing composition theorems, in which the algorithms themselves can be chosen adaptively, but the privacy parameters must be fixed up front. Indeed, it isn't even clear how to define differential privacy in the adaptive parameter setting. We proceed by defining two objects which cover the two main use cases of composition theorems. A privacy filter is a stopping time rule that allows an analyst to halt a computation before his pre-specified privacy budget is exceeded. A privacy odometer allows the analyst to track realized privacy loss as he goes, without needing to pre-specify a privacy budget. We show that unlike the case in which privacy parameters are fixed, in the adaptive parameter setting, these two use cases are distinct. We show that there exist privacy filters with bounds comparable (up to constants) with existing privacy composition theorems. We also give a privacy odometer that nearly matches non-adaptive private composition theorems, but is sometimes worse by a small asymptotic factor. Moreover, we show that this is inherent, and that any valid privacy odometer in the adaptive parameter setting must lose this factor, which shows a formal separation between the filter and odometer use-cases.

Subfields: Artificial Intelligence, Sociology and Political Science

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Sociology and Political Science

Citations in the corpus

Federated Learning and Differential Privacy: Software tools analysis, the Sherpa.ai FL framework and methodological guidelines for preserving data privacy (2020, methodology): “In order to remove some of the stated constraints, a more flexible experiment of composition is introduced [22]:”
Advanced Probabilistic Couplings for Differential Privacy (2016, neutral): “[43] consider a version of the advanced composition theorem where the privacy level i and δi for the i-th mechanism may be chosen adaptively, i.”
Differentially Private Model Publishing for Deep Learning (2019, background): “[31] that the strong composition theorem for ( , δ)-DP fails to hold in this adaptive privacy parameter setting since the theorem requires the privacy parameters to be pre-defined ahead of time.”
The Role of Interactivity in Local Differential Privacy (2019, unknown): “[30]).”
Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising (2018, methodology): “For example, recent works have proposed methods to account for the privacy loss under compositions occurring in complex mechanisms (Rogers et al., 2016; Abadi et al., 2016).”