Accuracy-First Rényi Differential Privacy and Post-Processing Immunity

The accuracy-first perspective of differential privacy addresses an important shortcoming by allowing a data analyst to adaptively adjust the quantitative privacy bound instead of sticking to a predetermined bound. Existing works on the accuracy-first perspective have neglected an important property of differential privacy known as post-processing immunity, which ensures that an adversary is not able to weaken the privacy guarantee by post-processing. We address this gap by determining which existing definitions in the accuracy-first perspective have post-processing immunity, and which do not. The only definition with post-processing immunity, pure ex-post privacy, lacks useful tools for practical problems, such as an ex-post analogue of the Gaussian mechanism, and an algorithm to check if accuracy on separate private validation set is high enough. To address this, we propose a new definition based on Rényi differential privacy that has post-processing immunity, and we develop basic theory and tools needed for practical applications. We demonstrate the practicality of our theory with applications to synthetic data generation and image classifier fine-tuning, where our algorithm successfully adjusts the privacy bound until an accuracy threshold is met on a private validation dataset.

Differential privacy is a mathematical definition of privacy -- any differentially private algorithm cannot leak too much information about individuals. However, the concrete bound for "too much information" must be chosen in advance in the standard version of differential privacy. Accuracy-first versions of differential privacy, known as ex-post privacy, relax this requirement and allow loosening the privacy guarantee after observing the results from an initial choice. This may be necessary if the initial choice lead to an outcome of poor quality, for example. Ex-post privacy is not as throughly studied as standard differential privacy. In particular, previous works have not checked whether performing further computations on the result of an ex-post private algorithm can weaken the privacy guarantee. In standard differential privacy, it is known this that this is not possible, which is an important result known as post-processing immunity. We address this gap by investigating which existing notions of ex-post privacy have post-processing immunity. It turns out that the only one with post-processing immunity lacks many useful tools needed to solve practical problems, so we propose a new definition based on so-called Rényi differential privacy. We prove that the new definition both has post-processing immunity, and we develop several tools for practical applications.