Privacy Odometers and Filters: Pay-as-you-Go Composition
Authors: Ryan M. Rogers, Aaron Roth, Jonathan Ullman, Salil Vadhan
NeurIPS 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. 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 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. |
| Researcher Affiliation | Academia | Department of Applied Mathematics and Computational Science, University of Pennsylvania. ryrogers@sas.upenn.edu. Department of Computer and Information Sciences, University of Pennsylvania. aaroth@cis.upenn.edu. Supported in part by an NSF CAREER award, NSF grant CNS-1513694, and a grant from the Sloan Foundation. College of Computer and Information Science, Northeastern University. jullman@ccs.neu.edu Center for Research on Computation & Society and John A. Paulson School of Engineering & Applied Sciences, Harvard University. salil@seas.harvard.edu. |
| Pseudocode | Yes | Algorithm 1 Fixed Param Comp(A, E = (E1, , Ek), b), where A is a randomized algorithm, E1, , Ek are classes of randomized algorithms, and b {0, 1}. Algorithm 2 Adapt Param Comp(A, k, b) |
| Open Source Code | No | The paper does not provide any concrete access information (specific repository link, explicit code release statement, or code in supplementary materials) for the methodology described in this paper. |
| Open Datasets | No | The paper does not provide concrete access information (specific link, DOI, repository name, formal citation with authors/year, or reference to established benchmark datasets) for a publicly available or open dataset. |
| Dataset Splits | No | The paper does not provide specific dataset split information (exact percentages, sample counts, citations to predefined splits, or detailed splitting methodology) needed to reproduce the data partitioning. |
| Hardware Specification | No | The paper does not provide specific hardware details (exact GPU/CPU models, processor types with speeds, memory amounts, or detailed computer specifications) used for running its experiments. |
| Software Dependencies | No | The paper does not provide specific ancillary software details (e.g., library or solver names with version numbers like Python 3.8, CPLEX 12.4) needed to replicate the experiment. |
| Experiment Setup | No | The paper does not contain specific experimental setup details (concrete hyperparameter values, training configurations, or system-level settings) in the main text. |