2018

Subsampled R\'enyi Differential Privacy and Analytical Moments Accountant

Wang, Yu-Xiang, Balle, Borja, Kasiviswanathan, Shiva

Understand

We study the problem of subsampling in differential privacy (DP), a question that is the centerpiece behind many successful differentially private machine learning algorithms.

Specifically, we provide a tight upper bound on the R\'enyi Differential Privacy (RDP) (Mironov, 2017) parameters for algorithms that: (1) subsample the dataset, and then (2) applies a randomized mechanism M to the subsample, in terms of the RDP parameters of M and the subsampling probability parameter.
Our results generalize the moments accounting technique, developed by Abadi et al.
(2016) for the Gaussian mechanism, to any subsampled RDP mechanism.

Built on

Characteristic functions
Lukacs, E. (1970) · 1970
Earlier work this paper cites.
χ α \chi^{\alpha} -divergence and generalized fisher information
Vajda, I. (1973) · 1973
Earlier work this paper cites.
Boosting and differential privacy
Dwork, C., Rothblum, G. N., & Vadhan, S. (2010) · 2010
Earlier work this paper cites.
What can we learn privately?
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., & Smith, A. (2011) · 2011
Earlier work this paper cites.
Characterizing the sample complexity of private learners
Beimel, A., Nissim, K., & Stemmer, U. (2013) · 2013
Earlier work this paper cites.
The algorithmic foundations of differential privacy
Dwork, C., & Roth, A. (2013) · 2013
Earlier work this paper cites.
Rényi divergence measures for commonly used univariate continuous distributions
Gil, M., Alajaji, F., & Linder, T. (2013) · 2013
Earlier work this paper cites.
Stochastic gradient descent with differentially private updates
Song, S., Chaudhuri, K., & Sarwate, A. D. (2013) · 2013
Earlier work this paper cites.
Private empirical risk minimization: Efficient algorithms and tight error bounds
Bassily, R., Smith, A., & Thakurta, A. (2014) · 2014
Earlier work this paper cites.
Rappor: Randomized aggregatable privacy-preserving ordinal response
Erlingsson, Ú., Pihur, V., & Korolova, A. (2014) · 2014
Earlier work this paper cites.
On the chi square and higher-order chi distances for approximating f-divergences
Nielsen, F., & Nock, R. (2014) · 2014
Earlier work this paper cites.
Rényi divergence and kullback-leibler divergence
Van Erven, T., & Harremos, P. (2014) · 2014
Earlier work this paper cites.

Similar

Differentially private release and learning of threshold functions
Bun, M., Nissim, K., Stemmer, U., & Vadhan, S. (2015) · 2015
Cited alongside, same era.
The composition theorem for differential privacy
Kairouz, P., Oh, S., & Viswanath, P. (2015) · 2015
Cited alongside, same era.
Only you, your doctor, and many others may know
Sweeney, L. (2015) · 2015
Cited alongside, same era.
Privacy for free: Posterior sampling and stochastic gradient monte carlo
Wang, Y.-X., Fienberg, S., & Smola, A. (2015) · 2015
Cited alongside, same era.
Deep learning with differential privacy
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., & Zhang, L. (2016) · 2016
Cited alongside, same era.
R \ \backslash ’enyi divergence and the central limit theorem
Original
Bobkov, S., Chistyakov, G., & Götze, F. (2016) · 2016
Cited alongside, same era.
Concentrated differential privacy: Simplifications, extensions, and lower bounds
Bun, M., & Steinke, T. (2016) · 2016
Cited alongside, same era.
Concentrated differential privacy
Original
Dwork, C., & Rothblum, G. N. (2016) · 2016
Cited alongside, same era.
Regulation (eu) 2016/679 of the european parliament and of the council of 27 april 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data, and repealing directive 95/46/ec (general data protection regulation)
European Parliament, & Council of the European Union (2016) · 2016
Cited alongside, same era.
On the theory and practice of privacy-preserving bayesian data analysis
Foulds, J., Geumlek, J., Welling, M., & Chaudhuri, K. (2016) · 2016
Cited alongside, same era.
The complexity of computing the optimal composition of differential privacy
Murtagh, J., & Vadhan, S. (2016) · 2016
Cited alongside, same era.
Learning with differential privacy: Stability, learnability and the sufficiency and necessity of erm principle
Wang, Y.-X., Lei, J., & Fienberg, S. E. (2016) · 2016
Cited alongside, same era.

Then

Learning with privacy at scale
Apple, D. (2017) · 2017
Later among the works it cites.
Equifax says cyberattack may have affected 143 million in the us
Bernard, T. S., Hsu, T., Perlroth, N., & Lieber, R. (2017) · 2017
Later among the works it cites.
The modernization of statistical disclosure limitation at the u.s. census bureau
Dajani, A., Lauger, A., Singer, P., Kifer, D., Reiter, J., Machanavajjhala, A., Garfinkel, S., Dahl, S., Graham, M., Karwa, V., Kim, H., Leclerc, P., Schmutte, I., Sexton, W., Vilhuber, L., & Abowd, J. (2017) · 2017
Later among the works it cites.
Renyi differential privacy mechanisms for posterior sampling
Geumlek, J., Song, S., & Chaudhuri, K. (2017) · 2017
Later among the works it cites.
Rényi differential privacy
Mironov, I. (2017) · 2017
Later among the works it cites.
Uber releases open source project for differential privacy
Uber Security (2017) · 2017
Later among the works it cites.
Cs7880: Rigorous approaches to data privacy, spring 2017
Ullman, J. (2017) · 2017
Later among the works it cites.
Privacy amplification by subsampling: Tight analyses via couplings and divergences
Balle, B., Barthe, G., & Gaboardi, M. (2018) · 2018
Closest in time.
Improving gaussian mechanism for differential privacy: Analytical calibration and optimal denoising
Balle, B., & Wang, Y.-X. (2018) · 2018
Closest in time.
Composable and versatile privacy via truncated cdp
Bun, M., Dwork, C., Rothblum, G. N., & Steinke, T. (2018) · 2018
Closest in time.
Revealed: 50 million facebook profiles harvested for cambridge analytica in major data breach
Cadwalladr, C., & Graham-Harrison, E. (2018) · 2018
Closest in time.
Per-instance differential privacy
Wang, Y.-X. (2018) · 2018
Closest in time.

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…