# On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 56 references that are in the map.
- First posted on arXiv 20 Jun 2026.

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

- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [Fingerprinting Codes and the Price of Approximate Differential Privacy](https://mlsanity.com/paper/1311.3158/) (2013)
- [Private Mean Estimation of Heavy-Tailed Distributions](https://mlsanity.com/paper/2002.09464/) (2020)
- [The Noisy Power Method: A Meta Algorithm with Applications](https://mlsanity.com/paper/1311.2495/) (2013)
- [Differentially Private Assouad, Fano, and Le Cam](https://mlsanity.com/paper/2004.06830/) (2020)
- [Practical Differentially Private Top-k Selection with Pay-what-you-get Composition](https://mlsanity.com/paper/1905.04273/) (2019)
- [Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery](https://mlsanity.com/paper/1410.1228/) (2014)
- [Tight Lower Bounds for Differentially Private Selection](https://mlsanity.com/paper/1704.03024/) (2017)
- [FriendlyCore: Practical Differentially Private Aggregation](https://mlsanity.com/paper/2110.10132/) (2021)
- [Statistical and computational trade-offs in estimation of sparse principal components](https://mlsanity.com/paper/1408.5369/) (2014)
- [DP-PCA: Statistically Optimal and Differentially Private PCA](https://mlsanity.com/paper/2205.13709/) (2022)
- [Sparse PCA via Covariance Thresholding](https://mlsanity.com/paper/1311.5179/) (2013)
- [Better and Simpler Lower Bounds for Differentially Private Statistical Estimation](https://mlsanity.com/paper/2310.06289/) (2023)
- [Oneshot Differentially Private Top-k Selection](https://mlsanity.com/paper/2105.08233/) (2021)
- [Optimal Differentially Private PCA and Estimation for Spiked Covariance Matrices](https://mlsanity.com/paper/2401.03820/) (2024)
- [Oja's Algorithm for Streaming Sparse PCA](https://mlsanity.com/paper/2402.07240/) (2024)
- [Differentially Private High Dimensional Sparse Covariance Matrix Estimation](https://mlsanity.com/paper/1901.06413/) (2019)
- [The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimation](https://mlsanity.com/paper/2009.08000/) (2020)
- [Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions](https://mlsanity.com/paper/2406.02789/) (2024)
- [Gradient-based Sparse Principal Component Analysis with Extensions to Online Learning](https://mlsanity.com/paper/1911.08048/) (2019)
- [Faster Algorithms for User-Level Private Stochastic Convex Optimization](https://mlsanity.com/paper/2410.18391/) (2024)
- [An Iterative Algorithm for Differentially Private k-PCA with Adaptive Noise](https://mlsanity.com/paper/2508.10879/) (2025)
- [The Sample Complexity of Distribution-Free Parity Learning in the Robust Shuffle Model](https://mlsanity.com/paper/2103.15690/) (2021)
- [Existence and polynomial time construction of biregular, bipartite Ramanujan graphs of all degrees](https://mlsanity.com/paper/2108.02534/) (2021)
- [Private Geometric Median in Nearly-Linear Time](https://mlsanity.com/paper/2505.20189/) (2025)

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

- [Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests](https://mlsanity.com/paper/2609.22783/) (2026)

## Abstract (arXiv)

We study high-dimensional differentially private (DP) covariance estimation in the operator norm, and principal component analysis (PCA), under k-row-column sparsity (k-RCS) of the covariance matrix. In the non-private setting, it is known that mathsfpoly(k, log d) samples suffice to solve both of these problems. However, the only comparable result known under DP (Wang et al. 2021) requires Omega(d) samples under standard parameterizations of the problem. We investigate when this curse of dimensionality is inherent for sparse covariance estimation tasks under DP. On the upper bound front, we show that a mathsfpoly(k, log d) sample complexity for PCA is possible under DP, if we also posit sparsity of the leading eigenvector. We complement this result with mathsfpoly(d) lower bounds under DP for both sparse covariance estimation and PCA, establishing an exponential gap between the private and non-private variants of these problems when k = mathsfpolylog(d). To our knowledge, no such separation has previously been demonstrated for any sparse estimation problems in private high-dimensional statistics. Our techniques are flexible enough that they imply stronger lower bounds even for the well-studied problem of standard DP PCA, without sparsity assumptions.