# A New Analysis of Differential Privacy's Generalization Guarantees

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Sep 2019.

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

- [Unlocking High-Accuracy Differentially Private Image Classification through Scale](https://mlsanity.com/paper/2204.13650/) (2022)
- [Adaptive Machine Unlearning](https://mlsanity.com/paper/2106.04378/) (2021)
- [Privacy Auditing with One (1) Training Run](https://mlsanity.com/paper/2305.08846/) (2023)
- [Low-Degree Multicalibration](https://mlsanity.com/paper/2203.01255/) (2022)
- [Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization](https://mlsanity.com/paper/2303.12921/) (2023)
- [An Algorithmic Framework for Bias Bounties](https://mlsanity.com/paper/2201.10408/) (2022)
- [Wide Network Learning with Differential Privacy](https://mlsanity.com/paper/2103.01294/) (2021)
- [Generalization Bounds for Noisy Iterative Algorithms Using Properties of Additive Noise Channels](https://mlsanity.com/paper/2102.02976/) (2021)
- [Reconciling Individual Probability Forecasts](https://mlsanity.com/paper/2209.01687/) (2022)
- [Multicalibrated Regression for Downstream Fairness](https://mlsanity.com/paper/2209.07312/) (2022)
- [Differential Privacy Mechanisms in Neural Tangent Kernel Regression](https://mlsanity.com/paper/2407.13621/) (2024)
- [Provable Differentially Private Computation of the Cross-Attention Mechanism](https://mlsanity.com/paper/2407.14717/) (2024)
- [Valid Inference After Causal Discovery](https://mlsanity.com/paper/2208.05949/) (2022)
- [A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators](https://mlsanity.com/paper/2107.14527/) (2021)
- [Adaptive Data Analysis with Correlated Observations](https://mlsanity.com/paper/2201.08704/) (2022)
- [On Differential Privacy and Adaptive Data Analysis with Bounded Space](https://mlsanity.com/paper/2302.05707/) (2023)
- [Generalization in the Face of Adaptivity: A Bayesian Perspective](https://mlsanity.com/paper/2106.10761/) (2021)
- [Fast John Ellipsoid Computation with Differential Privacy Optimization](https://mlsanity.com/paper/2408.06395/) (2024)
- [Adaptive Data Analysis in a Balanced Adversarial Model](https://mlsanity.com/paper/2305.15452/) (2023)
- [High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descent](https://mlsanity.com/paper/2207.01560/) (2022)
- [What Fits (Into Few Tokens) Doesn't Overfit: Compression and Generalization in ML Research Agents](https://mlsanity.com/paper/2606.11045/) (2026)
- [Generalization Bounds for Stochastic Gradient Langevin Dynamics: A Unified View via Information Leakage Analysis](https://mlsanity.com/paper/2112.08439/) (2021)
- [Adaptive Data Analysis for Growing Data](https://mlsanity.com/paper/2405.13375/) (2024)
- [Noise is All You Need: Private Second-Order Convergence of Noisy SGD](https://mlsanity.com/paper/2410.06878/) (2024)
- [Tight Bounds for Answering Adaptively Chosen Concentrated Queries](https://mlsanity.com/paper/2507.13700/) (2025)
- [Sample-efficient Multiclass Calibration under ℓp Error](https://mlsanity.com/paper/2509.23000/) (2025)
- [Private Realizable-to-Agnostic Transformation with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2510.01291/) (2025)
- [Improved Generalization Guarantees in Restricted Data Models](https://mlsanity.com/paper/2207.10668/) (2022)
- [Adversarially Robust Distributed Count Tracking via Partial Differential Privacy](https://mlsanity.com/paper/2311.00346/) (2023)
- [Loss Gradient Gaussian Width based Generalization and Optimization Guarantees](https://mlsanity.com/paper/2406.07712/) (2024)

## Abstract (arXiv)

We give a new proof of the "transfer theorem" underlying adaptive data analysis: that any mechanism for answering adaptively chosen statistical queries that is differentially private and sample-accurate is also accurate out-of-sample. Our new proof is elementary and gives structural insights that we expect will be useful elsewhere. We show: 1) that differential privacy ensures that the expectation of any query on the posterior distribution on datasets induced by the transcript of the interaction is close to its true value on the data distribution, and 2) sample accuracy on its own ensures that any query answer produced by the mechanism is close to its posterior expectation with high probability. This second claim follows from a thought experiment in which we imagine that the dataset is resampled from the posterior distribution after the mechanism has committed to its answers. The transfer theorem then follows by summing these two bounds, and in particular, avoids the "monitor argument" used to derive high probability bounds in prior work. An upshot of our new proof technique is that the concrete bounds we obtain are substantially better than the best previously known bounds, even though the improvements are in the constants, rather than the asymptotics (which are known to be tight). As we show, our new bounds outperform the naive "sample-splitting" baseline at dramatically smaller dataset sizes compared to the previous state of the art, bringing techniques from this literature closer to practicality.