# Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification

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

## Key facts

- Cited by 90 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jul 2020.

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

- [Large Language Models Can Be Strong Differentially Private Learners](https://mlsanity.com/paper/2110.05679/) (2021)
- [Differentially Private Fine-tuning of Language Models](https://mlsanity.com/paper/2110.06500/) (2021)
- [Unlocking High-Accuracy Differentially Private Image Classification through Scale](https://mlsanity.com/paper/2204.13650/) (2022)
- [Trustworthy AI: A Computational Perspective](https://mlsanity.com/paper/2107.06641/) (2021)
- [Large Scale Private Learning via Low-rank Reparametrization](https://mlsanity.com/paper/2106.09352/) (2021)
- [Do Not Let Privacy Overbill Utility: Gradient Embedding Perturbation for Private Learning](https://mlsanity.com/paper/2102.12677/) (2021)
- [Mixed Differential Privacy in Computer Vision](https://mlsanity.com/paper/2203.11481/) (2022)
- [Exploring the Limits of Differentially Private Deep Learning with Group-wise Clipping](https://mlsanity.com/paper/2212.01539/) (2022)
- [Public Data-Assisted Mirror Descent for Private Model Training](https://mlsanity.com/paper/2112.00193/) (2021)
- [Private Adaptive Gradient Methods for Convex Optimization](https://mlsanity.com/paper/2106.13756/) (2021)
- [High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2107.11136/) (2021)
- [Private Adaptive Optimization with Side Information](https://mlsanity.com/paper/2202.05963/) (2022)
- [Why Is Public Pretraining Necessary for Private Model Training?](https://mlsanity.com/paper/2302.09483/) (2023)
- [Does SGD really happen in tiny subspaces?](https://mlsanity.com/paper/2405.16002/) (2024)
- [Federated Learning with Sparsified Model Perturbation: Improving Accuracy under Client-Level Differential Privacy](https://mlsanity.com/paper/2202.07178/) (2022)
- [Just Fine-tune Twice: Selective Differential Privacy for Large Language Models](https://mlsanity.com/paper/2204.07667/) (2022)
- [Private Estimation with Public Data](https://mlsanity.com/paper/2208.07984/) (2022)
- [Fast and Memory Efficient Differentially Private-SGD via JL Projections](https://mlsanity.com/paper/2102.03013/) (2021)
- [PrE-Text: Training Language Models on Private Federated Data in the Age of LLMs](https://mlsanity.com/paper/2406.02958/) (2024)
- [DPZero: Private Fine-Tuning of Language Models without Backpropagation](https://mlsanity.com/paper/2310.09639/) (2023)
- [Selective Pre-training for Private Fine-tuning](https://mlsanity.com/paper/2305.13865/) (2023)
- [DPNAS: Neural Architecture Search for Deep Learning with Differential Privacy](https://mlsanity.com/paper/2110.08557/) (2021)
- [Differentially Private Adaptive Optimization with Delayed Preconditioners](https://mlsanity.com/paper/2212.00309/) (2022)
- [Wide Network Learning with Differential Privacy](https://mlsanity.com/paper/2103.01294/) (2021)
- [Subspace based Federated Unlearning](https://mlsanity.com/paper/2302.12448/) (2023)
- [Privately Learning Subspaces](https://mlsanity.com/paper/2106.00001/) (2021)
- [Choosing Public Datasets for Private Machine Learning via Gradient Subspace Distance](https://mlsanity.com/paper/2303.01256/) (2023)
- [Private Distribution Learning with Public Data: The View from Sample Compression](https://mlsanity.com/paper/2308.06239/) (2023)
- [Efficient and Private Federated Learning with Partially Trainable Networks](https://mlsanity.com/paper/2110.03450/) (2021)
- [DPMLBench: Holistic Evaluation of Differentially Private Machine Learning](https://mlsanity.com/paper/2305.05900/) (2023)

## Abstract (arXiv)

Differentially private SGD (DP-SGD) is one of the most popular methods for solving differentially private empirical risk minimization (ERM). Due to its noisy perturbation on each gradient update, the error rate of DP-SGD scales with the ambient dimension p, the number of parameters in the model. Such dependence can be problematic for over-parameterized models where p gg n, the number of training samples. Existing lower bounds on private ERM show that such dependence on p is inevitable in the worst case. In this paper, we circumvent the dependence on the ambient dimension by leveraging a low-dimensional structure of gradient space in deep networks -- that is, the stochastic gradients for deep nets usually stay in a low dimensional subspace in the training process. We propose Projected DP-SGD that performs noise reduction by projecting the noisy gradients to a low-dimensional subspace, which is given by the top gradient eigenspace on a small public dataset. We provide a general sample complexity analysis on the public dataset for the gradient subspace identification problem and demonstrate that under certain low-dimensional assumptions the public sample complexity only grows logarithmically in p. Finally, we provide a theoretical analysis and empirical evaluations to show that our method can substantially improve the accuracy of DP-SGD in the high privacy regime (corresponding to low privacy loss ε).