mlsanityData to 7 Oct 2026

Gradients Look Alike: Sensitivity is Often Overestimated in DP-SGD

arXiv 2307.00310 ↗First posted 1 Jul 2023cs.LG cs.AI cs.CRcited by 11

Not on the map. Why?

Abstract (arXiv)

Differentially private stochastic gradient descent (DP-SGD) is the canonical approach to private deep learning. While the current privacy analysis of DP-SGD is known to be tight in some settings, several empirical results suggest that models trained on common benchmark datasets leak significantly less privacy for many datapoints. Yet, despite past attempts, a rigorous explanation for why this is the case has not been reached. Is it because there exist tighter privacy upper bounds when restricted to these dataset settings, or are our attacks not strong enough for certain datapoints? In this paper, we provide the first per-instance (i.e., ``data-dependent") DP analysis of DP-SGD. Our analysis captures the intuition that points with similar neighbors in the dataset enjoy better data-dependent privacy than outliers. Formally, this is done by modifying the per-step privacy analysis of DP-SGD to introduce a dependence on the distribution of model updates computed from a training dataset. We further develop a new composition theorem to effectively use this new per-step analysis to reason about an entire training run. Put all together, our evaluation shows that this novel DP-SGD analysis allows us to now formally show that DP-SGD leaks significantly less privacy for many datapoints (when trained on common benchmarks) than the current data-independent guarantee. This implies privacy attacks will necessarily fail against many datapoints if the adversary does not have sufficient control over the possible training datasets.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 33 of its 52 references that are in the map. First posted on arXiv 1 Jul 2023.

Builds on

33 of 52 references.

References · 33

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2016Deep Learning with Differential Privacycited by 2,682
  3. 2019Machine Unlearningcited by 1,020
  4. 2018The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networkscited by 847
  5. 2022Quantifying Memorization Across Neural Language Modelscited by 755
  6. 2017Renyi Differential Privacycited by 643
  7. 2019Certified Data Removal from Machine Learning Modelscited by 512
  8. 2020What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimationcited by 492
  9. 2019Does Learning Require Memorization? A Short Tale about a Long Tailcited by 452
  10. 2019Making AI Forget You: Data Deletion in Machine Learningcited by 447
  11. 2022Memorization Without Overfitting: Analyzing the Training Dynamics of Large Language Modelscited by 218
  12. 2020Auditing Differentially Private Machine Learning: How Private is Private SGD?cited by 213
21 more
  1. 2019R'enyi Differential Privacy of the Sampled Gaussian Mechanismcited by 199
  2. 2021Adversary Instantiation: Lower Bounds for Differentially Private Machine Learningcited by 193
  3. 2021Numerical Composition of Differential Privacycited by 174
  4. 2021Adaptive Machine Unlearningcited by 164
  5. 2021On the Necessity of Auditable Algorithmic Definitions for Machine Unlearningcited by 164
  6. 2022The Privacy Onion Effect: Memorization is Relativecited by 128
  7. 2021Proof-of-Learning: Definitions and Practicecited by 81
  8. 2021Manipulating SGD with Data Ordering Attackscited by 73
  9. 2022Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Losscited by 60
  10. 2020Individual Privacy Accounting via a Renyi Filtercited by 57
  11. 2022Bounding Training Data Reconstruction in Private (Deep) Learningcited by 43
  12. 2019Identity Crisis: Memorization and Generalization under Extreme Overparameterizationcited by 33
  13. 2022Bayesian Estimation of Differential Privacycited by 31
  14. 2022Selective Prediction via Training Dynamicscited by 20
  15. 2022Individual Privacy Accounting for Differentially Private Stochastic Gradient Descentcited by 20
  16. 2022Optimal Membership Inference Bounds for Adaptive Composition of Sampled Gaussian Mechanismscited by 19
  17. 2022Individual Privacy Accounting with Gaussian Differential Privacycited by 19
  18. 2022Bounding Membership Inferencecited by 14
  19. 2022Proof-of-Learning is Currently More Broken Than You Thinkcited by 12
  20. 2022What You See is What You Get: Principled Deep Learning via Distributional Generalizationcited by 10
  21. 2023Training Private Models That Know What They Don't Knowcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 4; 2025: 4; 2026: 3.

11 papers.

  1. 2024Inexact Unlearning Needs More Careful Evaluations to Avoid a False Sense of Privacycited by 78
  2. 2024Fast Exact Unlearning for In-Context Learning Data for LLMscited by 33
  3. 2024Underestimated Privacy Risks for Minority Populations in Large Language Model Unlearningcited by 9
  4. 2025Rectifying Privacy and Efficacy Measurements in Machine Unlearning: A New Inference Attack Perspectivecited by 8
  5. 2024Free Record-Level Privacy Risk Evaluation Through Artifact-Based Methodscited by 6
  6. 2025Leveraging Per-Instance Privacy for Machine Unlearningcited by 4
  7. 2026Gauss-Newton Unlearning for the LLM Eracited by 4
  8. 2025Efficient Public Verification of Private ML via Regularizationcited by 1
  9. 2025Stabilization of Perturbed Loss Function: Differential Privacy without Gradient Noisecited by 0
  10. 2026Risk-Equalized Differentially Private Synthetic Data: Protecting Outliers by Controlling Record-Level Influencecited by 0
  11. 2026Certified Per-Instance Unlearning Using Individual Sensitivity Boundscited by 0