# Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learning

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

## Key facts

- Cited by 48 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 50 references that are in the map.
- First posted on arXiv 12 Nov 2022.

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

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Extracting Training Data from Large Language Models](https://mlsanity.com/paper/2012.07805/) (2020)
- [Adaptive Federated Optimization](https://mlsanity.com/paper/2003.00295/) (2020)
- [The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks](https://mlsanity.com/paper/1802.08232/) (2018)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Subsampled R'enyi Differential Privacy and Analytical Moments Accountant](https://mlsanity.com/paper/1808.00087/) (2018)
- [Unlocking High-Accuracy Differentially Private Image Classification through Scale](https://mlsanity.com/paper/2204.13650/) (2022)
- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity](https://mlsanity.com/paper/1811.12469/) (2018)
- [Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds](https://mlsanity.com/paper/1405.7085/) (2014)
- [Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling](https://mlsanity.com/paper/2012.12803/) (2020)
- [Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams](https://mlsanity.com/paper/2202.08312/) (2022)
- [The Power of Factorization Mechanisms in Local and Central Differential Privacy](https://mlsanity.com/paper/1911.08339/) (2019)
- [Optimizing error of high-dimensional statistical queries under differential privacy](https://mlsanity.com/paper/1808.03537/) (2018)
- [Almost Tight Error Bounds on Differentially Private Continual Counting](https://mlsanity.com/paper/2211.05006/) (2022)
- [Nearly Optimal Private Convolution](https://mlsanity.com/paper/1301.6447/) (2013)

## Built on by (most cited first, 30 of 48)

- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Federated Learning of Gboard Language Models with Differential Privacy](https://mlsanity.com/paper/2305.18465/) (2023)
- [(Amplified) Banded Matrix Factorization: A unified approach to private training](https://mlsanity.com/paper/2306.08153/) (2023)
- [Privacy Side Channels in Machine Learning Systems](https://mlsanity.com/paper/2309.05610/) (2023)
- [One-shot Empirical Privacy Estimation for Federated Learning](https://mlsanity.com/paper/2302.03098/) (2023)
- [Teach LLMs to Phish: Stealing Private Information from Language Models](https://mlsanity.com/paper/2403.00871/) (2024)
- [On the Convergence of Federated Averaging with Cyclic Client Participation](https://mlsanity.com/paper/2302.03109/) (2023)
- [Fine-Tuning Large Language Models with User-Level Differential Privacy](https://mlsanity.com/paper/2407.07737/) (2024)
- [Correlated Noise Provably Beats Independent Noise for Differentially Private Learning](https://mlsanity.com/paper/2310.06771/) (2023)
- [Differentially Private Natural Language Models: Recent Advances and Future Directions](https://mlsanity.com/paper/2301.09112/) (2023)
- [Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacy](https://mlsanity.com/paper/2302.01463/) (2023)
- [Privacy Amplification for Matrix Mechanisms](https://mlsanity.com/paper/2310.15526/) (2023)
- [A Unifying Framework for Differentially Private Sums under Continual Observation](https://mlsanity.com/paper/2307.08970/) (2023)
- [A Smooth Binary Mechanism for Efficient Private Continual Observation](https://mlsanity.com/paper/2306.09666/) (2023)
- [Banded Square Root Matrix Factorization for Differentially Private Model Training](https://mlsanity.com/paper/2405.13763/) (2024)
- [A Hassle-free Algorithm for Private Learning in Practice: Don't Use Tree Aggregation, Use BLTs](https://mlsanity.com/paper/2408.08868/) (2024)
- [Streaming Private Continual Counting via Binning](https://mlsanity.com/paper/2412.07093/) (2024)
- [Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGD](https://mlsanity.com/paper/2505.12128/) (2025)
- [On Design Principles for Private Adaptive Optimizers](https://mlsanity.com/paper/2507.01129/) (2025)
- [Private Federated Learning with Autotuned Compression](https://mlsanity.com/paper/2307.10999/) (2023)
- [Continual Release Moment Estimation with Differential Privacy](https://mlsanity.com/paper/2502.06597/) (2025)
- [Improved Communication-Privacy Trade-offs in L2 Mean Estimation under Streaming Differential Privacy](https://mlsanity.com/paper/2405.02341/) (2024)
- [General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation](https://mlsanity.com/paper/2301.13850/) (2023)
- [DMM: Distributed Matrix Mechanism for Differentially-Private Federated Learning Based on Constant-Overhead Linear Secret Resharing](https://mlsanity.com/paper/2410.16161/) (2024)
- [Empirical Privacy Variance](https://mlsanity.com/paper/2503.12314/) (2025)
- [Binned Group Algebra Factorization for Differentially Private Continual Counting](https://mlsanity.com/paper/2504.04398/) (2025)
- [Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting](https://mlsanity.com/paper/2509.14334/) (2025)
- [Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation](https://mlsanity.com/paper/2601.21636/) (2026)
- [DP-λCGD: Efficient Noise Correlation for Differentially Private Model Training](https://mlsanity.com/paper/2601.22334/) (2026)
- [An Empirical Evaluation of Federated Contextual Bandit Algorithms](https://mlsanity.com/paper/2303.10218/) (2023)

## Abstract (arXiv)

We introduce new differentially private (DP) mechanisms for gradient-based machine learning (ML) with multiple passes (epochs) over a dataset, substantially improving the achievable privacy-utility-computation tradeoffs. We formalize the problem of DP mechanisms for adaptive streams with multiple participations and introduce a non-trivial extension of online matrix factorization DP mechanisms to our setting. This includes establishing the necessary theory for sensitivity calculations and efficient computation of optimal matrices. For some applications like >!! 10,000 SGD steps, applying these optimal techniques becomes computationally expensive. We thus design an efficient Fourier-transform-based mechanism with only a minor utility loss. Extensive empirical evaluation on both example-level DP for image classification and user-level DP for language modeling demonstrate substantial improvements over all previous methods, including the widely-used DP-SGD . Though our primary application is to ML, our main DP results are applicable to arbitrary linear queries and hence may have much broader applicability.