Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences

Abstract

Differential privacy comes equipped with multiple analytical tools for the design of private data analyses. One important tool is the so-called "privacy amplification by subsampling" principle, which ensures that a differentially private mechanism run on a random subsample of a population provides higher privacy guarantees than when run on the entire population. Several instances of this principle have been studied for different random subsampling methods, each with an ad-hoc analysis. In this paper we present a general method that recovers and improves prior analyses, yields lower bounds and derives new instances of privacy amplification by subsampling. Our method leverages a characterization of differential privacy as a divergence which emerged in the program verification community. Furthermore, it introduces new tools, including advanced joint convexity and privacy profiles, which might be of independent interest.

To appear in NeurIPS 2018

Cited by in corpus (42)

• Federated Learning with Bayesian Differential Privacy
• How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy
• Federated Learning and Differential Privacy: Software tools analysis, the Sherpa.ai FL framework and methodological guidelines for preserving data privacy
• LDP-IDS: Local Differential Privacy for Infinite Data Streams
• GS-WGAN: A Gradient-Sanitized Approach for Learning Differentially Private Generators
• Do Not Let Privacy Overbill Utility: Gradient Embedding Perturbation for Private Learning
• Random Sampling Plus Fake Data: Multidimensional Frequency Estimates With Local Differential Privacy
• Federated Model Distillation with Noise-Free Differential Privacy
• Social-Aware Clustered Federated Learning with Customized Privacy Preservation
• Don't Look at the Data! How Differential Privacy Reconfigures the Practices of Data Science
• D2P-Fed: Differentially Private Federated Learning With Efficient Communication
• DPIS: An Enhanced Mechanism for Differentially Private SGD with Importance Sampling
• Differential Privacy for Government Agencies -- Are We There Yet?
• Differentially Private Accelerated Optimization Algorithms
• Optimal Accounting of Differential Privacy via Characteristic Function
• Network Shuffling: Privacy Amplification via Random Walks
• Computing Tight Differential Privacy Guarantees Using FFT
• Wide Network Learning with Differential Privacy
• Privacy For Free: Wireless Federated Learning Via Uncoded Transmission With Adaptive Power Control
• Privacy-preserving Active Learning on Sensitive Data for User Intent Classification
• Hyperparameter Tuning with Renyi Differential Privacy
• Revealing the True Cost of Locally Differentially Private Protocols: An Auditing Perspective
• Improved Differentially Private Decentralized Source Separation for fMRI Data
• Differentially Private Bayesian Neural Networks on Accuracy, Privacy and Reliability
• Privacy Amplification by Mixing and Diffusion Mechanisms
• Releasing Graph Neural Networks with Differential Privacy Guarantees
• Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descent
• Computing Differential Privacy Guarantees for Heterogeneous Compositions Using FFT
• Tight Differential Privacy for Discrete-Valued Mechanisms and for the Subsampled Gaussian Mechanism Using FFT
• Don't Generate Me: Training Differentially Private Generative Models with Sinkhorn Divergence
• Enhancing the Antidote: Improved Pointwise Certifications against Poisoning Attacks
• Differentially Private Fractional Frequency Moments Estimation with Polylogarithmic Space
• Universal Private Estimators
• Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and Averaging
• From Noisy Fixed-Point Iterations to Private ADMM for Centralized and Federated Learning
• Improving Utility of Differentially Private Mechanisms through Cryptography-based Technologies: a Survey
• Combining Differential Privacy and Byzantine Resilience in Distributed SGD
• Federated Learning with Sparsification-Amplified Privacy and Adaptive Optimization
• Infinitely Divisible Noise in the Low Privacy Regime
• Improving Differentially Private SGD via Randomly Sparsified Gradients
• Privacy Amplification Via Bernoulli Sampling
• Amplifying Rényi Differential Privacy via Shuffling