mlsanityData to 7 Oct 2026

Privacy Amplification for Matrix Mechanisms

arXiv 2310.15526 ↗First posted 24 Oct 2023cs.LG cs.CRcited by 17

Not on the map. Why?

Abstract (arXiv)

Privacy amplification exploits randomness in data selection to provide tighter differential privacy (DP) guarantees. This analysis is key to DP-SGD's success in machine learning, but, is not readily applicable to the newer state-of-the-art algorithms. This is because these algorithms, known as DP-FTRL, use the matrix mechanism to add correlated noise instead of independent noise as in DP-SGD. In this paper, we propose "MMCC", the first algorithm to analyze privacy amplification via sampling for any generic matrix mechanism. MMCC is nearly tight in that it approaches a lower bound as ε→0. To analyze correlated outputs in MMCC, we prove that they can be analyzed as if they were independent, by conditioning them on prior outputs. Our "conditional composition theorem" has broad utility: we use it to show that the noise added to binary-tree-DP-FTRL can asymptotically match the noise added to DP-SGD with amplification. Our amplification algorithm also has practical empirical utility: we show it leads to significant improvement in the privacy-utility trade-offs for DP-FTRL algorithms on standard benchmarks.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). Builds on 16 of its 29 references that are in the map. First posted on arXiv 24 Oct 2023.

Builds on

16 of 29 references.

References · 16

  1. 2016Deep Learning with Differential Privacycited by 2,682
  2. 2019R'enyi Differential Privacy of the Sampled Gaussian Mechanismcited by 199
  3. 2021Practical and Private (Deep) Learning without Sampling or Shufflingcited by 169
  4. 2018Amplification by Shuffling: From Local to Central Differential Privacy via Anonymitycited by 163
  5. 2023How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacycited by 150
  6. 2018Privacy Amplification by Iterationcited by 97
  7. 2020Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shufflingcited by 96
  8. 2021Optimal Accounting of Differential Privacy via Characteristic Functioncited by 83
  9. 2022Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streamscited by 59
  10. 2023(Amplified) Banded Matrix Factorization: A unified approach to private trainingcited by 49
  11. 2022Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learningcited by 48
  12. 2022Composition of Differential Privacy & Privacy Amplification by Subsamplingcited by 42
4 more
  1. 2020Privacy Amplification via Random Check-Inscited by 39
  2. 2022Constant matters: Fine-grained Complexity of Differentially Private Continual Observationcited by 23
  3. 2023A Unifying Framework for Differentially Private Sums under Continual Observationcited by 15
  4. 2021HDMM: Optimizing error of high-dimensional statistical queries under differential privacycited by 11

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 5; 2025: 6; 2026: 5.

17 papers.

Sort:

  1. 2024Teach LLMs to Phish: Stealing Private Information from Language Modelscited by 29
  2. 2024Fine-Tuning Large Language Models with User-Level Differential Privacycited by 28
  3. 2025Privacy amplification by random allocationcited by 13
  4. 2024Banded Square Root Matrix Factorization for Differentially Private Model Trainingcited by 12
  5. 2023Preserving Node-level Privacy in Graph Neural Networkscited by 11
  6. 2024Streaming Private Continual Counting via Binningcited by 7
  7. 2025Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGDcited by 7
  8. 2024Improved Communication-Privacy Trade-offs in L2 Mean Estimation under Streaming Differential Privacycited by 4
  9. 2025An Inversion Theorem for Buffered Linear Toeplitz (BLT) Matrices and Applications to Streaming Differential Privacycited by 3
  10. 2026Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocationcited by 3
  11. 2026DP-λCGD: Efficient Noise Correlation for Differentially Private Model Trainingcited by 1
  12. 2026Less Random, More Private: What is the Optimal Subsampling Scheme for DP-SGD?cited by 1
5 more
  1. 2025Federated Learning with Enhanced Privacy via Model Splitting and Random Client Participationcited by 0
  2. 2025Secret-Protected Evolution for Differentially Private Synthetic Text Generationcited by 0
  3. 2025Prediction with Expert Advice under Local Differential Privacycited by 0
  4. 2026Beyond Square Roots: A Memory-Efficient Explicit Factorization for Multi-Epoch Private Learningcited by 0
  5. 2026Provable Robustness against Backdoor Attacks via the Primal-Dual Perspective on Differential Privacycited by 0