# Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGD

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 35 references that are in the map.
- First posted on arXiv 17 May 2025.

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

- [Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising](https://mlsanity.com/paper/1805.06530/) (2018)
- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams](https://mlsanity.com/paper/2202.08312/) (2022)
- [(Amplified) Banded Matrix Factorization: A unified approach to private training](https://mlsanity.com/paper/2306.08153/) (2023)
- [Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learning](https://mlsanity.com/paper/2211.06530/) (2022)
- [Almost Tight Error Bounds on Differentially Private Continual Counting](https://mlsanity.com/paper/2211.05006/) (2022)
- [Correlated Noise Provably Beats Independent Noise for Differentially Private Learning](https://mlsanity.com/paper/2310.06771/) (2023)
- [Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacy](https://mlsanity.com/paper/2302.01463/) (2023)
- [Near Exact Privacy Amplification for Matrix Mechanisms](https://mlsanity.com/paper/2410.06266/) (2024)
- [Privacy Amplification for Matrix Mechanisms](https://mlsanity.com/paper/2310.15526/) (2023)
- [Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy](https://mlsanity.com/paper/2404.16706/) (2024)
- [A Unifying Framework for Differentially Private Sums under Continual Observation](https://mlsanity.com/paper/2307.08970/) (2023)
- [Balls-and-Bins Sampling for DP-SGD](https://mlsanity.com/paper/2412.16802/) (2024)
- [Scaling up the Banded Matrix Factorization Mechanism for Differentially Private ML](https://mlsanity.com/paper/2405.15913/) (2024)
- [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)
- [Improved Differentially Private Continual Observation Using Group Algebra](https://mlsanity.com/paper/2412.02840/) (2024)
- [Streaming Private Continual Counting via Binning](https://mlsanity.com/paper/2412.07093/) (2024)
- [Locally Differentially Private Online Federated Learning With Correlated Noise](https://mlsanity.com/paper/2411.18752/) (2024)
- [Continual Release Moment Estimation with Differential Privacy](https://mlsanity.com/paper/2502.06597/) (2025)
- [DMM: Distributed Matrix Mechanism for Differentially-Private Federated Learning Based on Constant-Overhead Linear Secret Resharing](https://mlsanity.com/paper/2410.16161/) (2024)
- [Binned Group Algebra Factorization for Differentially Private Continual Counting](https://mlsanity.com/paper/2504.04398/) (2025)
- [An Inversion Theorem for Buffered Linear Toeplitz (BLT) Matrices and Applications to Streaming Differential Privacy](https://mlsanity.com/paper/2504.21413/) (2025)
- [On the Space Complexity of Online Convolution](https://mlsanity.com/paper/2505.00181/) (2025)

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

- [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)
- [Learning Rate Scheduling with Matrix Factorization for Private Training](https://mlsanity.com/paper/2511.17994/) (2025)
- [Correlating Cross-Iteration Noise for DP-SGD using Model Curvature](https://mlsanity.com/paper/2510.05416/) (2025)
- [Matrix Factorization for Practical Continual Mean Estimation Under User-Level Differential Privacy](https://mlsanity.com/paper/2601.22320/) (2026)
- [Beyond Square Roots: A Memory-Efficient Explicit Factorization for Multi-Epoch Private Learning](https://mlsanity.com/paper/2605.18379/) (2026)

## Abstract (arXiv)

Matrix factorization mechanisms for differentially private training have emerged as a promising approach to improve model utility under privacy constraints. In practical settings, models are typically trained over multiple epochs, requiring matrix factorizations that account for repeated participation. Existing theoretical upper and lower bounds on multi-epoch factorization error leave a significant gap. In this work, we introduce a new explicit factorization method, Banded Inverse Square Root (BISR), which imposes a banded structure on the inverse correlation matrix. This factorization enables us to derive an explicit and tight characterization of the multi-epoch error. We further prove that BISR achieves asymptotically optimal error by matching the upper and lower bounds. Empirically, BISR performs on par with state-of-the-art factorization methods, while being simpler to implement, computationally efficient, and easier to analyze.