# Adversary Instantiation: Lower Bounds for Differentially Private Machine Learning

arXiv: https://arxiv.org/abs/2101.04535 · HTML: https://mlsanity.com/paper/2101.04535/

## Key facts

- Cited by 199 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 56 references that are in the map.
- First posted on arXiv 11 Jan 2021.

## Builds on (most cited first, 26 of 26)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [DeepFool: a simple and accurate method to fool deep neural networks](https://mlsanity.com/paper/1511.04599/) (2015)
- [The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks](https://mlsanity.com/paper/1802.08232/) (2018)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [Exploiting Unintended Feature Leakage in Collaborative Learning](https://mlsanity.com/paper/1805.04049/) (2018)
- [Label-Only Membership Inference Attacks](https://mlsanity.com/paper/2007.14321/) (2020)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [Scalable Private Learning with PATE](https://mlsanity.com/paper/1802.08908/) (2018)
- [Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences](https://mlsanity.com/paper/1807.01647/) (2018)
- [Subsampled R'enyi Differential Privacy and Analytical Moments Accountant](https://mlsanity.com/paper/1808.00087/) (2018)
- [Auditing Differentially Private Machine Learning: How Private is Private SGD?](https://mlsanity.com/paper/2006.07709/) (2020)
- [R'enyi Differential Privacy of the Sampled Gaussian Mechanism](https://mlsanity.com/paper/1908.10530/) (2019)
- [Machine Learning Models that Remember Too Much](https://mlsanity.com/paper/1709.07886/) (2017)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [Privacy Amplification by Iteration](https://mlsanity.com/paper/1808.06651/) (2018)
- [Gmail Smart Compose: Real-Time Assisted Writing](https://mlsanity.com/paper/1906.00080/) (2019)
- [AdaCliP: Adaptive Clipping for Private SGD](https://mlsanity.com/paper/1908.07643/) (2019)
- [Detecting Violations of Differential Privacy](https://mlsanity.com/paper/1805.10277/) (2018)
- [Towards Formalizing the GDPR's Notion of Singling Out](https://mlsanity.com/paper/1904.06009/) (2019)
- [A Better Bound Gives a Hundred Rounds: Enhanced Privacy Guarantees via f-Divergences](https://mlsanity.com/paper/2001.05990/) (2020)

## Built on by (most cited first, 30 of 199)

- [Membership Inference Attacks From First Principles](https://mlsanity.com/paper/2112.03570/) (2021)
- [Quantifying Memorization Across Neural Language Models](https://mlsanity.com/paper/2202.07646/) (2022)
- [TOFU: A Task of Fictitious Unlearning for LLMs](https://mlsanity.com/paper/2401.06121/) (2024)
- [Detecting Pretraining Data from Large Language Models](https://mlsanity.com/paper/2310.16789/) (2023)
- [Membership Inference Attacks on Machine Learning: A Survey](https://mlsanity.com/paper/2103.07853/) (2021)
- [Enhanced Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/2111.09679/) (2021)
- [Unlocking High-Accuracy Differentially Private Image Classification through Scale](https://mlsanity.com/paper/2204.13650/) (2022)
- [What Does it Mean for a Language Model to Preserve Privacy?](https://mlsanity.com/paper/2202.05520/) (2022)
- [Quantifying Privacy Risks of Masked Language Models Using Membership Inference Attacks](https://mlsanity.com/paper/2203.03929/) (2022)
- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [Counterfactual Memorization in Neural Language Models](https://mlsanity.com/paper/2112.12938/) (2021)
- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Reconstructing Training Data with Informed Adversaries](https://mlsanity.com/paper/2201.04845/) (2022)
- [On the Importance of Difficulty Calibration in Membership Inference Attacks](https://mlsanity.com/paper/2111.08440/) (2021)
- [The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation](https://mlsanity.com/paper/2102.06387/) (2021)
- [Privacy Auditing with One (1) Training Run](https://mlsanity.com/paper/2305.08846/) (2023)
- [Privacy for Free: How does Dataset Condensation Help Privacy?](https://mlsanity.com/paper/2206.00240/) (2022)
- [Measuring Forgetting of Memorized Training Examples](https://mlsanity.com/paper/2207.00099/) (2022)
- [Low-Cost High-Power Membership Inference Attacks](https://mlsanity.com/paper/2312.03262/) (2023)
- [Truth Serum: Poisoning Machine Learning Models to Reveal Their Secrets](https://mlsanity.com/paper/2204.00032/) (2022)
- [ML-Doctor: Holistic Risk Assessment of Inference Attacks Against Machine Learning Models](https://mlsanity.com/paper/2102.02551/) (2021)
- [Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descent](https://mlsanity.com/paper/2102.05855/) (2021)
- [EncoderMI: Membership Inference against Pre-trained Encoders in Contrastive Learning](https://mlsanity.com/paper/2108.11023/) (2021)
- [Mitigating Membership Inference Attacks by Self-Distillation Through a Novel Ensemble Architecture](https://mlsanity.com/paper/2110.08324/) (2021)
- [Membership Inference Attacks Against Recommender Systems](https://mlsanity.com/paper/2109.08045/) (2021)
- [Decentralized Federated Learning through Proxy Model Sharing](https://mlsanity.com/paper/2111.11343/) (2021)
- [AlexaTM 20B: Few-Shot Learning Using a Large-Scale Multilingual Seq2Seq Model](https://mlsanity.com/paper/2208.01448/) (2022)
- [TAPAS: a Toolbox for Adversarial Privacy Auditing of Synthetic Data](https://mlsanity.com/paper/2211.06550/) (2022)
- ["Real Attackers Don't Compute Gradients": Bridging the Gap Between Adversarial ML Research and Practice](https://mlsanity.com/paper/2212.14315/) (2022)
- [Antipodes of Label Differential Privacy: PATE and ALIBI](https://mlsanity.com/paper/2106.03408/) (2021)

## Abstract (arXiv)

Differentially private (DP) machine learning allows us to train models on private data while limiting data leakage. DP formalizes this data leakage through a cryptographic game, where an adversary must predict if a model was trained on a dataset D, or a dataset D' that differs in just one example.If observing the training algorithm does not meaningfully increase the adversary's odds of successfully guessing which dataset the model was trained on, then the algorithm is said to be differentially private. Hence, the purpose of privacy analysis is to upper bound the probability that any adversary could successfully guess which dataset the model was trained on.In our paper, we instantiate this hypothetical adversary in order to establish lower bounds on the probability that this distinguishing game can be won. We use this adversary to evaluate the importance of the adversary capabilities allowed in the privacy analysis of DP training algorithms.For DP-SGD, the most common method for training neural networks with differential privacy, our lower bounds are tight and match the theoretical upper bound. This implies that in order to prove better upper bounds, it will be necessary to make use of additional assumptions. Fortunately, we find that our attacks are significantly weaker when additional (realistic)restrictions are put in place on the adversary's capabilities.Thus, in the practical setting common to many real-world deployments, there is a gap between our lower bounds and the upper bounds provided by the analysis: differential privacy is conservative and adversaries may not be able to leak as much information as suggested by the theoretical bound.