mlsanityData to 7 Oct 2026

Faster Privacy Accounting via Evolving Discretization

arXiv 2207.04381 ↗First posted 10 Jul 2022cs.DS cs.CR cs.LGcited by 14

Not on the map. Why?

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

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

Builds on

15 of 34 references.

References · 15

  1. 2016Deep Learning with Differential Privacycited by 2,682
  2. 2017Renyi Differential Privacycited by 643
  3. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 339
  4. 2013The Composition Theorem for Differential Privacycited by 290
  5. 2014RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Responsecited by 262
  6. 2021Numerical Composition of Differential Privacycited by 174
  7. 2017Collecting Telemetry Data Privatelycited by 147
  8. 2016Concentrated Differential Privacycited by 139
  9. 2019Deep Learning with Gaussian Differential Privacycited by 112
  10. 2021Optimal Accounting of Differential Privacy via Characteristic Functioncited by 83
  11. 2020Tight Differential Privacy for Discrete-Valued Mechanisms and for the Subsampled Gaussian Mechanism Using FFTcited by 43
  12. 2021Fast and Memory Efficient Differentially Private-SGD via JL Projectionscited by 29
3 more
  1. 2020LinkedIn's Audience Engagements API: A Privacy Preserving Data Analytics System at Scalecited by 26
  2. 2021Computing Differential Privacy Guarantees for Heterogeneous Compositions Using FFTcited by 20
  3. 2018PriPeARL: A Framework for Privacy-Preserving Analytics and Reporting at LinkedIncited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 4; 2023: 3; 2024: 3; 2025: 2; 2026: 2.

14 papers.

Sort:

By area:

  1. 2022Composition of Differential Privacy & Privacy Amplification by Subsamplingcited by 42
  2. 2024Privacy-Preserving Instructions for Aligning Large Language Modelscited by 34
  3. 2023Selective Pre-training for Private Fine-tuningcited by 22
  4. 2024How Private are DP-SGD Implementations?cited by 22
  5. 2024Scalable DP-SGD: Shuffling vs. Poisson Subsamplingcited by 16
  6. 2022Feature-based Learning for Diverse and Privacy-Preserving Counterfactual Explanationscited by 11
  7. 2023A Randomized Approach for Tight Privacy Accountingcited by 11
  8. 2022Private Ad Modeling with DP-SGDcited by 6
  9. 2022The Saddle-Point Accountant for Differential Privacycited by 5
  10. 2023Sparsity-Preserving Differentially Private Training of Large Embedding Modelscited by 5
  11. 2025PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectorscited by 1
  12. 2026When Gradient Clipping Becomes a Control Mechanism for Differential Privacy in Deep Learningcited by 1
2 more
  1. 2025Auditable Early Stopping for Agentic Routing: Ledger-Verified Run-Wise Certificates under Local DPcited by 0
  2. 2026Provable Robustness against Backdoor Attacks via the Primal-Dual Perspective on Differential Privacycited by 0