2020

A Better Bound Gives a Hundred Rounds: Enhanced Privacy Guarantees via $f$-Divergences

Asoodeh, Shahab, Liao, Jiachun, Calmon, Flavio P. et al.

Understand

We derive the optimal differential privacy (DP) parameters of a mechanism that satisfies a given level of R\'enyi differential privacy (RDP).

Our result is based on the joint range of two $f$-divergences that underlie the approximate and the R\'enyi variations of differential privacy.
We apply our result to the moments accountant framework for characterizing privacy guarantees of stochastic gradient descent.
When compared to the state-of-the-art, our bounds may lead to about 100 more stochastic gradient descent iterations for training deep learning models for the same privacy budget.

Built on

M. A. Pinsker,
1964
Earlier work this paper cites.
S. M. Ali and S. D. Silvey, “A general class of coefficients of divergence of one distribution from another,”
1966
Earlier work this paper cites.
I. Csiszár, “Information-type measures of difference of probability distributions and indirect observations,”
1967
Earlier work this paper cites.
C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” in
2006
Earlier work this paper cites.
C. Dwork, G. N. Rothblum, and S. Vadhan, “Boosting and differential privacy,” in
2010
Earlier work this paper cites.
K. Chaudhuri, C. Monteleoni, and A. D. Sarwate, “Differentially private empirical risk minimization,”
2011
Earlier work this paper cites.
P. Harremoës and I. Vajda, “On pairs of
2011
Earlier work this paper cites.
N. Sharma and N. A. Warsi, “Fundamental bound on the reliability of quantum information transmission,”
Original
2013
Earlier work this paper cites.
G. Barthe and F. Olmedo, “Beyond differential privacy: Composition theorems and relational logic for
2013
Earlier work this paper cites.
R. Bassily, A. Smith, and A. Thakurta, “Private empirical risk minimization: Efficient algorithms and tight error bounds,” in
2014
Earlier work this paper cites.

Similar

T. van Erven and P. Harremos, “Rényi divergence and kullback-leibler divergence,”
2014
Cited alongside, same era.
R. Bassily, A. Smith, and A. Thakurta, “Private empirical risk minimization, revisited,” in
Original
2014
Cited alongside, same era.
R. Shokri and V. Shmatikov, “Privacy-preserving deep learning,” in
2015
Cited alongside, same era.
M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, “Deep learning with differential privacy,” in
2016
Cited alongside, same era.
I. Sason and S. Verdú, “
2016
Cited alongside, same era.
X. Wu, F. Li, A. Kumar, K. Chaudhuri, S. Jha, and J. Naughton, “Bolt-on differential privacy for scalable stochastic gradient descent-based analytics,” in
2017
Cited alongside, same era.
P. Kairouz, S. Oh, and P. Viswanath, “The composition theorem for differential privacy,”
2017
Cited alongside, same era.
I. Mironov, “Rényi differential privacy,” in
2017
Cited alongside, same era.
N. Papernot, M. Abadi, Úlfar Erlingsson, I. Goodfellow, and K. Talwar, “Semi-supervised knowledge transfer for deep learning from private training data,” in
2017
Cited alongside, same era.
J. Geumlek, S. Song, and K. Chaudhuri, “Rényi differential privacy mechanisms for posterior sampling,” in
2017
Cited alongside, same era.

Then

B. Balle, G. Barthe, and M. Gaboardi, “Privacy amplification by subsampling: Tight analyses via couplings and divergences,” in
2018
Later among the works it cites.
H. B. McMahan, G. Andrew, U. Erlingsson, S. Chien, I. Mironov, and P. Kairouz, “A general approach to adding differential privacy to iterative training procedures,” 2018. [Online]. Available:
Original
2018
Later among the works it cites.
Google, “Tensorflow privacy,” 2018. [Online]. Available:
2018
Later among the works it cites.
V. Feldman, I. Mironov, K. Talwar, and A. Thakurta, “Privacy amplification by iteration,”
2018
Later among the works it cites.
Y.-X. Wang, B. Balle, and S. P. Kasiviswanathan, “Subsampled Rényi differential privacy and analytical moments accountant,” in
2018
Later among the works it cites.
A. Bhowmick, J. Duchi, J. Freudiger, G. Kapoor, and R. Rogers, “Protection against reconstruction and its applications in private federated learning,” 2018
2018
Later among the works it cites.
B. Balle and Y.-X. Wang, “Improving the Gaussian mechanism for differential privacy: Analytical calibration and optimal denoising,” in
2018
Later among the works it cites.
B. Balle, G. Barthe, M. Gaboardi, J. Hsu, and T. Sato, “Hypothesis testing interpretations and Rényi differential privacy,”
Original
2019
Later among the works it cites.
B. Balle, G. Barthe, M. Gaboardi, and J. Geumlek, “Privacy amplification by mixing and diffusion mechanisms,”
Original
2019
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…