# Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions

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

## Key facts

- Cited by 52 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 31 references that are in the map.
- First posted on arXiv 10 Jul 2022.

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

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [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)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Numerical Composition of Differential Privacy](https://mlsanity.com/paper/2106.02848/) (2021)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [Optimal Accounting of Differential Privacy via Characteristic Function](https://mlsanity.com/paper/2106.08567/) (2021)
- [Individual Privacy Accounting via a Renyi Filter](https://mlsanity.com/paper/2008.11193/) (2020)
- [Tight Differential Privacy for Discrete-Valued Mechanisms and for the Subsampled Gaussian Mechanism Using FFT](https://mlsanity.com/paper/2006.07134/) (2020)
- [Privacy Odometers and Filters: Pay-as-you-Go Composition](https://mlsanity.com/paper/1605.08294/) (2016)
- [Fast and Memory Efficient Differentially Private-SGD via JL Projections](https://mlsanity.com/paper/2102.03013/) (2021)
- [Computing Differential Privacy Guarantees for Heterogeneous Compositions Using FFT](https://mlsanity.com/paper/2102.12412/) (2021)
- [Practical Privacy Filters and Odometers with R'enyi Differential Privacy and Applications to Differentially Private Deep Learning](https://mlsanity.com/paper/2103.01379/) (2021)

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

- [Private Fine-tuning of Large Language Models with Zeroth-order Optimization](https://mlsanity.com/paper/2401.04343/) (2024)
- [Fine-Tuning Large Language Models with User-Level Differential Privacy](https://mlsanity.com/paper/2407.07737/) (2024)
- [Mind the Privacy Unit! User-Level Differential Privacy for Language Model Fine-Tuning](https://mlsanity.com/paper/2406.14322/) (2024)
- [Learning to Generate Image Embeddings with User-level Differential Privacy](https://mlsanity.com/paper/2211.10844/) (2022)
- [How Private are DP-SGD Implementations?](https://mlsanity.com/paper/2403.17673/) (2024)
- [Tighter Privacy Auditing of DP-SGD in the Hidden State Threat Model](https://mlsanity.com/paper/2405.14457/) (2024)
- [Unlocking Accuracy and Fairness in Differentially Private Image Classification](https://mlsanity.com/paper/2308.10888/) (2023)
- [Scalable DP-SGD: Shuffling vs. Poisson Subsampling](https://mlsanity.com/paper/2411.04205/) (2024)
- [VaultGemma: A Differentially Private Gemma Model](https://mlsanity.com/paper/2510.15001/) (2025)
- [Bounding data reconstruction attacks with the hypothesis testing interpretation of differential privacy](https://mlsanity.com/paper/2307.03928/) (2023)
- [Unifying Re-Identification, Attribute Inference, and Data Reconstruction Risks in Differential Privacy](https://mlsanity.com/paper/2507.06969/) (2025)
- [Avoiding Pitfalls for Privacy Accounting of Subsampled Mechanisms under Composition](https://mlsanity.com/paper/2405.20769/) (2024)
- [A Randomized Approach for Tight Privacy Accounting](https://mlsanity.com/paper/2304.07927/) (2023)
- [Subsampling is not Magic: Why Large Batch Sizes Work for Differentially Private Stochastic Optimisation](https://mlsanity.com/paper/2402.03990/) (2024)
- [Beyond the Calibration Point: Mechanism Comparison in Differential Privacy](https://mlsanity.com/paper/2406.08918/) (2024)
- [A Hassle-free Algorithm for Private Learning in Practice: Don't Use Tree Aggregation, Use BLTs](https://mlsanity.com/paper/2408.08868/) (2024)
- [pfl-research: simulation framework for accelerating research in Private Federated Learning](https://mlsanity.com/paper/2404.06430/) (2024)
- [Attack-Aware Noise Calibration for Differential Privacy](https://mlsanity.com/paper/2407.02191/) (2024)
- [Private Ad Modeling with DP-SGD](https://mlsanity.com/paper/2211.11896/) (2022)
- [Auditing Differential Privacy Guarantees Using Density Estimation](https://mlsanity.com/paper/2406.04827/) (2024)
- [Gaussian DP for Reporting Differential Privacy Guarantees in Machine Learning](https://mlsanity.com/paper/2503.10945/) (2025)
- [The Saddle-Point Accountant for Differential Privacy](https://mlsanity.com/paper/2208.09595/) (2022)
- [Sparsity-Preserving Differentially Private Training of Large Embedding Models](https://mlsanity.com/paper/2311.08357/) (2023)
- [Sequentially Auditing Differential Privacy](https://mlsanity.com/paper/2509.07055/) (2025)
- [Empirical Privacy Variance](https://mlsanity.com/paper/2503.12314/) (2025)
- [GeoClip: Geometry-Aware Clipping for Differentially Private SGD](https://mlsanity.com/paper/2506.06549/) (2025)
- [ACTG-ARL: Differentially Private Conditional Text Generation with RL-Boosted Control](https://mlsanity.com/paper/2510.18232/) (2025)
- [Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation](https://mlsanity.com/paper/2601.21636/) (2026)
- [The importance of feature preprocessing for differentially private linear optimization](https://mlsanity.com/paper/2307.11106/) (2023)
- [Tight Group-Level DP Guarantees for DP-SGD with Sampling via Mixture of Gaussians Mechanisms](https://mlsanity.com/paper/2401.10294/) (2024)

## Abstract (arXiv)

The privacy loss distribution (PLD) provides a tight characterization of the privacy loss of a mechanism in the context of differential privacy (DP). Recent work has shown that PLD-based accounting allows for tighter (varepsilon, δ)-DP guarantees for many popular mechanisms compared to other known methods. A key question in PLD-based accounting is how to approximate any (potentially continuous) PLD with a PLD over any specified discrete support. We present a novel approach to this problem. Our approach supports both pessimistic estimation, which overestimates the hockey-stick divergence (i.e., δ) for any value of varepsilon, and optimistic estimation, which underestimates the hockey-stick divergence. Moreover, we show that our pessimistic estimate is the best possible among all pessimistic estimates. Experimental evaluation shows that our approach can work with much larger discretization intervals while keeping a similar error bound compared to previous approaches and yet give a better approximation than existing methods.