# Fast and Memory Efficient Differentially Private-SGD via JL Projections

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 39 references that are in the map.
- First posted on arXiv 5 Feb 2021.

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

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks](https://mlsanity.com/paper/1802.08232/) (2018)
- [Automatic differentiation in machine learning: a survey](https://mlsanity.com/paper/1502.05767/) (2015)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Does Learning Require Memorization? A Short Tale about a Long Tail](https://mlsanity.com/paper/1906.05271/) (2019)
- [Differentially Private Learning with Adaptive Clipping](https://mlsanity.com/paper/1905.03871/) (2019)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [Understanding Gradient Clipping in Private SGD: A Geometric Perspective](https://mlsanity.com/paper/2006.15429/) (2020)
- [Deep Learning with Gaussian Differential Privacy](https://mlsanity.com/paper/1911.11607/) (2019)
- [Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds](https://mlsanity.com/paper/1405.7085/) (2014)
- [Gmail Smart Compose: Real-Time Assisted Writing](https://mlsanity.com/paper/1906.00080/) (2019)
- [Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification](https://mlsanity.com/paper/2007.03813/) (2020)
- [Generative Models for Effective ML on Private, Decentralized Datasets](https://mlsanity.com/paper/1911.06679/) (2019)
- [Enabling Fast Differentially Private SGD via Just-in-Time Compilation and Vectorization](https://mlsanity.com/paper/2010.09063/) (2020)
- [Scaling up Differentially Private Deep Learning with Fast Per-Example Gradient Clipping](https://mlsanity.com/paper/2009.03106/) (2020)
- [Tight Differential Privacy for Discrete-Valued Mechanisms and for the Subsampled Gaussian Mechanism Using FFT](https://mlsanity.com/paper/2006.07134/) (2020)
- [Efficient Per-Example Gradient Computations](https://mlsanity.com/paper/1510.01799/) (2015)
- [Privacy Amplification via Random Check-Ins](https://mlsanity.com/paper/2007.06605/) (2020)
- [Efficient Per-Example Gradient Computations in Convolutional Neural Networks](https://mlsanity.com/paper/1912.06015/) (2019)
- [Diversifying Reply Suggestions using a Matching-Conditional Variational Autoencoder](https://mlsanity.com/paper/1903.10630/) (2019)

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

- [Large Language Models Can Be Strong Differentially Private Learners](https://mlsanity.com/paper/2110.05679/) (2021)
- [Opacus: User-Friendly Differential Privacy Library in PyTorch](https://mlsanity.com/paper/2109.12298/) (2021)
- [Numerical Composition of Differential Privacy](https://mlsanity.com/paper/2106.02848/) (2021)
- [Automatic Clipping: Differentially Private Deep Learning Made Easier and Stronger](https://mlsanity.com/paper/2206.07136/) (2022)
- [Differentially Private Optimization on Large Model at Small Cost](https://mlsanity.com/paper/2210.00038/) (2022)
- [Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions](https://mlsanity.com/paper/2207.04380/) (2022)
- [Exploring the Limits of Differentially Private Deep Learning with Group-wise Clipping](https://mlsanity.com/paper/2212.01539/) (2022)
- [Scalable and Efficient Training of Large Convolutional Neural Networks with Differential Privacy](https://mlsanity.com/paper/2205.10683/) (2022)
- [On the Convergence and Calibration of Deep Learning with Differential Privacy](https://mlsanity.com/paper/2106.07830/) (2021)
- [Selective Pre-training for Private Fine-tuning](https://mlsanity.com/paper/2305.13865/) (2023)
- [Faster Privacy Accounting via Evolving Discretization](https://mlsanity.com/paper/2207.04381/) (2022)
- [Differentially Private SGD Without Clipping Bias: An Error-Feedback Approach](https://mlsanity.com/paper/2311.14632/) (2023)
- [On Differential Privacy and Adaptive Data Analysis with Bounded Space](https://mlsanity.com/paper/2302.05707/) (2023)
- [Zero redundancy distributed learning with differential privacy](https://mlsanity.com/paper/2311.11822/) (2023)
- [Differentially Private Bayesian Neural Networks on Accuracy, Privacy and Reliability](https://mlsanity.com/paper/2107.08461/) (2021)
- [Private Ad Modeling with DP-SGD](https://mlsanity.com/paper/2211.11896/) (2022)
- [Private Federated Learning with Autotuned Compression](https://mlsanity.com/paper/2307.10999/) (2023)
- [Generative Model-Based Attack on Learnable Image Encryption for Privacy-Preserving Deep Learning](https://mlsanity.com/paper/2303.05036/) (2023)
- [Efficiently Train ASR Models that Memorize Less and Perform Better with Per-core Clipping](https://mlsanity.com/paper/2406.02004/) (2024)
- [Differentially Private Prototypes for Imbalanced Transfer Learning](https://mlsanity.com/paper/2406.08039/) (2024)
- [Memory-Efficient Differentially Private Training with Gradient Random Projection](https://mlsanity.com/paper/2506.15588/) (2025)
- [Rieoptax: Riemannian Optimization in JAX](https://mlsanity.com/paper/2210.04840/) (2022)
- [Noise is All You Need: Private Second-Order Convergence of Noisy SGD](https://mlsanity.com/paper/2410.06878/) (2024)
- [Federated Learning with Differential Privacy: An Utility-Enhanced Approach](https://mlsanity.com/paper/2503.21154/) (2025)
- [PLRV-O: Advancing Differentially Private Deep Learning via Privacy Loss Random Variable Optimization](https://mlsanity.com/paper/2509.06264/) (2025)
- [Efficient DP-SGD for LLMs with Randomized Clipping](https://mlsanity.com/paper/2605.24879/) (2026)
- [Towards Reliable and Generalizable Differentially Private Machine Learning (Extended Version)](https://mlsanity.com/paper/2508.15141/) (2025)
- [Stabilization of Perturbed Loss Function: Differential Privacy without Gradient Noise](https://mlsanity.com/paper/2508.15523/) (2025)
- [Lap2: Revisiting Laplace DP-SGD for High Dimensions via Majorization Theory](https://mlsanity.com/paper/2602.23516/) (2026)

## Abstract (arXiv)

Differentially Private-SGD (DP-SGD) of Abadi et al. (2016) and its variations are the only known algorithms for private training of large scale neural networks. This algorithm requires computation of per-sample gradients norms which is extremely slow and memory intensive in practice. In this paper, we present a new framework to design differentially private optimizers called DP-SGD-JL and DP-Adam-JL. Our approach uses Johnson-Lindenstrauss (JL) projections to quickly approximate the per-sample gradient norms without exactly computing them, thus making the training time and memory requirements of our optimizers closer to that of their non-DP versions. Unlike previous attempts to make DP-SGD faster which work only on a subset of network architectures or use compiler techniques, we propose an algorithmic solution which works for any network in a black-box manner which is the main contribution of this paper. To illustrate this, on IMDb dataset, we train a Recurrent Neural Network (RNN) to achieve good privacy-vs-accuracy tradeoff, while being significantly faster than DP-SGD and with a similar memory footprint as non-private SGD. The privacy analysis of our algorithms is more involved than DP-SGD, we use the recently proposed f-DP framework of Dong et al. (2019) to prove privacy.