# A Randomized Approach for Tight Privacy Accounting

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 51 references that are in the map.
- First posted on arXiv 17 Apr 2023.

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

- [LAION-5B: An open large-scale dataset for training next generation image-text models](https://mlsanity.com/paper/2210.08402/) (2022)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [BEiT: BERT Pre-Training of Image Transformers](https://mlsanity.com/paper/2106.08254/) (2021)
- [Scaling Vision Transformers](https://mlsanity.com/paper/2106.04560/) (2021)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [Auditing Differentially Private Machine Learning: How Private is Private SGD?](https://mlsanity.com/paper/2006.07709/) (2020)
- [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)
- [The Discrete Gaussian for Differential Privacy](https://mlsanity.com/paper/2004.00010/) (2020)
- [Deep Learning with Gaussian Differential Privacy](https://mlsanity.com/paper/1911.11607/) (2019)
- [Optimal Accounting of Differential Privacy via Characteristic Function](https://mlsanity.com/paper/2106.08567/) (2021)
- [Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions](https://mlsanity.com/paper/2207.04380/) (2022)
- [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)
- [Three Variants of Differential Privacy: Lossless Conversion and Applications](https://mlsanity.com/paper/2008.06529/) (2020)
- [A General Framework for Auditing Differentially Private Machine Learning](https://mlsanity.com/paper/2210.08643/) (2022)
- [Computing Differential Privacy Guarantees for Heterogeneous Compositions Using FFT](https://mlsanity.com/paper/2102.12412/) (2021)
- [Optimal Membership Inference Bounds for Adaptive Composition of Sampled Gaussian Mechanisms](https://mlsanity.com/paper/2204.06106/) (2022)
- [Property Testing for Differential Privacy](https://mlsanity.com/paper/1806.06427/) (2018)
- [Faster Privacy Accounting via Evolving Discretization](https://mlsanity.com/paper/2207.04381/) (2022)
- [Edgeworth Accountant: An Analytical Approach to Differential Privacy Composition](https://mlsanity.com/paper/2206.04236/) (2022)
- [Generalized PTR: User-Friendly Recipes for Data-Adaptive Algorithms with Differential Privacy](https://mlsanity.com/paper/2301.00301/) (2022)
- [The Saddle-Point Accountant for Differential Privacy](https://mlsanity.com/paper/2208.09595/) (2022)
- [Renyi Differential Privacy of Propose-Test-Release and Applications to Private and Robust Machine Learning](https://mlsanity.com/paper/2209.07716/) (2022)
- [On the (Im)Possibility of Estimating Various Notions of Differential Privacy](https://mlsanity.com/paper/2208.14414/) (2022)

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

- [Private Fine-tuning of Large Language Models with Zeroth-order Optimization](https://mlsanity.com/paper/2401.04343/) (2024)
- [Auditing f-Differential Privacy in One Run](https://mlsanity.com/paper/2410.22235/) (2024)
- [How Private are DP-SGD Implementations?](https://mlsanity.com/paper/2403.17673/) (2024)
- [Bounding data reconstruction attacks with the hypothesis testing interpretation of differential privacy](https://mlsanity.com/paper/2307.03928/) (2023)
- [Balls-and-Bins Sampling for DP-SGD](https://mlsanity.com/paper/2412.16802/) (2024)
- [Avoiding Pitfalls for Privacy Accounting of Subsampled Mechanisms under Composition](https://mlsanity.com/paper/2405.20769/) (2024)
- [Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation](https://mlsanity.com/paper/2601.21636/) (2026)
- [Machine Learning with Privacy for Protected Attributes](https://mlsanity.com/paper/2506.19836/) (2025)
- [Less Random, More Private: What is the Optimal Subsampling Scheme for DP-SGD?](https://mlsanity.com/paper/2605.07072/) (2026)
- [Auditing Differential Privacy in the Black-Box Setting](https://mlsanity.com/paper/2503.12045/) (2025)
- [When Are Trade-Off Functions Testable from Finite Samples?](https://mlsanity.com/paper/2605.10774/) (2026)

## Abstract (arXiv)

Bounding privacy leakage over compositions, i.e., privacy accounting, is a key challenge in differential privacy (DP). The privacy parameter (eps or δ) is often easy to estimate but hard to bound. In this paper, we propose a new differential privacy paradigm called estimate-verify-release (EVR), which addresses the challenges of providing a strict upper bound for privacy parameter in DP compositions by converting an estimate of privacy parameter into a formal guarantee. The EVR paradigm first estimates the privacy parameter of a mechanism, then verifies whether it meets this guarantee, and finally releases the query output based on the verification result. The core component of the EVR is privacy verification. We develop a randomized privacy verifier using Monte Carlo (MC) technique. Furthermore, we propose an MC-based DP accountant that outperforms existing DP accounting techniques in terms of accuracy and efficiency. Our empirical evaluation shows the newly proposed EVR paradigm improves the utility-privacy tradeoff for privacy-preserving machine learning.