# Privately Learning Subspaces

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 49 references that are in the map.
- First posted on arXiv 28 May 2021.

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

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Visualizing the Loss Landscape of Neural Nets](https://mlsanity.com/paper/1712.09913/) (2017)
- [Measuring the Intrinsic Dimension of Objective Landscapes](https://mlsanity.com/paper/1804.08838/) (2018)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Gradient Descent Happens in a Tiny Subspace](https://mlsanity.com/paper/1812.04754/) (2018)
- [Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification](https://mlsanity.com/paper/2007.03813/) (2020)
- [Fingerprinting Codes and the Price of Approximate Differential Privacy](https://mlsanity.com/paper/1311.3158/) (2013)
- [Private Selection from Private Candidates](https://mlsanity.com/paper/1811.07971/) (2018)
- [The Noisy Power Method: A Meta Algorithm with Applications](https://mlsanity.com/paper/1311.2495/) (2013)
- [Between Pure and Approximate Differential Privacy](https://mlsanity.com/paper/1501.06095/) (2015)
- [Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics](https://mlsanity.com/paper/1605.00353/) (2016)
- [Hessian based analysis of SGD for Deep Nets: Dynamics and Generalization](https://mlsanity.com/paper/1907.10732/) (2019)
- [Simultaneous Private Learning of Multiple Concepts](https://mlsanity.com/paper/1511.08552/) (2015)
- [Private Query Release Assisted by Public Data](https://mlsanity.com/paper/2004.10941/) (2020)
- [Private Multiplicative Weights Beyond Linear Queries](https://mlsanity.com/paper/1407.1571/) (2014)
- [Towards Instance-Optimal Private Query Release](https://mlsanity.com/paper/1811.03763/) (2018)
- [How neural networks find generalizable solutions: Self-tuned annealing in deep learning](https://mlsanity.com/paper/2001.01678/) (2020)

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

- [Private and polynomial time algorithms for learning Gaussians and beyond](https://mlsanity.com/paper/2111.11320/) (2021)
- [Does SGD really happen in tiny subspaces?](https://mlsanity.com/paper/2405.16002/) (2024)
- [FriendlyCore: Practical Differentially Private Aggregation](https://mlsanity.com/paper/2110.10132/) (2021)
- [A Private and Computationally-Efficient Estimator for Unbounded Gaussians](https://mlsanity.com/paper/2111.04609/) (2021)
- [Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions](https://mlsanity.com/paper/2301.12250/) (2023)
- [Differentially Private Covariance Revisited](https://mlsanity.com/paper/2205.14324/) (2022)
- [Efficiently Computing Similarities to Private Datasets](https://mlsanity.com/paper/2403.08917/) (2024)
- [Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codes](https://mlsanity.com/paper/2307.07604/) (2023)
- [PLAN: Variance-Aware Private Mean Estimation](https://mlsanity.com/paper/2306.08745/) (2023)
- [Dimension-free Private Mean Estimation for Anisotropic Distributions](https://mlsanity.com/paper/2411.00775/) (2024)
- [Differentially Private Low-dimensional Synthetic Data from High-dimensional Datasets](https://mlsanity.com/paper/2305.17148/) (2023)
- [An Iterative Algorithm for Differentially Private k-PCA with Adaptive Noise](https://mlsanity.com/paper/2508.10879/) (2025)
- [On Differentially Private Subspace Estimation in a Distribution-Free Setting](https://mlsanity.com/paper/2402.06465/) (2024)
- [Privately Estimating a Gaussian: Efficient, Robust and Optimal](https://mlsanity.com/paper/2212.08018/) (2022)
- [Towards Reliable and Generalizable Differentially Private Machine Learning (Extended Version)](https://mlsanity.com/paper/2508.15141/) (2025)
- [Privacy-preserving federated tensor decomposition of single-cell immune data: recovering multicellular programs across institutions](https://mlsanity.com/paper/2606.24938/) (2026)

## Abstract (arXiv)

Private data analysis suffers a costly curse of dimensionality. However, the data often has an underlying low-dimensional structure. For example, when optimizing via gradient descent, the gradients often lie in or near a low-dimensional subspace. If that low-dimensional structure can be identified, then we can avoid paying (in terms of privacy or accuracy) for the high ambient dimension. We present differentially private algorithms that take input data sampled from a low-dimensional linear subspace (possibly with a small amount of error) and output that subspace (or an approximation to it). These algorithms can serve as a pre-processing step for other procedures.