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

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

## Key facts

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

## Builds on (most cited first, 30 of 33)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Machine Unlearning](https://mlsanity.com/paper/1912.03817/) (2019)
- [The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks](https://mlsanity.com/paper/1802.08232/) (2018)
- [Quantifying Memorization Across Neural Language Models](https://mlsanity.com/paper/2202.07646/) (2022)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Certified Data Removal from Machine Learning Models](https://mlsanity.com/paper/1911.03030/) (2019)
- [What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation](https://mlsanity.com/paper/2008.03703/) (2020)
- [Making AI Forget You: Data Deletion in Machine Learning](https://mlsanity.com/paper/1907.05012/) (2019)
- [Does Learning Require Memorization? A Short Tale about a Long Tail](https://mlsanity.com/paper/1906.05271/) (2019)
- [Memorization Without Overfitting: Analyzing the Training Dynamics of Large Language Models](https://mlsanity.com/paper/2205.10770/) (2022)
- [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)
- [Adversary Instantiation: Lower Bounds for Differentially Private Machine Learning](https://mlsanity.com/paper/2101.04535/) (2021)
- [Numerical Composition of Differential Privacy](https://mlsanity.com/paper/2106.02848/) (2021)
- [Adaptive Machine Unlearning](https://mlsanity.com/paper/2106.04378/) (2021)
- [On the Necessity of Auditable Algorithmic Definitions for Machine Unlearning](https://mlsanity.com/paper/2110.11891/) (2021)
- [The Privacy Onion Effect: Memorization is Relative](https://mlsanity.com/paper/2206.10469/) (2022)
- [Proof-of-Learning: Definitions and Practice](https://mlsanity.com/paper/2103.05633/) (2021)
- [Manipulating SGD with Data Ordering Attacks](https://mlsanity.com/paper/2104.09667/) (2021)
- [Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss](https://mlsanity.com/paper/2205.13710/) (2022)
- [Individual Privacy Accounting via a Renyi Filter](https://mlsanity.com/paper/2008.11193/) (2020)
- [Bounding Training Data Reconstruction in Private (Deep) Learning](https://mlsanity.com/paper/2201.12383/) (2022)
- [Identity Crisis: Memorization and Generalization under Extreme Overparameterization](https://mlsanity.com/paper/1902.04698/) (2019)
- [Bayesian Estimation of Differential Privacy](https://mlsanity.com/paper/2206.05199/) (2022)
- [Selective Prediction via Training Dynamics](https://mlsanity.com/paper/2205.13532/) (2022)
- [Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent](https://mlsanity.com/paper/2206.02617/) (2022)
- [Individual Privacy Accounting with Gaussian Differential Privacy](https://mlsanity.com/paper/2209.15596/) (2022)
- [Optimal Membership Inference Bounds for Adaptive Composition of Sampled Gaussian Mechanisms](https://mlsanity.com/paper/2204.06106/) (2022)
- [Bounding Membership Inference](https://mlsanity.com/paper/2202.12232/) (2022)

## Built on by (most cited first, 11 of 11)

- [Inexact Unlearning Needs More Careful Evaluations to Avoid a False Sense of Privacy](https://mlsanity.com/paper/2403.01218/) (2024)
- [Fast Exact Unlearning for In-Context Learning Data for LLMs](https://mlsanity.com/paper/2402.00751/) (2024)
- [Underestimated Privacy Risks for Minority Populations in Large Language Model Unlearning](https://mlsanity.com/paper/2412.08559/) (2024)
- [Rectifying Privacy and Efficacy Measurements in Machine Unlearning: A New Inference Attack Perspective](https://mlsanity.com/paper/2506.13009/) (2025)
- [Free Record-Level Privacy Risk Evaluation Through Artifact-Based Methods](https://mlsanity.com/paper/2411.05743/) (2024)
- [Leveraging Per-Instance Privacy for Machine Unlearning](https://mlsanity.com/paper/2505.18786/) (2025)
- [Gauss-Newton Unlearning for the LLM Era](https://mlsanity.com/paper/2602.10568/) (2026)
- [Efficient Public Verification of Private ML via Regularization](https://mlsanity.com/paper/2512.04008/) (2025)
- [Stabilization of Perturbed Loss Function: Differential Privacy without Gradient Noise](https://mlsanity.com/paper/2508.15523/) (2025)
- [Risk-Equalized Differentially Private Synthetic Data: Protecting Outliers by Controlling Record-Level Influence](https://mlsanity.com/paper/2602.10232/) (2026)
- [Certified Per-Instance Unlearning Using Individual Sensitivity Bounds](https://mlsanity.com/paper/2602.15602/) (2026)

## 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.