# Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams

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

## Key facts

- Cited by 59 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 81 references that are in the map.
- First posted on arXiv 16 Feb 2022.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [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)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Federated Learning for Mobile Keyboard Prediction](https://mlsanity.com/paper/1811.03604/) (2018)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Differentially Private Learning with Adaptive Clipping](https://mlsanity.com/paper/1905.03871/) (2019)
- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [Federated Reconstruction: Partially Local Federated Learning](https://mlsanity.com/paper/2102.03448/) (2021)
- [On Large-Cohort Training for Federated Learning](https://mlsanity.com/paper/2106.07820/) (2021)
- [Training Production Language Models without Memorizing User Data](https://mlsanity.com/paper/2009.10031/) (2020)
- [The Price of Differential Privacy For Online Learning](https://mlsanity.com/paper/1701.07953/) (2017)
- [Tight Differential Privacy for Discrete-Valued Mechanisms and for the Subsampled Gaussian Mechanism Using FFT](https://mlsanity.com/paper/2006.07134/) (2020)
- [The Price of Differential Privacy under Continual Observation](https://mlsanity.com/paper/2112.00828/) (2021)
- [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)
- [That which we call private](https://mlsanity.com/paper/1908.03566/) (2019)
- [Differentially Private Histograms under Continual Observation: Streaming Selection into the Unknown](https://mlsanity.com/paper/2103.16787/) (2021)
- [Answering Range Queries Under Local Differential Privacy](https://mlsanity.com/paper/1812.10942/) (2018)
- [HDMM: Optimizing error of high-dimensional statistical queries under differential privacy](https://mlsanity.com/paper/2106.12118/) (2021)
- [Local Differential Privacy for Evolving Data](https://mlsanity.com/paper/1802.07128/) (2018)

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

- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [(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)
- [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)
- [Towards Federated Foundation Models: Scalable Dataset Pipelines for Group-Structured Learning](https://mlsanity.com/paper/2307.09619/) (2023)
- [Fine-Tuning Large Language Models with User-Level Differential Privacy](https://mlsanity.com/paper/2407.07737/) (2024)
- [Almost Tight Error Bounds on Differentially Private Continual Counting](https://mlsanity.com/paper/2211.05006/) (2022)
- [Constant matters: Fine-grained Complexity of Differentially Private Continual Observation](https://mlsanity.com/paper/2202.11205/) (2022)
- [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)
- [Differentially Private Adaptive Optimization with Delayed Preconditioners](https://mlsanity.com/paper/2212.00309/) (2022)
- [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)
- [DOPPLER: Differentially Private Optimizers with Low-pass Filter for Privacy Noise Reduction](https://mlsanity.com/paper/2408.13460/) (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)
- [PLAN: Variance-Aware Private Mean Estimation](https://mlsanity.com/paper/2306.08745/) (2023)
- [Locally Differentially Private Online Federated Learning With Correlated Noise](https://mlsanity.com/paper/2411.18752/) (2024)
- [On Design Principles for Private Adaptive Optimizers](https://mlsanity.com/paper/2507.01129/) (2025)
- [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)
- [Private Statistical Estimation of Many Quantiles](https://mlsanity.com/paper/2302.06943/) (2023)
- [Momentum Approximation in Asynchronous Private Federated Learning](https://mlsanity.com/paper/2402.09247/) (2024)
- [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)

## Abstract (arXiv)

Motivated by recent applications requiring differential privacy over adaptive streams, we investigate the question of optimal instantiations of the matrix mechanism in this setting. We prove fundamental theoretical results on the applicability of matrix factorizations to adaptive streams, and provide a parameter-free fixed-point algorithm for computing optimal factorizations. We instantiate this framework with respect to concrete matrices which arise naturally in machine learning, and train user-level differentially private models with the resulting optimal mechanisms, yielding significant improvements in a notable problem in federated learning with user-level differential privacy.