# Faster Privacy Accounting via Evolving Discretization

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

## Key facts

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

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

- [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)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [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)
- [Tight Differential Privacy for Discrete-Valued Mechanisms and for the Subsampled Gaussian Mechanism Using FFT](https://mlsanity.com/paper/2006.07134/) (2020)
- [Fast and Memory Efficient Differentially Private-SGD via JL Projections](https://mlsanity.com/paper/2102.03013/) (2021)
- [LinkedIn's Audience Engagements API: A Privacy Preserving Data Analytics System at Scale](https://mlsanity.com/paper/2002.05839/) (2020)
- [Computing Differential Privacy Guarantees for Heterogeneous Compositions Using FFT](https://mlsanity.com/paper/2102.12412/) (2021)
- [PriPeARL: A Framework for Privacy-Preserving Analytics and Reporting at LinkedIn](https://mlsanity.com/paper/1809.07754/) (2018)

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

- [Composition of Differential Privacy & Privacy Amplification by Subsampling](https://mlsanity.com/paper/2210.00597/) (2022)
- [Privacy-Preserving Instructions for Aligning Large Language Models](https://mlsanity.com/paper/2402.13659/) (2024)
- [Selective Pre-training for Private Fine-tuning](https://mlsanity.com/paper/2305.13865/) (2023)
- [How Private are DP-SGD Implementations?](https://mlsanity.com/paper/2403.17673/) (2024)
- [Scalable DP-SGD: Shuffling vs. Poisson Subsampling](https://mlsanity.com/paper/2411.04205/) (2024)
- [Feature-based Learning for Diverse and Privacy-Preserving Counterfactual Explanations](https://mlsanity.com/paper/2209.13446/) (2022)
- [A Randomized Approach for Tight Privacy Accounting](https://mlsanity.com/paper/2304.07927/) (2023)
- [Private Ad Modeling with DP-SGD](https://mlsanity.com/paper/2211.11896/) (2022)
- [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)
- [PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectors](https://mlsanity.com/paper/2503.11897/) (2025)
- [When Gradient Clipping Becomes a Control Mechanism for Differential Privacy in Deep Learning](https://mlsanity.com/paper/2602.10584/) (2026)
- [Auditable Early Stopping for Agentic Routing: Ledger-Verified Run-Wise Certificates under Local DP](https://mlsanity.com/paper/2509.10550/) (2025)
- [Provable Robustness against Backdoor Attacks via the Primal-Dual Perspective on Differential Privacy](https://mlsanity.com/paper/2605.21780/) (2026)
- [Can R'enyi Accountants Beat Lossless Accountants for DP-SGD?](https://mlsanity.com/paper/2610.17120/) (2026)

## Abstract (arXiv)

We introduce a new algorithm for numerical composition of privacy random variables, useful for computing the accurate differential privacy parameters for composition of mechanisms. Our algorithm achieves a running time and memory usage of polylog(k) for the task of self-composing a mechanism, from a broad class of mechanisms, k times; this class, e.g., includes the sub-sampled Gaussian mechanism, that appears in the analysis of differentially private stochastic gradient descent. By comparison, recent work by Gopi et al. (NeurIPS 2021) has obtained a running time of widetildeO(√k) for the same task. Our approach extends to the case of composing k different mechanisms in the same class, improving upon their running time and memory usage from widetildeO(k1.5) to widetildeO(k).