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

Abstract

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.

References in corpus (1)

• On the `Semantics' of Differential Privacy: A Bayesian Formulation

Cited by in corpus (13)

• Deep Learning with Differential Privacy
• Advanced Probabilistic Couplings for Differential Privacy
• Privacy Accounting and Quality Control in the Sage Differentially Private ML Platform
• Guidelines for Implementing and Auditing Differentially Private Systems
• Individual Privacy Accounting via a Renyi Filter
• Practical Privacy Filters and Odometers with Rényi Differential Privacy and Applications to Differentially Private Deep Learning
• Optimal Differential Privacy Composition for Exponential Mechanisms and the Cost of Adaptivity
• DPack: Efficiency-Oriented Privacy Budget Scheduling
• Turbo: Effective Caching in Differentially-Private Databases
• DiPPS: Differentially Private Propensity Scores for Bias Correction
• Testing Differential Privacy with Dual Interpreters
• Privacy accounting $\epsilon$conomics: Improving differential privacy composition via a posteriori bounds
• Cookie Monster: Efficient On-device Budgeting for Differentially-Private Ad-Measurement Systems