Privacy Amplification of Iterative Algorithms via Contraction Coefficients

We investigate the framework of privacy amplification by iteration, recently proposed by Feldman et al., from an information-theoretic lens. We demonstrate that differential privacy guarantees of iterative mappings can be determined by a direct application of contraction coefficients derived from strong data processing inequalities for f -divergences. In particular, by generalizing the Dobrushin's contraction coefficient for total variation distance to an f -divergence known as E Differential privacy (DP) [1, 2] has become the standard definition for designing privacy-preserving machine learning algorithms. One reason for its success is its operational significance, which can be best described in terms of binary hypothesis testing (see, e.g., [3, 4]). Nevertheless, it is often difficult to compute DP guarantees for applications where a high number of data accesses is needed for a single analysis [5, 6]. To obtain the DP parameters in such applications, which include machine learning models trained using stochastic gradient descent (SGD), one needs to resort to composition theorems which are often loose due to their generality. As a remedy, several variants of DP have been recently proposed [7-10] based on Rényi divergence. These variants enjoy better composition properties.