Privacy Odometers and Filters: Pay-as-you-Go Composition
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.
This paper mainly considers adaptive composition theorem for differential privacy. The paper allows privacy parameters and number of rounds to be adaptive, and to solve the corresponding problem (for example, differential privacy is not defined suitably), authors propose two natural concepts, the privacy odometer and privacy filter. The privacy odometer can give an upper bound of privacy loss on every round, and the privacy filter can determine whether to continue or to halt the process, in the guarantee of global privacy budget. What’s more, authors prove the privacy filter has the same asymptotic order of bound as advanced composition theorem (C. Dwork 2010), while this cannot be achieved by the privacy odometer, except with an addition O(\sqrt{\log \log(n)}) factor.
In my personal view, the situation considered in this paper is much more general than almost all the existing work, and is more appropriate to use if differential privacy is applied in real word. Besides it, authors also give a deep understanding for the proposed primitives. These are main reasons for me to accept or to rate high scores for this paper, and I think it may open another door for differential privacy related research.  Intuitively speaking, giving an upper bound for privacy loss every round is more difficult than determining whether to continue or to halt the process, as we can easily obtain a privacy filter from a privacy odometer. Thus, I think conclusions in this paper are theoretical sound. A question I am concerned is whether we can obtain a privacy odometer from a privacy filter, for example, once we can solve equation (7) to put \epsilon_g in only one side, could we say the corresponding term in the other side can be used as a privacy odometer?   Some minor comments: 1. For the last word in line 86, I think authors want to say “Continue” not “Halt”; 2. In definition 2.6, there is a clerical error with the third case in randomized response; 3. In line 278 – 279, it will be better to explain more for the content in the brackets, as I am not clear why the left side of the inequality is an upper bound of statistical distance, and why this can conclude \epsilon_i has to be larger than \frac{1}{10n} (though I know this is a basic fact for many DP algorithms); 4. The format of paper’s references and supplementary is different with NIPS standard format.