mlsanityData to 13 Oct 2026

Numerical Composition of Differential Privacy

arXiv 2106.02848 ↗First posted 5 Jun 2021cs.DS cs.CR cs.LGcited by 177

Not on the map. Why?

Abstract (arXiv)

We give a fast algorithm to optimally compose privacy guarantees of differentially private (DP) algorithms to arbitrary accuracy. Our method is based on the notion of privacy loss random variables to quantify the privacy loss of DP algorithms. The running time and memory needed for our algorithm to approximate the privacy curve of a DP algorithm composed with itself k times is tildeO(√k). This improves over the best prior method by Koskela et al. (2020) which requires tildeOmega(k1.5) running time. We demonstrate the utility of our algorithm by accurately computing the privacy loss of DP-SGD algorithm of Abadi et al. (2016) and showing that our algorithm speeds up the privacy computations by a few orders of magnitude compared to prior work, while maintaining similar accuracy.

Key facts. Cited by 177 papers in the map (data through 13 Oct 2026). Builds on 10 of its 25 references that are in the map. First posted on arXiv 5 Jun 2021.

Builds on

10 of 25 references.

References · 10

  1. 2016Deep Learning with Differential Privacycited by 2,718
  2. 2017Renyi Differential Privacycited by 648
  3. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 343
  4. 2013The Composition Theorem for Differential Privacycited by 296
  5. 2018Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoisingcited by 218
  6. 2016Concentrated Differential Privacycited by 141
  7. 2019Deep Learning with Gaussian Differential Privacycited by 113
  8. 2020Tight Differential Privacy for Discrete-Valued Mechanisms and for the Subsampled Gaussian Mechanism Using FFTcited by 43
  9. 2021Fast and Memory Efficient Differentially Private-SGD via JL Projectionscited by 29
  10. 2021Computing Differential Privacy Guarantees for Heterogeneous Compositions Using FFTcited by 20

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2021: 9; 2022: 33; 2023: 33; 2024: 40; 2025: 35; 2026: 27.

177 papers.

Sort:

By area:

  1. 2021Large Language Models Can Be Strong Differentially Private Learnerscited by 412
  2. 2021Differentially Private Fine-tuning of Language Modelscited by 398
  3. 2023Privacy Auditing with One (1) Training Runcited by 123
  4. 2022Differentially Private Diffusion Modelscited by 119
  5. 2021Large-Scale Differentially Private BERTcited by 118
  6. 2022Synthetic Text Generation with Differential Privacy: A Simple and Practical Recipecited by 108
  7. 2023Privacy-Preserving In-Context Learning with Differentially Private Few-Shot Generationcited by 96
  8. 2022Automatic Clipping: Differentially Private Deep Learning Made Easier and Strongercited by 88
  9. 2021Optimal Accounting of Differential Privacy via Characteristic Functioncited by 83
  10. 2022Differentially Private Language Models for Secure Data Sharingcited by 68
  11. 2023DP-Forward: Fine-tuning and Inference on Language Models with Differential Privacy in Forward Passcited by 66
  12. 2022Differentially Private Optimization on Large Model at Small Costcited by 65
38 more
  1. 2023Differentially Private Synthetic Data via Foundation Model APIs 1: Imagescited by 64
  2. 2022TAN Without a Burn: Scaling Laws of DP-SGDcited by 52
  3. 2022Exploring the Limits of Differentially Private Deep Learning with Group-wise Clippingcited by 52
  4. 2022Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributionscited by 50
  5. 2023Privacy-Preserving In-Context Learning for Large Language Modelscited by 50
  6. 2022Differentially Private Bias-Term Fine-tuning of Foundation Modelscited by 47
  7. 2023Bounding Training Data Reconstruction in DP-SGDcited by 45
  8. 2022Composition of Differential Privacy & Privacy Amplification by Subsamplingcited by 43
  9. 2024Private Fine-tuning of Large Language Models with Zeroth-order Optimizationcited by 41
  10. 2022Privately Fine-Tuning Large Language Models with Differential Privacycited by 39
  11. 2023Learn to Unlearn for Deep Neural Networks: Minimizing Unlearning Interference with Gradient Projectioncited by 37
  12. 2022Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimizationcited by 35
  13. 2024Privacy-Preserving Instructions for Aligning Large Language Modelscited by 35
  14. 2022Bayesian Estimation of Differential Privacycited by 32
  15. 2021Dynamic Differential-Privacy Preserving SGDcited by 30
  16. 2023SAFE: Machine Unlearning With Shard Graphscited by 28
  17. 2022FLUTE: A Scalable, Extensible Framework for High-Performance Federated Learning Simulationscited by 27
  18. 2021The Role of Adaptive Optimizers for Honest Private Hyperparameter Selectioncited by 25
  19. 2022CANIFE: Crafting Canaries for Empirical Privacy Measurement in Federated Learningcited by 24
  20. 2023Selective Pre-training for Private Fine-tuningcited by 23
  21. 2024Mind the Privacy Unit! User-Level Differential Privacy for Language Model Fine-Tuningcited by 23
  22. 2024How Private are DP-SGD Implementations?cited by 22
  23. 2022Individual Privacy Accounting for Differentially Private Stochastic Gradient Descentcited by 20
  24. 2023Differentially Private Natural Language Models: Recent Advances and Future Directionscited by 20
  25. 2022Individual Privacy Accounting with Gaussian Differential Privacycited by 19
  26. 2023Practical Differentially Private Hyperparameter Tuning with Subsamplingcited by 19
  27. 2023Arbitrary Decisions are a Hidden Cost of Differentially Private Trainingcited by 19
  28. 2023Differentially Private Image Classification by Learning Priors from Random Processescited by 19
  29. 2023Threshold KNN-Shapley: A Linear-Time and Privacy-Friendly Approach to Data Valuationcited by 19
  30. 2023Practical Differentially Private and Byzantine-resilient Federated Learningcited by 18
  31. 2024Tighter Privacy Auditing of DP-SGD in the Hidden State Threat Modelcited by 18
  32. 2023Private GANs, Revisitedcited by 17
  33. 2023Privately Aligning Language Models with Reinforcement Learningcited by 17
  34. 2023Privacy-Aware Document Visual Question Answeringcited by 17
  35. 2024Scalable DP-SGD: Shuffling vs. Poisson Subsamplingcited by 16
  36. 2022Edgeworth Accountant: An Analytical Approach to Differential Privacy Compositioncited by 14
  37. 2022Faster Privacy Accounting via Evolving Discretizationcited by 14
  38. 2023Bounding data reconstruction attacks with the hypothesis testing interpretation of differential privacycited by 14

50 most cited of 177 All 177 (JSON)